一、概念

棧是一種先進(jìn)后出的數(shù)據(jù)結(jié)構(gòu)。FILO(firt in late out)
邏輯結(jié)構(gòu)：線性結(jié)構(gòu)

二、存儲(chǔ)結(jié)構(gòu)：

（一） 順序存儲(chǔ)

順序棧
基于一個(gè)數(shù)組配合一個(gè)棧頂"指針（數(shù)組下標(biāo)）–top"
順序棧的本質(zhì)就是對(duì)順序表操作的一種約束：只能在一端進(jìn)行插入和刪除。

操作：
創(chuàng)建
清空
銷毀
入棧、壓?！袛鄺M
出棧、彈棧——判斷?？?br /> 打印棧所有元素

（二）鏈?zhǔn)酱鎯?chǔ)

1. 結(jié)構(gòu)體定義

//鏈表節(jié)點(diǎn)結(jié)構(gòu)體----數(shù)據(jù)元素
typedef struct _Node{int data;struct _Node *next;
}node_t;//鏈?zhǔn)綏５慕Y(jié)構(gòu)體----數(shù)據(jù)對(duì)象
typedef struct _Stack{node_t *top;int count;//記錄棧中元素個(gè)數(shù)//.....其他屬性信息
}stack_t;

2.創(chuàng)建棧表

（1）函數(shù)定義

int create_stack(stack_t **my_stack);

1. 在內(nèi)存中申請(qǐng)一塊stack_t類型大小的空間存儲(chǔ)棧的內(nèi)容；
2. 初始化棧的成員的數(shù)據(jù)：將count置0，top置NULL

（2）注意點(diǎn)

1. 進(jìn)入函數(shù)就需要判斷傳入的參數(shù)是否為NULL，為空退出函數(shù)
2. 在申請(qǐng)完內(nèi)存空間后判斷，申請(qǐng)空間是否成功，失敗退出函數(shù)

（3）代碼實(shí)現(xiàn)

int create_stack(stack_t **my_stack){if(NULL==my_stack) //判斷傳入?yún)?shù)是否為空{return -1;}*my_stack=(stack_t *)malloc(sizeof(stack_t));if(NULL==*my_stack){return -1;}//初始化(*my_stack)->top=NULL;(*my_stack)->count=0;return 0;
}

3. 入棧

（1）函數(shù)定義

int push_stack(stack_t *my_stack, int data);

1. 在內(nèi)存中申請(qǐng)一塊node_t類型大小的數(shù)據(jù)空間
2. 進(jìn)行頭插
3. count自加一

（2）注意點(diǎn)

1. 需要檢查傳入?yún)?shù)是否為空，為空退出函數(shù)
2. top指向的元素即是第一個(gè)數(shù)據(jù)節(jié)點(diǎn)

（3）代碼實(shí)現(xiàn)

int push_stack(stack_t *my_stack, int data){if(NULL==my_stack){return -1;}//申請(qǐng)一個(gè)新數(shù)據(jù)節(jié)點(diǎn)node_t *node=(node_t *)malloc(sizeof(node_t));if(NULL==node){return -1;}node->next=my_stack->top;my_stack->top=node;node->data=data;my_stack->count++;return 0;
}

3. 出棧

（1）函數(shù)定義

int pop_stack(stack_t *my_stack, int *num);

1. 頭刪
2. count自減

（2）注意點(diǎn)

1. 需要檢查傳入指針參數(shù)和*num是否為空，為空退出函數(shù)
2. 檢查棧是否為空，為空退出函數(shù)

（3）代碼實(shí)現(xiàn)

//出棧
int pop_stack(stack_t *my_stack, int *num){if(NULL==my_stack||NULL==num){return -1;}if(is_empty(my_stack)){return -1;}//頭刪node_t *pdel=my_stack->top;*num=pdel->data;my_stack->top=pdel->next;free(pdel);pdel=NULL;my_stack->count--;return 0;
}

4. 判斷棧是否為空

（1）函數(shù)定義

int is_empty(stack_t *my_stack);

（2）注意點(diǎn)

1. 判斷傳入的指針參數(shù)是否為空

（3）代碼實(shí)現(xiàn)

int is_empty(stack_t *my_stack){if(NULL==my_stack){return -1;}return (my_stack->count)?0:1; 
}

5. 清空棧

（1）函數(shù)定義

int clean_stack(stack_t *my_stack);

1. 循環(huán)頭刪
2. count置0
3. 只要top的指向不為空，就一直循環(huán)

（2）注意點(diǎn)

1. 入?yún)⒑侠硇詸z查
2. count不要忘記置0

（3）代碼實(shí)現(xiàn)

int clean_stack(stack_t *my_stack){if(NULL==my_stack){return -1;}node_t *pdel=NULL;while(my_stack->top){pdel=my_stack->top;my_stack->top=pdel->next;free(pdel);}pdel=NULL;my_stack->count=0;return 0;
}

6. 銷毀棧

（1）函數(shù)定義

int destroy_stack(stack_t **my_stack);

（2）注意點(diǎn)

（3）代碼實(shí)現(xiàn)

int destroy_stack(stack_t **my_stack){if(NULL==my_stack||NULL==*my_stack){return -1;}//先清空再銷毀if(clean_stack(*my_stack)){return -1;}free(*my_stack);*my_stack=NULL;return 0;
}

7. 打印棧

（1）函數(shù)定義

int print_stack(stack_t *my_stack);

（2）注意點(diǎn)

1. 入?yún)⒑侠硇詸z查

（3）代碼實(shí)現(xiàn)

int print_stack(stack_t *my_stack){if(NULL==my_stack){return -1;}if(is_empty(my_stack)){printf("?？誠(chéng)n");return -1;}node_t *ptemp=my_stack->top;for(int i=0;i<my_stack->count;i++){printf("%d ",ptemp->data);ptemp=ptemp->next;}putchar(10);return 0;
}