1. 棧的定義
1.1 定義
棧是限定僅在表尾進行插入和刪除操作的線性表。
棧頂：把允許插入和刪除的一端稱為棧頂。
棧底：把和棧頂對應的另一端稱為棧底。
空棧：不含任何數據元素的棧稱為空棧。
棧的特性：先進後出，也叫做後進先出。
棧是一種特殊的線性表，棧內元素具有線性關係，即前驅和後繼關係，定義中所說的僅在表尾進行插入和刪除操作，即在棧頂進行插入和刪除，而不是棧底。
1.2 插入與刪除概念
棧的插入操作，叫做進棧，也叫壓棧、入棧，如下圖所示：
棧的刪除操作，叫做出站，也叫彈棧，如下圖所示：
2. 棧的順序存儲結構
2.1 棧的順序存儲結構定義
棧是特殊的線性表，如果採用順序存儲結構，我們稱這種棧為順序棧，我們用數組來實現順序存儲。
在順序存儲結構中，如果在數組的頭部位置進行插入和刪除，會涉及到後續元素的移位工作，所以我們在數組的末尾進行插入和刪除操作，會更加便利，因此我們將數組的頭部（即下標為0的位置）稱為棧底，數組的尾部稱為棧頂。
我們定義top指針（這裡的指針並非實際意義上的指針，只是一種稱呼）用來記錄棧頂元素在數組中的位置，若棧的長度為MAXSIZE，那麼棧頂位置top必須小於MAXSIZE，當棧存在一個元素時，top等於0，若為空棧，則top等於-1。
順序棧的結構定義：
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20 /* 存儲空間初始分配量 */
typedef int Status;
typedef int SElemType; /* SElemType類型根據實際情況而定，這裡假設為int */
/* 順序棧結構 */
typedef struct
{
SElemType data[MAXSIZE];
int top; /* 用於指向棧頂位置 */
}SqStack;2.2 順序棧初始化
順序棧的結構比較簡單，我們使用一段地址連續的存儲單元來存儲數據，所以在創建棧對象的時候，即申請了存儲空間，因此初始化只需要設置初始值即可。
代碼實現：
//構建一個空棧S
Status InitStack(SqStack *S){
// 若棧不存在，返回error。
if (S == NULL) {
return ERROR;
}
// 設置top為-1，此時為空棧。
S->top = -1;
return OK;
}2.3 順序棧進棧操作——插入元素
進棧即為在棧頂插入元素。
思路
- 判斷棧是否已滿，如果滿了，則無法插入數據，返回error。
- 將棧頂指針top++。
- 將新插入的元素賦值給棧頂空間。
- 返回OK。
代碼實現
// 插入元素e為新棧頂元素
Status PushData(SqStack *S, SElemType e){
//棧已滿
if (S->top == MAXSIZE -1) {
return ERROR;
}
//棧頂指針+1;
S->top ++;
//將新插入的元素賦值給棧頂空間
S->data[S->top] = e;
return OK;
}2.4 順序棧出棧操作——刪除元素
思路
- 判斷棧是否為空棧，如果是空棧，則無法進行操作，返回error。
- 將刪除元素賦值給e，並帶回調用函數。
- 將棧頂指針top--。
- 返回OK。
代碼實現
// 刪除S棧頂元素,並且用e帶回
Status Pop(SqStack *S,SElemType *e){
//空棧,則返回error;
if (S->top == -1) {
return ERROR;
}
//將要刪除的棧頂元素賦值給e
*e = S->data[S->top];
//棧頂指針--;
S->top--;
return OK;
}2.5 順序棧置空與判斷
置空
將棧置空，我們不需要將順序棧的元素都清空，只需要修改top指針即可。
代碼實現
// 將棧置空
Status ClearStack(SqStack *S){
S->top = -1;
return OK;
}判斷
上面我們說過，當棧的top指針為-1的時候，則棧為空棧。
代碼實現
// 判斷順序棧是否為空;
Status StackEmpty(SqStack S){
if (S.top == -1)
return TRUE;
else
return FALSE;
}2.6 獲取順序棧棧頂元素
獲取順序棧棧頂元素即獲取數組最後一個元素。
代碼實現
// 獲取棧頂
Status GetTop(SqStack S,SElemType *e){
if (S.top == -1)
return ERROR;
else
*e = S.data[S.top];
return OK;
}2.7 遍歷順序棧元素
遍歷順序棧元素即遍曆數組的每個元素。
代碼實現
// 從棧底到棧頂依次對棧中的每個元素列印
Status StackTraverse(SqStack S){
int i = 0;
printf("此棧中所有元素");
while (i<=S.top) {
printf("%d ",S.data[i++]);
}
printf("\\n");
return OK;
}3. 棧的鏈式存儲結構
3.1 棧的鏈式存儲結構定義
上面我們了解的棧的順序存儲結構，那麼如果棧用鍊表結構進行存儲，即為棧的鏈式存儲結構，我們成為鏈式棧，或鏈棧。
在鏈式棧中，我們採用單鍊表的形式存儲棧的每個元素，那麼我們如何定義棧頂和棧底呢，如果將單鍊表的表尾當做棧頂，那麼每次插入和刪除的時候，我們則需要遍歷找到尾部元素，這樣很麻煩，每個鍊表都有自己的頭指針，因此，將鍊表的頭部當做棧頂，我們只需要修改一下鍊表元素前後關係即可。
鏈式棧中，我們只會在鍊表的頭部進行操作，所以鍊表的頭結點的意思蕩然無存，因此鍊表的第一個元素即為首元結點。
順序棧中，我們需要考慮棧的溢出情況，因為我們每次申請的空間是固定的，但是在鏈式棧中，無需考慮溢出情況，除非計算機的內存不夠了。
在鏈式棧中，當top指針為NULL的時候，則認為這是一個空鏈式棧。
鏈式棧的結構定義：
/* 鏈式棧結點結構 */
typedef struct StackNode
{
SElemType data;
struct StackNode *next;
}StackNode,*LinkStackPtr;
/* 鏈式棧結構 */
typedef struct
{
LinkStackPtr top;
int count;
}LinkStack;鏈式棧示意圖
3.2 鏈式棧初始化
鏈式棧中沒有採用頭結點，因此初始化時只需要設置初始值，不需要開闢空間。
代碼實現
/* 構造一個空棧S */
Status InitStack(LinkStack *S)
{
S->top=NULL;
S->count=0;
return OK;
}3.3 鏈式棧進棧操作——插入元素
思路
- 創建新增的結點temp，並對新增結點進行賦值。
- 將新增結點temp的後繼指向當前棧頂結點S->top。
- 修改棧頂指針S->top為temp。
- 棧元素數量加1。
- 返回OK。
代碼實現
/* 插入元素e到鏈棧S (成為棧頂新元素)*/
Status Push(LinkStack *S, SElemType e){
//創建新結點temp
LinkStackPtr temp = (LinkStackPtr)malloc(sizeof(StackNode));
//賦值
temp->data = e;
//把當前的棧頂元素賦值給新結點的直接後繼, 參考上圖第步驟;
temp->next = S->top;
//將新結點temp 賦值給棧頂指針,參考圖例第步驟;
S->top = temp;
S->count++;
return OK;
}3.4 鏈式棧出棧操作——刪除元素
思路
- 若棧內已無元素，則無法刪除元素，返回error。
- 將棧頂元素值賦值給e，並帶回調用函數。
- 創建臨時變量p指向棧頂元素。
- 將棧頂指針向下移動一位。
- 釋放原棧頂元素p。
- 棧元素數量減1.
- 返回OK。
代碼實現
/* 若棧不為空,則刪除S的棧頂元素,用e返回其值. 並返回OK,否則返回ERROR*/
Status Pop(LinkStack *S,SElemType *e){
LinkStackPtr p;
if ((*S).count == 0) {
return ERROR;
}
//將棧頂元素賦值給*e
*e = S->top->data;
//將棧頂結點賦值給p,參考圖例
p = S->top;
//使得棧頂指針下移一位, 指向後一結點. 參考圖例
S->top= S->top->next;
//釋放p
free(p);
//個數--
S->count--;
return OK;
}3.5 鏈式棧置空與判斷
置空
- 創建結點指針p,q，將p指向棧頂。
- 循環遍歷鍊表，將p賦值給q，p指向下一個結點，釋放q。
- 當遍歷到末尾時，即鍊表所有結點都已經釋放，設置棧元素數量為0.
- 返回OK。
代碼實現
/* 把鏈棧S置為空棧*/
Status ClearStack(LinkStack *S){
LinkStackPtr p,q;
p = S->top;
while (p) {
q = p;
p = p->next;
free(q);
}
S->count = 0;
return OK;
}判斷
判斷是否為空棧，只需要判斷count是否為0即可。
代碼實現
/* 若棧S為空棧,則返回TRUE, 否則返回FALSE*/
Status StackEmpty(LinkStack S){
if (S.count == 0)
return TRUE;
else
return FALSE;
}3.6 鏈式棧獲取棧頂元素
獲取鏈式棧棧頂元素即獲取鍊表的第一個結點元素。
代碼實現
/* 若鏈棧S不為空,則用e返回棧頂元素,並返回OK ,否則返回ERROR*/
Status GetTop(LinkStack S,SElemType *e){
if(S.top == NULL)
return ERROR;
else
*e = S.top->data;
return OK;
}3.7 遍歷鏈式棧元素
遍歷鏈式棧元素即遍歷鍊表的每個元素。
代碼實現
/* 遍歷鏈棧*/
Status StackTraverse(LinkStack S){
LinkStackPtr p;
p = S.top;
while (p) {
printf("%d ",p->data);
p = p->next;
}
printf("\\n");
return OK;
}