1.棧的定義

棧（stack）：是只允許在一端進行插入或者刪除操作的線性表（即后進先出，大概可以理解為吃飽了吐出來）

空棧：不含元素的空標配

棧頂：表尾端

棧底：表頭端

進棧順序：a1->a2->a3->a4->a5

出棧順序：a5->a4-a3->a2->a1

2. 對比線性表和棧基本操作

2.1 線性表的基本操作

InitList (&L): 初始化表。構造一個空的線性表 L，分配內存空間

DestoryList (&L): 銷毀操作。銷毀線性表，并且釋放線性表 L 所占用的空間

ListInsert (&L,i,e): 插入操作，在表 L 中的第 i 個位置上插入指定元素 e

ListDelete (&L,i,e): 刪除操作，刪除表 L 中的第 i 個位置的元素，并且用 e 返回刪除元素的值

LocateElem (L,e): 按值查找操作，在表 L 中查找具有給定關鍵字值的元素

GetElem (L,i): 按位查找操作，獲取表 L 中第 i 個位置的元素的值

2.2 棧的基本操作

InitStack (&S): 初始化棧，構造一個空棧 S，分配內存空間

DestoryStack (&S): 銷毀棧，銷毀并釋放棧 S 所占用的內存空間

Push (&S,x): 進棧，若棧 S 未滿，則將 x 加入使之成為新的棧頂

Pop (&S,&x): 出棧，若棧 S 非空，則彈出棧頂元素，并用 x 返回

GetTop (S,&x): 讀棧頂元素，若棧 S 非空，則用 x 返回棧頂元素

其他常見操作：StackEmpty (S): 判斷一個棧 S 是否為空，若 S 為空，則返回 true，否則返回 false

3. 順序棧

3.1 順序棧的定義

#define MaxSize 10           //定義棧中元素的最大個數 
typedef struct{
 ElemType data[MaxSize];   //靜態數組存放棧中的元素
    int top;      //棧頂指針
}SqStack;         //結構體重命名

聲明一個順序棧后就會在內存中分配一整片連續的空間，其中內存大小為：MaxSize*sizeof (ELemType)

void testStack(){
 SqStack S; //聲明一個順序棧
}

3.2 棧的初始化操作

由于棧頂指針 top 需要指向此時棧頂元素，所以讓 top 指向 0 是不合理的，可以初始化讓 top 指向 - 1; 判斷一個棧是否為空，即判斷 S.top 是否等于 - 1 初始化棧：

void Inittack(SqStack){
 SqStack S;   //聲明一個順序棧
 S.top=-1;
}

判斷棧空：

bool StackEmpty(SqStack S){
    if(S.top==-1)      //棧空
        return true;
    else 
        return false;  //非空
}

3.3 進棧操作

分析：

判斷棧是否為空

棧頂指針 + 1

新元素入棧

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

3.4 出棧操作

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

3.5 讀棧頂元素操作

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

4. 共享棧

兩個棧共享同一片空間

#define MaxSize 10           //定義棧中元素的最大個數 
typedef struct{
 ElemType data[MaxSize];   //靜態數組存放棧中的元素
    int top0;     //0號棧棧頂指針
    int top1;     //1號棧棧頂指針
}SqStack;         //結構體重命名
初始化棧：
void InitStack(ShStack &S){
 S.top0=-1;
 S.top1=MaxSize;
}

5. 鏈棧的定義

進棧 / 出棧都只能在棧頂一段進行

鏈頭作為棧頂

typedef struct Linknode{
 ElemType data;           //數據域
    struct Linknode *next;   //指針域
}*LiStack                    //棧類型定義

審核編輯：劉清