3.简答题
3.1 答:进栈操作是先将栈顶指针加 1 后,再将待插入元素入栈,退栈操作则是先取出
栈顶元素,在使栈顶指针减 1。
3.2 答:入队操作的指针移动语句为:cq.rear=(cq.rear+1)%QueueSize;
出队操作的指针移动语句为:cq.front=(cq.front+1)%QueueSize;
3.3 答:所有可能的出站顺序有:123,132,213,231,321,不可能是 312,因
为当 3 号车进站并出站后,站台上有 1 号车和 2 号车,不可能先出 1 号而后出 2 号。
3.4 答:出队操作是删除队头元素(修改头指针)之后,再返回该删除元素值,而取队
头操作仅仅是取出队头元素值返回,不修改队头指针。
3.5 答:简述下面给出的算法的功能是什么?(假设栈元素为整数类型)
此算法的功能是通过一个数组将一个栈中的所有元素逆置存放。
3.6 答:该算法的功能是通过一个中间栈 T,达到删除栈 S 中所有与变量 C 相同的元素。
3.7 答:只设头指针的入队操作时间复杂度为 O(n);只设尾指针的入队操作时间复
杂度为 O(1)
3.8 答:栈叫先进后出表或叫后进先出表。栈的插入和删除都从称为栈顶的一端进行,
一般线性表可以在线性表的中间及两端进行插入和删除操作。
3.9 答:队列叫先进先出表(FIFO)或叫后进后出表,队列的插入只能在队列的一端进
行,该端称为队尾。队列的删除只能从另一端进行,该端称为队头。一般线性表可以在
线性表的中间及两端进行插入和删除操作。
3. 10 答:栈和队列都是加了限制的线性表,栈叫后进先出表,队列叫先进先出表。栈
和队列的插入和删除运算都在端点进行,栈的插入与删除在同一端点,队列的插入与
删除在不同的端点进行。栈与队列的元素个数都是可变的,同一个栈或同一个队列中
的元素类型是一致的。
3.11 写出下列程序段的输出结果
输出结果:stack
3.12 简述下列算法的功能
借助数组将 S 栈内的元素倒置
3.13 简述下列算法的功能
借助 T 栈将 S 栈内的元素倒置
4.算法设计
4.1 顺序栈的六种基本操作
S-> data[++S->top]=x;
S->data[S->top]
4.2 循环队列基本算法
Q->rear=(Q->rear+1)%QueueSize;
return Q->data[Q->front]