信息学竞赛班数据结构专项培训教程——03栈和队列VIP免费

金山中学计算机竞赛班教程·数据结构3－1§3栈和队列§3.1栈栈（stack）是一种仅限于在称为栈顶（top）的一端进行插入和删除操作的线性表，另一端则被为栈底（bottom）。不含元素的空表称为空栈。栈的特点：后进先出（LastInFirstOut），简称：LIFO。栈的表示和实现和线性表类似，栈也有两种存储结构。（1）．顺序栈顺序栈即采用的顺序存储结构来表示栈，通常采用数组来实现。采用顺序栈受数组空间的约束，有“溢出”的可能，编程前应作空间估算，若有溢出可能，应作溢出判断及相应的处理。在一个程序中，常常会出现同时使用多个栈的情形。为了不因栈上溢而产生错误中断，必须给每个栈预分一个较大的空间，但这并不容易做到，因为栈实际所用的最大空间很难估计；而且各个栈的实际使用量在使用期间是变化的，往往会有这样的情况，即其中一个栈发生上溢，而另一个栈还是空的。设想，若令多个栈共享空间，则将提高空间的使用效率，并减少发生栈上溢的可能。所以，可以采用两个栈共享空间的方法：假设在程序中需设两个栈，并共享一维数组空间。则利用“栈底位置不变”的特性，可将两个栈的栈底分别设在数组空间的两端，然后各自向中间伸展（如图），仅当两个栈的栈顶相遇时才可能发生上溢。（2）．链栈采用链式存储结构的栈简称链栈。对于链栈，不含产生单个栈溢出的情况，但要记得回收结点空间（dispose（p）），否则会出现整个空间被占满，new（p）过程无法实现（即无法申请新的结点空间）的情况。出栈入栈栈顶栈底ana1a2⋯⋯栈1栈2栈1底栈1顶栈2顶栈2底金山中学计算机竞赛班教程·数据结构3－2【练习】回文串识别输入一字符串，判断它是否为一回文串。所谓回文串是指去掉其中的空格与标点符号等非字母符号后，从前后两个方向读到的串相同，例如：tenanimalsIslaminanet.（我将十只动物装在网里）输入：一字符串输出：Yes或No§3.2队列队列（queue）是所有的插入都在一端进行，而所有的删除都在另一端进行的线性表。允许插入的一端称为队尾（rear），允许删除的一端称为队头（front）。队列的特点：先进先出（|FirstInFirstOut），简称：FIFO。队列的表示和实现和栈一样，队列也有顺序存储和链式存储两种表示和实现方法。在顺序存储结构中，同样有溢出可能，即元素因队满而无法入队。对于队列来说，可以采用循环队列的技巧，仅当队头与队尾相遇时为队满。【例3.2.1】逐行打印二项展开式(a+b)i的系数：杨辉三角形(Pascal’striangle)要求：采用队列实现！输入：n——层数（n<50）25输出：如上图的数字阵列a1a2a3,,an出队列出队列队头队尾队头队尾11i=112121551314641415101051516152015616金山中学计算机竞赛班教程·数据结构3－3【算法思路】分析第i行元素与第i+1行元素的关系目的是从前一行的数据可以计算下一行的数据从第i行数据计算并存放第i+1行数据从数据结构上，可设计一个足够长的一维数组，以实现上述算法。【练习】根据上述思路分析，用队列的方法完成例3.2.1。【练习】再用二维数组，用其它方法完成例3.2.1。【练习】侦察兵队列有一个侦察班，由11人组成，其中6名是老侦察员，5名是新侦察员。一次执勤要穿越敌人的一道封锁线。根据当时的情况，队伍只能单线纵向排列，且前面第一、二人越过后，第三个人要返回报告情况，该侦察员随后编到队伍的末尾。接着第四、五人越过，第六人报告并排到末尾。依此类推。最后三人一齐顺次过去。越过封锁线后，队伍便形成老、新交替的队形。请问，穿越前队伍该怎样排？要求：采用队列实现！输出：O表示老队员，Y表示新队员金山中学计算机竞赛班教程·数据结构3－4【练习】倒水问题[问题描述]有三个分别装有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”中。第一...