---

棧的三要素

邏輯結構（定義）

棧是只允許在一端進行插入或刪除操作的線性表

特點：后進先出（LIFO）

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

InitStack(&S)
初始化棧：構造一個空棧S，分配內存空間DestroyStack(&S)
銷毀棧：銷毀并釋放棧S所占用的內存空間Push(&S,x)
進棧：若棧S未滿，則將x加入使之成為新棧頂Pop(&S,&x)
出棧：若棧非空，則彈出棧頂元素，并用x返回GetTop(S,&x)
讀棧頂元素：若棧S非空，則用x返回棧頂元素StackEmpty(S)
判斷一個棧S是否為空，若S為空，則返回true，否則返回false

棧的?？碱}型
已知進棧順序，問有哪些合法的出棧順序？
出棧元素不同排列的個數(shù)為

存儲結構（物理結構）

順序棧（順序存儲）

順序棧的定義

#define MaxSize 10
typedef struct{ELemType data[MaxSize];   // 靜態(tài)數(shù)組存放棧中元素int top;                  // 棧頂指針
}SqStack;

初始化棧

void InitStack(SqStack &S){S.top = 0;
}

判空

bool StackEmpty(SqStack S){if(S.top == -1)return true;elsereturn false;
]

進棧操作

bool Push(SqStack &S,ElemType x){if(S.top == MaxSize - 1)renturn false;S.top = S.top + 1;   // 指針先加1S.data[S.top] = x;   // 新元素入棧return true;
}

出棧操作

bool Pop(SqStack &S, ElemType &x){if(S.top == -1)return false;x = S.data[S.top];S.top = S.top - 1;return true;
}

讀棧頂元素

bool GetTop(SqStack S, ElemType &x){if(S.top == -1)return false;x = S.data[S.top];return true;
|

共享棧

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

棧滿的條件: top0 + 1 = top1

鏈棧（鏈式存儲）

鏈棧的定義
其操作相當于頭插法建立單鏈表（只從表頭進行增加刪除操作）

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

隊列的三要素

邏輯結構（定義）

隊列是只允許在一端進行插入，在另一端刪除的線性表

特點：先進先出（FIFO）

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

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

存儲結構（物理結構）

順序隊列（順序存儲）

隊列的順序實現(xiàn)

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

初始化隊列

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

判斷隊列是否為空

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

入隊

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

出隊

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

獲取隊頭元素的值，用x返回

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

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

鏈式隊列（鏈式存儲）

隊列的鏈式實現(xiàn)

typedef struct LinkNode{    // 鏈式隊列結點ElemType data;  struct LinkNode *next;
}LinkNode;typedef struct{             // 鏈式隊列LinkNode *front,*rear;  // 隊列的隊頭和隊尾指針
}LinkQueue;

初始化（帶頭結點）

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

隊列是否為空

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

新元素入隊（帶頭結點）

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;
}

入隊（不帶頭結點）

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

出隊（帶頭結點）

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

出隊（不帶頭結點）

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;
}

隊列的變種

雙端隊列：允許從兩端插入、兩端刪除的隊列

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

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

考點：對輸出序列的合法性的判斷

棧在括號匹配中的應用

代碼實現(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]);  // 掃描到左括號，入棧} else {if(StackEmpty(S))  // 掃描到右括號，并且當前?？?/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);   // 檢索完全部括號后，?？照f明匹配成功
} 

棧在表達式求值中的應用

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

中綴表達式 ------>后綴表達式

手算

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

機算

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

后綴表達式的計算

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

中綴表達式 ------>前綴表達式

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

前綴表達式的計算

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

用棧實現(xiàn)中綴表達式的計算

中綴表達式 ------>后綴表達式 與 后綴表達式的計算 的結合

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