文章目录

栈的基本概念

栈的实现

顺序栈

共享栈

链栈

栈的基本概念

栈的定义

栈（Stack）是只允许在一端进行插入或删除操作的线性表

 相关术语

• 栈顶（Top）线性表允许进行插入或删除的那一端称之为栈顶
• 栈底（Bottom）是固定的，不允许插入或者删除的另一端
• 空栈（Null Stack）不含任何数据元素的空表

重要特性

• 后进先出（Last In First Out）：即先入栈的元素后出栈
• 如入栈顺序为a1，a2，a3，a4 ，则出栈顺序为a4，a3，a2，a1

栈的实现

顺序栈

定义

        采用顺序存储的栈称之为顺序栈，它利用一组地址连续的存储单元存放自栈底至栈顶的数据元素，同时附设一个指针top，指向当前栈顶的位置。

基本操作

顺序存储类型

//栈的存储类型定义
typedef struct Stack{int data[MaxSize];//存放栈中元素int top;//指向当前栈顶元素 
}SqStack;

 初始化

//初始化
void InitStack(SqStack &S){S.top=-1;//初始化栈顶指针，指向当前的栈顶位置 
} 

判空

//判空
bool IsEmpty(SqStack &S){if(S.top==-1)return true;else return false;
} 

判满

//判满
bool IsFull(SqStack &S){if(S.top==MaxSize-1)return true;else return false;
} 

入栈（进栈）

//入栈（进栈）
bool Push(SqStack &S,int x){//栈满则报错，无法入栈 if(S.top==MaxSize-1)return false;S.data[++S.top]=x;//因为栈顶指针初始化为-1指向当前位置，故增加元素时应先令top加一再入栈 return true;
}

出栈

//出栈
bool Pop(SqStack &S,int &x){//栈空则报错，无法出栈 if(S.top==-1)return false;x=S.data[S.top--];//先出栈，指针再减一return true; 
} 

读取栈顶元素

//读取栈顶元素
bool GetTop(SqStack &S,int &x){//栈空则报错，无法读取 if(S.top==-1)return false;x=S.data[S.top];return true;
} 

测试

#include"stdio.h"
#include"stdlib.h"
#define MaxSize 10
//栈的存储类型定义
typedef struct Stack{int data[MaxSize];//存放栈中元素int top;//指向当前栈顶元素 
}SqStack;//初始化
void InitStack(SqStack &S){S.top=-1;//初始化栈顶指针，指向当前的栈顶位置 
} 
//判空
bool IsEmpty(SqStack &S){if(S.top==-1)return true;else return false;
} 
//判满
bool IsFull(SqStack &S){if(S.top==MaxSize-1)return true;else return false;
} 
//求栈长
int StackLength(SqStack &S){return S.top+1;
} 
//入栈（进栈）
bool Push(SqStack &S,int x){//栈满则报错，无法入栈 if(S.top==MaxSize-1)return false;S.data[++S.top]=x;//因为栈顶指针初始化为-1指向当前位置，故增加元素时应先令top加一再入栈 return true;
} 
//出栈
bool Pop(SqStack &S,int &x){//栈空则报错，无法出栈 if(S.top==-1)return false;x=S.data[S.top--];//先出栈，指针再减一return true; 
} 
//读取栈顶元素
bool GetTop(SqStack &S,int &x){//栈空则报错，无法读取 if(S.top==-1)return false;x=S.data[S.top];return true;
} 
//打印栈中所有元素
void PrintStack(SqStack &S){printf("\\n当前栈中元素如下：\\n");for(int i=S.top;i>=0;i--){printf("%d ",S.data[i]);}printf("\\n");
} 
//测试 
int main(){SqStack S;//1.初始化栈InitStack(S);//2.入栈printf("请输入10个整数进行入栈：\\n");int n;for(int i=0;i<10;i++){scanf("%d",&n);Push(S,n);} PrintStack(S);//3.出栈 printf("请输入你要出栈的次数：\\n");int x,times;//x带回被删除的栈顶元素 ，times为出栈次数 scanf("%d",&times);if(times>StackLength(S)){printf("出栈次数不合法！");}else{printf("依次出栈的元素如下：\\n");for(int i=0;i<times;i++){Pop(S,x);printf("%d ",x);}} PrintStack(S);return 0;
} /*
测试数据：
1 2 3 4 5 6 7 8 9 10 
*/

