詳解數(shù)據(jù)結(jié)構(gòu)中棧的定義和操作

1.棧的定義

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

空棧：不含元素的空標(biāo)配

棧頂：表尾端

棧底：表頭端

進(jìn)棧順序：a1->a2->a3->a4->a5

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

2. 對(duì)比線性表和棧基本操作

2.1 線性表的基本操作

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

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

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

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

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

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

2.2 棧的基本操作

InitStack (&S): 初始化棧，構(gòu)造一個(gè)空棧 S，分配內(nèi)存空間

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

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

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

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

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

3. 順序棧

3.1 順序棧的定義

#define MaxSize 10           //定義棧中元素的最大個(gè)數(shù) 
typedef struct{
 ElemType data[MaxSize];   //靜態(tài)數(shù)組存放棧中的元素
    int top;      //棧頂指針
}SqStack;         //結(jié)構(gòu)體重命名

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

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

3.2 棧的初始化操作

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

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

判斷棧空：

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

3.3 進(jìn)棧操作

分析：

判斷棧是否為空

棧頂指針 + 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. 共享?xiàng)?/strong>

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

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