数据结构第3章--限定性线性表——栈及队列.doc

第三章习题
1.         按图3.1(b)所示铁道（两侧铁道均为单向行驶道）进行车厢调度，回答：
    ⑴ 如进站的车厢序列为123，则可能得到的出站车厢序列是什么？
⑵如进站的车厢序列为123456，能否得到435612和135426的出站序列，并说明原因。
135426可以得到（即写出以“S”表示进栈、以“X”表示出栈的栈操作序列）。
2.         设队列中有A、B、C、D、E这5个元素，其中队首元素为A。如果对这个队列重复执行下列4步操作：
（1）       输出队首元素；
（2）       把队首元素值插入到队尾；
（3）       删除队首元素；
（4）       再次删除队首元素。
直到队列成为空队列为止，得到输出序列：A
（1）       A、C、E、C、C               （2） A、C、E
（3）  A、C、E、C、C、C           （4） A、C、E、C
3.         给出栈的两种存储结构形式名称，在这两种栈的存储结构中如何判别栈空与栈满？
栈空s.top==s。base 栈满 s.top-s.base>=s.stacksize
4.         按照四则运算加、减、乘、除和幂运算（↑）优先关系的惯例，画出对下列算术表达式求值时操作数栈和运算符栈的变化过程：
          A－B＊Ｃ／Ｄ＋Ｅ↑Ｆ
5.         要求循环队列不损失一个空间全部都能得到利用, 设置一个标志域tag , 以tag为0或1来区分头尾指针相同时的队列状态的空与满，请编写与此结构相应的入队与出队算法。
6.         简述以下算法的功能（其中栈和队列的元素类型均为int）：
（1）void proc_1(Stack S)
{ int i, n, A[255];
  n=0;
  while(!EmptyStack(S))
  {n++;  Pop(&S,  &A[n]);}
   for(i=1;  i<=n;  i++)
        Push(&S,  A[i]);
 }
（2）void proc_2(Stack S,  int e)
{ Stack T;  int d;
InitStack(&T);
  while(!EmptyStack(S))
  { Pop(&S,  &d);
    if (d!=e) Push( &T,  d);
  }
  while(!EmptyStack(T))
  { Pop(&T,  &d);
    Push( &S,  d);
  }
}
删除e
（3）void proc_3(Queue  *Q)
{ Stack S;  int d;
InitStack(&S);
  while(!EmptyQueue(*Q))
  {
DeleteQueue(Q,  &d);
Push( &S,  d);
        }
  while(!EmptyStack(S))
  { Pop(&S,  &d);
    EnterQueue(Q，d)
  }
  }