寫程序的時候，我們經常會說基本類型變量存在棧內存，引用類型的變量（對象，數組）存在堆內存。現在我們來看看棧這種數據結構是怎么實現的。
## 定義
一種可以實現“先進后出” 的存儲結構
棧類似于往箱子放衣服，先放的最后拿
## 棧的分類：
靜態棧：以數組方式實現，刪除時刪除下標最大的,插入時從最大下標+1插入
動態棧：以鏈表方式實現，刪除和插入都是從頭部
## 算法：出棧（POP），入棧（PUSH）
## 應用：
1.函數調用 :在函數f中調用另一個g函數，在g函數中調用k函數
執行到要調用g函數位置，先把g函數執行后下一句的地址以及變量壓棧，執行g函數，執行到調用k函數的位置，再把k函數執行后的下一句壓棧，然后執行k函數，執行后取出棧頂元素，賦給CPU，執行g函數中調用k函數后的下一句。
2.中斷
3.表達式求值：3*2+5/6-4兩個棧實現，一個放運算符，一個放數據
4.內存分配：把函數形參壓入棧中
5.緩沖處理
6.走迷宮
## C語言實現：
下面是C語言實現動態棧的代碼，為了方便在棧底部建立一個頭結點，不存有效數據。先看圖：
~~~
#include<stdio.h>
#include<malloc.h>
#include<stdbool.h>
//棧有一個不存放有效數據的頭節點，Pbotom始終指向頭結點。
/**
**定義節點的結構體
*/
typedef struct Node{
int data;//數據域
struct Node * PNext;//指針域
} Node,*PNext;
/**
**定義棧的結構體
*/
typedef struct Stack {
PNext top;
PNext bottom;
}Stack,* PStack;
/**
**初始化棧
*/
void init(PStack PStack )
{
//建立一個不存任何有限元素的頭結點，作為棧底
PStack->bottom=malloc(sizeof(Node));
PStack->top=PStack->bottom;
PStack->top->PNext=NULL;
}
/**
*遍歷棧
**/
void traverse(PStack Ps )
{
if(Ps->bottom==Ps->top)
{
printf("棧為空\n");
return ;
}
PNext pt=Ps->top;
while(pt!=Ps->bottom)//不能把pt換成ps->top這樣就修改了鏈表。尷尬。。
{
printf("%d ",pt->data);
pt=pt ->PNext;
}
printf("\n");
return ;
}
/**
**入棧
*/
void push(PStack Pstack,int val)
{
PNext Pnew=malloc(sizeof(Node));//生成一個新節點
Pnew->data=val;
Pnew->PNext=Pstack->top;
Pstack->top=Pnew;
}
/**
**出棧
*/
void pop(PStack ps )
{
if(ps->top==ps->bottom)
{
printf("棧為空，無法完成出棧操作\n");
return;
}
PNext temp=ps->top;//引入輔助變量，用于釋放內存
ps->top=ps->top->PNext;
free(temp);
temp=NULL;
}
/**
**清空棧
*/
void clear(PStack ps)
{
while(ps->top!=ps->bottom)
{
PNext temp=ps->top;
ps->top=ps->top->PNext;
free(temp);
}
}
int main()
{
Stack stack;
init(&stack);
push(&stack,6);
push(&stack,7);
push(&stack,8);
traverse(&stack);
pop(&stack);
traverse(&stack);
clear(&stack);
traverse(&stack);
push(&stack,7);
traverse(&stack);
return 0;
}
~~~
