Java開篇八：Stack and Queue
感恩節(jié)是美國人民獨創(chuàng)的一個古老節(jié)日，也是美國人合家歡聚的節(jié)日。1941年，美國國會正式將每年11月第四個星期四定位“感恩節(jié)”。
今天是小雪，也注意大家多穿點衣服，注意保暖，別凍著了。
定義
棧：后進先出（LIFO-last in first out）:最后插入的元素最先出來。
隊列：先進先出（FIFO-first in first out）:最先插入的元素最先出來。
棧(Stack)
棧(stack)，也可以叫做堆棧，是一種容器類型的數(shù)據(jù)結構，可以存入數(shù)據(jù)元素、訪問元素以及刪除元素。
特點：只允許在一端進行操作，采用了后進先出（Last in Fist out）的原理。
下面采用順序表的形式來實現(xiàn)
class Stack(object): ? ?"""棧""" ? ?def __init__(self): ? ? ? ?self.__list = [] ? ?def push(self, item): ? ? ? ?"""添加一個新元素到棧頂，就是將這個item放到append到最后面""" ? ? ? ?self.__list.append(item) ? ?def pop(self): ? ? ? ?"""彈出棧頂?shù)脑?，采用list中的pop方法""" ? ? ? ?return self.__list.pop() ? ?def peek(self): ? ? ? ?"""返回棧頂?shù)脑兀褪菑棾鰜碜詈蟮囊粋€元素""" ? ? ? ?if self.__list: ? ? ? ? ? ?return self.__list[-1] ? ? ? ?else: ? ? ? ? ? ?return None ? ?def is_empty(self): ? ? ? ?"""判斷棧是不是為空的""" ? ? ? ?return self.__list == [] ? ?def size(self): ? ? ? ?"""返回棧的元素個數(shù)"""????????return?len(self.__list)???
if __name__ == '__main__': ? ?s = Stack() ? ?print(s.is_empty()) # True ? ?print(s.size()) ? ? # 0 ? ?s.push(1) ? ?s.push(2) ? ?s.push(3) ? ?print(s.is_empty()) # False ? ?print(s.peek()) ? ? # 3 ? ?print(s.size()) ? ? # 3 ? ?s.pop() ? ?s.pop() ? ?print(s.is_empty()) # False ? ?print(s.size()) ? ? # 1
二、隊列(Queue)
隊列是一種只允許在一端進行插入操作，另外一端進行刪除操作的線性表
特點是：先進先出（First in First out）。舉個例子，就是排隊買票去動物園，先排隊買到票的小伙伴就先進去。其效果如下圖所示：
class Queue(object): ? ?"""隊列""" ? ?def __init__(self): ? ? ? ?self.__list = [] ? ?def enqueue(self, item): ? ? ? ?"""往隊列中添加一個元素""" ? ? ? ?self.__list.append(item) ? ?def dequeue(self): ? ? ? ?"""將隊列頭部的一個元素刪除""" ? ? ? ?self.__list.pop(0) ? ?def is_empty(self): ? ? ? ?"""判斷一個隊列是不是空的""" ? ? ? ?return self.__list==[] ? ?def size(self): ? ? ? ?"""返回隊列的大小""" ? ? ? ?return len(self.__list)
if __name__ == '__main__': ? ?q = Queue() ? ?print(q.is_empty()) ?# True ? ?print(q.size()) ? ? ?# 0 ? ?q.enqueue(1) ? ?q.enqueue(2) ? ?q.enqueue(3) ? ?q.enqueue(4) ? ?print(q.is_empty()) ?# False ? ?print(q.size()) ? ? ?# 4 ? ?q.dequeue() ? ?q.dequeue() ? ?print(q.is_empty()) ?# False ? ?print(q.size()) ? ? ?# 2
Stack? and? ?Queue
Java里有一個叫做Stack的類，卻沒有叫做Queue的類（它是個接口名字）。當需要使用棧時，Java已不推薦使用Stack，而是推薦使用更高效的ArrayDeque；既然Queue只是一個接口，當需要使用隊列時也就首選ArrayDeque了（次選是LinkedList）。
講解：
要講棧和隊列，首先要講Deque接口。Deque的含義是“double ended queue”，即雙端隊列，它既可以當作棧使用，也可以當作隊列使用。下表列出了Deque與Queue相對應的接口：
下表列出了Deque與Stack對應的接口：
上面兩個表共定義了Deque的12個接口。添加，刪除，取值都有兩套接口，它們功能相同，區(qū)別是對失敗情況的處理不同。一套接口遇到失敗就會拋出異常，另一套遇到失敗會返回特殊值（false或null）。除非某種實現(xiàn)對容量有限制，大多數(shù)情況下，添加操作是不會失敗的。雖然Deque的接口有12個之多，但無非就是對容器的兩端進行操作，或添加，或刪除，或查看。明白了這一點講解起來就會非常簡單。
ArrayDeque和LinkedList是Deque的兩個通用實現(xiàn)，由于官方更推薦使用AarryDeque用作棧和隊列，加之上一篇已經(jīng)講解過LinkedList，本文將著重講解ArrayDeque的具體實現(xiàn)。
從名字可以看出ArrayDeque底層通過數(shù)組實現(xiàn)，為了滿足可以同時在數(shù)組兩端插入或刪除元素的需求，該數(shù)組還必須是循環(huán)的，即循環(huán)數(shù)組（circular array），也就是說數(shù)組的任何一點都可能被看作起點或者終點。ArrayDeque是非線程安全的（not thread-safe），當多個線程同時使用的時候，需要程序員手動同步；另外，該容器不允許放入null元素。
上圖中我們看到，head指向首端第一個有效元素，tail指向尾端第一個可以插入元素的空位。因為是循環(huán)數(shù)組，所以head不一定總等于0，tail也不一定總是比head大。
案例：
2.用數(shù)組實現(xiàn)棧和隊列
實現(xiàn)棧：
由于數(shù)組大小未知，如果每次插入元素都擴展一次數(shù)據(jù)（每次擴展都意味著構建一個新數(shù)組，然后把舊數(shù)組復制給新數(shù)組），那么性能消耗相當嚴重。
這里使用貪心算法，數(shù)組每次被填滿后，加入下一個元素時，把數(shù)組拓展成現(xiàn)有數(shù)組的兩倍大小。
每次移除元素時，檢測數(shù)組空余空間有多少。當數(shù)組里的元素個數(shù)只有整個數(shù)組大小的四分之一時，數(shù)組減半。
為什么不是當數(shù)組里的元素個數(shù)只有整個數(shù)組大小的二分之一時，數(shù)組減半？考慮以下情況：數(shù)組有4個元素，數(shù)組大小為4個元素空間。此時，加一個元素，數(shù)組拓展成8個空間；再減一個元素，數(shù)組縮小為4個空間；如此循環(huán)，性能消耗嚴重。
具體代碼（Java）:
public ResizingArrayStackOfStrings(){ ? ?s=new String[1]; ? ?int N = 0;}pubilc void Push(String item){ ? ?//如果下一個加入元素超出數(shù)組容量，拓展數(shù)組 ? ?if(N == s.length) Resize(2 * s.length); ? ?s[N++] = item;}private void Resize(int capacity){ ? String[] copy = new String[capacity]; ? //將舊數(shù)組元素復制給新數(shù)組 ? for(int i=0; i<N; i++) copy[i] = s[i]; ? s = copy;}public String Pop(){ ?String item = s[--N]; ?s[N] = null;//剩余元素只占數(shù)組四分之一空間時，數(shù)組減半 ?if(N>0 && N=s.length/4) Resize(s.length/2); ?return item;}
實現(xiàn)隊列
與棧類似：
? ? ? ?數(shù)組每次被填滿后，加入下一個元素時，把數(shù)組拓展成現(xiàn)有數(shù)組的兩倍大小。
每次移除元素時，檢測數(shù)組空余空間有多少。當數(shù)組里的元素個數(shù)只有整個數(shù)組大小的四分之一時，數(shù)組減半。
不同之處在于：
? ? ? ?由于是先進先出，移除是從隊列的最前端開始的。所以當我們移除數(shù)個數(shù)據(jù)后，隊列數(shù)據(jù)是存儲在數(shù)組的中間部分的。令隊列數(shù)據(jù)的尾端數(shù)據(jù)ID為Num,首端數(shù)據(jù)ID為HeadIndex，則Num - HeadIndex為隊列數(shù)據(jù)元素個數(shù)。
? ? ? ?當隊列數(shù)據(jù)元素個數(shù)為整個數(shù)組空間的四分之一時，數(shù)組減半，且隊列數(shù)據(jù)左移至數(shù)組最左端。即Num-=HeadIndex；HeadIndex=0；
具體代碼：
.h:UCLASS()class ALGORITHM_API AStackAndQueuesExerciseTwo : public AActor{ ? ?GENERATED_BODY() public: ? ? ? ?// Sets default values for this actor's properties ? ?AStackAndQueuesExerciseTwo(); ? ?// Called every frame ? ?virtual void Tick(float DeltaTime) override; ? ?//輸入 ? ?void Enqueue(int Input); ? ?//重構數(shù)組（拓展或縮?。?/code> ? ?void Resize(int Capacity); ? ?//輸出且移除 ? ?int Dequeue(); ? ?//隊列里沒元素了？ ? ?bool IsEmpty();protected: ? ?// Called when the game starts or when spawned ? ?virtual void BeginPlay() override;public: ? ? private: ? ?//記錄數(shù)組中有多少個Int ? ?int Num; ? ?//隊列數(shù)組 ? ?TArray<int> MyIntArray; ? ?//記錄下一個移除的數(shù)據(jù)ID ? ?int HeadIndex;};.cpp:AStackAndQueuesExerciseTwo::AStackAndQueuesExerciseTwo(){ ? ? // Set this actor to call Tick() every frame. ?You can turn this off to improve performance if you don't need it. ? ?PrimaryActorTick.bCanEverTick = true; ? ?//一開始數(shù)組沒成員 ? ?Num = 0; ? ?HeadIndex = 0; ? ?//數(shù)組中有一個假元素 ? ?MyIntArray.Add(0);}// Called when the game starts or when spawnedvoid AStackAndQueuesExerciseTwo::BeginPlay(){ ? ?Super::BeginPlay(); ? ?//測試 ? ?Enqueue(1); ? ?Enqueue(2); ? ?Enqueue(3); ? ?Enqueue(4); ? ?Enqueue(5); ? ?Dequeue(); ? ?Dequeue(); ? ?Dequeue(); ? ?//隊列數(shù)組成員 ? ?for (int i = HeadIndex; i < Num; i++) ? ?{ ? ? ? ?UKismetSystemLibrary::PrintString(this, "i: " + FString::FromInt(i) + " End: " + FString::FromInt(MyIntArray[i])); ? ?} ? ?//隊列數(shù)組的容量 ? ?UKismetSystemLibrary::PrintString(this, "MyIntArray.Num(): " + FString::FromInt(MyIntArray.Num()));}// Called every framevoid AStackAndQueuesExerciseTwo::Tick(float DeltaTime){ ? ?Super::Tick(DeltaTime);}void AStackAndQueuesExerciseTwo::Enqueue(int Input){ ? ?//如果隊列數(shù)組已滿，拓展數(shù)組 ? ?if (Num == MyIntArray.Num()) ? ?{ ? ? ? ?Resize(2 * MyIntArray.Num()); ? ?} ? ?//拓展或者數(shù)組有空位時，添加元素 ? ?if (Num < MyIntArray.Num()) ? ?{ ? ? ? ?MyIntArray[Num] = Input; ? ?} ? ?Num++;}void AStackAndQueuesExerciseTwo::Resize(const int Capacity){ ? ?//int a[] = new int[Capacity]; ? ?TArray<int> Copy; ? ?//添加數(shù)個假元素填充數(shù)組 ? ?for (int i = 0; i < Capacity; i++) ? ?{ ? ? ? ?Copy.Add(0); ? ?} ? ?//將隊列數(shù)組賦值給Copy數(shù)組，如果是縮小數(shù)組，則把隊列數(shù)組左移，節(jié)省空間 ? ?for (int i = HeadIndex; i < Num; i++) ? ?{ ? ? ? ?Copy[i - HeadIndex] = MyIntArray[i]; ? ?} ? ?MyIntArray = Copy;}int AStackAndQueuesExerciseTwo::Dequeue(){ ? ?//判斷數(shù)組是否為空 ? ?if (IsEmpty()) ? ?{ ? ? ? ?UKismetSystemLibrary::PrintString(this, "No Element Exist!!!"); ? ? ? ?return 0; ? ?} ? ?else ? ?{ ? ? ? ?UKismetSystemLibrary::PrintString(this, "Dequeue: " + FString::FromInt(MyIntArray[HeadIndex])); ? ?} ? ?HeadIndex++; ? ?//如果移除元素后，所剩元素為數(shù)組空間的四分之一，則數(shù)組減半 ? ?if ((Num - HeadIndex) != 0 && (Num - HeadIndex) == (MyIntArray.Num() / 4)) ? ?{ ? ? ? ?Resize(MyIntArray.Num() / 2); ? ? ? ?//移除空間后，隊列數(shù)組左移，節(jié)省空間 ? ? ? ?Num -= HeadIndex; ? ? ? ?HeadIndex = 0; ? ? ? ?return MyIntArray[HeadIndex]; ? ?} ? ?else ? ?{ ? ? ? ?return MyIntArray[HeadIndex - 1]; ? ?} }//如果下一個要移除的數(shù)據(jù)不存在，則為空數(shù)組bool AStackAndQueuesExerciseTwo::IsEmpty(){ ? ?return HeadIndex >= Num;}
方法剖析
無論我蜷縮在屋子里 還是遠在另一個地方的冬天。紛紛揚揚的雪 都會落在我正在經(jīng)歷的一段歲月里。
addFirst()
addFirst(E e)的作用是在Deque的首端插入元素，也就是在head的前面插入元素，在空間足夠且下標沒有越界的情況下，只需要將elements[--head] = e即可。
實際需要考慮：1.空間是否夠用，以及2.下標是否越界的問題。上圖中，如果head為0之后接著調(diào)用addFirst()，雖然空余空間還夠用，但head為-1，下標越界了。下列代碼很好的解決了這兩個問題。
? ? ? ? ? ? ? ? ? ?
//addFirst(E e)public void addFirst(E e) { ? ?if (e == null)//不允許放入null ? ? ? ?throw new NullPointerException(); ? ?elements[head = (head - 1) & (elements.length - 1)] = e;//2.下標是否越界 ? ?if (head == tail)//1.空間是否夠用 ? ? ? ?doubleCapacity();//擴容}
上述代碼我們看到，空間問題是在插入之后解決的，因為tail總是指向下一個可插入的空位，也就意味著elements數(shù)組至少有一個空位，所以插入元素的時候不用考慮空間問題。
下標越界的處理解決起來非常簡單，head = (head - 1) & (elements.length - 1)就可以了，這段代碼相當于取余，同時解決了head為負值的情況。因為elements.length必需是2的指數(shù)倍，elements - 1就是二進制低位全1，跟head - 1相與之后就起到了取模的作用，如果head - 1為負數(shù)（其實只可能是-1），則相當于對其取相對于elements.length的補碼。
下面再說說擴容函數(shù)doubleCapacity()，其邏輯是申請一個更大的數(shù)組（原數(shù)組的兩倍），然后將原數(shù)組復制過去。過程如下圖所示：
圖中我們看到，復制分兩次進行，第一次復制head右邊的元素，第二次復制head左邊的元素。
? ? ? ? ? ? ? ? ? ? ? ? ? ? ??
//doubleCapacity()private void doubleCapacity() { ? ?assert head == tail; ? ?int p = head; ? ?int n = elements.length; ? ?int r = n - p; // head右邊元素的個數(shù) ? ?int newCapacity = n << 1;//原空間的2倍 ? ?if (newCapacity < 0) ? ? ? ?throw new IllegalStateException("Sorry, deque too big"); ? ?Object[] a = new Object[newCapacity]; ? ?System.arraycopy(elements, p, a, 0, r);//復制右半部分，對應上圖中綠色部分 ? ?System.arraycopy(elements, 0, a, r, p);//復制左半部分，對應上圖中灰色部分 ? ?elements = (E[])a; ? ?head = 0; ? ?tail = n;}
三、雙端隊列(Deque)
雙端隊列具有隊列和棧的數(shù)據(jù)結構。
class Deque(object): ? ?"雙端隊列" ? ?def __init__(self): ? ? ? ?self.items = [] ? ?def is_empty(self): ? ? ? ?"""判斷雙端隊列是不是空""" ? ? ? ?return self.items ==[] ? ?def add_front(self, item): ? ? ? ?"""從隊頭添加元素""" ? ? ? ?self.items.insert(0, item) ? ?def add_rear(self, item): ? ? ? ?"""從隊尾添加元素""" ? ? ? ?self.items.append(item) ? ?def remove_front(self): ? ? ? ?"""從隊頭刪除元素""" ? ? ? ?return self.items.pop(0) ? ?def remove_rear(self): ? ? ? ?"""從隊尾刪除元素""" ? ? ? ?return self.items.pop() ? ?def size(self): ? ? ? ?"""返回隊列大小""" ? ? ? ?return len(self.items)
if __name__ == '__main__': ? ?deque = Deque() ? ?deque.add_front(1) ? ?deque.add_front(2) ? ?deque.add_rear(3) ? ?deque.add_rear(4) ? ?print(deque.size()) ? ? ? ? ?# 4 ? ?print(deque.remove_front()) ?# 2 ? ?print(deque.remove_front()) ?# 1 ? ?print(deque.remove_rear()) ? # 4 ? ?print(deque.remove_rear()) ? # 3
無論我蜷縮在屋子里 還是遠在另一個地方的冬天。紛紛揚揚的雪 都會落在我正在經(jīng)歷的一段歲月里。
addLast()
addLast(E e)的作用是在Deque的尾端插入元素，也就是在tail的位置插入元素，由于tail總是指向下一個可以插入的空位，因此只需要elements[tail] = e;即可。插入完成后再檢查空間，如果空間已經(jīng)用光，則調(diào)用doubleCapacity()進行擴容。
public void addLast(E e) { ? ?if (e == null)//不允許放入null ? ? ? ?throw new NullPointerException(); ? ?elements[tail] = e;//賦值 ? ?if ( (tail = (tail + 1) & (elements.length - 1)) == head)//下標越界處理 ? ? ? ?doubleCapacity();//擴容}
下標越界處理方式addFirt()中已經(jīng)講過，不再贅述。
pollFirst()
pollFirst()的作用是刪除并返回Deque首端元素，也即是head位置處的元素。如果容器不空，只需要直接返回elements[head]即可，當然還需要處理下標的問題。由于ArrayDeque中不允許放入null，當elements[head] == null時，意味著容器為空。
public E pollFirst() { ? ?E result = elements[head]; ? ?if (result == null)//null值意味著deque為空 ? ? ? ?return null; ? ?elements[h] = null;//let GC work ? ?head = (head + 1) & (elements.length - 1);//下標越界處理 ? ?return result;}
pollLast()
pollLast()的作用是刪除并返回Deque尾端元素，也即是tail位置前面的那個元素。
public E pollLast() { ? ?int t = (tail - 1) & (elements.length - 1);//tail的上一個位置是最后一個元素 ? ?E result = elements[t]; ? ?if (result == null)//null值意味著deque為空 ? ? ? ?return null; ? ?elements[t] = null;//let GC work ? ?tail = t; ? ?return result;}
無論我蜷縮在屋子里 還是遠在另一個地方的冬天。紛紛揚揚的雪 都會落在我正在經(jīng)歷的一段歲月里。
peekFirst()
peekFirst()的作用是返回但不刪除Deque首端元素，也即是head位置處的元素，直接返回elements[head]即可。
public E peekFirst() { ? ?return elements[head]; // elements[head] is null if deque empty}
peekLast()
peekLast()的作用是返回但不刪除Deque尾端元素，也即是tail位置前面的那個元素。
public E peekLast() { ? ?return elements[(tail - 1) & (elements.length - 1)];}
? ? ? ? ? ? ? ? ? ? ? ?
棧和隊列(Stack and Queue)
棧，先進后出，像桶一樣，先放進去，最后才出來。
隊列，先進先出，就像管道一樣，自來水管道，先進先出
總結：
我這計劃：246生活文章，135技術文章 （星期一：技術文章）
這Stack and Queue也是集合的范疇，只是我們平常用不到，他屬于底層的東西，用法跟arrylist差不多。
再說了，我們這做應用開發(fā)的很少用到棧，當需要使用棧時，Java已不推薦使用Stack，而是推薦使用更高效的ArrayDeque；既然Queue只是一個接口，當需要使用隊列時也就首選ArrayDeque了（次選是LinkedList）。
棧，先進后出，像桶一樣，先放進去，最后才出來。隊列，先進先出，就像管道一樣，自來水管道，先進先出
希望這一篇文章可以幫助你對棧和隊列有一定的認識
從這章我看到一個問題Java這我一輩子都不可能學得透徹，只有日積月累慢慢的累計，一天一天的進步一點，加油吧！打工人。
? ? ? ? ? ? ?
