1、基本概念

• 棧：只允許在一端插入或刪除操作的線性表
• 棧底（buttom）：固定的，不允許進行插入和刪除操作的另一端
• 棧頂（top）：線性表允許插入和刪除的一段
  棧是線性表，只不過受到限制了，只允許在棧頂進行插入和刪除操作，所以先入棧的后出棧
  

2、順序棧

棧是線性表的特例，棧的順序存儲也是線性表順序存儲。棧的順序存儲結構叫做順序棧，由于棧是受到限制的（只允許在棧頂進行插入和刪除），所以順序棧需要在順序表是基礎上修改點

/*順序棧的定義 */ #define MaxSize 50 //定義棧中有多少個元素 typedef int ElemType; typedef struct {ElemType data[MaxSize];//存放棧中元素int top; //棧頂指針 }SqStack;

• top值不能超過MaxSize
• 空棧的判斷條件top==-1，初始值也是這個值，當沒有元素時，top指向buttom后一個元素，滿棧的判斷條件top==MaxSize-1

2.1 基本操作

2.1.1 判空

/*判斷空 */ bool StackEmpty(SqStack S) {if (S.top == -1)return true;elsereturn false; }

2.1.2 進棧
棧不滿時，棧頂指針先加1，再送值到棧頂元素

/*進棧 */ bool Push(SqStack& S, ElemType x) {if (S.top == MaxSize - 1)return false;S.data[++S.top] = x;return true; }

2.1.3 出棧
先判斷棧是否為空，不為空，取棧頂元素，top減一

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

2.1.4 讀取棧頂元素
棧頂不為空，取棧頂元素

/*讀取棧頂元素 */ bool GetTop(SqStack S, ElemType& x) {if (S.top == -1)return false;x = S.data[S.top];return true; }

3、共享棧

棧底位置相對不變的，可以讓兩個順序棧共享一個一維數組，將兩個棧的棧底分別設置在共享棧的兩端，兩個棧頂向共享空間的中間延伸，當一個棧存放數據少，一個棧存放數據多，可以考慮共享棧

typedef struct {ElemType data[MaxSize]; //存放元素int top1; //棧1棧頂int top2; //棧2棧頂 }SqDoubleStack;

• 初始狀態：top1=-1，top2=MaxSize，所以當top1=-1時表示棧1空，top2=MaxSize時，表示棧2空
• 棧滿：當top1和top2相差1時，棧滿，此時兩個棧的棧頂緊挨著，沒有空間存放數據了
• 出棧：top2加1，top1要減1
• 入棧：top1加1，top2減1

3.1基本操作

3.1.1 進棧

/*進棧stackNum:棧的序號*/bool Push(SqDoubleStack& S, ElemType x, int stackNum) {if (S.top1 + 1 == S.top2)return false; //棧滿if (stackNum == 1)S.data[++S.top1] = x;if (stackNum == 2)S.data[++S.top2] = x;return true; }

4、鏈式棧

采用鏈式存儲的棧稱為鏈棧，鏈棧的優點是便于多個棧共享存儲空間和提高其效率，并且不存在棧滿溢出的情況,通常采用單鏈表實現，并規定所有操作都是在單鏈表的表頭進行的
帶頭結點：

typedef struct SNode {ElemType data; //數據域struct SNode* next; //指針域 } SNode,*SLink; //鏈棧的結點 typedef struct LinkStack {SLink top; //棧頂指針int count; //鏈棧結點數 }LinkStack; //鏈棧

不帶頭結點：

typedef struct SNode {ElemType data; //數據域struct SNode* next; //指針域 } SNode,*SLink;

注意不帶頭結點和帶頭結點的鏈棧，在具體實現方面有所不同

• 可以將頭指針當做棧頂
• 空棧的判斷條件定為top==null

4.1 基本操作

4.1.1 進棧

/* 進棧 */ bool Push(LinkStack *S, ElemType x) {SLink p = (SLink)malloc(sizeof(SNode));p->data = x;p->next = S->top;S->top = p;S->count++;return true;}

4.1.2 出棧

/*出棧 */ bool Pop(LinkStack* S, ElemType& x) {if (S->top == NULL)return false;x = S->top->data;SLink p = S->top;S->top = S->top->next;free(p);S->count--;return true; }

總結

以上是生活随笔為你收集整理的线性表------栈的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。