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