第三章栈和队列
- 格式：ppt
- 大小：1.41 MB
- 文档页数：59
下载文档原格式
合集下载
大学数据结构课件--第3章 栈和队列
top top 栈空 F E D C B A
栈满 top-base=stacksize
top
F
E
D C B
top top top top top top base
入栈PUSH(s,x):s[top++]=x; top 出栈 POP(s,x):x=s[--top]; top
base
4
A
3.1 栈
例1：一个栈的输入序列为1,2,3，若在入栈的过程中 允许出栈，则可能得到的出栈序列是什么？ 答： 可以通过穷举所有可能性来求解：
3.2 栈的应用举例
二、表达式求值
“算符优先法”
一个表达式由操作数、运算符和界限符组成。 # 例如：3*（7-2*3） （1）要正确求值，首先了解算术四则运算的规则 a.从左算到右 b.先乘除后加减 c.先括号内，后括号外 所以，3*（7-2*3）=3*(7-6)=3*1=3
9
3.2 栈的应用举例
InitStack(S); while (!QueueEmpty(Q))
{DeQueue(Q,d);push(S,d);}
while (!StackEmpty(S)) {pop(S,d);EnQueue(Q,d);} }
第3章 栈和队列
教学要求：
1、掌握栈和队列的定义、特性，并能正确应用它们解决实 际问题；
用一组地址连续的存储单元依次存放从队头到队尾的元素， 设指针front和rear分别指示队头元素和队尾元素的位置。
Q.rear 5 4 Q.rear 3 2 3 2 5 4 Q.rear 3 3 5 4 5 4
F E D C
C B A
Q.front
2 1 0
C B
Q.front 2 1 0
栈满 top-base=stacksize
top
F
E
D C B
top top top top top top base
入栈PUSH(s,x):s[top++]=x; top 出栈 POP(s,x):x=s[--top]; top
base
4
A
3.1 栈
例1：一个栈的输入序列为1,2,3，若在入栈的过程中 允许出栈，则可能得到的出栈序列是什么？ 答： 可以通过穷举所有可能性来求解：
3.2 栈的应用举例
二、表达式求值
“算符优先法”
一个表达式由操作数、运算符和界限符组成。 # 例如：3*（7-2*3） （1）要正确求值，首先了解算术四则运算的规则 a.从左算到右 b.先乘除后加减 c.先括号内，后括号外 所以，3*（7-2*3）=3*(7-6)=3*1=3
9
3.2 栈的应用举例
InitStack(S); while (!QueueEmpty(Q))
{DeQueue(Q,d);push(S,d);}
while (!StackEmpty(S)) {pop(S,d);EnQueue(Q,d);} }
第3章 栈和队列
教学要求：
1、掌握栈和队列的定义、特性，并能正确应用它们解决实 际问题；
用一组地址连续的存储单元依次存放从队头到队尾的元素， 设指针front和rear分别指示队头元素和队尾元素的位置。
Q.rear 5 4 Q.rear 3 2 3 2 5 4 Q.rear 3 3 5 4 5 4
F E D C
C B A
Q.front
2 1 0
C B
Q.front 2 1 0
第3章 栈和队列总结
第三章 栈和队列
3.1 栈
3.1.1 抽象数据类型的定义
栈是一类特殊的线性表，数据元素的插入和删除运算只能在表的一端进 行，通常将进行插入和删除的一端称为栈顶，另一端称为栈底。将元素的插 入称为入栈或进栈，元素的删除称为出栈或退栈。 栈也称为后进先出的线性表（简称LIFO表）如图3.1(a)所示。 在日常生活中，栈的形式经常出现。例如，一叠盘子或一叠书的取放、 铁路调度站，如图3.1(b)所示。 栈的基本运算： （1）置空栈setnull(s)：将栈s置成空栈，建立起栈顶指针。 （2）判栈空empty(s)：若s为空栈，则返回TRUE值，否则返回FALSE值。 （3）入栈push(s,x)：若s未满，将x插入s栈栈顶，并使栈顶指针指向x。 （4）出栈pop(s)：若s栈非空，则从栈中删去栈顶元素，返回原栈顶元素。 （5）取栈顶元素gettop(s)：若s栈非空，则返回当前栈顶元素。
第三章 栈和队列
(3）入栈 int push(seqstack *s,elemtype x)//入栈 { if(s->top>=MAXSIZE-1) { printf("stack overflow！\n"); return 0; } else { s->stack[++s->top]=x; return 1; } }
第三章 栈和队列
进栈
出栈 进栈 出栈
栈顶
an
栈底
（a）栈的示意图
…
a2 a1
（b）铁路调度站示意图 3.1 栈示例
第三章 栈和队列
3.1.2 栈的表示和实现
1.顺序栈： 栈的顺序存储结构又称为顺序栈，顺序栈也可用向量来实现。顺序栈的 类型定义如下： #define MAXSIZE 100 /*栈的最大容量，这里设为100*/ typedef int elemtype; typedef struct { elemtype stack[MAXSIZE]; int top; }seqstack; /*顺序栈类型定义*/ seqstack *s; /*定义s为指向顺序栈的指针变量*/ 在顺序栈中进栈或 出栈运算时要注意空间的“溢出”。当栈满时，若再进行入栈运算，会产 生空间“上溢” ；而当栈空时，再进行出栈运算，会产生空间“下溢” 。 图3.2说明了栈中元素与栈顶指针的关系。
第3章_栈和队列
第三章 栈和队列
（Chapter 3. பைடு நூலகம்tack and Queue)
栈的概念、存储结构及其基本操作
栈的应用举例 队列的概念、存储结构及其基本操作
§3.1 栈
3.1.1 栈的定义及基本运算
• 定义：只能在表尾（栈顶）进行插入和删除操 作进行的线性表。 • 特点: 后进先出(LIFO—Last In First Out )
top 栈顶
an an-1
. . .
a1 ∧
栈底
空栈： top == NULL
16
入栈
LinkStack Push_LS (LinkStack top，datatype x) { StackNode *p ; top p = (StackNode *) malloc (sizeof( StackNode)); p->data = x; top p->next = top; top = p; return top; }
23
2
括号匹配的检验：
问题：两种括号，可以嵌套使用，但不能重叠 解决：使用栈。 ｛（［ ］［ ］）｝ 左括号进栈， 右括号就从栈顶出栈一个左括号， 检查是否能够匹配。 算法开始和结束时，栈都应该是空的。
匹配一个字符串中的左、右括号。如
[ a * ( b + c ) + d ]
( 出栈
( )匹配
[ 出栈
3.1.2 栈的存储及运算实现
顺序栈 -- 栈的顺序存储表示 链栈 -- 栈的链式存储表示
4
1 顺序栈
顺序栈类型的定义 – 本质 顺序表的简化，唯一需要确定的是栈顶、栈底。 – 通常 栈底：下标为0的一端 栈顶：由top指示，空栈时top=-1
（Chapter 3. பைடு நூலகம்tack and Queue)
栈的概念、存储结构及其基本操作
栈的应用举例 队列的概念、存储结构及其基本操作
§3.1 栈
3.1.1 栈的定义及基本运算
• 定义：只能在表尾（栈顶）进行插入和删除操 作进行的线性表。 • 特点: 后进先出(LIFO—Last In First Out )
top 栈顶
an an-1
. . .
a1 ∧
栈底
空栈： top == NULL
16
入栈
LinkStack Push_LS (LinkStack top，datatype x) { StackNode *p ; top p = (StackNode *) malloc (sizeof( StackNode)); p->data = x; top p->next = top; top = p; return top; }
23
2
括号匹配的检验：
问题：两种括号，可以嵌套使用，但不能重叠 解决：使用栈。 ｛（［ ］［ ］）｝ 左括号进栈， 右括号就从栈顶出栈一个左括号， 检查是否能够匹配。 算法开始和结束时，栈都应该是空的。
匹配一个字符串中的左、右括号。如
[ a * ( b + c ) + d ]
( 出栈
( )匹配
[ 出栈
3.1.2 栈的存储及运算实现
顺序栈 -- 栈的顺序存储表示 链栈 -- 栈的链式存储表示
4
1 顺序栈
顺序栈类型的定义 – 本质 顺序表的简化，唯一需要确定的是栈顶、栈底。 – 通常 栈底：下标为0的一端 栈顶：由top指示，空栈时top=-1
数据结构第三章 栈和队列
计 3467
433
算 433
54
顺 54
6
序
6
0
3
低输
1
出
6
顺
6
高序
所以：（3467）10 =（6613）8
28
算法思想：当N>0时重复1，2 1. 若 N≠0，则将N % r 压入栈s中 ，执行2;
若N=0，将栈s的内容依次出栈， 算法结束。 2. 用N / r 代替 N
29
【算法3-10】数制转换算法一
队满时 m=maxsize，队空时m=0
front rear
data
0
a1
1
a2
2
a3
…
…
n-1
an
…
…
Max-1
Top=-1，B、A出栈
13
顺序栈的主要运算
• 特殊情况表示： • 栈空：top == -1 • 栈满：top == maxsize-1
• 运算实现： • 入栈：若栈不满 s->top++ ； • 出栈：若栈不空 s->top-- ；
14
⑴ 置空栈
【算法3-1】栈的初始化算法 SeqStack *Init_SeqStack(){
若空则出错 (2)获取栈顶元素 x (3)栈顶指针减1
int Pop_SeqStack(SeqStack *s,DataType x){ if (Empty_SeqStack(s)) return 0; //栈空不能出栈，返回错误代码0 else { x=s->data[s->top]; //保存栈顶元素值
typedef struct {
datatype data[maxsize];
数据结构课件第3篇章栈和队列
循环队列实现原理
01
循环队列定义
将一维数组看作首尾相接的环形结构，通过两个指针（队头和队尾指针）
在数组中循环移动来实现队列的操作。当队尾指针到达数组末端时，再
回到数组起始位置，形成循环。
02
判空与判满条件
在循环队列中，设置一个标志位来区分队列为空还是已满。当队头指针
等于队尾指针时，认为队列为空；当队尾指针加1等于队头指针时，认
栈在函数调用中应用
函数调用栈
在程序执行过程中，每当发生函数调用时，系统会将当前函数的执行上下文压入一个专门的栈中，称为函数调用 栈。该栈用于保存函数的局部变量、返回地址等信息。当函数执行完毕后，系统会从函数调用栈中弹出相应的执 行上下文，并恢复上一个函数的执行状态。
递归调用实现
递归调用是一种特殊的函数调用方式，它通过在函数调用栈中反复压入和弹出同一函数的执行上下文来实现对问 题的分解和求解。在递归调用过程中，系统会根据递归深度动态地分配和管理函数调用栈的空间资源。
栈和队列的应用
栈和队列在计算机科学中有着广泛的应用，如函数调用栈、表达式求 值、缓冲区管理等。
常见误区澄清说明
误区一
栈和队列的混淆。虽然栈和队列都是线性数据结构，但它们的操作方式和应用场景是不同的。栈是后进先出，而队列 是先进先出。
误区二
认为栈和队列只能通过数组实现。实际上，栈和队列可以通过多种数据结构实现，如链表、循环数组等。具体实现方 式取决于应用场景和需求。
后缀表达式求值
利用栈可以方便地实现后缀表达式的求值。具体步骤 为：从左到右扫描表达式，遇到数字则入栈，遇到运 算符则从栈中弹出所需的操作数进行计算，并将结果 入栈，最终栈中剩下的元素即为表达式的结果。
中缀表达式转换为后缀表达式
第3章 栈和队列
显然，为循环队列所分配的空间可以被充分利 用，除非向量空间真的被队列元素全部占用， 否则不会上溢。因此，真正实用的顺序队列是循环队列。 例：设有循环队列QU[0，5]，其初始状态是 front=rear=0，各种操作后队列的头、尾指针的状态变 化情况如下图3-7所示。
rear front front 1 2 4 3 rear
队尾(rear) ：允许进行插入的一端称为队尾。
队列中没有元素时称为空队列。在空队列中依次加入元 素a1, a2, …, an之后，a1是队首元素，an是队尾元素。显然 退出队列的次序也只能是a1, a2, …, an ，即队列的修改是 依先进先出的原则进行的，如图3-5所示。
出队
a1 , a2 , … , an
◆ 入队：将新元素插入rear所指的位置，然后rear加1。
在非空队列里，队首指针始终指向队头元素，而队尾指 针始终指向队尾元素的下一位置。 顺序队列中存在“假溢出”现象。因为在入队和出队操 作中，头、尾指针只增加不减小，致使被删除元素的空间 永远无法重新利用。因此，尽管队列中实际元素个数可能 远远小于数组大小，但可能由于尾指针已超出向量空间的 上界而不能做入队操作。该现象称为假溢出。
结点进栈：首先将数据元素保存到栈顶(top所指的当前位置)，然后执
行top加1，使top指向栈顶的下一个存储位置;
结点出栈：首先执行top减1，使top指向栈顶元素的存储位置，然后将栈
顶元素取出。
3.1.2.2 栈的静态顺序存储表示
采用静态一维数组来存储栈。
◆ 栈底固定不变的；栈顶则随着进栈和退栈操作而变化，用一个整型变量top(称为 栈顶指针)来指示当前栈顶位置。 ◆ 用top=0表示栈空的初始状态，每次top指向栈顶在数组中的存储位置。 ◆
第3章 限定性线性表——栈和队列
两栈共享技术（双端栈）：
主要利用了栈“栈底位置不变，而栈顶位置动态变
化”的特性。首先为两个栈申请一个共享的一维数 组空间S[M]，将两个栈的栈底分别放在一维数组的 两端，分别是0，M-1。
共享栈的空间示意为：top[0]和top[1]分别为两个 栈顶指示器 。
Stack：0
M-1
top[0]
top[1]
(1)第i号栈的进栈操作 int pushi(LinkStack top[M], int i, StackElementType x) { /*将元素x进入第i号链栈*/
LinkStackNode *temp; temp=(LinkStackNode * )malloc(sizeof(LinkStackNode)); if(temp==NULL) return(FALSE); /* 申请空间失败 */ temp->data=x; temp->next=top[i]->next; top[i]->next=temp; /* 修改当前栈顶指针 */ return(TRUE); }
case 1:if(S->top[1]==M) return(FALSE);
*x=S->Stack[S->top[1]];S->top[1]++;break;
default: return(FALSE);
}
return(TRUE);
返回主目录
}
【思考题】
说明读栈顶与退栈顶的处理异同，并标明将已知 的退栈顶算法改为读栈顶算法时应做哪些改动。
返回主目录
链栈的进栈操作
int Push(LinkStack top, StackElementType x)
第三章栈与队列
第三章1.栈的定义与基本操作：1.概念：栈是一种特殊的线性表（操作限定在表的一端进行的线性表）栈顶：允许进行插入，删除等操作的一端栈底：固定的，不允许进行插入和删除的一端入栈：插入一个新元素出栈(退栈)：从栈中删除一个元素空栈：栈中没有数据元素时特点：先进的元素后出，后进的元素先出2.栈的应用：1.撤销操作2.在函数调用时保存断点信息3.栈的基本操作：初始化，求栈的长度，判断栈是否为空，入栈操作，出栈操作，取栈顶元素(书上P48面)栈的顺序存储结构概念：栈是特殊的线性表，因此线性表的存储结构对于栈也是适用的栈的两种存储结构：顺序存储结构和链式存储结构1.顺序栈的定义：与顺序表的定义类似，顺序栈是指用一片连续的存储空间存储数据元素的栈。
实现形式：采用数组的形式，把栈底设在数组的底端，同时用一个记录栈顶位置的整型变量top(栈顶指针)存储栈顶元素的位置2.顺序栈的三种存储池状态：空栈，满栈，非空非满栈3.顺序栈的溢出问题：栈是一个动态结构，而数组的空间大小有限，是静态的：当处于满栈状态时，再进行进栈操作会产生溢出错误(上溢出)，当处于空栈状态时，再进行出栈操作时也会产生溢出错误(下溢出).解决方法：在执行进出栈之前，应该进行溢出判断4.顺序栈的基本操作初始化操作，求顺序栈的长度，判断顺序栈是否为空，入栈操作，出栈操作(书上P51面，自己看)栈的链式存储结构栈的顺序存储结构是一种静态的存储结构，必须确定存储空间的大小，太大会造成存储空间的浪费，太小又会因栈满而产生溢出。
实际应用中，如果难以估计栈的最大容量，最好采用栈的链式存储结构(可自行略过)1.链栈的定义：概念：采用链式存储结构的栈。
链栈通常采用单链表表示，其结点结构与单链表的结构一样，每个数据元素都存放在链表结点的数据域中，在指针域中存放直接后继结点的地址，栈底结点的指针域为空(NULL)【不想看的，还是要看看，作个了解】链栈的特点：由于栈的链接存储结构，是一种动态的存储结构，其结点是动态产生的，因此它不会存在满栈状态，也不会发生上溢出错误2.链栈的基本操作：初始化链栈和清空链栈的操作，判断链栈是否为空，入栈操作，出栈操作(书上P54面,并非不是重点，自己看!!!)队列的定义与基本操作队列的定义：1.由于排列的队列是单行的，因此每个元素之间是“一对一”的关系，即它是一种线性结构2.排列的队列是一种特殊的线性表，插入元素的操作(入队)只能在线性表的一端完成，而删除元素的操作(出队)只能在线性表的另一端完成。
第3章栈和队列
第3章栈和队列
3.1.2 栈的表示和算法实现
1.顺序栈 2.链栈
第3章栈和队列
1. 顺序栈 顺序栈是用顺序存储结构实现的栈，即利 用一组地址连续的存储单元依次存放自栈 底到栈顶的数据元素，同时由于栈的操作 的特殊性，还必须附设一个位置指针top（ 栈顶指针）来动态地指示栈顶元素在顺序 栈中的位置。通常以top=-1表示空栈。
第 3 章 栈和队列
3.1 栈 3.2 队列 3.3 栈和队列的应用
第3章栈和队列
3.1 栈
3.1.1 栈的抽象数据类型定义 3.1.2 栈的表示和算法实现
第3章栈和队列
3.1.1 栈的定义
1．栈的定义 栈（stack）是一种只允许在一端进行插入和删除的线 性表，它是一种操作受限的线性表。在表中只允许进
行插入和删除的一端称为栈顶（top），另一端称为 栈 底 (bottom) 。 栈 的 插 入 操 作 通 常 称 为 入 栈 或 进 栈 (push)，而栈的删除操作则称为出栈或退栈(pop)。 当栈中无数据元素时，称为空栈。
栈是按照后进先出 （LIFO）的原则组 织数据的，因此， 栈也被称为“后进 先出”的线性表。
第3章栈和队列
（2）入栈操作
Status Push(SqStack &S, Elemtype e)
【算法3.2 栈的入栈操作】
{ /*将元素e插入到栈S中，作为S的新栈顶*/
if (S->top>= Stack_Size -1) return ERROR;
else { S->top++;
S->elem[S->top]=e;
return OK;}
Push(S,’you’)
3.1.2 栈的表示和算法实现
1.顺序栈 2.链栈
第3章栈和队列
1. 顺序栈 顺序栈是用顺序存储结构实现的栈，即利 用一组地址连续的存储单元依次存放自栈 底到栈顶的数据元素，同时由于栈的操作 的特殊性，还必须附设一个位置指针top（ 栈顶指针）来动态地指示栈顶元素在顺序 栈中的位置。通常以top=-1表示空栈。
第 3 章 栈和队列
3.1 栈 3.2 队列 3.3 栈和队列的应用
第3章栈和队列
3.1 栈
3.1.1 栈的抽象数据类型定义 3.1.2 栈的表示和算法实现
第3章栈和队列
3.1.1 栈的定义
1．栈的定义 栈（stack）是一种只允许在一端进行插入和删除的线 性表，它是一种操作受限的线性表。在表中只允许进
行插入和删除的一端称为栈顶（top），另一端称为 栈 底 (bottom) 。 栈 的 插 入 操 作 通 常 称 为 入 栈 或 进 栈 (push)，而栈的删除操作则称为出栈或退栈(pop)。 当栈中无数据元素时，称为空栈。
栈是按照后进先出 （LIFO）的原则组 织数据的，因此， 栈也被称为“后进 先出”的线性表。
第3章栈和队列
（2）入栈操作
Status Push(SqStack &S, Elemtype e)
【算法3.2 栈的入栈操作】
{ /*将元素e插入到栈S中，作为S的新栈顶*/
if (S->top>= Stack_Size -1) return ERROR;
else { S->top++;
S->elem[S->top]=e;
return OK;}
Push(S,’you’)
数据结构与算法C版课件第三章栈和队列
x成为新的栈顶元素。 （4）出栈pop（s）：删除栈s的栈顶元素。 （5）读栈顶元素top（s）：栈顶元素作为结果返回，
不改变栈的状态。
4.栈的存储 （1）采用顺序方式存储的栈称为顺序栈（sequential stack） （2） 采用链接方式存储的栈称为链栈（linked stack）
3.1.2 顺序栈及运算的算法实现
用栈来实现括号匹配检查的原则是，对表达式从左到右扫描。 （1）当遇到左括号时，左括号入栈； （2）当遇到右括号时，首先检查栈是否空，若栈空，则表明该“右括弧”多余；否则比 较栈顶左括号是否与当前右括号匹配，若匹配，将栈顶左括号出栈，继续操作；否则，表明 不匹配，停止操作。 （3）当表达式全部扫描完毕，若栈为空，说明括号匹配，否则表明“左括弧”有多余的。
出队
a1 a2 a3 a4 a5
入队
队列图示
4.队列的应用
5. 在队列上进行的基本运算
（1）队列初始化initQueue（q）：构造一个空队列。 （2）判队空emptyQueue（q）：若q为空队则返回为1，否
则返回为0。
（3）入队enQueue（q，x）：对已存在的队列q，插入一个元素x
到队尾，队发生变化。
队列中元素个数的计算公式。
（4）出队deQueue（q，x）：删除队头元素，并通过x返回其值，
队发生变化。
（5）读队头元素frontQueue（q）：读队头元素，并返回其值，
队不变。
3.2.2 顺序队列及运算的实现
采用顺序方法存储的队列称为顺序队列（sequential queue）
顺序队列的存储结构用c语言定义如下：
#define MAXSIZE 1024
运算受限的线性 表
表两端插删
不改变栈的状态。
4.栈的存储 （1）采用顺序方式存储的栈称为顺序栈（sequential stack） （2） 采用链接方式存储的栈称为链栈（linked stack）
3.1.2 顺序栈及运算的算法实现
用栈来实现括号匹配检查的原则是，对表达式从左到右扫描。 （1）当遇到左括号时，左括号入栈； （2）当遇到右括号时，首先检查栈是否空，若栈空，则表明该“右括弧”多余；否则比 较栈顶左括号是否与当前右括号匹配，若匹配，将栈顶左括号出栈，继续操作；否则，表明 不匹配，停止操作。 （3）当表达式全部扫描完毕，若栈为空，说明括号匹配，否则表明“左括弧”有多余的。
出队
a1 a2 a3 a4 a5
入队
队列图示
4.队列的应用
5. 在队列上进行的基本运算
（1）队列初始化initQueue（q）：构造一个空队列。 （2）判队空emptyQueue（q）：若q为空队则返回为1，否
则返回为0。
（3）入队enQueue（q，x）：对已存在的队列q，插入一个元素x
到队尾，队发生变化。
队列中元素个数的计算公式。
（4）出队deQueue（q，x）：删除队头元素，并通过x返回其值，
队发生变化。
（5）读队头元素frontQueue（q）：读队头元素，并返回其值，
队不变。
3.2.2 顺序队列及运算的实现
采用顺序方法存储的队列称为顺序队列（sequential queue）
顺序队列的存储结构用c语言定义如下：
#define MAXSIZE 1024
运算受限的线性 表
表两端插删
第3章数据结构栈和队列
第3章数据结构栈和队列数据结构是计算机科学中重要的基础知识之一，它是用于组织和管理数据的方法。
栈和队列是其中两种常见的数据结构，它们分别以后进先出（Last In First Out，LIFO）和先进先出（First In First Out，FIFO）的方式操作数据。
本文将详细介绍栈和队列的概念、特点以及应用。
一、栈栈是一种限制仅在表尾进行插入和删除操作的线性表。
插入和删除操作称为入栈和出栈，即数据项的入栈相当于把数据项放入栈顶，而数据项的出栈相当于从栈顶移除数据项。
栈具有后进先出的特点，即后入栈的数据项先出栈，而最先入栈的数据项最后出栈。
类比现实生活中的例子就是一叠盘子，我们只能从最上面取盘子或放盘子。
栈的实现方式有两种：基于数组和基于链表。
基于数组的栈实现相对简单，通过一个数组和一个指向栈顶的指针来完成栈的操作。
基于链表的栈实现则需要定义一个节点结构，每个节点包含一个数据域和一个指向下一个节点的指针，通过头指针来操作栈。
栈的应用非常广泛，比如浏览器中的返回功能就是通过栈来实现的。
当我们点击浏览器的返回按钮时，当前页面会入栈，点击前进按钮时，当前页面会出栈。
在编程中，栈也被广泛应用，比如函数调用栈用于存储函数调用的上下文信息。
二、队列队列是一种限制仅在表头删除和在表尾插入的线性表。
表头删除操作称为出队列，表尾插入操作称为入队列。
和栈不同，队列采用先进先出的原则，即最先入队列的元素最先出队列。
队列的实现方式也有两种：基于数组和基于链表。
基于数组的队列实现和栈类似，通过一个数组和两个指针（一个指向队头，一个指向队尾）来完成队列的操作。
基于链表的队列实现则需要定义一个节点结构，每个节点包含一个数据域和一个指向下一个节点的指针，通过头指针和尾指针来操作队列。
队列同样具有广泛的应用，比如操作系统中的进程调度就是通过队列来实现的。
CPU会按照进程到达的顺序，依次从队列中取出进程进行执行。
在编程中，队列也常用于解决一些需要按顺序处理数据的问题。
栈和队列
2. 栈的顺序存储
顺序栈：栈的顺序存储结构简称为顺序栈，即利 用一组地址连续的存储单元依次存放从栈底到栈 顶的数据元素。
如何改造数组实现栈的顺序存储？
top an … a3 a2 a1
栈顶 栈底
a1
栈底
a1
确定用数组的低端表示栈底，并 利用空间分配时的初始指针base 来指示栈底位置 附设指针top指示栈顶元素在数组 中的位置
利用堆栈保存调用前后程序的上下文，恢复时一层 层弹出。
主程序 r 子程序1 s 子程序2 t 子程序3
中缀表达式：运算符写在操作数之间。 后缀表达式：运算符紧跟在它所操作的操作数之后 ，求值过程自左到右，每遇一个运算符，就取其左 边的两个操作数进行运算。 例： 中缀表达式 后缀表达式
栈顶指针指向栈顶元素
入栈：*++s.top=e; 或： s.top++; *s.top=e; 出栈: e=*s.top--;
10
status Push(Sqstack &s, Selemtype e) { if (s.top-s.base>=s.stacksize) //是否栈满？避免上溢 { s.base=(SElemType *)realloc(s.base, (s.tacksize+Stackincrement)*sizeof(SElemType)); if(!s.base) exit(OVERFLOW); s.top=s.base+s.stacksize; s.stacksize+=Stackincrement; } *s.top++=e; return OK; } 注意边界条件：上溢和下溢 status Pop(Sqstack &s,Selemtype &e) { if (s.top==s.base) return ERROR; //是否栈空？避免下溢 e=*--s.top; return Ok; }
数据结构第三章栈和队列
性能比较与选择依据
性能比较
栈和队列的时间复杂度均为O(1)，空间复杂度均为O(n)。在实际应用中，栈通常用于 需要后进先出（LIFO）的场景，而队列则用于需要先进先出（FIFO）的场景。
选择依据
在选择使用栈还是队列时，应根据具体需求和应用场景进行判断。如果需要后进先出的 特性，应选择栈；如果需要先进先出的特性，则应选择队列。同时，还需要考虑数据结
栈中的元素只能在栈顶进行插入和删 除操作。
栈具有记忆功能，能保存数据元素进 入栈的先后顺序。
栈的基本操作
01
入栈（Push）：在栈顶 插入一个元素。
02
出栈（Pop）：删除栈 顶元素并返回其值。
03
查看栈顶元素（Top） ：返回栈顶元素的值， 但不删除该元素。
04
判断栈是否为空（ IsEmpty）：检查栈中 是否还有元素。
回溯到上一个状态。
广度优先搜索中的队列应用
搜索队列
广度优先搜索使用队列来保存待 搜索的节点，按照先进先出的原
则进行搜索。
状态转移
在广度优先搜索中，队列用于保存 状态转移的信息，以便在搜索过程 中根据状态转移规则进行状态的扩 展和搜索。
最短路径问题
广度优先搜索可用于解决最短路径 问题，通过队列保存待访问的节点 ，并按照距离起始节点的远近进行 排序和访问。
其他算法中的栈和队列应用
深度优先搜索
在深度优先搜索中，栈用于保存当前路径的状态信息，以便在需要时 回溯到上一个状态。
括号匹配问题
栈可用于解决括号匹配问题，遇到左括号时将其压入栈中，遇到右括 号时从栈中弹出左括号并判断是否匹配。
表达式求值
栈可用于表达式求值中，保存操作数和运算符，并按照运算优先级进 行求值。
chapter03栈和队列课件PPT
队列为空：判断队列是 否为空，返回一个布尔 值。
队列满：判断队列是否 已满，返回一个布尔值。
队列的性质和应用
队列的性质
队列具有先进先出的特性，即最早进 入队列的元素将最先被删除。
队列的应用
队列在计算机科学中被广泛应用于各 种场景，如任务调度、缓冲处理、事 件处理等。
04
栈和队列的比较与选择
栈和队列的异同点
相同点 都是线性数据结构
都有后进先出（LIFO）的特性
栈和队列的异同点
01
不同点
02
栈只允许在固定的一端（称为栈顶）进行插入和删除操作，而队列允 许在两端进行操作。
03
栈中的元素必须按照先进后出的顺序进行操作，而队列中的元素则按 照先进先出的顺序进行操作。
04
栈主要用于实现递归、括号匹配等算法，而队列主要用于实现生产者 消费者模型、打印机的打印队列等应用。
课件：Chapter03栈和队列
• 引言 • 栈的概念和操作 • 队列的概念和操作 • 栈和队列的比较与选择 • 总结与回顾
01
引言
主题简介
栈和队列是两种常见的数据结构，在 计算机科学和编程中有着广泛的应用。
队列是一种先进先出（FIFO）的数据 结构，用于存储元素的集合，其中新 元素总是添加到队列尾部，而删除操 作总是在队列头部进行。
展望
后续课程将介绍更多数据结构和算法，如链表、树、图等， 这些数据结构在计算机科学中有着广泛的应用。建议学生提 前预习相关内容，为后续课程打下坚实的基础。
THANKS
感谢观看
栈是一种后进先出（LIFO）的数据结 构，用于存储元素的集合，其中新元 素总是添加到栈顶，而删除操作总是 在栈顶进行。
课程目标和意义
教学课件第三章栈和队列
A( ){ …
B( ) { …
C( ) { …
A( ) ;
C( );
B( );
… }
… }
… }
A 直接调用自己
B间接调用自己
递归算法的编写 1）将问题用递归的方式描述（定义） 2）根据问题的递归描述（定义）编写递归算法
问题的递归描述（定义） 递归定义包括两项 基本项（终止项）：描述递归终止时问题的求解； 递归项：将问题分解为与原问题性质相同，但规模较小 的问题；
}
top
f(1) 1
f(1)=1
f(2) 2*f(1) f(2)=2*f(1)
f(3) 3*f(2) f(3)=3*f(2)
f(4) 4*f(3) f(4)=4*f(3)
f(5) 5*f(4) f(5)=5*f(4)
例2 递归的执行情况分析
void print(int w) { int i;
if ( w!=0) { print(w-1);
（LIFO）。
a2
栈的特点
a1
后进先出(LIFO)
栈的示意图
栈在函数嵌套调用中的应用：
主函数 a 函数
b 函数
c 函数
r
s
t
函数的嵌套调用与返回
t
s
s
s
r
r
r
r
r
(a) 调用a函数, r进栈 (c) 调用c函数,t进栈 (e) 返回a函数,s退栈 (b) 调用b函数,s进栈 (d) 返回b函数,t退栈 (f) 返回主程序,r退栈
1
m
栈1底
栈1顶
栈2顶
栈2底
常采用将两个栈底设在可用空间的两端。
仅当两个栈顶相遇时，才产生上溢，即所有可用空间已用完。对 每个栈可用的最大空间就可能大于整个可用空间的一半m/2。
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
第三章栈和队列
3.1 栈 3.2 栈的应用 3.3 栈与递归的实现 3.4 队列
出站
入站 火车站
•栈的抽象数据类型
ADT Stack {数据对象:D ={a i∣a i ∈ElemSet, i= 1,2,…,n, n≥0} 数据关系: R = {< a i-1 , a i > ∣ a i-1 , a i ∈D, i = 2,…,n }
int StackLength(SqStack S);
∥返回S的元素个数,即栈的长度
Status GetTop(SqStack S, SElemType &e);
∥若栈不空,则用e返回S的栈顶元素,并返回OK; 否则返回ERROR
Status Push(SqStack &S, SElemType e);
路径中最先被删除的位置是最近搜索过的 利用栈存放路径
设定当前位置的初值为入口位置; do{
若当前位置可通, { 将当前位置入栈; 切换当前位置的东邻方块为新的当前位置; }
若当前位置不可通, {出栈 找到下一个可能通的位置
} }while(栈不空)
设定当前位置的初值为入口位置;
do{
若当前位置可通,
StackTraverse(S, visit( ))；
初始条件:栈S已存在且非空. 操作结果:从栈底到栈顶依次对S的每个数据元素调用函数visit().
一旦visit()失败, 则操作失效.
}ADT Stack
InitStack(&S)；
DestroyStack(&S)；
ClearStack(&S)；
Status InitStack(SqStack &S);
∥构造一个空栈S
Status DestroyStack(SqStack &S);
∥销毁栈S,S不在存在
Status ClearStack(SqStack &S);
∥把S置为空栈
Status StackEmpty(SqStack S);
∥若栈S为空栈,则返回TRUE,否则返回FALSE
{ ∥栈满,追加存储空间
S.base = (SElemType*)realloc(S.base, (S.stacksize+
STACKINCREMENT)*sizeof(SElemType));
if(!S.base)exit(OVERFLOW);
∥存储分配失败
S.top = S.base + S.stacksize;
∥存储分配失败
S.top = S.base;
S.stacksize = STACK_INIT_SIZE;
return OK;
}∥InitStack
100
top base
Status GetTop(SqStack S, SElemType &e) {∥若栈不空,则用e返回S的栈顶元素,并返回OK;
∥否则返回ERROR
S.stacksize +=STACKINCREMENT;
}
*S.top++ = e;
top
return OK;
top
e
e
}∥Push
base
Status Pop(SqStack &S,SElemType &e)
{ ∥若栈不空,则删除S的栈顶元素,用e返回其值,并返回OK;否则返回ERROR;
if(S.top==S.base) return ERROR;
{ ∥当前位置可以通过,即是未曾走到过的通道块
FootPrint(curpos);
∥留下足迹
e = (curstep,curpos,1);
Push(S,e);
∥加入路径
if(curpos==end) return(TRUE);
∥到达终点(出口)
curpos = NextPos(curpos,1); 一位置是当前位置的东邻
SElemType *top; int stacksize; }SqStack;
3·顺序栈的实现
∥ –––––栈的顺序存储表示 ––––– #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10
∥存储空间初始分配 ∥存储空间分配增量
∥––––– 基本操作的函数原型说明 –––––
while(N)
{ Push(S, N%8); N = N/8; }
while(!StatckEmpty(S))
{ Pop(S,e); printf("%d",e)； }
}∥conversion
二、 括号匹配
输入一个符号串，判断其中圆括号和方括号是否匹配
(ab[hj](f[h(j)k]gh))
算法思想： (1)凡出现左括号，则进栈 (2)凡出现右括号，首先检查栈是否空
一、数制转换 二、 括号匹配 三、 行编辑 四、迷宫求解 五、 表达式求值
一、数制转换
对于输入的任意一个非负十进制整数 打印输出与其等值的八进制数
4107 513 64
3余
八
1数 产
0生
进 制 输 出
8
0顺
顺
1
序
序
1
0
void conversion ( )
{ InitStack(S);
∥建空栈
scanf(&N);
if (S.top ==S.base) return ERROR; e = *(S.top-1); return OK; }∥GetTop
top
e
base
Status Push (SqStack &S,SElemType e)
{ ∥插入元素e为新的栈顶元素
if(S.top-S.base>=S.stacksize)
{ int x,y;
}PosType; ∥坐标
typedef struct
{ int
ord;
∥通道块在路径上的"序号"
PosType seat; ∥通道块在迷宫中的"坐标位置"
int
di;
∥从此通道块走向下一通道块的"方向"
}SElemType;
∥栈的元素类型
FootPrint(curpos); //记录位置curpos已经搜索过
(b)若是界限符或运算符，
则与OPTR栈内运算符比较优先级，
若栈内高，
则从OPTR弹出运算符，
并OPND从弹出相应个数的操作数进行运算，
将运算结果压入OPND栈
否则，将读入的运算符压入OPTR栈
(3) 重复(2)，直到读入‘#’且栈顶为‘#’为止
OperandType EvaluateExpression( ) { ∥算术表达式求值的算符优先算法, OP为运算符集合
PosType end)
{ ∥若迷宫maze中存在从入口start到出口end的通道,则求得一条存放在栈中
∥(从栈底到栈顶),并返回TRUE;否则返回FALSE
InitStack(S); curpos = start; ∥设定"当前位置"为"入口位置"
curstep = 1;
∥探索第一步
do
{ if(Pass(curpos))
//设OPTR和OPND分别为运算符栈和运算数栈
InitStack(OPTR); Push(OPTR,'#'); InitStack(OPND); c = getchar( ); while(c!='#'‖GetTop(OPTR)!='#') { if (!In(c,OP)) {Push((OPND,c);c = getchar( ); }
e = * --S.top;
return OK; }∥Pop
top
top
e
base
4．栈式链 *top为首元结点，做栈顶 链式栈是在表头进行插入删除操作的链
top
a5
a4
a3
a2 a1
头结点?
三、 多个栈共享空间 1．两个栈共享空间
base1
top1
2．多个栈共享空间
top2
base2
3．2栈的应用
Pass(curpos)
//返回位置curpos是否可通(搜索过)
NextPos(curpos,i); //返回从位置curpos按方向i到达的新位置
MarkPrint(curpos); //记录位置curpos4个方向都搜索过不可通
Status MazePath (MazeType maze, PosType start,
∥ –––––基本操作的算法描述(部分)–––––
Status InitStack(SqStack &S)
{ ∥构造一个空栈S
S.base=(SElemType*) malloc(STACK_INIT_SIZE
*sizeof(SElemType));
if (!S.base) exit(OVERFLOW);
则{ 将当前位置入栈;
∥纳入路径
若该位置是出口位置,则结束; ∥求得路径存放在栈中
否则切换当前位置的东邻方块为新的当前位置;
}
否则
若栈不空
{ 出栈e 若e的四周均不可通(或探索过)则继续出栈 若e尚有其他方向未经探索 沿顺时针方向找到新的当前位置
}
}while(栈不空)
typedef struct
{ e.di++; Push (S,e);
∥换下一个方向探索
curpos = NextPos(e.seat, e.di);
3.1 栈 3.2 栈的应用 3.3 栈与递归的实现 3.4 队列
出站
入站 火车站
•栈的抽象数据类型
ADT Stack {数据对象:D ={a i∣a i ∈ElemSet, i= 1,2,…,n, n≥0} 数据关系: R = {< a i-1 , a i > ∣ a i-1 , a i ∈D, i = 2,…,n }
int StackLength(SqStack S);
∥返回S的元素个数,即栈的长度
Status GetTop(SqStack S, SElemType &e);
∥若栈不空,则用e返回S的栈顶元素,并返回OK; 否则返回ERROR
Status Push(SqStack &S, SElemType e);
路径中最先被删除的位置是最近搜索过的 利用栈存放路径
设定当前位置的初值为入口位置; do{
若当前位置可通, { 将当前位置入栈; 切换当前位置的东邻方块为新的当前位置; }
若当前位置不可通, {出栈 找到下一个可能通的位置
} }while(栈不空)
设定当前位置的初值为入口位置;
do{
若当前位置可通,
StackTraverse(S, visit( ))；
初始条件:栈S已存在且非空. 操作结果:从栈底到栈顶依次对S的每个数据元素调用函数visit().
一旦visit()失败, 则操作失效.
}ADT Stack
InitStack(&S)；
DestroyStack(&S)；
ClearStack(&S)；
Status InitStack(SqStack &S);
∥构造一个空栈S
Status DestroyStack(SqStack &S);
∥销毁栈S,S不在存在
Status ClearStack(SqStack &S);
∥把S置为空栈
Status StackEmpty(SqStack S);
∥若栈S为空栈,则返回TRUE,否则返回FALSE
{ ∥栈满,追加存储空间
S.base = (SElemType*)realloc(S.base, (S.stacksize+
STACKINCREMENT)*sizeof(SElemType));
if(!S.base)exit(OVERFLOW);
∥存储分配失败
S.top = S.base + S.stacksize;
∥存储分配失败
S.top = S.base;
S.stacksize = STACK_INIT_SIZE;
return OK;
}∥InitStack
100
top base
Status GetTop(SqStack S, SElemType &e) {∥若栈不空,则用e返回S的栈顶元素,并返回OK;
∥否则返回ERROR
S.stacksize +=STACKINCREMENT;
}
*S.top++ = e;
top
return OK;
top
e
e
}∥Push
base
Status Pop(SqStack &S,SElemType &e)
{ ∥若栈不空,则删除S的栈顶元素,用e返回其值,并返回OK;否则返回ERROR;
if(S.top==S.base) return ERROR;
{ ∥当前位置可以通过,即是未曾走到过的通道块
FootPrint(curpos);
∥留下足迹
e = (curstep,curpos,1);
Push(S,e);
∥加入路径
if(curpos==end) return(TRUE);
∥到达终点(出口)
curpos = NextPos(curpos,1); 一位置是当前位置的东邻
SElemType *top; int stacksize; }SqStack;
3·顺序栈的实现
∥ –––––栈的顺序存储表示 ––––– #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10
∥存储空间初始分配 ∥存储空间分配增量
∥––––– 基本操作的函数原型说明 –––––
while(N)
{ Push(S, N%8); N = N/8; }
while(!StatckEmpty(S))
{ Pop(S,e); printf("%d",e)； }
}∥conversion
二、 括号匹配
输入一个符号串，判断其中圆括号和方括号是否匹配
(ab[hj](f[h(j)k]gh))
算法思想： (1)凡出现左括号，则进栈 (2)凡出现右括号，首先检查栈是否空
一、数制转换 二、 括号匹配 三、 行编辑 四、迷宫求解 五、 表达式求值
一、数制转换
对于输入的任意一个非负十进制整数 打印输出与其等值的八进制数
4107 513 64
3余
八
1数 产
0生
进 制 输 出
8
0顺
顺
1
序
序
1
0
void conversion ( )
{ InitStack(S);
∥建空栈
scanf(&N);
if (S.top ==S.base) return ERROR; e = *(S.top-1); return OK; }∥GetTop
top
e
base
Status Push (SqStack &S,SElemType e)
{ ∥插入元素e为新的栈顶元素
if(S.top-S.base>=S.stacksize)
{ int x,y;
}PosType; ∥坐标
typedef struct
{ int
ord;
∥通道块在路径上的"序号"
PosType seat; ∥通道块在迷宫中的"坐标位置"
int
di;
∥从此通道块走向下一通道块的"方向"
}SElemType;
∥栈的元素类型
FootPrint(curpos); //记录位置curpos已经搜索过
(b)若是界限符或运算符，
则与OPTR栈内运算符比较优先级，
若栈内高，
则从OPTR弹出运算符，
并OPND从弹出相应个数的操作数进行运算，
将运算结果压入OPND栈
否则，将读入的运算符压入OPTR栈
(3) 重复(2)，直到读入‘#’且栈顶为‘#’为止
OperandType EvaluateExpression( ) { ∥算术表达式求值的算符优先算法, OP为运算符集合
PosType end)
{ ∥若迷宫maze中存在从入口start到出口end的通道,则求得一条存放在栈中
∥(从栈底到栈顶),并返回TRUE;否则返回FALSE
InitStack(S); curpos = start; ∥设定"当前位置"为"入口位置"
curstep = 1;
∥探索第一步
do
{ if(Pass(curpos))
//设OPTR和OPND分别为运算符栈和运算数栈
InitStack(OPTR); Push(OPTR,'#'); InitStack(OPND); c = getchar( ); while(c!='#'‖GetTop(OPTR)!='#') { if (!In(c,OP)) {Push((OPND,c);c = getchar( ); }
e = * --S.top;
return OK; }∥Pop
top
top
e
base
4．栈式链 *top为首元结点，做栈顶 链式栈是在表头进行插入删除操作的链
top
a5
a4
a3
a2 a1
头结点?
三、 多个栈共享空间 1．两个栈共享空间
base1
top1
2．多个栈共享空间
top2
base2
3．2栈的应用
Pass(curpos)
//返回位置curpos是否可通(搜索过)
NextPos(curpos,i); //返回从位置curpos按方向i到达的新位置
MarkPrint(curpos); //记录位置curpos4个方向都搜索过不可通
Status MazePath (MazeType maze, PosType start,
∥ –––––基本操作的算法描述(部分)–––––
Status InitStack(SqStack &S)
{ ∥构造一个空栈S
S.base=(SElemType*) malloc(STACK_INIT_SIZE
*sizeof(SElemType));
if (!S.base) exit(OVERFLOW);
则{ 将当前位置入栈;
∥纳入路径
若该位置是出口位置,则结束; ∥求得路径存放在栈中
否则切换当前位置的东邻方块为新的当前位置;
}
否则
若栈不空
{ 出栈e 若e的四周均不可通(或探索过)则继续出栈 若e尚有其他方向未经探索 沿顺时针方向找到新的当前位置
}
}while(栈不空)
typedef struct
{ e.di++; Push (S,e);
∥换下一个方向探索
curpos = NextPos(e.seat, e.di);