在計算機領域離不開算法和資料結構，而在資料結構中尤為重要與基礎的便是兩個線性資料結構：棧與隊列，本文将簡單的介紹棧(Stack)和隊列(Queue)的實作。
棧與隊列
- 棧 (Stack)是一種後進先出(last in first off，LIFO)的資料結構
- 隊列(Queue)則是一種先進先出 (fisrt in first out，FIFO)的結構
動畫如下：
隊列
棧 (Stack)
棧是一種線性結構，與數組相比，棧對應的操作是數組的子集。
它隻能從一端添加元素，也隻能從一端取出元素(這一端稱之為棧頂)。
Stack這種資料結構用途很廣泛，在計算機的使用中，大量的運用了棧，比如編譯器中的詞法分析器、Java虛拟機、軟體中的撤銷操作（Undo）、浏覽器中的回退操作，編譯器中的函數調用實作等等。
說明：push和pop操作在最後面進行，有可能觸發resize，但均攤來算是O(1)的。
如果你想了解更多時間複雜度的分析，歡迎關注筆者後續要更新的文章：O(n)說明的是什麼問題？
棧的實作可以通過 數組 或者 連結清單 實作，在這裡我們使用 數組來實作上述接口。
在棧的設計中，使用者隻關注棧頂元素存取和棧長度，是以設計代碼如下：
讀者可以使用 棧 這種資料結構去解決LeetCode上的第20号問題：有效的括号，也可以檢視 每天一算：Valid Parentheses。
隊列 Queue
隊列也是一種線性資料結構，與數組相比，隊列對應的操作是數組的子集。
隻能從一端 (隊尾) 添加元素，隻能從另一端 (隊首) 取出元素。
隊列的應用可以在播放器上的播放清單，資料流對象，異步的資料傳輸結構(檔案IO，管道通訊，套接字等)上展現，當然最直覺的的就是排隊了。
入隊是從隊尾開始，有可能觸發resize，是以均攤下來是O(1)。出隊是在隊首，數組實作每次都要挪動所有元素,O(n)。
來源 | 五分鐘學算法
作者 | 程式員小吳