下载文档原格式
数据结构实验三栈和队列的应用数据结构实验三：栈和队列的应用在计算机科学领域中，数据结构是组织和存储数据的重要方式，而栈和队列作为两种常见的数据结构，具有广泛的应用场景。
本次实验旨在深入探讨栈和队列在实际问题中的应用，加深对它们特性和操作的理解。
一、栈的应用栈是一种“后进先出”（Last In First Out，LIFO）的数据结构。
这意味着最后进入栈的元素将首先被取出。
1、表达式求值在算术表达式的求值过程中，栈发挥着重要作用。
例如，对于表达式“2 ＋ 3 4”，我们可以通过将操作数压入栈，操作符按照优先级进行处理，实现表达式的正确求值。
当遇到数字时，将其压入操作数栈；遇到操作符时，从操作数栈中弹出相应数量的操作数进行计算，将结果压回操作数栈。
最终，操作数栈中的唯一值就是表达式的结果。
2、括号匹配在程序代码中，检查括号是否匹配是常见的任务。
可以使用栈来实现。
遍历输入的字符串，当遇到左括号时，将其压入栈；当遇到右括号时，弹出栈顶元素，如果弹出的左括号与当前右括号类型匹配，则继续，否则表示括号不匹配。
3、函数调用和递归在程序执行过程中，函数的调用和递归都依赖于栈。
当调用一个函数时，当前的执行环境（包括局部变量、返回地址等）被压入栈中。
当函数返回时，从栈中弹出之前保存的环境，继续之前的执行。
递归函数的执行也是通过栈来实现的，每次递归调用都会在栈中保存当前的状态，直到递归结束，依次从栈中恢复状态。
二、队列的应用队列是一种“先进先出”（First In First Out，FIFO）的数据结构。
1、排队系统在现实生活中的各种排队场景，如银行排队、餐厅叫号等，可以用队列来模拟。
新到达的顾客加入队列尾部，服务完成的顾客从队列头部离开。
通过这种方式，保证了先来的顾客先得到服务，体现了公平性。
2、广度优先搜索在图的遍历算法中，广度优先搜索（BreadthFirst Search，BFS）常使用队列。
从起始节点开始，将其放入队列。
栈和队列是信息学竞赛中经常涉及的数据结构，它们在算法和程序设计中有着广泛的应用。
掌握栈和队列的基本原理和操作方法，对于参加信息学竞赛的同学来说是非常重要的。
本文将深入探讨栈和队列的相关知识点，帮助大家更好地理解和掌握这两种数据结构。
一、栈的定义与特点栈是一种先进后出（LIFO）的数据结构，它的特点是只允许在栈顶进行插入和删除操作。
栈可以用数组或链表来实现，常见的操作包括压栈（push）、出栈（pop）、获取栈顶元素（top）等。
栈的应用非常广泛，比如在计算机程序中，函数的调用和返回值的存储就是通过栈来实现的。
二、栈的基本操作1. 压栈（push）：将元素压入栈顶2. 出栈（pop）：将栈顶元素弹出3. 获取栈顶元素（top）：返回栈顶元素的值，但不把它从栈中移除4. 判空：判断栈是否为空5. 获取栈的大小：返回栈中元素的个数三、栈的应用1. 括号匹配：利用栈来检查表达式中的括号是否匹配2. 表达式求值：利用栈来实现中缀表达式转换为后缀表达式，并进行求值3. 迷宫求解：利用栈来实现迷宫的路径搜索4. 回溯算法：在深度优先搜索和递归算法中，通常会用到栈来保存状态信息四、队列的定义与特点队列是一种先进先出（FIFO）的数据结构，它的特点是只允许在队尾进行插入操作，在队首进行删除操作。
队列同样可以用数组或链表来实现，常见的操作包括入队（enqueue）、出队（dequeue）、获取队首元素（front）、获取队尾元素（rear）等。
队列在计算机领域也有着广泛的应用，比如线程池、消息队列等都可以用队列来实现。
五、队列的基本操作1. 入队（enqueue）：将元素插入到队列的末尾2. 出队（dequeue）：从队列的头部删除一个元素3. 获取队首元素（front）：返回队列的头部元素的值4. 获取队尾元素（rear）：返回队列的尾部元素的值5. 判空：判断队列是否为空6. 获取队列的大小：返回队列中元素的个数六、队列的应用1. 广度优先搜索算法（BFS）：在图的搜索中，通常会用队列来实现BFS算法2. 线程池：利用队列来实现任务的调度3. 消息队列：在分布式系统中，常常会用队列来进行消息的传递4. 最近最少使用（LRU）缓存算法：利用队列实现LRU缓存淘汰在信息学竞赛中，栈和队列的相关题目经常出现，并且有一定的难度。
数据结构第三章数据结构堆栈和队列在计算机科学中，数据结构是组织和存储数据的方式，以便能够高效地访问和操作这些数据。
在数据结构的众多类型中，堆栈和队列是两种非常重要且常用的结构。
首先，让我们来了解一下堆栈。
堆栈就像是一个垂直堆放的容器，遵循着“后进先出”（Last In First Out，简称LIFO）的原则。
想象一下，你有一堆盘子，每次你把新盘子放在最上面，而当你要取盘子时，也只能从最上面拿。
这就是堆栈的工作方式。
在编程中，堆栈有着广泛的应用。
比如，函数调用就是一个典型的例子。
当一个函数调用另一个函数时，新函数的信息被压入堆栈。
当被调用的函数执行完毕后，其信息从堆栈中弹出，程序回到原来的函数继续执行。
此外，表达式求值也常常会用到堆栈。
例如，计算一个复杂的算术表达式时，可以将操作数和运算符依次压入堆栈，然后按照特定的规则进行计算。
堆栈的实现可以通过数组或者链表来完成。
如果使用数组实现，需要注意堆栈的大小可能会有限制。
而链表实现则相对灵活，但其操作的复杂度可能会略高一些。
接下来，我们再看看队列。
队列则像是一条排队的队伍，遵循“先进先出”（First In First Out，简称 FIFO）的原则。
就好比在银行排队办理业务，先来的人先得到服务并离开队伍。
在实际应用中，队列也非常有用。
例如，打印机的打印任务队列就是一个典型的例子。
新的打印任务被添加到队列的末尾，而打印机按照任务进入队列的顺序依次处理。
还有操作系统中的任务调度，也常常会用到队列来管理等待执行的任务。
队列同样可以通过数组或者链表来实现。
使用数组实现时，可能会面临队列前端元素删除后空间浪费的问题。
而链表实现虽然可以避免这个问题，但需要额外的指针操作。
那么，堆栈和队列在操作上有哪些不同呢？对于堆栈，主要的操作是入栈（push）和出栈（pop）。
入栈就是将元素添加到堆栈的顶部，出栈则是从堆栈的顶部取出元素。
而对于队列，主要的操作是入队（enqueue）和出队（dequeue）。
信息学竞赛班数据结构专项培训教程——03栈和队列栈和队列是数据结构中重要的两种线性结构，它们分别具有后进先出（Last In First Out，LIFO）和先进先出（First In First Out，FIFO）的特点。
在信息学竞赛中，掌握栈和队列的基本概念、实现方式及应用场景是非常重要的。
本文将为大家介绍栈和队列的相关知识，并讲解一些典型的应用题。
首先，我们来介绍栈。
栈是一个只允许在一端插入和删除操作的线性表，这一端被称为栈顶。
栈的插入操作称为入栈，栈的删除操作称为出栈。
由于栈的特点是后进先出，所以最后入栈的元素将是第一个出栈的元素。
栈可以用数组和链表实现。
使用数组实现栈时，需要定义一个指针top来指示当前栈顶的位置，同时需要一个数组来存放栈元素。
入栈操作相当于在数组中将元素放入top位置，并将top指针向上移动；出栈操作相当于将top所指位置的元素移出，并将top指针向下移动。
使用链表实现栈时，需要定义一个结点结构体包含数据域和指针域，指针域指向下一个结点。
入栈操作相当于在链表头部插入一个结点，并将头指针指向新的结点；出栈操作相当于将头指针指向的结点删除，并将头指针指向下一个结点。
接下来，我们来介绍队列。
队列是一个只允许在一端插入和在另一端删除的线性表，插入操作一般称为入队，删除操作一般称为出队。
队列的特点是先进先出，即第一个入队的元素将是第一个出队的元素。
队列也可以用数组和链表实现。
使用数组实现队列时，需要定义两个指针front和rear，分别指示队列的头部和尾部位置。
入队操作相当于在rear位置插入元素，并将rear指针向后移动；出队操作相当于删除front位置的元素，并将front指针向后移动。
使用链表实现队列时，需要定义一个结点结构体包含数据域和指针域，指针域指向下一个结点。
同时需要定义头指针和尾指针，分别指示队列的头部和尾部。
入队操作相当于在尾指针位置插入结点，并将尾指针移到下一个结点；出队操作相当于删除头指针指向的结点，并将头指针移到下一个结点。
§3栈和队列§3.1 栈栈（stack）是一种仅限于在称为栈顶（top）的一端进行插入和删除操作的线性表，另一端则被为栈底（bottom）。
不含元素的空表称为空栈。
栈的特点：后进先出（Last In First Out），简称：LIFO。
栈的表示和实现和线性表类似，栈也有两种存储结构。
（1）．顺序栈顺序栈即采用的顺序存储结构来表示栈，通常采用数组来实现。
采用顺序栈受数组空间的约束，有“溢出”的可能，编程前应作空间估算，若有溢出可能，应作溢出判断及相应的处理。
在一个程序中，常常会出现同时使用多个栈的情形。
为了不因栈上溢而产生错误中断，必须给每个栈预分一个较大的空间，但这并不容易做到，因为栈实际所用的最大空间很难估计；而且各个栈的实际使用量在使用期间是变化的，往往会有这样的情况，即其中一个栈发生上溢，而另一个栈还是空的。
设想，若令多个栈共享空间，则将提高空间的使用效率，并减少发生栈上溢的可能。
所以，可以采用两个栈共享空间的方法：假设在程序中需设两个栈，并共享一维数组空间。
则利用“栈底位置不变”的特性，可将两个栈的栈底分别设在数组空间的两端，然后各自向中间伸展（如图），仅当两个栈的栈顶相遇时才可能发生上溢。
（2）．链栈采用链式存储结构的栈简称链栈。
对于链栈，不含产生单个栈溢出的情况，但要记得回收结点空间（dispose（p）），否则会出现整个空间被占满，new（p）过程无法实现（即无法申请新的结点空间）的情况。
【练习】 回文串识别输入一字符串，判断它是否为一回文串。
所谓回文串是指去掉其中的空格与标点符号等非字母符号后，从前后两个方向读到的串相同，例如：ten animals I slam in a net. （我将十只动物装在网里）输入：一字符串 输出：Yes 或No§3.2 队列队列（queue ）是所有的插入都在一端进行，而所有的删除都在另一端进行的线性表。
允许插入的一端称为队尾（rear ），允许删除的一端称为队头（front ）。
队列的特点：先进先出（|First In First Out ），简称：FIFO 。
队列的表示和实现和栈一样，队列也有顺序存储和链式存储两种表示和实现方法。
在顺序存储结构中，同样有溢出可能，即元素因队满而无法入队。
对于队列来说，可以采用循环队列的技巧，仅当队头与队尾相遇时为队满。
【例3.2.1】逐行打印二项展开式 (a + b )i 的系数：杨辉三角形 (Pascal’s triangle)要求：采用队列实现！输入： n ——层数（n<50）25 a 1 a 2 a 3 …… a n出队列出队列队头 队尾 队头 队尾 1 1 i = 11 2 121 5 5 131 4 6 4 141 5 10 10 5 15 16 15 20 15 6 16【算法思路】分析第 i 行元素与第i+1行元素的关系目的是从前一行的数据可以计算下一行的数据从第 i 行数据计算并存放第 i+1 行数据从数据结构上，可设计一个足够长的一维数组，以实现上述算法。
【练习】根据上述思路分析，用队列的方法完成例3.2.1。
【练习】再用二维数组，用其它方法完成例3.2.1。
【练习】侦察兵队列有一个侦察班，由11人组成，其中6名是老侦察员，5名是新侦察员。
一次执勤要穿越敌人的一道封锁线。
根据当时的情况，队伍只能单线纵向排列，且前面第一、二人越过后，第三个人要返回报告情况，该侦察员随后编到队伍的末尾。
接着第四、五人越过，第六人报告并排到末尾。
依此类推。
最后三人一齐顺次过去。
越过封锁线后，队伍便形成老、新交替的队形。
请问，穿越前队伍该怎样排？要求：采用队列实现！输出：O表示老队员，Y表示新队员【练习】倒水问题[问题描述]有三个分别装有a升水、b升水和c升水的量筒（c>b>a>0，且b与a互质）, 如果c 筒装满水，a与b均为空筒，三个筒相互倒水且不准把水倒往三个筒之外，一个往另一个筒倒水记为一次倒水。
问是否能量出d升水(c>d>0)，若能，请求出最少的倒水次数使它能倒出容量为d的水的方案。
[输入格式]数据存放在当前目录下的文本文件“water.in”中。
文件中以一行的形式存放四个正整数，分别a、b、c、d的值。
[输出格式]答案输出到当前目录下的文本文件“water.out”中。
第一次行是最少的倒水次数Q，第二起的Q行是每次例水时量简的水量，依次为a、b、c （输入与输出数据中同一行相邻两个数之间用空格区分。
）[输入输出举例]water.in3 7 10 5water.out10 90 0 10 0 0 103 0 7 0 7 30 3 7 3 4 33 34 0 4 60 6 4 3 1 63 6 1 0 1 92 7 1 1 0 92 0 8 1 7 20 2 8 3 5 23 2 5（仅有第二组才是最优的一个解。
）§3.3 栈的应用实例§3.3.1 中缀表达式和后缀表达式对于高级语言程序中的表达式，在编译时求解用栈来实现。
任何一个表达式是由操作数（常量、常量名、变量名）、运算符（算术、关系和逻辑三种运算符）和界限符（左、右圆括号，结束符）所组成。
运算符在两个操作数之间的表达式，如a+b、e*f-d等，称为中缀表达式。
求值时，一般会有运算符号的优先权和结合权问题。
例如：a+b*c-d，我们知道b*c要先求，但编译器只能从左到有逐一检查，检查到加号时尚无法知道是否可执行，待检查到乘号时，因乘号运算优先级比加号高，所有a+b不可以被执行，待继续基础到减号时，方可执行b*c。
而后缀表达式是运算符在两个操作数之后，如ab*，也称为“逆波兰式”。
后缀表达式可以顺序计算求值，所以编译程序常把中缀表达式变换成后缀表达式，然后再求值。
下表是中缀表达式所对应的后缀表达式：(一)、将中缀表达式转换成后缀表达式在转换过程中为了确定计算次序，要按运算符的优先级进行，各运算符优先级如下表，优先级数大的先执行。
【例3.3.1】将中缀表达式转换成后缀表达式。
输入：中缀表达式，如：B * (D-C) + A输出：后缀表达式，如：BDC-*A+【算法思想】设立一个栈来实现中缀表达式变后缀表达式。
设中缀表达式在字符数组E中，E的末尾再加‘#’作为结束符，将转成后缀表达式，存于字符串A中。
对E中表达式自左向右扫描，遇数直接送到A中，若遇到运算符就考虑进栈，进栈的原则是保持栈顶的运算符优先级最高。
即若欲进栈的算符是‘( ’或欲进栈的运算符优先级大于栈顶运算符的优先级，则将算符入栈，否则从栈中退出算符送至A中，直至欲进栈的算符优先级大于栈顶算符的优先级，这时才将欲进栈的算符入栈。
若遇到‘)’时，将栈中算符退出送入A 中，直至退出‘( ’为止。
若遇表达式结束符‘#’，则依次退出栈中算符送入A 中。
根据上述算法，将中缀表达式B * (D -C) + A 转换成后缀表达式BDC -*A+ 的过程图3_1所示。
【参考程序段】const m=100;var E , A , S : array [1..m] of char;{ E 中为中缀式，A 中为后缀式，S 为栈}i , j , t : integer; procedure postexp; begini:=1; j:=1; t:=0;while E[ i ]<>’#’ do begin case E[ i ] of‘a ’.. ‘z ’, ‘A ’.. ‘Z ’ : beginA[ j ]:=E[ i ]; j:=j+1; end; ‘(’ : begint:=t+1; S[ t ]:= ‘(’; end; ‘)’ : beginwhile s[ t ]< > ‘(’ do beginA[ j ]:=s[ t ]; j:=j+1; t:=t -1; end; t:=t -1; end; ‘+’, ‘-’ : beginwhile (t< >0) and (s[t]< > ‘(’) do begin A[ j ]:=S[ t ]; j:=j+1; t:=t -1; end;t:=t+1; s[ t ]:=E[ i ]; end; ‘*’, ‘/’ : beginwhile (t< >0) and (S[ t ]= ‘*’ or S[ t ]= ‘/’) do beginA[ j ]:=S[ t ]; j:=j+1; t:=t -1;扫描E 栈S 转换至A B * B * * ( B ( * ( B D * ( - BD -* ( -BDC * BDC) + BDC -+ + BDC -*A BDC -*A# BDC -*A+ 图3_1end; {while}t:=t+1; S[ t ]:=E[ i ];end;end; {case}i:=i+1;end; {while}while t< >0 do beginA[ j ]:=S[ t ]; j:=j+1; t:=t-1;end;A[ j ]:= ‘#’;end;(二)、对后缀表达式求值计算一个后缀表达式的值，在算法上比中缀表达式要简单得多，这是因为后缀表达式有两个优点：表达式无括号，也不需考虑运算符的优先级。
【算法思想】对后缀表达式求值要使用一个栈来实现。
自左至右扫描后缀表达式，若遇数就入栈，若遇到运算符就从栈中退出两个数进行运算，并把计算结果入栈。
如此下去，直至遇到结束符“#”为止。
最后栈底元素值为所求得的结果。
【练习】将一个中缀表达式转换成后缀表达式，并对后缀表达式求值。
输入格式：（输入文件bds.in）第一行：中缀表达式，运算数均为大写字母，运算符含乘方‘^’第二行开始：每行为表达式中字母，及其对应的值，输入顺序按字典排序输出格式：（输入文件bds.out）第一行：该中缀表达式所对应的后缀表达式第二行：该表达式的值输入输出举例：§3.3.2 地图着色问题对地图着色，可使用“四染色”定理，它是计算机科学中的著名定理之一，可以用不多于四色对地图着色，使相邻的行政区域不重色。
应用这个定理的结论，利用回溯算法可对一幅给定的地图染色。
作为地图四色的示例如图 3_3所示，图中01、02、03、04、05、06、07为行政区编号，1色、2色、3色、4色为各区域的颜色，称为色数。
【算法思想】从编号为01的区域开始逐一进行染色，对每个区域用色数1，2，3，4依次进行试探，并尽可能取小色数。
若当前所取色数与周围已染色的区域不重色，则把该区的色数入栈，否则依次使用下一色数进行试探。
若从1色至4色均与相邻的某区域发生重色，则需退栈回溯，修改栈顶区域的色数。
