#define MaxSize 10
typedef struct{ElemType data[MaxSize];int top0;      // 0號(hào)棧棧頂指針int top1;      // 1號(hào)棧棧頂指針
} ShStack;// 初始化棧
void InitStack(ShStack &S){S.top0 = -1;S.top1 = MaxSize;
}

棧滿的條件: top0 + 1 = top1

鏈棧（鏈?zhǔn)酱鎯?chǔ)）

鏈棧的定義
其操作相當(dāng)于頭插法建立單鏈表（只從表頭進(jìn)行增加刪除操作）

typedef struct LinkNode{ELemType data;   // 數(shù)據(jù)域struct LinkNode *next;     // 指針域
}*LinkStack;

隊(duì)列的三要素

邏輯結(jié)構(gòu)（定義）

隊(duì)列是只允許在一端進(jìn)行插入，在另一端刪除的線性表

特點(diǎn)：先進(jìn)先出（FIFO）

數(shù)據(jù)的運(yùn)算（基本操作）

InitQueue(&Q)
初始化隊(duì)列：構(gòu)造一個(gè)空隊(duì)列QDestroyQueue(&Q)
銷毀隊(duì)列：銷毀并釋隊(duì)列Q所占用的內(nèi)存空間EnQueue(&Q,x)
入隊(duì)：若隊(duì)列Q未滿，則將x加入使之成為新的隊(duì)尾DeQueue(&Q,&x)
出隊(duì)：若隊(duì)列非空，刪除隊(duì)頭元素，并用x返回GetHead(Q,&x)
讀隊(duì)頭元素：若隊(duì)列Q非空，則用x返回隊(duì)頭元素QueueEmpty(Q)
判斷一個(gè)隊(duì)列Q是否為空，若Q為空，則返回true，否則返回false

存儲(chǔ)結(jié)構(gòu)（物理結(jié)構(gòu)）

順序隊(duì)列（順序存儲(chǔ)）

隊(duì)列的順序?qū)崿F(xiàn)

#define MaxSize 10
typedef struct{ElemType data[MaxSize];int front,rear;
} SqQueue;

初始化隊(duì)列

void InitQueue(SqQueue &Q){Q.rear = Q.front = 0;
}

判斷隊(duì)列是否為空

bool QueueEmpty(SqQueue Q){if(Q.rear == Qfront)return true;elsereturn false;
}

入隊(duì)

bool EnQueue(SqQueue &Q,ElemType x){if((Q.rear + 1) % MaxSize == Q.front)return false;    //隊(duì)滿則報(bào)錯(cuò)Q.data[Q.rear] = x;Q.rear = (Q.rear + 1) % MaxSize;  //隊(duì)尾指針加一取模return true;
} 

出隊(duì)

bool DeQueue(SqQueue &Q,ElemType &x){if(Q.rear == Q.front)return false;   // 隊(duì)空則報(bào)錯(cuò)x = Q.data[Q.front];Q.front = (Q.front + 1) % MaxSize;return true;
}

獲取隊(duì)頭元素的值，用x返回

bool GetHead(SqQueue Q,ElemType &x){if(Q.rear == Q.front)return false;x = Q.data[Q.front];return true;
}

隊(duì)列元素的個(gè)數(shù)：
（rear - front + MaxSzie）% MaxSize

鏈?zhǔn)疥?duì)列（鏈?zhǔn)酱鎯?chǔ)）

隊(duì)列的鏈?zhǔn)綄?shí)現(xiàn)

typedef struct LinkNode{    // 鏈?zhǔn)疥?duì)列結(jié)點(diǎn)ElemType data;  struct LinkNode *next;
}LinkNode;typedef struct{             // 鏈?zhǔn)疥?duì)列LinkNode *front,*rear;  // 隊(duì)列的隊(duì)頭和隊(duì)尾指針
}LinkQueue;

初始化（帶頭結(jié)點(diǎn)）

void InitQueue(LinkQueue &Q){// 初始化 front、rear 都指向頭結(jié)點(diǎn)Q.front = Q.rear = (LinkNode *) malloc(sizeof(LinkNode));Q.front->next = NULL;
}

