数据结构(二)

数据结构(二)栈和队列栈的定义•栈（stack）又叫堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。•在日常生活中，有许多类似栈的例子，如刷洗盘子时，把洗净的盘子一个接一个地向上放（相当于进栈），取用盘子时，则从上面一个接一个地向下拿（相当于出栈）；又如向自动步枪的弹夹装子弹时，子弹被一个接一个地压入（相当于进栈），射击时总是后压入的先射出（相当于出栈）。•由于栈的插入和删除运算仅在栈顶一端进行，后进栈的元素必定先被删除，所以又把栈称作后进先出表（LastInFirstOut，简称LIFO）。栈的顺序存储•栈的一种最简单的存储结构当然也是顺序存储。因此，可把栈的顺序存储结构所使用的记录类型定义为：typestack=reordvec：array[1..m0]ofelemtype；top：Integerend其中vec域用来顺序存储栈的元素，top域用来存储栈顶元素所在单元的编号（即下标），所以又把top称为栈顶指针，m0表示栈能够达到的最大深度（即长度）。设一个栈为T=（1,2,3,4），栈T所对应的顺序存储结构如图1（a）所示，若在T中插入一个元素5或删除一个元素，则分别对应的顺序存储结构如图1（b）和（c）所示。在栈的顺序存储结构中，为形象地使栈顶在上，栈底在下，所以采用的单元编号是向上递增的。栈的运算•栈的运算主要是插入和删除，除此之外，还有读取栈顶元素、置空栈和判断一个栈是否为空等。栈的运算都比较简单，具体列出如下：1、进栈（push），即向栈顶插入一个新元素；2、出栈（pop），即删除栈顶元素；3、读取栈顶元素（readtop）；4、置空栈（setnull）；5、判断一个栈是否为空（empty）。栈的应用举例栈在计算机科学领域具有广泛地应用。比如，在编译和运行计算机语言程序的过程中，就需要利用栈进行语法检查（如检查begin和end、“（”和“）”、“[”和“]”是否配对等）、计算表达式的值、实现递归过程和函数的调用等。下面举例说明栈在这些方面的应用。表达式的计算队列•队列的定义队列（queue）简称队，它也是一种运算受限的线性表，其限制是仅允许在表的一端进行插入，而在表的另一端进行删除。我们把进行插入的一端称作队尾（rear），进行删除的一端称作队首（front）。向队列中插入新元素称作进队或入队，新元素进队后就成为新的队尾元素；从队列中删除元素称作出队，出队后，其后继元素成为队首元素。由于队列的插入和删除分别在表的两端进行，所以要删除的元素是队列中最先进入的元素，因此又把队列称作先进先出（FirstInFirstOut，简称FIFO）表。队列的顺序存储队列的一种最简单的存储结构当然也是顺序存储，所使用的记录类型可定义为typequeue=recordvec:array[1..m0]ofelemtype；f，r:integerend；其中vec域用来存储队列的元素，f和r域分别用来存储队首元素和队尾元素所在单元的编号，因此又把f和r分别称作队首指针和队尾指针。队列的运算1、插入算法•insert（Q，x）ifQ.r=m0thenerror（‘overflow’）Q.rQ.r+1{队尾指针后移}Q.vec[Q.r]x{新元素赋给队尾单元）ifQ.f=0thenQ.f1（若原为空队，则进行插入后，同时把队首指针置为1}2、删除算法此算法既可写成过程的形式，也可写成函数的形式，若写成过程的形式为：•delete（Q，x）ifQ.f=0thenerror（‘underflow’）xQ.vec[Q.f]（把队首元素赋给x）ifQ.f=Q.rthenQ.f0Q.r0elseQ.fQ.f+13、置空队算法此算法很简单，只要把队首和队尾指针均赋0即可。•setnull（Q）Q.f0Q.r0队列的应用举例•例题合并石子小Ray在河边玩耍，无意中发现一些很漂亮的石子堆，于是他决定把这些石子搬回家。河滩上一共有n（1≤n≤30000）堆石子，每次小Ray合并两个石子数最少的两堆石子成为一堆。经过n-1次合并操作以后，只剩下一堆石子，然后小Ray就将这一堆石子搬回家。每合并两堆石子的时候，小Ray消耗的体力是两堆石子的数量之和。请你算一算，小Ray合并所有石子堆消耗的体力是多少呢。•解析：设这些石子堆的数量为w1、w2、……、wn，且满足:w1≤w2≤...≤wn。首先小Ray肯定将1和2两堆石子合并，设新合并的石子堆为y1=w1+w2。接着小Ray一定是在{y1}∪{w3...wn}中选择两个最小的石子堆合并，那么设新合并的石子堆为y2。如此类推，第三次合并的石子堆记作y3，第四次合并的记作y4……第n-1次合并的石子堆记作yn-1。可以证明，新合并的石子堆的大小一定满足：y1≤y2≤y3≤...≤yn-1。因为每次合并的新石子堆一定是选择当前所剩下的石子堆中最小的两堆合并，而剩下的石子堆的石子数量又是不断增多的，所以越早合并的石子堆的石子数量越少。有了上面这条事实，我们知道在合并过程中w和y数组始终是保持有序的。因此假设当前剩下的石子堆为wi...wn和yj...ym，那么最小的石子堆不是wi就是yj，拿出其中最小的一个，然后再拿出次小的一个，合并成新的石子堆一定是放在ym之后。也就是说将y看成一个队列，在队首取出元素，在队尾插入元素，且在插入和删除的过程队列始终保证了从小到大的顺序（越靠近队首越小）。由于w中的每个元素最多删除一次，y中的元素最多插入队列和从队列中取出一次，所以总的复杂度为O（n）。例题马的遍历在一个n×n的棋盘上有一匹马站在第x行第y列的格子上。棋盘上有些格子有障碍物，用’*’表示，马是不能够站在有障碍物的格子上。问：马按照国际象棋中的走法能够到达棋盘上的哪些格子，且到达这些格子最少的步数是多少。马在国际象棋中的走法如下：如果马站在（x,y）上，那么马可以走到的格子是（x+2,y+1）,（x+2,y-1）,（x+1,y+2）,（x+1,y-2）,（x-1,y+2）,（x-1,y-2）,（x-2,y+1）,（x-2,y-1）。具体如图所示：•输入：第一行为n,x,y，接下来n行为棋盘的描述。’_’表示空格子，’*’表示有障碍物。•输出：一共n行，每行n个数，表示马到这个格子最少需要的步数，如果无法到达用-1表示。•解析：这种遍历很容易用队列实现。首先队列中只有（x,y）这个点，然后从（x,y）这个点扩展，看下一步能够达到哪些点，如果这些点没有到扩展过（即没有加入队列），那么就把这些点加入到队尾。显然，扩展的格子在队列中是按照到达的最少步数从小到大的顺序排列的。在实现的过程中，我们需要一个队列存下这些已扩展的格子，还要用一个数组标记某个格子是否扩展过且到达的最少步数是多少。•算法的伪代码如下：map——表示棋盘的类型dis——表示到达棋盘上每个格子的最少步数,一开始除了起始点，都为-1（sx,sy）——马的起始位置queue——存储已扩展格子的队列h——队首指针t——队尾指针•TourOfHorse（sx,sy,map）h0t1queue[t]（sx,sy）dix[sx,sy]-1whilehtdohh+1（x,y）queue[h]fordir1to8do（tx,ty）（x,y）在dir方向的下一步能够到达的格子if（map[tx,ty]=‘_’）and（dis[tx,ty]=-1）thendis[tx,ty]dis[x,y]+1tt+1queue[t]（tx,ty）return（dis）这种按照达到步数（或者说层次）从小到大扩展的方法我们通常叫做广度优先遍历。