數(shù)據(jù)結(jié)構(gòu)中的棧是什么
舉一個(gè)簡(jiǎn)單的例子：在往箱子里面放衣物的時(shí)候，放在最上面的衣物總是我們最后放上去的；而當(dāng)我們從箱子里取出衣物的時(shí)候，總是最先拿出上面的。這就是現(xiàn)實(shí)生活中的棧。
準(zhǔn)確的講，棧就是一種可以實(shí)現(xiàn)“先進(jìn)后出(或者叫后進(jìn)先出)”的存儲(chǔ)結(jié)構(gòu)。
學(xué)過數(shù)據(jù)結(jié)構(gòu)的人都知道：棧可以用兩種方式來實(shí)現(xiàn)，一種方法是用數(shù)組實(shí)現(xiàn)棧，這種棧成為靜態(tài)棧；另外一種方法是用鏈表實(shí)現(xiàn)棧，這種棧叫做動(dòng)態(tài)棧。
棧中通常存放著程序的局部變量等。棧通常有出棧和入棧操作。
棧的結(jié)構(gòu)
空棧的結(jié)構(gòu)：【其實(shí)就是棧頂和棧頂都指向一個(gè)無用的頭結(jié)點(diǎn)】
存有結(jié)點(diǎn)的棧結(jié)構(gòu)：【棧頂指針指向棧頂結(jié)點(diǎn)，棧底指針指向頭結(jié)點(diǎn)】
棧的實(shí)現(xiàn)
下面是用C實(shí)現(xiàn)的一個(gè)鏈棧結(jié)構(gòu)的源碼及詳細(xì)注釋：
#include
#include
#include
//定義結(jié)點(diǎn)結(jié)構(gòu)體
typedef struct Node
{
int data; //內(nèi)容
struct Node * pNext; //指向下一結(jié)點(diǎn)的指針
} NODE, * PNODE; //NODE等價(jià)于struct Node, PNODE等價(jià)于struct Node *
//定義棧的結(jié)構(gòu)體
typedef struct Stack
{
PNODE pTop; //棧頂結(jié)點(diǎn)
PNODE pBottom; //棧底結(jié)點(diǎn)
} STACK, * PSTACK; //STACK等價(jià)于struct Stack, PSTACK等價(jià)于struct Stack *
//函數(shù)聲明
void initStack(PSTACK pStack); //對(duì)棧進(jìn)行初始化的函數(shù)
void pushStack(PSTACK pStack, int val); //入棧的函數(shù)
bool popStack(PSTACK pStack, int * pVal);//出棧的函數(shù)，*pVal用來保存出棧的元素內(nèi)容
void traverseStack(PSTACK pStack); //遍歷棧的函數(shù)
bool isEmpty(PSTACK pStack); //判斷棧是否為空的函數(shù)
void clearStack(PSTACK pStack); //清空棧的函數(shù)
//棧調(diào)用示例
int main(void)
{
STACK stack; //定義一個(gè)棧變量,STACK等價(jià)于struct Stack
int val; //用來保存出棧的內(nèi)容
initStack(&stack); //調(diào)用棧的初始化函數(shù)
pushStack(&stack, 10); //調(diào)用入棧的函數(shù)
pushStack(&stack, 20);
pushStack(&stack, 30);
pushStack(&stack, 50);
traverseStack(&stack); //調(diào)用遍歷棧的函數(shù)
//調(diào)用出棧的函數(shù)
if(popStack(&stack, &val))
printf("出棧成功，出棧的元素值為：%d\n", val);
else
printf(" 出棧失敗!");
//調(diào)用清空棧的函數(shù)
clearStack(&stack);
traverseStack(&stack); //調(diào)用遍歷棧的函數(shù)
system("pause");
return 0;
}
//操作函數(shù)的實(shí)現(xiàn)
void initStack(PSTACK pStack)
{
//創(chuàng)建一個(gè)空結(jié)點(diǎn)，讓pTop指向它
pStack->pTop = (PN ODE)malloc(sizeof(NODE));
if(NULL != pStack->pTop)
{
//將pBottom也指向空節(jié)點(diǎn)
pStack->pBottom = pStack->pTop;
//清空空結(jié)點(diǎn)的指針域
pStack->pTop->pNext = NULL;
}
else //如果內(nèi)存分配失敗
{
printf("內(nèi)存分配失敗!程序退出!\n");
exit(-1);
}
return;
}
void pushStack(PSTACK pStack, int val)
{
//動(dòng)態(tài)創(chuàng)建一個(gè)新結(jié)點(diǎn)
PNODE pNew = (PNODE)malloc(sizeof(NODE));
//設(shè)置新結(jié)點(diǎn)的數(shù)據(jù)域的值
pNew->data = val;
//將新結(jié)點(diǎn)的指針域指向之前建的空節(jié)點(diǎn)
pNew->pNext = pStack->pTop; //pStack->pTop不能換成pStack->pBottom
//pTop指向新的結(jié)點(diǎn)
pStack->pTop = pNew;
return;
}
bool popStack(PSTACK pStack, int * pVal)
{
if(isEmpty(pStack))
{
return false;
}
else
{
//先保存棧頂元素的地址，然后將pTop指向下一元素,最后釋放之前棧頂元素的內(nèi)存
PNODE rNode = pStack->pTop;
*pVal = rNode->data;
pStack->pTop = rNode->pNext;
free(rNode);
rNode = NULL;
return true;
}
}
void traverseStack(PSTACK pStack)
{
//將棧頂賦給一個(gè)臨時(shí)結(jié)點(diǎn),因?yàn)樵诒闅v棧的時(shí)候不能銷毀棧
PNODE pNode = pStack->pTop;
//循環(huán)遍歷棧,直到棧底
while(pStack->pBottom != pNode )
{
printf("%d ", pNode->data);
pNode = pNode->pNext;
}
printf("\n");
return;
}
bool isEmpty(PSTACK pStack)
{
if(pStack->pTop == pStack->pBottom)
return true;
else
return false;
}
void clearStack(PSTACK pStack)
{ //棧為空，則退出該函數(shù)
if(isEmpty(pStack))
{
return;
}
else
{
//兩個(gè)結(jié)點(diǎn)指針變量用來釋放棧中元素的內(nèi)存
PNODE p = pStack->pTop;
PNODE q = NULL;
//循環(huán)釋放內(nèi)存
while(p != pStack->pBottom)
{
q = p->pNext;
free(p);
p = q;
}
//將棧頂和棧底指向同一個(gè)指針域?yàn)榭盏慕Y(jié)點(diǎn)
pStack->pTop = pStack->pBottom;
return;
}
}
棧的典型應(yīng)用
生產(chǎn)消費(fèi)模型常用棧來實(shí)現(xiàn)。生產(chǎn)者生產(chǎn)的東西都放入棧中，然后消費(fèi)者從棧中依次取出東西，當(dāng)棧頂和棧底指向都指向首結(jié)點(diǎn)時(shí)，生產(chǎn)的東西就被消耗光了。