隊(duì)列是否為空

bool IsEmpty(LinkQueue Q){if(Q.rear == Qfront)return true;elsereturn false;
}

新元素入隊(duì)（帶頭結(jié)點(diǎn)）

void EnQueue(LinkNode &Q,ElemType x){LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));s->data = x;s->next = null;Q.rear->next = s;Q.rear = s;
}

入隊(duì)（不帶頭結(jié)點(diǎn)）

void EnQueue(LinkQueue &Q,ElemType x){LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));s->data = x;s->next = NULL;if(Q.front == NULL){   // 在空隊(duì)列中插入第一個(gè)元素Q.front = s;       // 修改隊(duì)頭隊(duì)尾的指針Q.rear = s;} else{Q.rear->next = s;Q.rear = s;}
}

出隊(duì)（帶頭結(jié)點(diǎn)）

bool DeQueue(LinkQueue &Q,ElemType &x){if(Q.front == Q.rear)return false;    // 空隊(duì)LinkNode *p = Q.front->next;x = p.data;Q.front->next = p->next;if(Q.rear == p)   // 此次是最后一個(gè)結(jié)點(diǎn)出隊(duì)Q.rear = Q.front;free(p);          // 釋放結(jié)點(diǎn)空間return true;
}

出隊(duì)（不帶頭結(jié)點(diǎn)）

bool DeQueue(LinkQueue &Q,ElemType &x){if(Q.front == NULL)return false;LinkNode *p = Q.front;x = p->data;Q.front = p->next;if(Q.rear = p)[Q.front = NULL;Q.rear = NULL;}free(p);return true;
}

隊(duì)列的變種

雙端隊(duì)列：允許從兩端插入、兩端刪除的隊(duì)列

輸入受限的雙端隊(duì)列：允許從兩端刪除、從一端插入的隊(duì)列

輸出受限的雙端隊(duì)列：允許從兩端插入、從一端刪除的隊(duì)列

考點(diǎn)：對(duì)輸出序列的合法性的判斷

棧在括號(hào)匹配中的應(yīng)用

代碼實(shí)現(xiàn)

#define MaxSize 10
typedef struct{char data[MaxSize];int top;
}SqStack;// 初始化棧
void InitStack(SqStack &S)// 判斷棧是否為空
bool StackEmpty(SqStack S)// 新元素入棧
bool Push(SqStack &S,char x)// 棧頂元素出棧，用x返回
bool Pop(SqStack &S,char &x)bool bracketCheck(char str[],int length){SqStack S;InitStack(S);  // 初始化for(int i = 0; i < length; i++){if(str[i] == '(' || str[i] == '[' || str[i] == '{'){Push(S, str[i]);  // 掃描到左括號(hào)，入棧} else {if(StackEmpty(S))  // 掃描到右括號(hào)，并且當(dāng)前?？?/span>return false;  // 匹配失敗char topElem;Pop(S, topElem);   // 棧頂元素出棧if(str[i] == ')' && topElem != '(')return false;if(str[i] == ']' && topElem != '[')return false;if(str[i] == '}' && topElem != '{')return false;}}return StackEmpty(S);   // 檢索完全部括號(hào)后，棧空說(shuō)明匹配成功
} 

棧在表達(dá)式求值中的應(yīng)用

三種算術(shù)表達(dá)式：
1、中綴表達(dá)式：運(yùn)算符在兩個(gè)操作數(shù)中間 —— a+b
2、后綴表達(dá)式（逆波蘭表達(dá)式）：運(yùn)算符在兩個(gè)操作數(shù)后面 —— ab+
3、前綴表達(dá)式（波蘭表達(dá)式）：運(yùn)算符在兩個(gè)操作數(shù)前面 —— +ab

中綴表達(dá)式 ------>后綴表達(dá)式

手算

