下载文档原格式
第3章栈和队列一选择题1. 对于栈操作数据的原则是（）。
【青岛大学2001 五、2（2分）】A. 先进先出B. 后进先出C. 后进后出D. 不分顺序2. 在作进栈运算时,应先判别栈是否( ①),在作退栈运算时应先判别栈是否( ②)。
当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为( ③)。
为了增加内存空间的利用率和减少溢出的可能性,由两个栈共享一片连续的内存空间时,应将两栈的( ④)分别设在这片内存空间的两端,这样,当( ⑤)时，才产生上溢。
①, ②: A. 空 B. 满 C. 上溢 D. 下溢③: A. n-1 B. n C. n+1 D. n/2④: A. 长度 B. 深度 C. 栈顶 D. 栈底⑤: A. 两个栈的栈顶同时到达栈空间的中心点.B. 其中一个栈的栈顶到达栈空间的中心点.C. 两个栈的栈顶在栈空间的某一位置相遇.D. 两个栈均不空,且一个栈的栈顶到达另一个栈的栈底.【上海海运学院1997 二、1（5分）】【上海海运学院1999 二、1（5分）】3. 一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（）。
A. 不确定B. n-i+1C. iD. n-i【中山大学1999 一、9(1分)】4. 若一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素是i，则第j个输出元素是（）。
A. i-j-1B. i-jC. j-i+1D. 不确定的【武汉大学2000 二、3】5. 若已知一个栈的入栈序列是1,2,3,…,n，其输出序列为p1,p2,p3，…，p N,若p N是n，则p i是( )。
A. iB. n-iC. n-i+1D. 不确定【南京理工大学2001 一、1（1.5分）】6. 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（）A. 5 4 3 6 1 2B. 4 5 3 1 2 6C. 3 4 6 5 2 1D. 2 34 15 6【北方交通大学2001 一、3（2分）】7. 设栈的输入序列是1，2，3，4,则（）不可能是其出栈序列。
栈和队列是信息学竞赛中经常涉及的数据结构，它们在算法和程序设计中有着广泛的应用。
掌握栈和队列的基本原理和操作方法，对于参加信息学竞赛的同学来说是非常重要的。
本文将深入探讨栈和队列的相关知识点，帮助大家更好地理解和掌握这两种数据结构。
一、栈的定义与特点栈是一种先进后出（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缓存淘汰在信息学竞赛中，栈和队列的相关题目经常出现，并且有一定的难度。
中缀式和后缀式的相互转换中缀式和后缀式是数学表达式的两种常见表示方式。
中缀式是我们常见的表达式形式，例如"3 + 4 * 5"，而后缀式是将运算符放在操作数后面表示，例如"3 4 5 * +"。
将中缀式转换为后缀式可以通过使用栈和优先级规则来完成。
具体步骤如下：1. 创建一个空栈和一个空字符串后缀表达式2. 从左到右扫描中缀表达式的每个元素3. 如果遇到操作数，则将其添加到后缀表达式中4. 如果遇到运算符，则将其与栈顶运算符进行比较：- 如果栈为空或栈顶是左括号"("，则将运算符入栈- 如果运算符优先级高于栈顶运算符，则将运算符入栈- 否则，将栈顶运算符弹出并添加到后缀表达式中，直到栈为空或栈顶是左括号为止，然后将当前运算符入栈5. 如果遇到左括号"("，则将其入栈6. 如果遇到右括号")"，则将栈顶运算符弹出并添加到后缀表达式中，直到遇到左括号为止，然后将左括号弹出（左括号不添加到后缀表达式中）7. 扫描完整个中缀表达式后，将栈中剩余的运算符依次弹出并添加到后缀表达式中8. 后缀表达式即为转换结果例如，将中缀式"3 + 4 * 5"转换为后缀式的过程如下：中缀表达式： 3 + 4 * 5初始化：栈为空，后缀表达式为空扫描 3：后缀表达式：3扫描 +：栈为空，运算符入栈扫描 4：后缀表达式：3 4扫描 *：栈顶运算符优先级低于当前运算符，运算符入栈扫描 5：后缀表达式：3 4 5扫描完毕，将栈中剩余运算符弹出：后缀表达式：3 4 5 * +因此，中缀式"3 + 4 * 5"转化为后缀式"3 4 5 * +"。
将后缀式转换为中缀式可以通过使用栈和逆序扫描后缀表达式的方式来完成。
具体步骤如下：1. 创建一个空栈2. 从左到右逆序扫描后缀表达式的每个元素3. 如果遇到操作数，则将其入栈4. 如果遇到运算符，则从栈中弹出两个操作数，并将运算符与操作数组合成一个中缀表达式，并将该中缀表达式入栈5. 扫描完整个后缀表达式后，栈顶的中缀表达式即为转换结果例如，将后缀式"3 4 5 * +"转换为中缀式的过程如下：后缀表达式：3 4 5 * +初始化：栈为空从右到左逆序扫描：扫描 +：弹出操作数5和4，组合为中缀表达式"4 + 5"，入栈扫描 *：弹出操作数4和中缀表达式"4 + 5"，组合为中缀表达式"(4 + 5) * 4"，入栈扫描 3：入栈扫描完毕，栈顶的中缀表达式即为转换结果：中缀表达式："(4 + 5) * 3"因此，后缀式"3 4 5 * +"转化为中缀式"(4 + 5) * 3"。
中缀表达式转后缀表达式最难例题以下是一个较复杂的中缀表达式转后缀表达式的示例：中缀表达式：(3+4*2)/(1-5)^2^3后缀表达式：342*+15-23^^/首先，我们可以使用运算符优先级来决定操作符的顺序。
一般来说，乘法和除法的优先级最高，然后是加法和减法，最后是幂运算。
在同一优先级下，操作符从左到右处理。
接下来，我们使用一个栈来辅助转换。
按照从左到右的顺序扫描中缀表达式：1. 如果遇到数字，直接将其添加到后缀表达式中。
2. 如果遇到运算符，首先将栈顶的运算符与当前运算符进行优先级比较：- 如果栈为空，或者栈顶运算符为左括号"("，则将当前运算符直接入栈。
- 如果当前运算符的优先级高于栈顶运算符，则将当前运算符入栈。
- 如果当前运算符的优先级低于或等于栈顶运算符，则将栈顶运算符弹出并添加到后缀表达式中，然后继续比较当前运算符与新的栈顶运算符的优先级，直到当前运算符可以入栈。
3. 如果遇到左括号"("，直接将其入栈。
4. 如果遇到右括号")"，则将栈顶运算符弹出并添加到后缀表达式中，直到遇到左括号"("。
注意，左括号"("只弹出并丢弃，不添加到后缀表达式中。
5. 最后，如果中缀表达式扫描完成，但栈中仍有运算符，则依次弹出并添加到后缀表达式中。
根据上述规则，将中缀表达式“(3+4*2)/(1-5)^2^3”转换为后缀表达式的过程如下：中缀表达式: (3+4*2)/(1-5)^2^3后缀表达式:遍历字符"("，将其入栈。
中缀表达式: 3+4*2)/(1-5)^2^3后缀表达式:遍历数字"3"，将其添加到后缀表达式中。
中缀表达式: +4*2)/(1-5)^2^3后缀表达式: 3遍历字符"+"，将其入栈。
中缀表达式: 4*2)/(1-5)^2^3后缀表达式: 3遍历数字"4"，将其添加到后缀表达式中。
前缀、中缀、后缀表达式它们都是对表达式的记法，因此也被称为前缀记法、中缀记法和后缀记法。
它们之间的区别在于运算符相对与操作数的位置不同：前缀表达式的运算符位于与其相关的操作数之前；中缀和后缀同理。
举例：(3 + 4) × 5 - 6 就是中缀表达式- × + 3 4 5 6 前缀表达式3 4 + 5 × 6 - 后缀表达式中缀表达式（中缀记法）中缀表达式是一种通用的算术或逻辑公式表示方法，操作符以中缀形式处于操作数的中间。
中缀表达式是人们常用的算术表示方法。
虽然人的大脑很容易理解与分析中缀表达式，但对计算机来说中缀表达式却是很复杂的，因此计算表达式的值时，通常需要先将中缀表达式转换为前缀或后缀表达式，然后再进行求值。
对计算机来说，计算前缀或后缀表达式的值非常简单。
前缀表达式（前缀记法、波兰式）前缀表达式的运算符位于操作数之前。
前缀表达式的计算机求值：从右至左扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（栈顶元素op 次顶元素），并将结果入栈；重复上述过程直到表达式最左端，最后运算得出的值即为表达式的结果。
例如前缀表达式“- × + 3 4 5 6”：(1) 从右至左扫描，将6、5、4、3压入堆栈；(2) 遇到+运算符，因此弹出3和4（3为栈顶元素，4为次顶元素，注意与后缀表达式做比较），计算出3+4的值，得7，再将7入栈；(3) 接下来是×运算符，因此弹出7和5，计算出7×5=35，将35入栈；(4) 最后是-运算符，计算出35-6的值，即29，由此得出最终结果。
可以看出，用计算机计算前缀表达式的值是很容易的。
将中缀表达式转换为前缀表达式：遵循以下步骤：(1) 初始化两个栈：运算符栈S1和储存中间结果的栈S2；(2) 从右至左扫描中缀表达式；(3) 遇到操作数时，将其压入S2；(4) 遇到运算符时，比较其与S1栈顶运算符的优先级：(4-1) 如果S1为空，或栈顶运算符为右括号“)”，则直接将此运算符入栈；(4-2) 否则，若优先级比栈顶运算符的较高或相等，也将运算符压入S1；(4-3) 否则，将S1栈顶的运算符弹出并压入到S2中，再次转到(4-1)与S1中新的栈顶运算符相比较；(5) 遇到括号时：(5-1) 如果是右括号“)”，则直接压入S1；(5-2) 如果是左括号“(”，则依次弹出S1栈顶的运算符，并压入S2，直到遇到右括号为止，此时将这一对括号丢弃；(6) 重复步骤(2)至(5)，直到表达式的最左边；(7) 将S1中剩余的运算符依次弹出并压入S2；(8) 依次弹出S2中的元素并输出，结果即为中缀表达式对应的前缀表达式。
《数据结构与算法设计》实验报告——实验二学院：自动化学院班级：06111001学号：**********姓名：宝竞宇一、实验目的掌握栈的建立，输入，删除，出栈等基本操作。
应用栈解决实际问题。
二、实验内容实现简单计算器的功能,请按照四则运算加、减、乘、除、幂（^）和括号的优先关系和惯例，编写计算器程序。
要求支持运算符：+、-、*、/、%、（）和=：①从键盘输入一个完整的表达式，以回车作为表达式输入结束的标志；②输入表达式中的数值均为大于等于零的整数，如果中间计算过程中出现小数也只取整进行计算。
例如，输入：4+2*5= 输出：14输入：(4+2)*(2-10)= 输出：-48三、程序设计1、概要设计抽象数据类型定义：两个栈结构，分别用来储存数据和计算符号宏定义：函数“成功”，“失败的返回值”在主程序程序中先依次输入各表达式，存入相应各栈，然后，调用“判断函数”来判断计算符的优先次序，然后再利用计算函数来计算，表达式值。
其中还有，取栈顶元素函数，存入栈函数。
2、详细设计数据类型实现：struct t{ char dat[200];int top;}prt;入栈函数：存入数组，栈顶指针上移void pushd(long int a){ prd.dat[prd.top++]=a;}出栈：取出对应值，栈顶指针下移long int popd( ){ return prd.dat[--prd.top];}比较优先级：建立数组，比较返回大于小于号。
计算函数：以字符型输入，运算符号，用switch来分支计算判断，返回计算数值long int operation ( long int x, long int y, char a){ s witch(a){ case '+': return x+y;case '-': return x-y;case '*': return x*y;case '/': if ( y )return x/y;else{ printf("Divide 0.\n");return 0;}case '%': return (long int) fmod(x,y);case '^': if (y>=0 ) return (long int) pow(x,y);else return (0);default: printf("Error No. 3\n");return 0;}}主程序：在主程序内，以字符串的形式输入表达式，然后分别调用函数存入各相应栈，然后用数组判断，比较运算符的优先顺序。
取栈顶元素栈是一种常见的数据结构，它按照后进先出（LIFO）的原则工作。
栈的特点在于只能在一端进行插入和删除操作，这一端被称为栈顶。
栈顶元素指的是在栈中位于最顶端的元素。
它是最新插入到栈中的元素，也是最后一个被弹出的元素。
要取栈顶元素，可以使用栈的相关操作进行操作实现。
在大多数编程语言中，栈的操作通常包括入栈（push）、出栈（pop）、获取栈顶元素（peek）等操作。
1.入栈（push）操作：将一个新元素插入到栈的顶端，并将栈顶指针向上移动一个位置。
2.出栈（pop）操作：从栈的顶端移除一个元素，并将栈顶指针向下移动一个位置。
3.获取栈顶元素（peek）操作：返回栈顶的元素值，但不移除该元素。
取栈顶元素（peek）是一个常见的操作，常用于判断栈是否为空、获取栈顶元素的值等场景。
在编程中，我们可以通过使用编程语言提供的栈结构或自己实现一个栈，然后调用相关的方法来获取栈顶元素。
以下是一个示例，展示了如何使用Python语言实现一个栈，并取栈顶元素：```pythonclass Stack:def __init__(self):self.stack = []def push(self, item):self.stack.append(item)def pop(self):if not self.is_empty():return self.stack.pop()raise IndexError("Stack is empty!")def peek(self):if not self.is_empty(): return self.stack[-1] return Nonedef is_empty(self):return len(self.stack) == 0 #创建一个栈对象stack = Stack()#入栈操作stack.push(1)stack.push(2)stack.push(3)#获取栈顶元素top_element = stack.peek()print("栈顶元素为:", top_element)#出栈操作while not stack.is_empty():item = stack.pop()print("弹出元素:", item)```以上代码创建了一个`Stack`类，实现了入栈（`push`）、出栈（`pop`）、获取栈顶元素（`peek`）、判断栈是否为空（`is_empty`）等相关操作。
顺序栈的基本操作及应用顺序栈是一种常见的数据结构，它是一种特殊的线性表，具有先进先出的特点。
顺序栈的基本操作包括压栈、弹栈、获取栈顶元素和判断栈是否为空。
它的应用非常广泛，常见的应用场景包括表达式求值、括号匹配、浏览器的前进后退功能等。
顺序栈的基本操作之一是压栈。
当需要将数据元素插入到栈中时，我们可以通过压栈操作将其放入栈顶。
具体而言，我们需要先判断栈是否已满，若已满则无法插入元素；若未满，则将元素放入栈顶，并更新栈顶指针的位置。
压栈操作的时间复杂度为O(1)，即常数时间。
弹栈是顺序栈的另一个基本操作。
当需要从栈中删除元素时，我们可以通过弹栈操作将栈顶元素移除。
具体而言，我们需要先判断栈是否为空，若为空则无法删除元素；若不为空，则将栈顶元素移除，并更新栈顶指针的位置。
弹栈操作的时间复杂度也为O(1)。
获取栈顶元素是顺序栈的第三个基本操作。
当我们需要获取栈顶元素时，只需返回栈顶指针所指向的元素即可。
获取栈顶元素的时间复杂度为O(1)。
判断栈是否为空是顺序栈的最后一个基本操作。
当我们需要判断栈是否为空时，只需判断栈顶指针是否指向-1即可。
若栈顶指针为-1，则说明栈为空；否则，栈不为空。
顺序栈的应用非常广泛。
一种常见的应用是表达式求值。
在数学表达式的计算过程中，我们通常需要借助栈来实现运算符的优先级比较和计算。
具体而言，当遇到一个运算符时，我们可以将其压入栈中；当遇到一个数字时，我们可以将其转化为整数，并与栈顶的运算符进行运算。
通过不断地进行压栈、弹栈和计算操作，最终可以得到表达式的计算结果。
另一个常见的应用是括号匹配。
在编程中，括号的匹配是一项重要的检查工作。
我们可以借助栈来判断一个字符串中的括号是否匹配。
具体而言，当遇到一个左括号时，我们可以将其压入栈中；当遇到一个右括号时，我们可以弹出栈顶元素，并判断弹出的括号是否与当前的右括号匹配。
如果匹配，继续处理下一个字符；如果不匹配，说明括号不匹配，返回错误。
