棧和隊(duì)列其實(shí)是一種特殊的線性表，他們是限定只能在表的一端或兩端進(jìn)行插入夕春、刪除元素，所以狞甚，這些被統(tǒng)稱為限定性數(shù)據(jù)結(jié)構(gòu)
棧
定義：
検诎裕可以說是線性表的具體形式巡验，僅允許在表尾進(jìn)行插入刪除操作，我們把允許進(jìn)行插入刪除操作的一端碘耳，稱為棧頂显设，另一端稱為棧底。
對于棧來說辛辨，最主要的操作就是插入和刪除操作捕捂，插入操作稱為，入椨溲郑或進(jìn)棧绞蹦，刪除操作稱為，出棸竦或退棧幽七。由于只能在棧頂進(jìn)行插入和刪除操作，所以棧有一個(gè)特點(diǎn)就是棧里的元素一般都是是先進(jìn)后出（后進(jìn)先出）溅呢，就好像手槍的彈夾澡屡，最先壓進(jìn)去的子彈，最后才打出來咐旧。
棧的基本操作：
- InitStack(S): 構(gòu)造一個(gè)空棧
- ClearStack(S): 將棧S清為一個(gè)空棧
- EmptyStack(S): 判斷棧S是否為空
- LengthStack(S): 求棧S的長度（棧中元素的個(gè)數(shù)）
- GetTop(S,e): 獲取棧頂元素
- Push(S,e): 入棧操作
- Pop(S,e): 出棧操作
因?yàn)闂５谋举|(zhì)是一個(gè)線性表驶鹉，所以棧也分為順序棧和鏈棧
棧的順序存儲(chǔ)結(jié)構(gòu)的類型定義
#define MAXSIZE 20
typedef int ElemType;
typedef struct
{
ElemType data[MAXSIZE]; //用數(shù)組來模擬順序棧,下標(biāo)從零開始
int top; //棧頂?shù)闹羔槪簿褪菞ｍ數(shù)奈恢孟聵?biāo)
}SeqStack;
棧的順序存儲(chǔ)結(jié)構(gòu)的具體操作
#define OK 1
#define ERROR 0
typedef int Status;
Status InitStack(SeqStack *S)
{
S->top = -1; //因?yàn)閿?shù)組下標(biāo)從零開始铣墨，所以-1為空
return OK;
}
Status ClearStack(SeqStack *S)
{
S->top = -1;
return OK;
}
int EmptyStack(SeqStack S)
{
if(S.top==-1)
return 1;
else
return 0;
}
int LengthStack(SeqStack S)
{
return S.top+1;
}
Status GetTop(SeqStack S,ElemType *e)
{
if(EmptyStack(S)) //棧為空
return ERROR;
*e = S.data[S.top];
return OK;
}
Status Push(SeqStack *S,ElemType e)
{
if(S->top == MAXSIZE-1) //棧滿了
return ERROR;
else
{
S->top++;
S->data[S->top] = e;
}
return OK;
}
Status Pop(SeqStack *S,ElemType *e)
{
if(ElemType(S)) //棧為空
return ERROR;
*e = S->data[S->top];
S->top--;
return OK;
}
鏈棧
鏈棧其實(shí)就是利用單鏈表作為棧的存儲(chǔ)結(jié)構(gòu)室埋，單鏈表的第一個(gè)結(jié)點(diǎn)為棧頂，最后一個(gè)結(jié)點(diǎn)為棧底。鏈椧ο可以有頭結(jié)點(diǎn)也可以沒有孕蝉，不帶頭結(jié)點(diǎn)，棧頂指針就指向棧頂結(jié)點(diǎn)腌逢，帶頭結(jié)點(diǎn)就指向頭結(jié)點(diǎn)降淮。
棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)描述：
typedef struct node
{
ElemType data; //數(shù)據(jù)域
struct node *next; //指針域
}StackNode,*LinkStack;
基礎(chǔ)操作
//這里只描述棧的三個(gè)重要操作，其他操作可與單鏈表進(jìn)行類比
Status GetTop(LinkStack top,ElemType *e)
{
if(!top->next) //棧為空
return ERROR;
*e = top->next->data; //有頭結(jié)點(diǎn)的棧
return OK;
}
Status Push(LinkStack top,e)
{
StackNode *p;
p = (StackNode*)malloc(sizeof(StackNode)); //為新結(jié)點(diǎn)開辟存儲(chǔ)空間
s->data = e; //數(shù)據(jù)域賦值
s->next = top->next; //將s插入到棧頂
top->next = s;
return OK;
}
Status Pop(LinkStack top,*e)
{
if(!top->next) //空棧
return ERROR;
StackNode *p;
*e = top->next->data; //用e來返回棧頂元素
p = top->next;
top->next = p->next; //刪除棧頂結(jié)點(diǎn)并更新棧頂
free(p); //釋放空間
return OK;
}
