栈数据结构:定义，基本操作与应用
目录
一、栈的定义
栈（Stack）是一种特殊的线性数据结构，其插入和删除操作都只允许在表的一端进行。这一端被称为栈顶（top），另一端则被称为栈底（bottom）。栈遵循后进先出（Last In First Out，LIFO）的规则，即最后存入的元素将被最先取出。
栈示意图：
二、栈的顺序存储结构
1.栈的顺序存储及其基本操作实现
栈的顺序存储结构是一种使用数组来实现栈数据结构的方式。在顺序存储中，栈的元素被存储在连续的内存位置上，通常使用一个一维数组来实现
假设栈的元素个数不超过最大正整数MaxSize，所有元素具有同一数据类型ElemType,可以用下面的方式声明栈的类型 SqStack.
代码：
typedef int ElemType;
#define Maxsize 10
typedef struct // 栈的顺序存储结构 及基本运算的实现
{
ElemType data[Maxsize];
int top;
}SqStack;（1）初始化栈
创建一个空栈，由s指向它。并为栈顶指针设置为-1.
代码：
// 1)初始化栈
void InitStack(SqStack*& s)
{
s = (SqStack*)malloc(sizeof(SqStack)); //分配一个顺序栈空间，首地址存放在s当中
s->top = -1; //栈顶指针置为 -1
}（2）入栈
元素加入栈顶的过程称为入栈。如果当前栈未满，新元素将被添加到栈顶位置。否则，将产生栈满（Stack Overflow）的错误。
代码：
// 4）入栈
bool Push(SqStack*& s,ElemType e)
{
//判断栈是否满了
if (s->top == Maxsize - 1)
{
return false;
}
s->top++; //栈顶指针加1
s->data[s->top] = e;//插入元素e
return true;
}（3）出栈
元素从栈顶移除的过程称为出栈。如果栈非空，栈顶元素将被移除并返回。否则，将产生栈空（Stack Underflow）的错误。
代码：
// 5）出栈
bool Pop(SqStack*& s, ElemType &e)
{
if (s->top == -1)//栈为空的情况（栈下溢出），返回
return false;
e = s->data[s->top];//取出栈顶元素
s->top--;//栈顶指针减一
return true;
}（4）读取栈顶元素
查看当前栈顶的元素，但不将其从栈中移除。
代码：
// 6）取栈顶元素
bool GetTop(SqStack*& s, ElemType& e)
{
if (s->top == -1)//栈为空的情况（栈下溢出），返回
return false;
e = s->data[s->top];//取出栈顶元素
return true;
}（5）检查栈是否为空
判断栈中是否还有元素，当栈顶指针值为-1时，栈为空，如果栈中没有任何元素，则返回真（True），否则返回假（False）。
// 3)判断栈是否为空
bool StackEmpty(SqStack* s)
{
return(s->top == -1);
}（6）销毁栈
该运算释放顺序栈s占用的存储空间。
代码：
// 2)销毁栈
void DestroyStack(SqStack*& s)
{
free(s);
}2.共享栈的操作及其基本运算实现
2.1共享栈的定义
顺序栈采用一个数组存放栈中的元素。如果需要用到两个类型相同的栈，这时若为它们各自开辟一个数组空间,极有可能出现这样的情况：第一个栈已满,再进栈就溢出了，而另一个栈还有很多空闲的存储空间。解决这个问题的方法是
将两个栈合起来，如图所示，用一个数组来实现这两个栈，这称为共享栈(share stack）
共享栈的示意图：
2.2共享栈的基本运算实现
在设计共享栈时，由于一个数组（大小为MaxSize）有两个端点，两个栈有两个栈底，让一个栈的栈底为数组的始端，即下标为0处，另一个栈的栈底为数组的末端，即下标为MaxSize-1处，这样在两个栈中进栈元素时栈顶向中间伸展。
代码：
// 共享栈
typedef struct
{
ElemType data[Maxsize];
int top1, top2;
}DStack;在实现共享栈的基本运算算法时需要增加一个形参i=1表示对栈1进行操作，i=2表示对栈2进行操作。
（1）入栈
代码：
// 3) 进栈 stackNumber=1 表示对栈1进行操作，stackNumber=2 表示对栈2进行操作
bool DStackPush(DStack*& s, ElemType e, int stackNumber)
{
//判断栈满 条件 top1 == top2-1
if (s->top1 == s->top2 - 1) return false;
if (stackNumber == 1)//栈1有元素进栈
{
s->data[++s->top1] = e;//若栈1则先top1+1后给数组元素赋值
}
else if (stackNumber == 2)//栈2有元素进栈
{
s->data[--s->top2] = e;//若栈2则先top1-1后给数组元素赋值
}
return true;
}
（2）出栈
代码：
// 4) 出栈 判断栈空的条件 栈一空top1 == -1 ， 栈二空 top2 == Maxsize
bool DStackPop(DStack*& s, ElemType& e, int stackNumber)
{
if (stackNumber == 1)
{
if (s->top1 == -1) //判断栈是否为空
return false;
else
{
e = s->data[s->top1--]; //将栈1的栈顶元素出栈，随后栈顶指针减1
}
}
else if (stackNumber == 2)
{
if (s->top2 == Maxsize) //判断栈是否为空
return false;
else
{
e = s->data[s->top2++];//将栈2的栈顶元素出栈，随后栈顶指针加1
}
}
return true;
}（3）初始化及销毁
代码：
// 1）初始化栈
void InitDStack(DStack*& s)
{
s = (DStack*)malloc(sizeof(DStack));
s->top1 = -1;
s->top2 = Maxsize;
}
// 2) 销毁栈
void DestroyDStack(DStack*& s)
{
free(s);
}三、栈的链式存储结构
1.栈的链式存储结构及其基本运算实现
采用链式存储的栈称为链栈，链栈的优点是便于多个栈共享存储空间和提高其效率，且不存在栈满上溢的情况。通常采用单链表实现，并规定所有操作都是在单链表的表头进行的。
链栈示意图：
链栈中结点类型LinkStNode的声明如下：
代码：
//栈的链式存储结构和基本运算实现
typedef struct linkNode
{
ElemType1 data; //数据域
struct linkNode* next; //指针域
}LinkStNode;（1）初始化栈
创建一个空栈，由s指向它。并为栈顶指针设置为-1.
代码：
// 1)初始化栈
void InitLinkStack(LinkStNode*& s)
{
s = (LinkStNode*)malloc(sizeof(LinkStNode));
s->next = NULL;
}（2）入栈
元素加入栈顶的过程称为入栈。如果当前栈未满，新元素将被添加到栈顶位置。否则，将产生栈满（Stack Overflow）的错误。
代码：
// 4）入栈
bool LinkStPush(LinkStNode*& s, ElemType1 e)
{
LinkStNode* p = (LinkStNode*)malloc(sizeof(LinkStNode));
p->data = e;
p->next = s->next;
s->next = p;
return true;
}（3）出栈
元素从栈顶移除的过程称为出栈。如果栈非空，栈顶元素将被移除并返回。否则，将产生栈空（Stack Underflow）的错误。
代码：
// 5）出栈
bool LinkStPop(LinkStNode*& s, ElemType1& e)
{
if (s->next == NULL)
return false;
LinkStNode* p = s->next; //p指向首节点
e = p->data;
s->next = p->next;//删除首结点
free(p); //释放出栈的节点
return true;
}（4）读取栈顶元素
查看当前栈顶的元素，但不将其从栈中移除。
代码：
// 6）取栈顶元素
bool LinkStGetTop(LinkStNode* s, ElemType1& e)
{
if (s->next == NULL)
return false;
e = s->next->data;
return true;
}（5）检查栈是否为空
判断栈中是否还有元素，当栈顶指针值为-1时，栈为空，如果栈中没有任何元素，则返回真（True），否则返回假（False）。
// 3)判断栈是否为空
bool LinkStackEmpty(LinkStNode* s)
{
return (s->next == NULL);
}（6）销毁栈
该运算释放栈s占用的存储空间。
代码：
// 2）销毁栈
void DestroyLinkStack(LinkStNode*& s)
{
//和单链表的销毁相同
LinkStNode* pre = s, * p = s->next;//pre指向头结点，p指向首节点
while (p!=NULL) //循环到p不为空
{
free(pre);
pre = p;
p = p->next;
}
free(pre);//最后，pre指向尾节点，释放它的空间
}
四丶栈的应用
1.数制转换 10进制 转化为 d进制数
不同数制间的转换(例如 十进制数→d进制数)假设待转换的十进制数为N，转化后的数制为d，则用d不断地去除待转换的十进制数整数N，直到商等于0为止。然后将各次所得余数，以最后一次的余数为d进制数的最高数位，依次排列，即得到所求的d进制数。
代码：
//1） 数制转换 10进制 转化为 d进制数
void conversion(int data, int d,SqStack *&s)
{
int N = data; //10进制数
int D = d; //转换的进制
while(N) //短除法
{
Push(s, N %D);
N = N /D;
}
while (!StackEmpty(s)) //打印结果
{
int e;
Pop(s, e);
printf("%d", e);
}
}2.括号匹配
括号匹配检验
在文字处理软件或编译程序时，常常需要检查一个表达式中的括号是否相匹配。如:[([][])]
算法思想:从左至右扫描一个表达式，则每个右括号将与最近遇到的那个左括号相匹配。则可以在从左至右扫描过程中把所遇到的左括号存放到栈中。每当遇到一个右括号时，就将它与栈顶的左括号(如果存在)相匹配，同时从栈顶删除该左括号。
代码：
// 2)括号匹配函数
void bracketCheck(char str[], int length) {
LinkStNode *s;
InitLinkStack(s); // 第一步 栈初始化
int flag = 1; //标志是否匹配成功
for (int i = 0; i < length; i++)
{
if (str[i] == '(' || str[i] == '{' || str[i] == '[') //第二步 当读到左括号时，左括号进栈
{
LinkStPush(s, str[i]);
}
else if (str[i] == ')' || str[i] == '}' || str[i] == ']') //第三步 当读到右括号时，出栈 ，栈顶元素与对应左括号进行匹配
{
if (!LinkStackEmpty(s))
{
char topElem;
LinkStPop(s, topElem);
if (str[i] == ')' && topElem != '(')
{
flag = 0;
printf("匹配失败，第 % d 个右括号 % c 与栈顶符号 % c 不匹配\n", i + 1, str[i], topElem);
}
if (str[i] == ']' && topElem != '[')
{
flag = 0;
printf("匹配失败，第 % d 个右括号 % c 与栈顶符号 % c 不匹配\n", i + 1, str[i], topElem);
}
if (str[i] == '}' && topElem != '{')
{
flag = 0;
printf("匹配失败，第 % d 个右括号 % c 与栈顶符号 % c 不匹配\n", i + 1, str[i], topElem);
}
}
else
{
printf("\n匹配失败，第%d个是单身右括号%c\n", i + 1, str[i]);//栈空存在单身右括号
flag = 0;
}
}
}
if (LinkStackEmpty(s) && flag != 0) // 第四步 表达式扫描完成 ，若栈不为空，表示左括号过多
{
printf("匹配成功！\n");
}
else if(flag==1)
{
printf("匹配失败，左括号过多！\n");
}
DestroyLinkStack(s);
}3.迷宫问题
给定一个迷宫，指明起点和终点，找出从起点出发到终点的有效可行路径，就是迷宫问题（maze problem）。
迷宫可以以二维数组来存储表示。0表示通路，1表示障碍。注意这里规定移动可以从上、下、左、右四方方向移动
求迷宫中一条从入口到出口的路径的算法:
设定当前位置的初值为入口位置;
do {
若当前位置可通
则{将当前位置插入栈顶;
可通:未曾走过的通道块
若该位置是出口位置，则算法结束;//此时栈中存放的是一条从入口到出口的路径否则切换当前位置的东邻方块为新的当前位置;
否则{
若栈不空且栈顶位置尚有其他方向未被探索
则设定新的当前位置为: 沿顺时针方向旋转找到的栈顶位置的下一相邻块若栈不空但栈顶位置的四周均不可通，删去栈顶位置; //从路径中删去该通道块若栈不空，则重新测试新的栈顶位置，直至找到一个可通的相邻块或出栈至栈空
则{
}while (栈不空);若栈空，则表明迷宫没有通路
代码：
#include<stdio.h>
#include<stdlib.h>
#define Maxsize 10000
#define M 8
#define N 8
int mg[M + 2][N + 2] =
{ {1,1,1,1,1,1,1,1,1,1},
{1,0,0,1,0,0,0,1,0,1},
{1,0,0,1,0,0,0,1,0,1},
{1,0,0,0,0,1,1,0,0,1},
{1,0,1,1,1,0,0,0,0,1},
{1,0,0,0,1,0,0,0,0,1},
{1,0,1,0,0,0,1,0,0,1},
{1,0,1,1,1,0,1,1,0,1},
{1,1,0,0,0,0,0,0,0,1},
{1,1,1,1,1,1,1,1,1,1}
};
typedef struct
{
int i; //方块的行号
int j;//方块的列号
int di;// 下一个方块可走的列号 0 1 2 3 -1
}Box;
typedef struct // 栈的顺序存储结构 及基本运算的实现
{
Box data[Maxsize];
int top;
}StType;
// 1)初始化栈
void InitStack(StType*& s)
{
s = (StType*)malloc(sizeof(StType)); //分配一个顺序栈空间，首地址存放在s当中
s->top = -1; //栈顶指针置为 -1
}
// 2)销毁栈
void DestroyStack(StType*& s)
{
free(s);
}
// 3)判断栈是否为空
bool StackEmpty(StType* s)
{
return(s->top == -1);
}
// 4）进栈
bool Push(StType*& s, Box e)
{
//判断栈是否满了
if (s->top == Maxsize - 1)
{
return false;
}
s->top++; //栈顶指针加1
s->data[s->top] = e;//插入元素e
return true;
}
// 5）出栈
bool Pop(StType*& s, Box& e)
{
if (s->top == -1)//栈为空的情况（栈下溢出），返回
return false;
e = s->data[s->top];//取出栈顶元素
s->top--;//栈顶指针减一
return true;
}
// 6）取栈顶元素
bool GetTop(StType*& s, Box& e)
{
if (s->top == -1)//栈为空的情况（栈下溢出），返回
return false;
e = s->data[s->top];//取出栈顶元素
return true;
}
bool mgpath(int xi, int yi, int xe, int ye)//求解 （xi,yi）到（xe,ye）
{
Box Path[10000], e;
int i, j, di;//用于记录栈顶元素
int i1, j1;//用于记录下一方位的坐标
int k;
int find; //记录是否找到可走相邻元素
StType* st; //定义栈st
InitStack(st); //初始化
e.i = xi, e.j = yi, e.di = -1; //-1表示不可以走的方块，设置入口
Push(st, e);
mg[xi][yi] = -1; //将入口置为-1 避免重复走到该方块
while (!StackEmpty(st))
{
GetTop(st, e);
i = e.i, j = e.j, di = e.di;
if (i == xe && j == ye)//找到出口 输出该路径
{
printf("一条迷宫路径如下;\n");
k = 0; //k表示路径中的方块数量
while (!StackEmpty(st))
{
Pop(st, e);
Path[k++] = e;
}
while (k > 0)
{
printf("\t(%d,%d)", Path[k - 1].i, Path[k - 1].j);
if (((k + 1) % 5 == 0))
{
printf("\n");
}
k--;
}
printf("\n");
DestroyStack(st);
return true;
}
find = 0; //初始化为0 为找到可走相邻方块
while (di < 4 && find == 0)
{
di++;
switch (di) {
case 0: {i1 = i - 1, j1 = j; break; }
case 1: {i1 = i; j1 = j + 1; break; }
case 2: {i1 = i + 1; j1 = j; break; }
case 3: {i1 = i; j1 = j - 1; break; }
}
if (mg[i1][j1] == 0) //找到可走方块
find = 1;
}
if (find) //找到了可走的方块
{
st->data[st->top].di = di; //修改原来栈顶元素的di值 di值表示当前方块下一个可以走的号
e.i = i1, e.j = j1; e.di = -1;
Push(st,e);
mg[i1][j1] = -1; //将这个方块的di值置为-1 避免重复走
}
else //没有找到可走的方块 退栈
{
Pop(st, e);
mg[e.i][e.j] = 0; //让退栈方块变为其它路径可走的方块
}
}
DestroyStack(st);
return false;
}
int main()
{
if (!mgpath(1, 1, M, N))
printf("迷宫问题没有解决");
return 0;
}栈还有很多相关的应用，比如递归，表达式的求值等等。
五丶全部代码（含测试）
代码：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef int ElemType;
typedef char ElemType1;
#define Maxsize 10
typedef struct // 栈的顺序存储结构 及基本运算的实现
{
ElemType data[Maxsize];
int top;
}SqStack;
// 1)初始化栈
void InitStack(SqStack*& s)
{
s = (SqStack*)malloc(sizeof(SqStack)); //分配一个顺序栈空间，首地址存放在s当中
s->top = -1; //栈顶指针置为 -1
}
// 2)销毁栈
void DestroyStack(SqStack*& s)
{
free(s);
}
// 3)判断栈是否为空
bool StackEmpty(SqStack* s)
{
return(s->top == -1);
}
// 4）进栈
bool Push(SqStack*& s,ElemType e)
{
//判断栈是否满了
if (s->top == Maxsize - 1)
{
return false;
}
s->top++; //栈顶指针加1
s->data[s->top] = e;//插入元素e
return true;
}
// 5）出栈
bool Pop(SqStack*& s, ElemType &e)
{
if (s->top == -1)//栈为空的情况（栈下溢出），返回
return false;
e = s->data[s->top];//取出栈顶元素
s->top--;//栈顶指针减一
return true;
}
// 6）取栈顶元素
bool GetTop(SqStack*& s, ElemType& e)
{
if (s->top == -1)//栈为空的情况（栈下溢出），返回
return false;
e = s->data[s->top];//取出栈顶元素
return true;
}
//栈的链式存储结构和基本运算实现
typedef struct linkNode
{
ElemType1 data; //数据域
struct linkNode* next; //指针域
}LinkStNode;
// 1)初始化栈
void InitLinkStack(LinkStNode*& s)
{
s = (LinkStNode*)malloc(sizeof(LinkStNode));
s->next = NULL;
}
// 2）销毁栈
void DestroyLinkStack(LinkStNode*& s)
{
//和单链表的销毁相同
LinkStNode* pre = s, * p = s->next;//pre指向头结点，p指向首节点
while (p!=NULL) //循环到p不为空
{
free(pre);
pre = p;
p = p->next;
}
free(pre);//最后，pre指向尾节点，释放它的空间
}
// 3)判断栈是否为空
bool LinkStackEmpty(LinkStNode* s)
{
return (s->next == NULL);
}
// 4）进栈
bool LinkStPush(LinkStNode*& s, ElemType1 e)
{
LinkStNode* p = (LinkStNode*)malloc(sizeof(LinkStNode));
p->data = e;
p->next = s->next;
s->next = p;
return true;
}
// 5）出栈
bool LinkStPop(LinkStNode*& s, ElemType1& e)
{
if (s->next == NULL)
return false;
LinkStNode* p = s->next; //p指向首节点
e = p->data;
s->next = p->next;//删除首结点
free(p); //释放出栈的节点
return true;
}
// 6）取栈顶元素
bool LinkStGetTop(LinkStNode* s, ElemType1& e)
{
if (s->next == NULL)
return false;
e = s->next->data;
return true;
}
// 共享栈
typedef struct
{
ElemType data[Maxsize];
int top1, top2;
}DStack;
// 1）初始化栈
void InitDStack(DStack*& s)
{
s = (DStack*)malloc(sizeof(DStack));
s->top1 = -1;
s->top2 = Maxsize;
}
// 2) 销毁栈
void DestroyDStack(DStack*& s)
{
free(s);
}
// 3) 进栈 stackNumber=1 表示对栈1进行操作，stackNumber=2 表示对栈2进行操作
bool DStackPush(DStack*& s, ElemType e, int stackNumber)
{
//判断栈满 条件 top1 == top2-1
if (s->top1 == s->top2 - 1) return false;
if (stackNumber == 1)//栈1有元素进栈
{
s->data[++s->top1] = e;//若栈1则先top1+1后给数组元素赋值
}
else if (stackNumber == 2)//栈2有元素进栈
{
s->data[--s->top2] = e;//若栈2则先top1-1后给数组元素赋值
}
return true;
}
// 4) 出栈 判断栈空的条件 栈一空top1 == -1 ， 栈二空 top2 == Maxsize
bool DStackPop(DStack*& s, ElemType& e, int stackNumber)
{
if (stackNumber == 1)
{
if (s->top1 == -1) //判断栈是否为空
return false;
else
{
e = s->data[s->top1--]; //将栈1的栈顶元素出栈，随后栈顶指针减1
}
}
else if (stackNumber == 2)
{
if (s->top2 == Maxsize) //判断栈是否为空
return false;
else
{
e = s->data[s->top2++];//将栈2的栈顶元素出栈，随后栈顶指针加1
}
}
return true;
}
//栈 的应用
//1） 数制转换 10进制 转化为 d进制数
void conversion(int data, int d,SqStack *&s)
{
int N = data; //10进制数
int D = d; //转换的进制
while(N) //短除法
{
Push(s, N %D);
N = N /D;
}
while (!StackEmpty(s)) //打印
{
int e;
Pop(s, e);
printf("%d", e);
}
}
// 2)括号匹配函数
void bracketCheck(char str[], int length) {
LinkStNode *s;
InitLinkStack(s); // 第一步 栈初始化
int flag = 1; //标志是否匹配成功
for (int i = 0; i < length; i++)
{
if (str[i] == '(' || str[i] == '{' || str[i] == '[') //第二步 当读到左括号时，左括号进栈
{
LinkStPush(s, str[i]);
}
else if (str[i] == ')' || str[i] == '}' || str[i] == ']') //第三步 当读到右括号时，出栈 ，栈顶元素与对应左括号进行匹配
{
if (!LinkStackEmpty(s))
{
char topElem;
LinkStPop(s, topElem);
if (str[i] == ')' && topElem != '(')
{
flag = 0;
printf("匹配失败，第 % d 个右括号 % c 与栈顶符号 % c 不匹配\n", i + 1, str[i], topElem);
}
if (str[i] == ']' && topElem != '[')
{
flag = 0;
printf("匹配失败，第 % d 个右括号 % c 与栈顶符号 % c 不匹配\n", i + 1, str[i], topElem);
}
if (str[i] == '}' && topElem != '{')
{
flag = 0;
printf("匹配失败，第 % d 个右括号 % c 与栈顶符号 % c 不匹配\n", i + 1, str[i], topElem);
}
}
else
{
printf("\n匹配失败，第%d个是单身右括号%c\n", i + 1, str[i]);//栈空存在单身右括号
flag = 0;
}
}
}
if (LinkStackEmpty(s) && flag != 0) // 第四步 表达式扫描完成 ，若栈不为空，表示左括号过多
{
printf("匹配成功！\n");
}
else if(flag==1)
{
printf("匹配失败，左括号过多！\n");
}
DestroyLinkStack(s);
}
int main()
{
//SqStack * s;
//InitStack(s);
//int data, d;
//printf("请输入要要转换的数字:\n");
//scanf_s("%d", &data);
//printf("请输入将数字转换的进制:\n");
//scanf_s("%d", &d);
//conversion(data, d, s);
//DestroyStack(s);
char str[Maxsize] = "\0"; //字符数组初始化\0
printf("请输入您要判断的表达式:\t");
if (fgets(str, sizeof(str), stdin) != NULL) {
// 移除字符串末尾的换行符
str[strcspn(str, "\n")] = 0;
printf("您输入的文本是: %s\n", str);
}
else {
printf("读取输入时发生错误。\n");
}
printf("\n");
bracketCheck(str, Maxsize);
return 0;
}通过上述介绍，我们可以看到栈作为一种基本的数据结构，其简洁的特性在解决特定问题时展现出强大的功能。掌握栈的原理和操作，对于编程和算法设计有着重要的意义。
原文地址：https://blog.csdn.net/m0_66847953/article/details/142603156
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！