[TOC]
寫在前面
本篇文章整理《數(shù)據(jù)結(jié)構(gòu)（C++語言版）》關(guān)于棧與隊(duì)列這種線性結(jié)構(gòu)知識點(diǎn)。
整個數(shù)據(jù)結(jié)構(gòu)部分章節(jié)列表如下:
1 向量
-- 1.1 遍歷
-- 1.2 唯一化
-- 1.3 查找
2 列表
-- 2.1 列表節(jié)點(diǎn)
---- 2.1.1前插入算法
-- 2.2 列表模板類
---- 2.2.1 列表初始化
3 棧
--3.1 棧應(yīng)用
---- 3.1.1 括號匹配
---- 3.1.2 椃岚混洗甄別
---- 3.1.3 中綴表達(dá)式
4 隊(duì)列
3 棧
后進(jìn)先出（LIFO）是棧這種結(jié)構(gòu)最大的特點(diǎn)禁熏。對棧而言，只有一端的可訪問稱作邑彪，頂端top瞧毙。
棧也是一種線性結(jié)構(gòu)，即滿足邏輯地址連續(xù)锌蓄，故可直接基于向量或列表派生升筏。
//基于vector結(jié)構(gòu)的棧初始化
template<typename T>
class Stack: public Vector<T>{
public:
void push(T const& e) { insert( size(), e);} //入棧，等效于作為向量末元素插入
T pop() { return remove( size() -1); } //出棧瘸爽，等效于刪除向量末元素
T& top() { return ( *this ) [ size() - 1 ]; } //取頂您访，直接返回向量的末元素
}；
3.1 棧應(yīng)用
基于棧結(jié)構(gòu)的應(yīng)用剪决，就是要充分利用其后進(jìn)先出LIFO的特性灵汪。
3.1.1 括號匹配
解決問題：判斷一個只含括號的表達(dá)式是否匹配。
算法：從表達(dá)式左側(cè)開始掃描柑潦，當(dāng)掃描到左括號(則壓入棧中享言，若掃描到右括號)則彈出棧頂元素，繼續(xù)掃描下去渗鬼。當(dāng)且僅當(dāng)最后掃描完成時(shí)览露，棧類所有左括號(均已彈出，棧為空棧時(shí)該表達(dá)式括號匹配譬胎。
代碼實(shí)現(xiàn)
bool paren( char exp[], int lo, int hi ) { //exp[lo, hi)
Stack<char> s;
for(int i=lo; i < hi; i++){
if( '(' == exp[i] ) s.push(exp[i]); //若左括號差牛，入棧
else if( !s.empty() ) s.pop(); //若右括號命锄，且棧非空，彈出棧頂
else return false; //若括號表達(dá)式未掃描結(jié)束偏化，棧已空脐恩，則不匹配
}
return s.empty();
}
TIPS:字符串與字符數(shù)組
字符串以空字符\0結(jié)尾，用來標(biāo)記字符串的結(jié)尾侦讨。
char dog[4] = {'a', 'b', 'c', 'd'}; //不是字符串驶冒，是char數(shù)組
char cat[4] = {'a', 'b', 'c', '\0'}; //是字符串，也是char數(shù)組
另一種操作方法是通過雙引號聲明字符串韵卤，若聲明長度比實(shí)際長度長骗污，則空字符將自動補(bǔ)全到實(shí)際長度之后。
char bird[5] = "abc"; //實(shí)際為 abc\0\0
char bird[] = "abc"; //編譯器自己判斷字符串長度
3.1.2 椓混洗甄別
解決問題：將棧A中的元素通過棧S轉(zhuǎn)移入棧B中身堡。對元素的移入移出操作只允許以入棧出棧方式。進(jìn)而判斷棧B中元素序列是否是一種椗睦穑混洗贴谎。
算法：不妨設(shè)棧A的元素為升序排列季稳。對棧B中第i個元素擅这，當(dāng)其從棧S彈出前景鼠，S棧頂端以下元素按降序排列溯香。即，若棧S頂元素小于B[i]湿镀，則依次將A中元素入棧树肃；若棧S頂元素等于B[i]，則S出棧廓脆，繼續(xù)判斷B[i+1]蚊伞；若棧S頂元素大于B[i]，則不是椔尤混洗。
該算法的一個典型應(yīng)用場景為火車調(diào)度問題柏靶。
代碼實(shí)現(xiàn)
/*
判斷棧B中序列是否為一種棧混洗
為了簡化問題，棧A、B元素確定，因此可以通過數(shù)組等方式實(shí)現(xiàn)捍靠。
/*
int A = 1;
int B[] = {2, 3, 1, 4, 5};
bool Stackverfi(int A, const int* array_B){
Stack<int> S;
for(int i = 0; i < 5; i++){
while( S.top() < B[i] ){
S.push(A++);
std::cout << "push\n";
}
if( S.top() == B[i] ){
S.pop();
std::cout << "pop\n";
}
else{
std::cout << "NO!!!";
return false;
}
}
}
3.1.3 中綴表達(dá)式
算法：對于一個正確的算數(shù)表達(dá)式沐旨，先準(zhǔn)備兩個棧A，B分別用于存儲運(yùn)算符和運(yùn)算數(shù)榨婆。掃描到運(yùn)算數(shù)磁携，則入棧A中；掃描到運(yùn)算符時(shí)良风，與棧B的棧頂運(yùn)算符比較谊迄，若棧頂運(yùn)算符優(yōu)先級較低，則入棧烟央；若棧頂運(yùn)算符優(yōu)先級較高统诺，則彈出棧B頂運(yùn)算符，彈出棧A兩個運(yùn)算數(shù)（若為單元素操作符疑俭，只彈出一個元素）粮呢，將運(yùn)算結(jié)果壓入棧A。
4 隊(duì)列
隊(duì)列的特性與棧結(jié)構(gòu)正好相反钞艇，其主要性能是先進(jìn)先出(FIFO)啄寡。具體實(shí)現(xiàn)方式與棧結(jié)構(gòu)類似，這里不過多敘述哩照。
