《算法与数据结构考研试题精析》笔记(3) - 栈与队列
Published:
by
Authur Lee
- Categories:
- Data_Structure 44
一些规律
栈
元素a,b,c,d,e依次进栈，那么，如果元素d第i个出栈，那么进栈序列d前面的a,b,c；在出栈序列中，除了在d之前已经出栈的元素外，剩下的元素必然逆序排列。如果d是第一个出栈，那么a,b,c一定会以c,b,a的顺序出栈，当然其中可能会参杂一些元素d以后的元素。
输出受限的双端队列
只能在已有队列的两侧出现新成员。
如下，如果元素a,b,c,d,e依次进入队列，那么可能得到的出队序列一定有如下操作：
a
b (a)
c (ba)
(cba) d
e (cbad)
输入受限的双端队列
输入序列为1,2,3,4,5；如何判断可能的出队序列？
如果是先全部入队然后再出队，那么就如下：
(1,2,3,4,5)
1 (2,3,4,5)
(2,3,4) 5
(2,3) 4
2 (3)
3
上面例子的出队序列：1,5,4,2,3
但是如果出队和入队两个操作可以交替进行，就脑中模拟。
俩栈共享一存储区
俩栈的栈底分别设在内存空间的两端，这样只有在栈顶指针相邻时才会产生溢出。
栈用一维数组stack(1,n)表示，两栈顶指针为top[1]与top[2]，则：
栈一为空时，top[1]=0；栈二为空时，top[2]=n+1;
栈满时，top[1] + 1 = top[2]. （或者说，两栈顶指针相减的绝对值为1；或者说，两栈顶指针相邻）
如果题中，给出了top[]之类的数据，那么就写公式，否则写后面的纯文字，二者选一。
Points
关于栈
对于Hanoi塔，n个圆盘，则总的移动次数为.
C语言标识符：点击链接跳转
队列的“先进先出”特性指的是： 【正确表述】最后插入队列中的元素总是最后被删除。 【错误表述】每次从队中删除的总是最早插入的元素。
上述的错误表述中，错误的是“最早”二字。为什么呢？ 若队列不空，每次删除的是队头元素，不是“最早”插入的元素。 最后插入的一定是队尾元素，但是最早插入的不一定是队头元素。
在算符优先级中，算符“+”和“(”优先关系是："+" < "(".
在带头结点的链队列中，队头指针指向链表的头结点。
同一组不重复输入序列执行不同的入、出栈组合操作，所得结果也可能相同。
【解释】比如说不重复序列a,b。有下面两种策略同样得到“a,b”的出栈序列： 第一种策略：a push, a pop, b push, b pop； 第二种策略：b push, a push, a pop, b pop； （输入序列的数序可以换吗？不可换序的例子想不出来）
消除递归不一定需要使用栈。
解释：尾递归的消除不需要用栈。 详细介绍见链接
【错误说法】只有那种使用了局部变量的递归过程在转换成非递归过程时才必须使用栈。
解释：使用了全局变量的也可
有n个数顺序(依次)进栈，出栈序列有Cn种，Cn=.
任何一个递归过程都可以转换成非递归过程。
在栈的ADT定义中，除初始化操作外，其他基本操作的初始条件都要求栈已存在。在进行入栈运算前，应先判别栈是否满，出栈操作判断栈是否为空。
在给出入栈顺序以及入栈出栈操作序列的题目中，我们对输出序列的回答模板：已经输出序列，不写还在栈中的序列(或者说，"栈中尚有…")
退栈是将栈顶元素赋值给某个变量，并从栈中去掉（删除）这个栈顶元素，栈中少了一个元素； 读栈顶元素时只是将栈顶元素值赋值给某个变量，但是并不去掉栈顶元素，因此栈中元素个数不变。
顺序栈用data[1…n]存储数据，栈顶指针是top，则值为x的元素入栈的操作是if(top != n) data[top++] = x.
关于循环队列
循环队列的引入，目的是为了克服假溢出时大量地移动数据。
循环队列中，除非是求长度(此时会出现front和rear相减的情况)，否则不需要(rear+1+length)%length，直接(rear+1)%length即可。
在循环队列中，要牺牲一个单元区别队列的空与满，所以在计算队列容量的时候，要减1。