2017-2018-1 學習總結目錄： 1 2 3 5 6 7 9 10 11 12
目錄
0. 教材學習内容總結
* 0.1 集合的介紹
* 0.2 棧集合
* 0.3 繼承、多态和泛型
* 0.4 棧的ADT
* 0.5 使用棧：計算字尾表達式
* 0.6 異常
* 0.7 使用數組實作棧
* 0.8 ArrayStack類
* 0.9 将引用作為鍊
* 0.10 管理連結清單
* 0.11 沒有鍊的元素
* 0.12 使用鍊實作棧
* 0.13 使用
java.util.Stack
類實作棧
* 0.14 包
* 分析Java Collections API中的Stack類
1. 教材學習中的問題和解決過程
* 1.1 ArrayStack類的expandCapacity方法
2. 代碼調試中的問題和解決過程
* 2.1 LinkedStack類中的push方法
- 3. 代碼托管
- 4. 上周考試錯題總結
- 5. 結對及互評
- 6. 其他（感悟、思考等，可選）
- 7. 學習進度條
- 8. 參考資料
教材學習内容總結
第14章 棧
集合的介紹
- 集合是 收集 并 組織 其他對象的對象。
-
分類：線性集合（排成一行）、非線性集合（層次、網絡等方式組織）。
【推論】棧集合中元素的添加及删除都在一端進行，是以 棧集合屬于線性集合。
-
集合中元素之間的組織方式取決于：
① 元素加入集合的次序；
② 元素之間的某些固有關系。
- 抽象資料類型：（abstract data type）簡稱ADT，其值和操作都沒有被定義。（隐藏細節：集合）
- 資料結構：用來實作集合的基本程式結構集合。
- Java Collections API：（application programming interface）使用不同方式實作的幾類集合的一組類。（包含API）
棧集合
- 處理元素方式：LIFO（後進先出）
- 棧頂：元素入棧或出棧的一端。
在解決問題時，如果要通路非頂端元素，則不适合使用棧。
- 注意pop和peek操作的差別：pop為 删除 棧頂元素，peek為 檢視 棧頂元素。
從單詞上了解，pop有蹦出、離開之意，就相當于彈出了棧中元素；而peek有偷看之意，就相當于檢視棧中元素。
繼承、多态和泛型
- 類型相容（多态）、類型檢查（編譯）。
- 泛型：（儲存、操作、管理）直到執行個體化時才确定類型的對象。
棧的ADT
- 從僞代碼中就能清楚地了解棧接口中的各個抽象方法：
public interface Stack<T>
{
// Adds the specified element to the top of the stack.
public void push (T element);
// Removes and returns the top element from the stack.
public T pop();
// Returns a reference to the top element of this stack without removing it.
public T peek();
// Returns true if this stack contains no elements and false otherwise.
public boolean isEmpty();
// Returns the number of elements in the stack.
public int size();
// Returns a string representation of the stack.
public String toString();
}
【注意】棧接口是用泛型 T 定義的，實作這個接口時，要用一個具體類型取代 T。
使用棧：計算字尾表達式
- 字尾表達式：<操作數> <操作數> <運算符>
字尾表達式不用考慮優先級和括号，比中綴表達式更易于計算。
- 棧是計算字尾表達式時使用的理想資料結構。
異常
-
潛在異常：
① 入棧時棧滿；（資料結構）
② 出棧時棧空；（字尾表達式不正确）
③ 掃描完表達式完成計算時棧中的值多于1個。（字尾表達式不正确）
-
處理異常的方式：
① 可以通過預先檢查棧空以避免異常：
if (!theStack.isEmpty())
element = theStack.pop();
② 當異常發生時，使用 try-catch 語句處理：
try {
element = theStack.pop();
} catch (EmptyStackException exception) {
System.out.println("No elements available");
}
③ 先設定抛出異常，再自定義一個異常類：
public class EmptyCollectionException extends RuntimeException
{
/**
* Sets up this exception with an appropriate message.
* @param collection String representing the name of the collection
*/
public EmptyCollectionException (String collection)
{
super ("The " + collection + " is empty.");
}
}
使用數組實作棧
- 管理容量：需要時自動擴充。
ArrayStack類
- 數組實作的棧将棧底放在下标為 0 的位置。（順序、連續）
-
關鍵代碼：
不能執行個體化泛型數組，但是可以強制轉換：
stack = (T[]) (new Object[DEFAULT_CAPACITY]);
/**
* Creates a new array to store the contents of this stack with twice the capacity of the old one.
*/
private void expandCapacity() {
T[] larger = (T[]) (new Object[stack.length * 2]);
for (int index = 0; index < stack.length; index++)
larger[index] = stack[index];
stack = larger;
}
- 需要實作的方法：
//删除并傳回棧頂元素
public T pop() {
T result = null; //置空臨時變量的引用
if (!isEmpty()) { //確定棧不空
count--;
result = stack[count];
stack[count] = null;
} else
try {
isEmpty();
} catch (EmptyStackException exception) {
System.out.println("No elements available");
}
return result;
}
//傳回棧頂元素的引用
public T peek() {
if (isEmpty()) {
try {
isEmpty();
} catch (EmptyStackException exception) {
System.out.println("No elements available");
}
}
return stack[count - 1];
}
public boolean isEmpty() {
return (count == 0);
}
public int size() {
return count;
}
- 注意 push 和 pop 操作的初始條件，push一個元素的前提是 棧不滿，pop一個元素的前提是 棧不空。
将引用作為鍊
- 鍊式結構：使用對象引用變量建立聯系。（自訓示）
-
連結清單（對象之間指向關系）
結點（存儲對象）
- 注意：必須使用一個 單獨的 引用變量指向表中第一個結點。結點的 next 引用為 null 時表示結束。
- 數組有固定大小，連結清單沒有容量限制。
管理連結清單
- 通路元素：必須通路第一個元素。
- 插入結點：首先，新節點的 next 指向 current 指向的下一個結點，然後結束目前結點的 next 引用重置指向新節點。（頭插法、尾插法、表中插入）
20162330 2017-2018-1《程式設計與資料結構》第五周學習總結 - 删除結點：第1個結點（将表頭引用指向目前第2個結點）、中間節點（前一個的 next 指向目前結點的 next 引用所指向的結點）。
20162330 2017-2018-1《程式設計與資料結構》第五周學習總結 - 哨兵結點：不用考慮如何處理第1個結點。
沒有鍊的元素
- 雙向連結清單：維護第1個結點和最後一個結點。
使用鍊實作棧
- 注意初始時構造方法中将表頭變量設定為 null，元素個數設定為 0。
//--------------------------------------------------------------------
// Creates an empty stack using the default capacity.
//--------------------------------------------------------------------
public LinkedStack() {
count = 0;
top = null;
}
//删除并傳回棧頂元素
public void push(T element) {
LinearNode<T> eNode = new LinearNode<>(element); //新元素入棧對應新的對象
eNode.setNext(top); //新結點next引用指向棧頂
top = eNode;
count++;
}
//傳回目前棧頂所儲存元素的引用
public T peek() throws EmptyStackException {
return top.getElement();
}
public boolean isEmpty() {
return count == 0;
}
public int size() {
return count;
}
- push、pop等操作的每個步驟都含有一次比較或者指派，是以其複雜度都是O（1）。
使用 java.util.Stack 類實作棧
-
java.util.Stack
包
- 包的組織：一般按代碼功能組織為包（集合，異常）。
- 使用
package XXX
分析Java Collections API中的Stack類
- 首先在API中Stack類的類聲明語句
public class Stack<E> extends Vector<E>
public class Vector<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
而該類又繼承了其他方法，進而使得Stack類實作了List、Collection等接口：
中文版API介紹Stack類說：
它通過五個操作對類 Vector 進行了擴充 ，允許将向量視為堆棧。它提供了通常的 push 和 pop 操作，以及取堆棧頂點的 peek 方法、測試堆棧是否為空的 empty 方法、在堆棧中查找項并确定到堆棧頂距離的 search 方法。
-
由于這個類依賴于vector（向量），是以它既展示出 vector 的特性也展示出棧的特性。
相比起書中實作的棧，在Stack類中加入了一種特殊方法：search（傳回對象在棧中的位置，即第一次出現時與棧頂之間的距離）
public synchronized int search(Object o) {
int i = lastIndexOf(o);
if (i >= 0) {
return size() - i;
}
return -1;
}
這個方法将對象o作為一個棧中的元素，先擷取其位置，即最後一次出現（離棧頂最近）時的索引值，最小值為 1，如果此對象不存在或者檢測對象為空值，則會傳回 -1，舉個例子：
結果展現得很明顯了。
- 相比起書中實作的棧，除了額外提供了search方法之外，我還發現search、peek 和 pop 方法在聲明時，public後出現了新的關鍵字
synchronized
synchronized 方法控制對類成員變量的通路，每個類執行個體都對應一把鎖，每個 synchronized 方法都必須獲得調用該方法的類執行個體的鎖方能執行，否則所屬線程阻塞，方法一旦執行，就獨占該鎖，直到從該方法傳回時才将鎖釋放，此後被阻塞的線程方能獲得該鎖，重新進入可執行狀态。這種機制確定了同一時刻對于每一個類執行個體，其所有聲明為 synchronized 的成員函數中至多隻有一個處于可執行狀态。（因為至多隻有一個能夠獲得該類執行個體對應的鎖）
這樣一來就可以避免類成員變量通路沖突，但如果為一些時間複雜度高的方法增加對象鎖，就會明顯降低其效率。
- 除此之外，由于Stack類是繼承類，是以一些方法中的屬性是從Vector類繼承而來，比如說：pop方法
public synchronized E pop() {
E obj;
int len = size();
obj = peek();
removeElementAt(len - 1);
return obj;
}
其中的`removeElementAt(int index)`方法就是繼承而來：
```
public synchronized void removeElementAt(int index) {
modCount++;
if (index >= elementCount) { //索引參數越界
throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount);
}
else if (index < 0) { //索引參數越界
throw new ArrayIndexOutOfBoundsException(index);
}
int j = elementCount - index - 1;
if (j > 0) {
System.arraycopy(elementData, index + 1, elementData, index, j); //元素後移
}
elementCount--; //元素個數減1
elementData[elementCount] = null; //置空
}
- 再看看peek方法：
public synchronized E peek() {
int i = size();
if (i == 0)
throw new EmptyStackException();
return elementAt(i - 1);
}
這裡又調用了Vector中的`elementAt(int index)`方法：
```
public synchronized E elementAt(int index) {
if (index >= elementCount) {
throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount);
}
return elementData(index);
}
和
removeElementAt(int index)
方法一樣，
elementAt(int index)
方法也首先判斷參數是否合法，之後就直接調用
elementData(int index)
傳回具體的對象值：
E elementData(int index) {
return (E) elementData[index]; //儲存Stack中的每個元素
}
- 總的來說，Stack源碼是通過數組實作的，再加上Vector中的擴容和其他方法屬性，除此之外還使用了關鍵字
synchronized
【傳回目錄】
教材學習中的問題和解決過程
- 【問題】：ArrayStack類的expandCapacity方法中的
stack = larger
-
解決方案 ：（詢問後總結）
完整擴容方法如下：
private void expandCapacity() {
T[] larger = (T[]) (new Object[stack.length * 2]);
for (int index = 0; index < stack.length; index++)
larger[index] = stack[index];
stack = larger;
}
在建立新大小的泛型數組larger後，再将stack中的元素周遊進去，但是最後又要将larger賦給容量更小的stack。原來我以為stack是原來的引用，是以将larger數組賦給stack時就認為是将容量大數組的指派給了一個容量小的數組，不能夠實作。詢問了張旭升之後，發現我對原stack引用了解有誤，在給stack數組賦larger數組的時候，相當于更新了原數組，stack數組在被更新時就已經改變了預設的容量，進而實作擴容效果。
代碼調試中的問題和解決過程
- 【問題】：在設計LinkedStack類中的push方法時，Junit測試出現紅條，添加的元素并沒有在删除時顯示。
20162330 2017-2018-1《程式設計與資料結構》第五周學習總結 -
解決方案 ：（嘗試）
我最初設計方法時，仔細看了書中的文字步驟：
其中前兩步比較重要：第一步是建立一個新結點，其中包含一個指向要放置到棧中對象的引用。接着設定新結點的 next 引用指向目前棧頂（如果棧為空，則它為null）
看完這兩段話，原來我想要使用條件語句判斷棧頂元素，但是仔細一想，如果棧頂元素為空，在給新結點指派或者被新結點的引用指向時并不會因非空指派語句造成影響，于是我的代碼如下：
public void push(T element) {
LinearNode<T> eNode = new LinearNode<>();
eNode.setNext(top); //新結點指向棧頂
top = eNode;
count++;
}
但是在進行Junit測試時并沒有成功，pop或者peek方法傳回的值一直為空，在仔細看了第一條指派語句後，發現我定義的結點中并沒有傳入push元素，是以就一直保持了棧預設為空的狀态，是以隻需要将傳入的element加入即可：
LinearNode<T> eNode = new LinearNode<>(element);
最初出現這個錯誤是因為忽略了泛型結點預設的初始值。
代碼托管
-
統計的代碼包含了第四周的實驗一，是以是第四周和第五周一共的代碼量：
（statistics.sh腳本的運作結果截圖）
20162330 2017-2018-1《程式設計與資料結構》第五周學習總結
上周考試錯題總結
- 上周國慶放假無考試，是以總結第三周的錯題：
-
【錯題1】A __________________ search looks through the search pool one element at a time.
A .binary
B .clever
C .insertion
D .selection
E .linear
-
錯誤原因：我覺得二分查找每次也是搜尋比較一個中間元素，錯選A。
加深了解：線性查找會逐一在查找池中查找（疊代）一個元素；二分查找每次也在查找池中查找一個元素，但是并不是逐一，每次會篩選掉一半。
【注意】look through 在這裡并不是浏覽之意，而是 “逐一檢查” 的意思。
-
【錯題2】A linear search always requires more comparisons than a binary search.
A .true
B .false
-
錯誤原因：考慮情況不全面，錯選A。
加深了解：如果正在搜尋的元素是清單中的第一個元素，那麼線性查找比二分查找需要的比較次數更少。
結對及互評
本周結對學習情況
- 莫禮鐘本周比第三周的狀态好一點，雖然實驗隻完成了第一個和第五個，設計的方法比較簡單，但是都是自己做的。在學習十四章的過程中，他已經基本掌握了如何使用數組實作棧，其中一些比較重要的方法（push、pop）我已經看着他寫了一遍，希望多熟練已掌握的内容，并且再恢複一些學習狀态。
- 20162319
- 結對學習内容
- 線性表
- 用數組實作棧（push、pop方法的實作）
- 結對學習内容
其他（感悟、思考等，可選）
本周算是比較忙的一周了，國慶之後的第一周并不輕松，除了運動會的一些雜事之外，本周的學習任務真心有點多。本周在課堂上我們又複習了查找與排序的内容，我的掌握情況還算過關，對于棧、隊列這部分内容我選擇了“先聽課再看書”的方式。到現在為止，棧的基本内容掌握了，隊列的掌握情況還差很多，雲班課的測試成績也不算高。本周我的狀态有些下降，主要因為睡眠時間不足導緻，下周我會将精力集中回來，并且平衡好完成團隊任務和個人任務的時間。
-
【附1】教材及考試題中涉及到的英語：
Chinese | English | Chinese | English
:---😐:---😐:---😐:---:
線性集合 | linear collection | 預設值 | default
非線性集合 | nonlinear collection | 自訓示 | self-referential
封裝 | encapsulate | 動态 | dynamic
類型相容 | type compatibility | 堆 | heap
中綴 | infix | 哨兵結點 | sentinel node
字首 | prefix | 虛位結點 | dummy node
矢量 | vector | 常量 | constant(s)
操作數 | operand(s) | 指定的 | designated
優化 | optimize | 空閑存儲區 | free store
- 【附2】本周小組部落格
學習進度條
-
| | 代碼行數（新增/累積）| 部落格量（新增/累積）|學習時間（新增/累積）|重要成長|
|:--------😐 :----------------😐:----------------😐:---------------: |:-----😐
| 目标 | 5000行 | 30篇 | 400小時 | |
| 第一周 | 234/234 | 1/28 | 14/14 | 了解算法效率、大O符号等理論内容 |
| 第二周 | 255/489 | 1/29 | 12/26 | 了解靈活的團隊、泛型的使用 |
| 第三周 | 436/925 | 2/31 | 10/36 | 了解一些查找和排序的算法 |
| 第四周 | 977/1902 | 3/34 | 10/46 | 掌握實作線性結構 |
| 第五周 | 800/2702 | 2/36 | 12/58 | 掌握實作棧集合 |
- 計劃學習時間：14小時
- 實際學習時間：12小時
- 有效學習時間：5小時
- 改進情況：學習内容有所增加，本周我的效率極低，下周必須恢複到之前的狀态，學習時務必心無旁骛。
參考資料
- 《Java程式設計與資料結構教程（第二版）》
- 《Java程式設計與資料結構教程（第二版）》學習指導
- java synchronized詳解
- 藍墨雲班課 棧 ppt