面試官問我什么是「棧」，我隨手畫了10張圖來解釋
ID：技術(shù)讓夢想更偉大
作者:李肖遙
棧的概念
棧（stack）是限定僅在表的一端進行操作的數(shù)據(jù)結(jié)構(gòu)，且棧是一種先進后出的數(shù)據(jù)結(jié)構(gòu)，允許操作的一端稱為棧頂，不允許操作的稱為棧底，如下圖所示：
之前我們講到了鏈表，我們只能夠?qū)ζ滏湵淼谋砦步Y(jié)點進行操作，并且只能進行插入一個新的結(jié)點與刪除最末尾的這個結(jié)點兩個操作，而這樣強限制性的‘鏈表’，就是我們所說的棧。
就像是一個死胡同一樣，只有一個出口，如圖所示，有個概念：
棧的結(jié)點設(shè)計
棧分為數(shù)組棧和鏈表棧，其區(qū)別如下：
數(shù)組棧使用數(shù)組進行功能的模擬，實現(xiàn)較為快速和便利；鏈表棧使用鏈表的思路去設(shè)計，實現(xiàn)相比較說較為麻煩，但是其穩(wěn)定，且不易出錯；
在鏈表棧中又分為靜態(tài)鏈表棧和動態(tài)鏈表棧，其區(qū)別如下：
靜態(tài)鏈表棧給定棧的空間大小，不允許超過存儲超過給定數(shù)據(jù)大小的元素；動態(tài)棧使用的是自動創(chuàng)建空間的方法進行創(chuàng)建，只要符合機器的硬件要求以及編譯器的控制，其理論上是極大的。
數(shù)組棧
其實際就是用一段連續(xù)的存儲空間來存儲棧中的數(shù)據(jù)元素，有以下特點：
元素所占的存儲空間必須連續(xù)，這里的連續(xù)是指的邏輯連續(xù)，而不是物理連續(xù)。
元素在存儲空間的位置是按邏輯順序存放的
我們來舉例說明，鑒于C語言數(shù)組下標都是0開始，并且棧的使用需要的空間大小難以估計，所以初始化空棧的時候，不應(yīng)該設(shè)定棧的最大容量。
我們先為棧設(shè)定一個基本容量，在應(yīng)用過STACK_程當中，當棧的空間不夠用時，再逐漸擴大。
設(shè)定2個常量，STACK_INIT_SIZE(存儲空間初始化分配量)和STACK_INCREMENT(存儲空間分配增量),宏定義如下
#define STACK_INIT_SIZE 1000 //數(shù)值可以根據(jù)實際情況確定
#define STACK_INCREMENT 10 //數(shù)值可以根據(jù)實際情況確定
棧的定義如下
typedef struct
{
void *base;
void *top;
int stackSize;
} SqSTACK;
base 表示棧底指針
top 表示棧頂指針
stackSize 表示棧當前可以使用的最大容量
若base的值是NULL，表示棧結(jié)構(gòu)不存在;top初始值指向棧底，即top = base;
每當插入新的元素時，指針top就增1，反之刪除就減1，非空棧中的棧頂指針始終在棧頂元素的下一個指針上面。
數(shù)據(jù)元素和棧頂指針的關(guān)系如下圖所示：
鏈表棧
我們以鏈表棧的動態(tài)鏈表棧為例子，進行棧的設(shè)計。
首先是棧的結(jié)點，設(shè)計出兩個結(jié)構(gòu)體，一個結(jié)構(gòu)體Node表示結(jié)點，其中包含有一個data域和next指針，如圖所示：
其中data表示數(shù)據(jù)，next指針表示下一個的指針，其指向下一個結(jié)點，通過next指針將各個結(jié)點鏈接。
接下來是我們設(shè)計的重點，為這個進行限制性的設(shè)計，我們需要額外添加一個結(jié)構(gòu)體，其包括了一個永遠指向棧頭的指針top和一個計數(shù)器count記錄元素個數(shù)。
其主要功效就是設(shè)定允許操作元素的指針以及確定棧何時為空，如圖所示：
這里我采用的是top和count組合的方法。其代碼可以表示為：
//棧的結(jié)點設(shè)計
//單個結(jié)點設(shè)計，數(shù)據(jù)和下一個指針
typedef struct node
{
int data;
struct node *next;
} Node;
利用上面的結(jié)點創(chuàng)建棧，分為指向頭結(jié)點的top指針和計數(shù)用的count
typedef struct stack
{
Node *top;
int count;
} Link_Stack;
棧的基本操作—入棧（壓棧）
入棧的基本順序可以用以下圖所示：
入棧(push)操作時，我們只需要找到top所指向的空間，創(chuàng)建一個新的結(jié)點，將新的結(jié)點的next指針指向top指針指向的空間，再將top指針轉(zhuǎn)移，并且指向新的結(jié)點，這就是是入棧操作。
其代碼可以表示為：
//入棧 push
Link_Stack *Push_stack(Link_Stack *p, int elem)
{
if (p == NULL)
return NULL;
Node *temp;
temp=(Node*)malloc(sizeof(Node));
//temp = new Node;
temp->data = elem;
temp->next = p->top;
p->top = temp;
p->count++;
return p;
}
棧的基本操作—出棧
出棧（pop）操作，是在棧不為空的情況下，重復(fù)說一次，一定要進行判空操作，將棧頂?shù)脑貏h除，同時top指針，next向下進行移動即可的操作。
其代碼可以表示為：
//出棧 pop
Link_Stack *Pop_stack(Link_Stack *p)
{
Node *temp;
temp = p->top;
if (p->top == NULL)
{
printf("錯誤：棧為空");
return p;
}
else
{
p->top = p->top->next;
free(temp);
//delete temp;
p->count--;
return p;
}
}
棧的基本操作—遍歷
這個就很常見了，也是我們調(diào)試必須的手段。
棧的遍歷相對而言比較復(fù)雜，由于棧的特殊性質(zhì)，其只允許在一端進行操作，所以遍歷操作操作永遠都是逆序的。
簡單一點描述，其過程為，在棧不為空的情況下，一次從棧頂元素向下訪問，直到指針指向空（即到棧尾）為結(jié)束。
其代碼可以表示為：
//遍歷棧：輸出棧中所有元素
int show_stack(Link_Stack *p)
{
Node *temp;
temp = p->top;
if (p->top == NULL)
{
printf("");
printf("錯誤：棧為空");
return 0;
}
while (temp != NULL)
{
printf("%d\t", temp->data);
temp = temp->next;
}
printf("\n");
return 0;
}
棧數(shù)組與棧鏈表的代碼實現(xiàn)
最后呢，我們使用代碼來幫助我們了解一下：
棧數(shù)組
數(shù)組棧是一種更為快速的模擬實現(xiàn)棧的方法，這里我們不多說。
模擬，就是不采用真實的鏈表設(shè)計，轉(zhuǎn)而采用數(shù)組的方式進行模擬操作。
也就是說這是一種仿真類型的操作，其可以快速的幫助我們構(gòu)建代碼，分析過程，相應(yīng)的實現(xiàn)起來也更加的便捷。
其代碼如下:
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define maxn 10000
//結(jié)點設(shè)計
typedef struct stack{
int data[maxn];
int top;
}stack;
//創(chuàng)建
stack *init(){
stack *s=(stack *)malloc(sizeof(stack));
if(s==NULL){
printf("分配內(nèi)存空間失敗");
exit(0);
}
memset(s->data,0,sizeof(s->data));
//memset操作來自于庫文件string.h，其表示將整個空間進行初始化
//不理解可以查閱百度百科https://baike.baidu.com/item/memset/4747579?fr=aladdin
s->top=0; //棧的top和bottom均為0（表示為空）
return s;
}
//入棧push
void push(stack *s,int data){
s->data[s->top]=data;
s->top++;
}
//出棧pop
void pop(stack *s){
if(s->top!=0){
s->data[s->top]=0; //讓其回歸0模擬表示未初始化即可
s->top--;
}
}
//模擬打印棧中元素
void print_stack(stack *s){
for(int n=s->top-1;n>=0;n--){
printf("%d\t",s->data[n]);
}
printf("\n"); //習(xí)慣性換行
}
int main(){
stack *s=init();
int input[5]={11,22,33,44,55}; //模擬五個輸入數(shù)據(jù)
for(int i=0;i<5;i++){
push(s,input[i]);
}
print_stack(s);
/////////////
pop(s);
print_stack(s);
return 0;
}
其編譯結(jié)果如下：
棧鏈表
#include <stdio.h>
#include <stdlib.h>
//棧的結(jié)點設(shè)計
//單個結(jié)點設(shè)計，數(shù)據(jù)和下一個指針
typedef struct node
{
int data;
struct node *next;
} Node;
//利用上面的結(jié)點創(chuàng)建棧，分為指向頭結(jié)點的top指針和計數(shù)用的count
typedef struct stack
{
Node *top;
int count;
} Link_Stack;
//創(chuàng)建棧
Link_Stack *Creat_stack()
{
Link_Stack *p;
//p = new Link_Stack;
p=(Link_Stack*)malloc(sizeof(Link_Stack));
if(p==NULL){
printf("創(chuàng)建失敗，即將退出程序");
exit(0);
}
else
{printf("創(chuàng)建成功\n");
}
p->count = 0;
p->top = NULL;
return p;
}
//入棧 push
Link_Stack *Push_stack(Link_Stack *p, int elem)
{
if (p == NULL)
return NULL;
Node *temp;
temp=(Node*)malloc(sizeof(Node));
//temp = new Node;
temp->data = elem;
temp->next = p->top;
p->top = temp;
p->count++;
return p;
}
//出棧 pop
Link_Stack *Pop_stack(Link_Stack *p)
{
Node *temp;
temp = p->top;
if (p->top == NULL)
{
printf("錯誤：棧為空");
return p;
}
else
{
printf("\npop success");
p->top = p->top->next;
free(temp);
//delete temp;
p->count--;
return p;
}
}
//遍歷棧：輸出棧中所有元素
int show_stack(Link_Stack *p)
{
Node *temp;
temp = p->top;
if (p->top == NULL)
{
printf("");
printf("錯誤：棧為空");
return 0;
}
while (temp != NULL)
{
printf("%d\t", temp->data);
temp = temp->next;
}
printf("\n");
return 0;
}
int main()
{ //用主函數(shù)測試一下功能
int i;
Link_Stack *p;
p = Creat_stack();
int n = 5;
int input[6] = {10,20,30,40,50,60};
/////////////以依次入棧的方式創(chuàng)建整個棧//////////////
for(i=0;i<n;i++){
Push_stack(p, input[i]);
}
show_stack(p);
////////////////////出棧///////////////////////
Pop_stack(p);
show_stack(p);
return 0;
}
編譯結(jié)果如下：
關(guān)于棧的總結(jié)
棧-它是一種運算受限的線性表，在數(shù)制轉(zhuǎn)換，括號匹配的檢驗，表達式求值等方面都可以使用，并且較為簡便的解決問題。
今天?；A(chǔ)就講到這里，下一期，我們再見！
推薦閱讀：嵌入式編程專輯 Linux 學(xué)習(xí)專輯 C/C++編程專輯 關(guān)注微信公眾號『技術(shù)讓夢想更偉大』。 長按前往圖中包含的公眾號關(guān)注