栈和队列及其应用7.doc

1、栈和队列及其应用栈和队列通常用来存储程序执行期间产生的一些临时信息。 这两种特殊表结构的共同特点是， 只做插入和删除， 不做查找，而且所有的插入和删除只在端点进行。栈是一种特殊的表结构，满足先进后出策略（LIFO:last in first out栈的插入和删除操作只在同一端点进行。可以进行插入的端点叫栈顶(top) ，另一个端点叫栈底 (bottom) 。）,栈的插入操作又叫进栈 (push) 或压栈，栈删除操作又叫退栈(pop) 或出栈。栈的结构示意图注意：进栈和退栈可以不定期地、反复交替进行。生活中类似栈的应用的例子：装药片的小圆桶，军用子弹卡等。思考：假设有编号为 1，2，3 的 3

2、辆车，如果按照编号为 1，2，3 的顺序入栈，那么可能的出栈顺序有几种情况？栈的存储方式：1. 顺序存储2. 链式存储栈的常见操作（顺序存储方式实现）数组 sM 存储一个栈（ M代表栈的容量），top 变量指示栈顶指针（下标） 。M=6时：进栈算法：/ 宏定义#define M 6#define EMPTY -1void pushs(int s,int&top)int x,k;coutx;if(top=M-1)cout 栈已经满，进栈失败 !endl;return;/s+top;top+;stop=x;coutx已成功进栈 !endl;出栈算法：void pops(int s,int&top)

3、int x,k;if(top=EMPTY)cout栈已经空，退栈失败 !endl;return ;/x=stop-;x=stop;top-;cout已退栈顶元素 xendl;课堂实践：结合入栈和出栈算法完成入栈、出栈、显示栈的当前元素程序(stack.cpp)。队又称为队列， 是一种特殊的表结构， 满足先来先服务策略 （FIFO:first in first out ） , 队的插入和删除只在两个端点进行。允许插入的一端交队尾（last ）, 允许删除的一端叫队头 (first)。队的插入和删除操作分别称为进队和出队。队结构示意图生活中队的例子很多：排队上车或购物等。同栈的结构一样，进队和入队

4、操作是不定期地、反复地进行的。队的存储方式：1. 顺序存储2. 链式存储队的常见操作（顺序存储方式实现）（详见板书）循环队列（详见板书）数据结构 - 栈和队列栈和队列的基础知识栈：栈是一种特殊的表结构，满足先进后出策略（ LIFO:last in first out）,栈的插入和删除操作只在同一端点进行。栈的常见操作：入栈、出栈（栈空和栈满的判断）队：队又称为队列， 是一种特殊的表结构， 满足先来先服务策略 （FIFO:firstinfirst out ） , 队的插入和删除只在两个端点进行。队的常见操作：入队、出队（队空、队满的判断）数据结构 -栈和队列简单应用文字输入（enter.cpp

5、）问题描述在文字输入的过程中，出现输入错误是不可避免的，所以需要给用户提供一个改正的方法。我们的方法是这样的：用 $符号表示前一个字符无效，用 #符号表示本行之前输入的所有内容无效。比如 一个 字符 串 “ abcd$bcd ”， 它的 实际 内容 是 “ abcbcd ”， 字 符串“ abc#abc$d”的实际内容是“ ad”。输入文件输入文件名： enter.in文件第一行是一个整数N（ 1N100 ），表示这个文本文件的行数。 之后 N行，每行一个长长的字符串（长度不会超过10000），其中就包括 $和 #这样的字符和一些英文字母，没有其它的字符。输出文件输出文件名： enter.out文件中有个字符串，每个字符串一行，是输入文件的最终结果。样例输入2abcd$bcdabc#abc$d样例输出abcbcdad天使之城(angel.cpp)问题描述天使城有一个火车站，每辆火车都从 A 方向驶入车站，再从 B 方向驶出车站。为了调度火车，火车站设有停放轨道，可存放 5 辆火车。已知从 A 进入车站顺序为 1、2、3 。现在给你一个调度方案，判断是否可行，如果可行，输出出站顺序。有以下几种调度方法：A. 将 A 上的头一辆车驶出 B 方向B. 将 A