文档介绍：会计学
1
数据结构栈和队列****题课
(1) 123 , 132 , 213 , 231 , 321
(2) 435612不能得到（6出站时，12必须在站中，只能出站成21，无法得到12）
135426可以 1S1X2S3S3X4S5S5X4X2X6S6X
（1）如果进站的车厢序列为123，则可能得到的出站车厢序列是什么?
（2）如果进站的车厢序列为123456，则能否得到435612和135426出站序列，并请说明为什么不能得到或如何得到。
第1页/共14页
分析：
while循环 将栈中数据依次出栈到A数组
for循环 将数组A中元素依次入栈
结果：
将堆栈中的元素逆序
（1）status algol(Stack S){
int I,n,A[255];
n = 0;
while (!Stackempty(S)) {n++;Pop(S,A[n]);}
for (i=1 ; i<=n ; i++) Push(S,A[i]);
}
第2页/共14页
分析：
第一个while循环：将S栈中不等于e的元素放入T栈。最后S为空栈
第二个while循环：将T栈中元素出栈到S栈
结果：
将堆栈S中不等于e的元素逆序
（2）
status algo2(Stack S , int e){
Stack T ; int d ;
InitStack(T);
while (! StackEmpty(S)){
Pop(S,d);
if (d!=e) Push(T,d);
}
while(!Stackempty(T)){
Pop(T,d);
Push(S,d);
}
}
第3页/共14页
分析：
[队列] x y
1. [h] e c
2. [hr] e c
3. [hrc] e c
4. [rc] h c
5. [rch] h c
6. [ch] r c
7. [cha] r c
结果：
char
Void main(){
Queue Q ; InitQueue(Q);
char x=‘e’ , y =‘c’ ;
EnQueue(Q,’h’); //1
EnQueue(Q,’r’); //2
EnQueue(Q,y); //3
DeQueue(Q,x); //4
Enqueue(Q,x); //5
DeQueue(Q,x); //6
EnQueue(Q,’a’); //7
while (!QueueEmpty(Q)){
DeQueue(Q,y);
printf(y);
}
printf(x);
}
第4页/共14页
以1234作为双端队列的输入序列，分别求出满足以下条件的输出序列
解： 可能的组合（24种）
1234，1243，1324，1342，1423，1432，
2134，2143，2314，2341，2413，2431，
3124，3142，3214，3241，3412，3421，
4123，4132，4213，4231，4312，4321
输入受限不能得到:4213 4231
输出受限不能得到:4132 4231
都不能得到:4231
(1)4213 (2)4132 (3)4231
（1）能由输入受限的双端队列得到，但不能由输出受限的双端队列得到的输出序列
（2）能由输出受限的双端队列得到，但不能由输入受限的双端队列得到的输出序列
（3）既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列
第5页/共14页
n节硬席或软席车厢调度成软席在硬席之前
HSSHS => SSSHH
思路：判断每节车厢，如果是H的只入栈，如果