@[TOC]
数据结构和算法（五）栈的操作和实现
- 本篇博客的Demo下载：
1. 栈的简介
栈是一种后进先出的结构，有一个栈底指针，一个栈顶指针，入栈只能从栈顶入栈，出栈也只能从栈顶出栈。它的结构示意图如下：
栈的结构图
我们可以对比一下队列：队列是一种先进先出的数据结构，只能从队尾入队，从对头出队，队列的结构图如下图：
队列的结构示意图
2. 顺序栈的实现
2.1 顺序栈的基本操作
2.1.1 顺序栈结构
//顺序栈结构
typedef struct KSqueueStack{
KStackElementType data[MAXSIZE];
int top; //用于栈顶指针
}SqStack;
2.1.2 顺序栈建栈
//1. 构建一个空栈S
KStatus initStack(SqStack *S) {
S->top = -1;
return OK;
}
2.1.3 顺序栈置空
//2. 将栈置空
KStatus clearStack(SqStack *S) {
S->top = -1;
return OK;
}```
#### 2.1.4 顺序栈判空
```swift
//3. 判断顺序栈是否为空
KStatus isEmpty(SqStack S) {
return S.top == -1 ;
}
2.1.5 顺序栈获取长度
//4. 获取栈长度
int getLength(SqStack S) {
return S.top + 1;
}
2.1.6 顺序栈获取栈顶元素
//5. 获取栈顶
KStatus getTop(SqStack S, KStackElementType *e) {
//栈空，则返回错误
if (S.top == -1) return ERROR;
*e = S.data[S.top];
return OK;
}
2.1.7 顺序栈压栈
入栈前如下图所示：
入栈前
入栈后如下图所示：
入栈后
入栈代码实现：
//6. 压栈
KStatus push(SqStack *S, KStackElementType e) {
//判断是否 栈满
if (S->top == MAXSIZE -1) return ERROR;
//1. 栈顶指针+1;
//2. 将新插入的元素赋值给栈顶空间
//S->top ++;
//S->data[S->top] = e;
S->data[++(S->top)] = e;
return OK;
}
2.1.8 顺序栈出栈
//7. 出栈
KStatus pop(SqStack *S, KStackElementType *e) {
//判断是否栈空
if(S->top == -1) return ERROR;
//1. 将要删除的栈顶元素赋值给e
//2. 栈顶指针--;
//*e = S->data[S->top];
//S->top--;
*e = S->data[S->top--];
return OK;
}
2.1.9 顺序栈遍历
//8. 栈遍历
KStatus traverse(SqStack S) {
int i = 0;
printf("栈所有元素：");
while (i < S.top) {
printf("%d ",S.data[i++]);
}
printf("\n");
return OK;
}
2.1.10 顺序栈单元测试
//9. 测试
void test() {
SqStack S;
int e;
if (initStack(&S) == OK) {
for (int j = 1 ; j < 10; j++) {
push(&S, j);
}
}
printf("顺序栈中元素为:\n");
traverse(S);
pop(&S, &e);
printf("弹出栈顶元素为: %d\n",e);
traverse(S);
printf("是否为空栈:%d\n",isEmpty(S));
getTop(S, &e);
printf("栈顶元素:%d \n栈长度:%d\n",e,getLength(S));
clearStack(&S);
printf("是否已经清空栈 %d, 栈长度为:%d\n",isEmpty(S),getLength(S));
}
- 输出结果
Hello, World!
顺序栈中元素为:
栈所有元素：1 2 3 4 5 6 7 8
弹出栈顶元素为: 9
栈所有元素：1 2 3 4 5 6 7
是否为空栈:0
栈顶元素:8
栈长度:8
是否已经清空栈 1, 栈长度为:0
Program ended with exit code: 0
3. 链式栈的实现
链式栈是有链表来实现的一种栈结构，它的结构示意图如下图：
链式栈的结构图
3.1 链式栈的基本操作
栈的入栈出栈过程图
3.1.1 链式栈结构
//链栈结点
typedef struct KStackNode {
KStackElementType data; //结点数据
struct KStackNode *next; //指向下一个结点的指针
}StackNode, *LinkStackPtr;
//链栈结构
typedef struct KLinkStack {
LinkStackPtr top; //栈顶结点
int count; //栈大小
}LinkStack;
3.1.2 链式栈建栈
//1. 构造一个空栈S
KStatus initStack(LinkStack *S) {
S->top = NULL;
S->count = 0;
return OK;
}
3.1.3 链式栈置空
//2. 链栈置空
KStatus clearStack(LinkStack *S) {
LinkStackPtr p,q;
//p指向栈顶结点
p = S->top;
while (p) {
//保存要删除的结点p
q = p;
//然p指向它的下一个结点
p = p->next;
//删除 p结点
free(q);
}
return OK;
}
3.1.4 链式栈判空
//3. 判断栈是否为空
KStatus isEmpty(LinkStack S) {
return S.count == 0;
}
3.1.5 链式栈获取长度
//4. 获取栈长度
int getLength(LinkStack S) {
return S.count;
}
3.1.6 链式栈获取栈顶元素
//5. 获取栈顶元素
KStatus getTop(LinkStack S, KStackElementType *e) {
//判断是否栈空
if (S.top == NULL) return ERROR;
*e = S.top->data;
return OK;
}
3.1.7 链式栈压栈
链式栈结构，入栈示意图如下：
链式栈入栈示意图
//6. 压栈
KStatus push(LinkStack *S, KStackElementType e) {
//1. 创建一个新结点，
LinkStackPtr newNode = (LinkStackPtr)malloc(sizeof(StackNode));
//2. 赋值给新结点
newNode->data = e;
//3. 插入新结点到栈顶结点后面
//3.1 把当前的栈顶元素的结点指针指向直接后继结点
newNode->next = S->top;
//3.2 将新结点赋值给栈顶指针
S->top = newNode;
//栈大小+1
S->count++;
return OK;
}
3.1.8 链式栈出栈
链式栈结构，出栈示意图如下图：
链式栈出栈图
//7. 出栈
KStatus pop(LinkStack *S, KStackElementType *e) {
LinkStackPtr p;
if (isEmpty(*S)) return ERROR;
//1. 将栈顶元素赋值给*e
*e = S->top->data;
//2. 将栈顶结点赋值给p
p = S->top;
//3. 使得栈顶指针下移一位, 指向后一结点
S->top = S->top->next;
//4. 释放p结点
free(p);
//栈大小减1
S->count--;
return OK;
}
3.1.9 链式栈遍历
//8. 遍历栈
KStatus traverse(LinkStack S) {
LinkStackPtr p = S.top;
printf("遍历栈元素：");
while (p) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
return OK;
}
3.1.10 链式栈单元测试
//9. 单元测试
void test() {
int j;
LinkStack s;
int e;
if(initStack(&s)==OK)
for(j=1;j<=10;j++)
push(&s,j);
printf("栈中元素依次为：");
traverse(s);
pop(&s,&e);
printf("弹出的栈顶元素 e=%d\n",e);
traverse(s);
printf("栈空否：%d(1:空 0:否)\n",isEmpty(s));
getTop(s,&e);
printf("栈顶元素 e=%d 栈的长度为%d\n",e,getLength(s));
clearStack(&s);
printf("清空栈后，栈空否：%d(1:空 0:否)\n",isEmpty(s));
}
- 输出结果
Hello, World!
栈中元素依次为：遍历栈元素：10 9 8 7 6 5 4 3 2 1
弹出的栈顶元素 e=10
遍历栈元素：9 8 7 6 5 4 3 2 1
栈空否：0(1:空 0:否)
栈顶元素 e=9 栈的长度为9
清空栈后，栈空否：0(1:空 0:否)
Program ended with exit code: 0
3. 栈的应用
3.1 递归
3.1.1 函数调用及递归实现
下⾯面3种情况下,我们会使⽤用到递归来解决问题
- 定义是递归的
- 数据结构是递归的
- 问题的解法是递归的
递归函数调用分析
函数递归入栈过程
3.1.2 深度优先搜索
3.1.3 回溯算法
3.1.4 Hanoi塔问题
问题描述: 假如有3个分别命名为A,B,C的塔座,在塔座A上插有n个直接⼤大⼩小各不不相同的,从⼩小到⼤大的 编号为1,2,3...n的圆盘. 现在要求将塔座A上的n个圆盘移动到塔座C上. 并仍然按照同样的顺序叠 排. 圆盘移动时必须按照以下的规则:1. 每次只能移动⼀一个圆盘;2. 圆盘可以插在A,B,C的任⼀一塔座 上;3. 任何时刻都不不能将⼀一个较⼤大的圆盘压在⼩小的圆盘之上.
hanoi塔问题
求解过程图如下：
hanoi塔问题求解过程图
3.2 表达式求值
在编译系统中，算术表达式可以分为三类：算术表达式，关系表达式，逻辑表达式。
任何一个算术表达式都是由：操作数，运算符和分界符组成。我们把操作数，运算符和分界符（分界符标志了一个算术表达式的结束）称为一个算术表达式的单词。
-
中缀表达式：算术表达式中的运算符总是出现在两个操作数之间（除单目运算符外）例如：
A+（B-C/D）*E -
后缀表达式：表达式中的运算符出现在操作数之后。编译系统对于中缀表达式处理方法是将其变成后缀表达式，例如：
ABCD/-E*+
后缀表达式的特点：
- 后缀表达式的操作数和中缀表达式的操作数先后次序完全相同（上面ABCDE），只是运算符的先后次序改变了（+-/*）；
- 后缀表达式中没有括号，后缀表达式的运算次序就是其执行次序
应用堆栈实现后缀表达式求值的基本过程：
从左到右读入后缀表达式的各项（运算符或运算数）：
- 运算数：入栈
- 运算符：从堆栈中弹出适当数量的运算数，计算并结果入栈
- 最后，堆栈顶上的元素就是表达式的结果值
3.2.1 中缀表达式求值
基本策略：将中缀表达式转换为后缀表达式，然后求值。
- 如何将中缀表达式转换为后缀表达式？
例如：2+9/3-5->2 9 3 / +5 -
过程：
- 运算数相对顺序不变
- 运算符号顺序发生改变
- 需要存储“等待中”的运算符号
- 要将当前运算符号与“等待中”的最后一个运算符号比较
3.2.2 中缀表达式如何转换为后缀表达式
从头到尾读取中缀表达式的每个对象，对不同对象按不同的情况处理。
- 运算数：直接输出
- 左括号：压入堆栈
- 右括号：将栈顶的运算符弹出并输出，直到遇到左括号（出栈，不输出）
- 运算符:
(1) 若优先级大于栈顶运算符时，则把它压栈
(2) 若优先级小于等于栈顶运算符时，将栈顶运算符弹出并输出；再比较新的栈顶运算符，直到该运算符大于栈顶运算符优先级为止，然后将该运算符压栈- 若各对象处理完毕，则把堆栈中存留的运算符一并输出
中缀表达式如何转换为后缀表达式
3.2.3 后缀表达式的实现过程
编译系统设置一个存放运算符的堆栈，初始时栈顶置一个分界符“#”。编译系统从左到右依次扫描中缀表达式，每读到一个操作数就把它作为后缀表达式的一部分输出，每读到一个运算符（分界符也看作运算符）就将其优先级与栈顶运算符优先级运算符进行比较，以决定是就所读到的运算符进栈，还是将栈顶运算符作为最为后缀算术表达式的一部分输出。
- 运算符优先级别注意： 若把O1看成栈顶运算符，O2看成当前扫描读到的运算符。
- 当O1为“+”或“-”，O2为“*”或“/”时，O1的优先级 < O2的优先级(满足先乘除，后加减)
- 当O1为“+”“-”“*”或“/”，O2为“（”时，O1的优先级 < O2的优先级（满足先括号内，后括号外的规则）
- 当O1的运算符和O2的运算符同级别时，O1的优先级 > O2的优先级别（同级别先左后右规则）
- 由于后缀表达式无括号，当O1为“（”，O2为“）”时，用标记“=”使算法在此时去掉该对算法；
- 当O1为“#”时，O2为“#”时，用标记“=”使算法在此时结束处理
- 若表中的值为空，则不允许出现这种情况，一旦出现即为中缀算术表达式语法出错，如O1为“）”，而O2为“（”情况，即为中缀表达式语法错误！)。
- 算法步骤：
- 设置一个堆栈，初始时将栈顶元素置为#
- 顺序读入中缀算术表达式，当读到的单词为操作数是就将其输出，并接着读下一个单词
- 单读到的单词为运算符时，令a为当前栈顶运算符的变量，b为当前扫描读到运算符的变量，把当前读到的运算符赋给b,然后比较变量a的优先级和b的优先级。若a的优先级高于ｂ的优先级，则将ａ退栈并作为后缀表达式的一个单词输出，，然后比较新的栈顶元素运算符ａ的优先级与ｂ的优先级。
若优先级 ａ＜ｂ，则将ｂ的值进栈，然后接着读下一个单词
若优先级 ａ＞ｂ，则将ａ退栈并作为后缀表达式的一个单词输出，然后比较新的栈顶元素运算符ａ的优先级与ｂ的优先级。
若优先级 ａ＝ｂ且ａ为“（”，ｂ为“）”。则将ａ退栈，接着读下一个单词
若优先级 ａ＝ｂ且ａ为“＃”，ｂ为“＃”。算法结束。
- 代码实现：
int PostExp(char str[]) //借助堆栈计算后缀表达式str的值
{
KStackElementType x,x1,x2;
int I;
KNode *head; //定义头指针变量head
initStack(&head); //初始化链式堆栈head
for(i-0;str[i]!=#;i++) //循环直到输入为#
{
if(isdigit(str[i])) //当str[i]为操作数时
{
x=(int)(str[i]-48); //转换成int类型数据存于变量x中
push(head,x); //x入栈
}
else //当str[i]为运算符时
{
pop(head,&x2); //退栈的操作数，存于变量x2中
pop(head,&x1); //退栈的被操作数，存于变量x1中
switch(str[i]) //执行str[i]所表示的运算
{
case '+':
{
x1+=x2; break;
}
case '-':
{
x1-=x2; break;
}
case '*':
{
x1*=x2; break;
}
case '/':
{
if(x2==0.0)
{
printf("除数为0错误！\n");
exit(0);
}
else
{
x1/=x2;
break;
}
}
}
push(head,x1); //运算结果入栈
}
}
pop(head,&x); //得到计算结果存于x
return x; //返回计算结果
}
4. 队列
队列：具有一定操作约束的线性表
有以下特点：
- 插入和删除操作：只能在一端插入，而在另一端删除
- 数据插入：入队（AddQ）
- 数据删除：出队列（DeleteQ）
- 先进先出：FIFO
4.1 队列基本操作
队列基本操作
4.2 循环队列
循环队列基本结构
- 循环队列中头尾指针和元素之间的关系
循环队列中头尾指针和元素之间的关系1
循环队列中头尾指针和元素之间的关系2
循环队列的操作
