大家在學習程式設計時或程式開發中，經常涉及資料結構中的“隊列”和“棧”。那麼他們分别具有什麼結構特點？底層實作原理是什麼？他們在STL中是如何實作的呢？都有哪些應用場景呢？
備注：因為篇幅限制，本文先講解資料結構中的棧(stack)。
1.引言
棧和隊列是兩種特殊的線性表，是操作受限的線性表，稱限定性DS。
通常稱，棧和隊列是限定插入和删除隻能在表的“端點”進行的線性表。
舉例：
線性表Insert(L, i, x)1≤i≤n+1Delete(L, i) 1≤i≤n
棧Insert(S, n+1, x) Delete(S, n)
隊列Insert(Q, n+1, x)Delete(Q, 1)
2.棧的定義和特點
棧(stack)是一種先進後出的資料結構。它隻有一個出口。stack允許新增元素、删除元素、取得最頂端元素。但是除了最頂端外，沒有任何其它方法可以存取stack的其他元素。換言之，stack不允許有周遊行為。
定義：限定僅在表尾進行插入或删除操作的線性表。表尾是棧頂，表頭是棧底，不含元素的空表稱空棧。
特點：先進後出（FILO）或後進先出（LIFO）
3.棧的實作原理
類似于線性表的順序映象實作，利用一組存儲單元依次存放自棧底到棧頂的資料元素，同時附設指向表尾的指針top，訓示棧頂元素在順序棧中的位置，稱為棧頂指針，連續存儲單元的基址用指針base訓示，稱為棧底指針。
//----- 棧的順序存儲表示 -----
#define STACK_INIT_SIZE 100;
typedef struct {
SElemType *base;
SElemType *top;
int stacksize;
} SqStack;
top的初值指向棧底：top=base，此條件也可作為判棧空的條件；
在實際使用中，top 始終指向棧頂元素的下一個位置上；
入棧（插入新的棧頂元素）：top增1；
出棧（删除棧頂元素）： top減1。
3.1.順序棧
利用一組"位址連續"的存儲單元依次存放自棧底到棧頂的資料元素
資料結構和入棧出棧示意圖：
3.2.鍊棧
利用一組連結清單依次存放自棧底到棧頂的資料元素。
連結清單節點定義：
typedef struct node
{
int data;
struct node *link;
} node;
資料結構和入棧出棧示意圖：
4.STL中的棧實作
在c++開發中，我們常常直接使用STL中封裝好的容器。那麼，對于棧在STL中是如何實作的呢？又有哪些特點呢？
①SGI STL的stack預設是以deque為底層資料容器的。(對應前面提到的“順序棧”，也可以使用vector為底層資料容器)
以某種既有容器作為底部結構，将其接口改變，使之符合“先進後出”的特性，形成一個stack,是很容易做到的。deque是雙向開口的資料結構，若以deque為底部結構并封閉其頭端開口，便輕而易舉地形成了一個stack。是以，SGI STL便以deque作為預設情況下的stack底部結構，stack的實作因而非常簡單，源代碼十分簡短。
template <class T, class Sequence = deque<T> >
class stack {
friend bool operator== __STL_NULL_TMPL_ARGS (const stack&, const stack&);
friend bool operator< __STL_NULL_TMPL_ARGS (const stack&, const stack&);
public:
typedef typename Sequence::value_type value_type;
typedef typename Sequence::size_type size_type;
typedef typename Sequence::reference reference;
typedef typename Sequence::const_reference const_reference;
protected:
Sequence c;// 底層容器
public:
// 以下完全利用 Sequence c 的操作，完成 stack 的操作。
bool empty() const { return c.empty(); }
size_type size() const { return c.size(); }
reference top() { return c.back(); }
const_reference top() const { return c.back(); }
// deque 是兩頭可進出，stack 是末端進，末端出（是以後進者先出）。
void push(const value_type& x) { c.push_back(x); }
void pop() { c.pop_back(); }
};
template <class T, class Sequence>
bool operator==(const stack<T, Sequence>& x, const stack<T, Sequence>& y) {
return x.c == y.c;
}
template <class T, class Sequence>
bool operator<(const stack<T, Sequence>& x, const stack<T, Sequence>& y) {
return x.c < y.c;
}
②stack沒有提供疊代器
stack所有元素的進出都必須符合“先進後出”的條件，隻有stack頂端的元素，才有機會被外界取用。stck不提供走訪功能，也不提供疊代器。
③可以使用list作為stack的底層容器。(對應前面提到的“鍊棧”)
除了deque之外，Iist也是雙向開口的資料結構。上述stack源代碼中使用的底層容器的函數list都具備。是以，若以list為底部結構并封閉其頭端開口，一樣能夠輕易形成一個stack。
測試代碼：
參考文章最後的附錄。
測試程式運作效果：
分别使用STL的deque、list、vector作為stack的底層容器，進行同樣資料的入棧和出棧。
5.棧的應用舉例
①數制轉換
例如：（1348)10 = (2504)8 ，其運算過程如下：
②括号比對的檢驗
例如：假設在表達式中，隻有［］（）兩種括号，如：（［］（））、［（［ ］［ ］）］等為正确的格式，［（ ］）或（［（ ））或 （（） ］ ）均為不正确的格式。檢驗括号是否比對。
算法的設計思想：
1）凡出現左括号，則進棧；
2）凡出現右括号，首先檢查棧是否空：
若棧空，則表明該“右括号”多餘不比對，
否則和棧頂元素比較，
若相比對，則“左括号出棧”，否則表明不比對
3）表達式檢驗結束時，
若棧空，則表明表達式中比對正确
否則表明“左括号”有餘，不比對
③回文遊戲
例如：順讀與逆讀字元串一樣（不含空格）
比如，字元串：“madam im adam”
算法設計思想：
1.讀入字元串
2.去掉空格（原串）
3.壓入棧
4.原串字元與出棧字元依次比較
若不等，非回文
直到棧空都相等，回文
④行編輯程式問題、迷宮求解、表達式求值、實作遞歸等
這些場景就不給大家一一舉例了，感興趣的同學可以再評論區留言，我再留言區回複大家。
6.附錄
測試代碼源碼。
#include<iostream>
#include <stack>
#include <list>
#include <vector>
#include <algorithm>
using namespace std;
template <class T, class Sequence = deque<T> >
void stack_fun_test(stack<T, Sequence> & list_stack)
{
//入棧
list_stack.push(1);
list_stack.push(3);
list_stack.push(5);
list_stack.push(7);
if (true != list_stack.empty())
{
}
// 元素依次出棧
while (true != list_stack.empty())
{
// 列印棧頂元素
// 出棧
list_stack.pop();
}
}
//以deque作為預設情況下的stack底部結構
void stack_fun_deque_test()
{
stack<int> list_stack; //建立stack
stack_fun_test(list_stack);
}
//以list作為stack底部結構
void stack_fun_list_test()
{
stack<int, list<int>> list_stack; //建立stack
stack_fun_test(list_stack);
}
//以vector作為stack底部結構
void stack_fun_vector_test()
{
stack<int, vector<int>> list_stack; //建立stack
stack_fun_test(list_stack);
}
int main(int argc, char* argv[])
{
stack_fun_deque_test();
stack_fun_list_test();
stack_fun_vector_test();
return 0;
}
原創不易，歡迎關注、收藏、轉發！