3.6 堆疊 ADT
堆疊是限制插入和洗掉只能在一個位置上進行的表，叫做堆疊的頂部，對堆疊的基本操作有進堆疊和出堆疊，進堆疊在頂部插入元素，出堆疊洗掉最后插入的元素，
堆疊是一個表，因此任何實作表的方法都能實作堆疊，顯然 ArrayList 和 LinkedList 都支持堆疊操作；因為堆疊操作是常數時間操作，除非在非常特殊的情形下，不能產生明顯改進，
堆疊的鏈表實作
在表的頂端或末端插入來實作進堆疊，洗掉頂端或末端實作出堆疊，
堆疊的陣列實作
在表的末端插入實作進堆疊，洗掉末端實作出堆疊，
堆疊的應用
平衡符號
編譯器檢查程式語法錯誤時，經常由于符號錯誤導致，大量診斷報錯，因為每個右括號必然對應其相應的左括號如{([])}是合法的，[({)]}是不合法的，通過堆疊可以方便的檢查符號：
一個空堆疊，從檔案頭部讀入字符到檔案尾，如果字符是左半部分則進堆疊，如果字符是右半部分，當堆疊空時報錯，否則將左半部分出堆疊，如果出堆疊的符號不是對應的左半部分則報錯，檔案讀完，堆疊非空則報錯，
后綴運算式
使用科學計算器計算時對于乘除法優先于加減法的記法，例如：
3 × 5 + 4 + 9 ÷ 3 = 22 將被記錄為 3 5 × 4 + 9 3 ÷ +
當見到一個數時，將其進堆疊，遇到一個運算子該運算子作用于出堆疊的兩個數上，再講所得結果進堆疊，就可以不必知道優先規則而直接計算，
中綴到后綴的轉換
除了用了計算后綴運算式，堆疊同樣可以將標準形式運算式(中綴運算式)轉換為后綴式，
讀到運算元時立即將其放到后綴式中，運算子則進入堆疊中(包括括號)，當堆疊中存在高優先級運算子，且下個運算子是低優先級時，將高優先級運算子出堆疊到后綴式，低優先級運算子進堆疊，左括號進堆疊后在遇到右括號前不出堆疊，讀到有括號時則一直出堆疊直到左括號出堆疊，括號出堆疊時不添加到后綴式中，
3.7 佇列 ADT
佇列也是表，基本操作是入隊，在隊尾插入一個元素；出隊，在隊頭洗掉一個元素，
佇列的陣列實作
佇列的鏈表實作很簡單，
下面是使用陣列實作的佇列，用到了回圈陣列，否則陣列的空間將被很快耗盡，
public class MyArrayQueue<E> {
private int front;
private int back;
private E[] queue;
private int theSize;
public static final int DEFAULT_CAPACITY = 10;
public MyArrayQueue() {
theSize = 0;
ensureCapacity(DEFAULT_CAPACITY);
front = queue.length / 2;
back = front;
}
/**
* 擴容陣列的同時需要對佇列進行拼接
*
* @param newCapacity 新陣列長度2倍
*/
public void ensureCapacity(int newCapacity) {
if (newCapacity < theSize) {
return;
}
E[] old = queue;
queue = (E[]) new Object[newCapacity];
if (back < front) {
for (int i = front; i < theSize; i++) {
queue[i] = old[i];
}
for (int i = 0; i < back + 1; i++) {
queue[theSize + i] = old[i];
}
back = front + theSize - 1;
} else {
for (int i = 0; i < theSize; i++) {
queue[i] = old[i];
}
}
}
public void enqueue(E e) {
if (queue.length == theSize) {
ensureCapacity(theSize * 2);
}
if (theSize != 0) {
if (back == queue.length - 1) {
back = 0;
} else {
back++;
}
}
queue[back] = e;
theSize++;
}
public E dequeue() {
if (theSize == 0) {
return null;
}
E returnVal = queue[front];
if (front == queue.length - 1) {
front = 0;
} else {
front++;
}
theSize--;
return returnVal;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/5283.html
標籤：其他