C語言程式設計之線性結構兩種常見的應用之：棧
先看下面的一個例子：
//////////////////////////////////////////////////
//一個示例說明記憶體在棧和堆中的分配
#include
#include
void f（int k）
{
int t；
double *p = （double *）malloc（100）；
}
int main（void）
{
int i = 10；
int *q = （int *）malloc（10）；
}
在棧中分配的記憶體，凡是靜態分配的都是在棧中分配
在堆中分配的記憶體，凡是動態分配的都是在堆中分配
什麼是棧？一種可以實現“先進後出“的儲存結構
分類：
靜態棧：以陣列為基本核心
動態棧：以連結串列為基本核心
演算法：
出棧push
入棧（壓棧）pop
應用：
1、函式呼叫。
2、中斷。
3、表示式求值。
4、記憶體分配。
5、緩衝處理
//一個示例：
#include
#include
#include
typedef struct Node{
int data；
struct Node * pNext；
}NODE，* PNODE；
typedef struct Stack{
PNODE pTop；//永遠指向棧頂元素
PNODE pBottom；//永遠指向棧底的下一個沒有實際意義的元素，類似連結串列的頭節點
}STACK，* PSTACK；
void init（PSTACK pS）；//初始化
void push（PSTACK pS，int val）；
void traverse（PSTACK pS）；
bool pop（PSTACK pS，int * val）；
bool is_empty（PSTACK pS）；
void clear（PSTACK pS）；
int main（void）
{
STACK s；
int popVal；
init（&s）；//棧的初始化
push（&s，1）；
push（&s，3）；
push（&s，5）；
push（&s，7）；
traverse（&s）；
if（pop（&s，&popVal））
{
printf（“pop stack is success！the pop value is %d\n”，popVal）；
}
else
{
printf（“pop stack is failed！\n”）；
}
traverse（&s）；
if（pop（&s，&popVal））
{
printf（“pop stack is success！the pop value is %d\n”，popVal）；
}
else
{
printf（“pop stack is failed！\n”）；
}
traverse（&s）；
if（pop（&s，&popVal））
{
printf（“pop stack is success！the pop value is %d\n”，popVal）；
}
else
{
printf（“pop stack is failed！\n”）；
}
traverse（&s）；
if（pop（&s，&popVal））
{
printf（“pop stack is success！the pop value is %d\n”，popVal）；
}
else
{
printf（“pop stack is failed！\n”）；
}
traverse（&s）；
if（pop（&s，&popVal））
{
printf（“pop stack is success！the pop value is %d\n”，popVal）；
}
else
{
printf（“pop stack is failed！\n”）；
}
traverse（&s）；
push（&s，2）；
push（&s，4）；
push（&s，6）；
push（&s，8）；
traverse（&s）；
clear（&s）；
if（pop（&s，&popVal））
{
printf（“pop stack is success！the pop value is %d\n”，popVal）；
}
// traverse（&s）；
return 0；
}
void init（PSTACK pS）
{
PNODE pHead；
pHead = （PNODE）malloc（sizeof（NODE））；
if（NULL == pHead）
{
printf（“分配記憶體失敗！”）；
exit（-1）；
}
pS->pTop = pHead；
pS->pBottom = pHead；
pS->pTop->pNext = NULL；
}
/****************************************************************************************************************************
psuh()函式說明：假設已經初始化了一個棧pTop忽和pBottom都指向了一個頭節點pHead,pHead->pNext = NULL,
這時執行第一次壓棧push操作,line1建立了一個節點pNew，line2給節點賦值，line3將pTop指向pNew，
注意：此時pTop是指向頭節點pHead的。line4將pTop指向pNew。
經過上述4步，壓入了第一個棧節點。壓入第二個棧節點以此類推！
關鍵是line3和line4！！！
***************************************************************************************************************************/
void push（PSTACK pS，int val）
{
PNODE pNew = （PNODE）malloc（sizeof（NODE））；//line1
pNew->data = val；//line2
pNew->pNext = pS->pTop；//不能是pBottom，line3
pS->pTop = pNew；//line4
}
void traverse（PSTACK pS）
{
PNODE p = pS->pTop；
while（pS->pBottom ！= p）
{
printf（“%d ”，p->data）；
p = p->pNext；
}
printf（“\n”）；
}
bool is_empty（PSTACK pS）
{
if（pS->pBottom == pS->pTop）
return true；
else
return false；
}
bool pop（PSTACK pS，int * val）
{
if（is_empty（pS））
{
printf（“the stack is empty！\n”）；
return false；
}
PNODE p = pS->pTop；
* val = p->data；
pS->pTop = p->pNext；
free（p）；
p = NULL；
return true；
}
void clear（PSTACK pS）
{
if（is_empty（pS））
return；
else
{
PNODE p = pS->pTop；
PNODE q = NULL；
while（pS->pBottom ！= p）
{
q = p->pNext；
free（p）；
p = q；
}
pS->pTop = pS->pBottom；
}
}
~~~~~~~~~~~~~~~end~~~~~~~~~~~~~~~~~~~