简答题

设栈S和队列Q的初始状态为空,元素e1,e2,e3,e4,e5和e6依次通过S,一个元素出栈后即进队列Q,若6个元素出队的序列是e2,e4,e3,e6,e5,e1,则栈S的容量至少应该是多少?

正确答案

出队序列是e2,e4,e3,e6,e5,e1的过程:
(1)e1入栈(栈底到栈顶元素是e1)
(2)e2入栈(栈底到栈顶元素是e1,e2)
(3)e2出栈(栈底到栈顶元素是e1)
(4)e3入栈(栈底到栈顶元素是e1,e3)
(5)e4入栈(栈底到栈顶元素是e1,e3,e4)
(6)e4出栈(栈底到栈顶元素是e1,e3)
(7)e3出栈(栈底到栈顶元素是e1)
(8)e5入栈(栈底到栈顶元素是e1,e5)
(9)e6入栈(栈底到栈顶元素是e1,e5,e6)
(10)e6出栈(栈底到栈顶元素是e1,e5)
(11)e5出栈(栈底到栈顶元素是e1)
(12)e1出栈(栈底到栈顶元素是空)
栈中最多时有3个元素,所以栈S的容量至少是3。

答案解析

相似试题
  • 判断一个顺序队列(最多元素为m)为空的条件是()。

    单选题查看答案

  • 判断一个循环队列LU(最多元素为m)为空的条件是()。

    填空题查看答案

  • 排序方法中,从未排序序列中挑选元素,并将其依次放入已排序序列(初始为空)的一端的方法,称为()排序。

    单选题查看答案

  • 排序方法中,从尚未排序序列中挑选元素,并将其依次放入已排序序列(初始为空)的一端的方法,称为()排序。

    单选题查看答案

  • 排序算法中,从未排序序列中依次取出元素与已排序序列(初始为空)中的元素进行比较(要求比较次数尽量少),然后将其放入已排序序列的正确位置的方法是()。

    单选题查看答案

  • 循环队列用a[0],...,a[7]的一维数组存放队列元素,(采用少用一个元素的模式),设front和rear分别为队头和队尾指针,且front和rear 的值分别为2和7,当前队列中的元素个数是()。

    填空题查看答案

  • 在队列的顺序存储结构中,当插入一个新的队列元素时,()指针的值增1,当删除一个元素队列时,()指针的值增1。

    填空题查看答案

  • 循环队列的最大存储空间为MaxSize=6,采用少用一个元素空间以有效地判断栈空或栈满,若队头指针front=4,当队尾指针rear=()时队满,队列中共有()个元素。

    填空题查看答案

  • 循环队列队头指针在队尾指针()位置,队列是“满”状态。

    填空题查看答案