1、確定中綴表達(dá)式中各個(gè)運(yùn)算符的運(yùn)算順序
2、選擇下一個(gè)運(yùn)算符，按照【 左操作符 右操作符 運(yùn)算符 】的方式組合成一個(gè)新的操作數(shù)
3、如果還有運(yùn)算符沒(méi)被處理，就繼續(xù)2
注意：為了保證手算和機(jī)算結(jié)果相同，采用“左優(yōu)先”原則：只有左邊的運(yùn)算符能先運(yùn)算，就優(yōu)先算左邊（可保證運(yùn)算順序唯一）

機(jī)算

初始化一個(gè)棧，用于保存暫時(shí)還不能確定運(yùn)算順序的運(yùn)算符
從左到右處理各個(gè)元素，直到末尾，可能遇到三種情況：
1、遇到操作數(shù)：直接加入后綴表達(dá)式
2、遇到界限符：遇到 “ ( ” 直接入棧，遇到 “ ) ” 則依次彈出棧內(nèi)運(yùn)算符并加入后綴表達(dá)式，直到彈出 “ ( ” 為止。注意：“ ( ” 不加入后綴表達(dá)式
3、遇到運(yùn)算符：依次彈出棧中優(yōu)先級(jí)高于或者等于當(dāng)前運(yùn)算符的所有運(yùn)算符，并加入后綴表達(dá)式，若碰到 “ ( ” 或?？談t停止。之后再把當(dāng)前的運(yùn)算符入棧
4、處理完所有字符后，將棧中剩余運(yùn)算符依次彈出，并加入后綴表達(dá)式

后綴表達(dá)式的計(jì)算

1、從左往右掃描下一個(gè)元素，直到處理完所有的元素
2、若掃描到操作數(shù)則壓入棧，并回到1；否則執(zhí)行3
3、若掃描到運(yùn)算符，則彈出兩個(gè)棧頂元素，執(zhí)行相應(yīng)運(yùn)算（先出棧的是右操作數(shù)），運(yùn)算結(jié)果壓回棧頂，回到1
4、若表達(dá)式合法。則最后棧中只會(huì)留下一個(gè)元素，就是最終結(jié)果

中綴表達(dá)式 ------>前綴表達(dá)式

1、確定中綴表達(dá)式中各個(gè)運(yùn)算符的運(yùn)算順序
2、選擇下一個(gè)運(yùn)算符，按照【 運(yùn)算符 左操作符 右操作符 】的方式組合成一個(gè)新的操作數(shù)
3、如果還有運(yùn)算符沒(méi)被處理，就繼續(xù)2
注意：為了保證手算和機(jī)算結(jié)果相同，采用“右優(yōu)先”原則：只有右邊的運(yùn)算符能先運(yùn)算，就優(yōu)先算右邊（可保證運(yùn)算順序唯一）

前綴表達(dá)式的計(jì)算

1、從右往左掃描下一個(gè)元素，直到處理完所有的元素
2、若掃描到操作數(shù)則壓入棧，并回到1；否則執(zhí)行3
3、若掃描到運(yùn)算符，則彈出兩個(gè)棧頂元素，執(zhí)行相應(yīng)運(yùn)算（先出棧的是左操作數(shù)），運(yùn)算結(jié)果壓回棧頂，回到1
4、若表達(dá)式合法。則最后棧中只會(huì)留下一個(gè)元素，就是最終結(jié)果

用棧實(shí)現(xiàn)中綴表達(dá)式的計(jì)算

中綴表達(dá)式 ------>后綴表達(dá)式 與 后綴表達(dá)式的計(jì)算 的結(jié)合

*初始化兩個(gè)棧：操作數(shù)棧 和 運(yùn)算符棧
若掃描到操作數(shù)，壓入操作數(shù)棧
若掃描到運(yùn)算符或者界限符，則按照“中綴轉(zhuǎn)后綴”相同的邏輯壓入運(yùn)算符棧
每當(dāng)彈出一個(gè)運(yùn)算符時(shí)，就需要在彈出兩個(gè)操作數(shù)棧的棧頂元素并執(zhí)行相應(yīng)的運(yùn)算，運(yùn)算結(jié)果再壓回操作數(shù)棧中