共享栈

概念

        利用栈底位置不变的特性，可以让两个顺序栈共享一个一维数组的空间，将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸

性质

以上图所示的共享栈为例：

• 当top1= -1，1号栈为空；当top2=MaxSize=10时，2号栈为空
• 当 top2-top1=1 时，即两个栈顶指针相邻时，则栈满
• 当1号栈入栈时，top1先加1再赋值；当2号栈入栈时，top2先减1再赋值
• 出栈时与入栈时相反

代码实现

存储类型

//共享栈的存储结构类型
typedef struct CommonStack{int data[MaxSize];int top1;int top2;
}ComStack; 

初始化

//初始化共享栈
void InitComStack(ComStack &S){S.top1=-1;S.top2=MaxSize;
} 

入栈

//共享栈的入栈
bool Push(ComStack &S,int StackType,int x){//判满 if(S.top2-S.top1==1)return false;//说明是1号栈入栈 if(StackType==1){S.data[++S.top1]=x;}else if(StackType==2){//说明是2号栈入栈 S.data[--S.top2]=x;}return true;
} 

出栈

// 共享栈的出栈
bool Pop(ComStack &S,int StackType,int &y){//判空if(S.top1==-1&&S.top2==MaxSize)return false;//说明是1号栈出栈 if(StackType==1){y=S.data[S.top1--];}else if(StackType==2){//说明是2号栈出栈 y=S.data[S.top2++];}return true;
} 

测试

#include"stdio.h"
#include"stdlib.h"
#define MaxSize 10
//共享栈的存储结构类型
typedef struct CommonStack{int data[MaxSize];int top1;int top2;
}ComStack; //初始化共享栈
void InitComStack(ComStack &S){S.top1=-1;S.top2=MaxSize;
} 
//共享栈的入栈
bool Push(ComStack &S,int StackType,int x){//判满 if(S.top2-S.top1==1)return false;//说明是1号栈入栈 if(StackType==1){S.data[++S.top1]=x;}else if(StackType==2){//说明是2号栈入栈 S.data[--S.top2]=x;}return true;
} 
// 共享栈的出栈
bool Pop(ComStack &S,int StackType,int &y){//判空if(S.top1==-1&&S.top2==MaxSize)return false;//说明是1号栈出栈 if(StackType==1){y=S.data[S.top1--];}else if(StackType==2){//说明是2号栈出栈 y=S.data[S.top2++];}return true;
} 
int main(){ComStack S;//初始化共享栈InitComStack(S);//入栈int a1,a2;printf("请输入5个整数进入1号栈：\\n");for(int i=0;i<5;i++){scanf("%d",&a1);Push(S,1,a1);} printf("请再输入5个整数进入2号栈：\\n");for(int i=0;i<5;i++){scanf("%d",&a2);Push(S,2,a2);} printf("共享栈内元素如下：\\n");for(int i=0;i<10;i++){printf("%d ",S.data[i]);} printf("\\n");int y,type;printf("请输入你要执行出栈操作的栈号：");scanf("%d",&type);Pop(S,type,y);printf("已成功将%d号栈的栈顶元素：%d 弹出栈！\\n",type,y);printf("此时共享栈内的元素如下：\\n");//打印1号栈 for(int i=0;i<=S.top1;i++){printf("%d ",S.data[i]);}//打印2号栈 for(int j=S.top2;j<10;j++){printf("%d ",S.data[j]);}return 0;
} 

链栈

        顾名思义，采用链式存储的栈称之为链栈。其优点是便于多个栈共享存储空间和提高效率，且不存在栈满上溢的情况，通常采用单链表实现，并规定所有的操作都只能在单链表的表头进行。

 由于链栈是用单链表实现，且规定只在表头进行操作，故链栈的操作与单链表类似，入栈和出栈都在单链表的表头进行，注意带头结点与不带头结点的区别，操作上会有所不同，具体可以参考我之前写的文章。

单链表的基本知识与基本操作https://blog.csdn.net/qq_52487066/article/details/129604063?spm=1001.2014.3001.5501

 END.