简答题

设顺序栈S中有2n个元素,从栈顶到栈底的元素依次为a2n,a2n-1,…,a1,要求通过一个循环队列重新排列栈中元素,使得从栈顶到栈底的元素依次为a2n,a2n-2,…,a2,a2n-1,a2n-3,…,a1,请设计算法实现该操作,要求空间复杂度和时间复杂度均为O(n)。

正确答案

操作步骤为:
①将所有元素出栈并入队;
②依次将队列元素出队,如果是偶数结点,则再入队,如果是奇数结点,则入栈;
③将奇数结点出栈并入队;
④将偶数结点出队并入栈;
⑤将所有元素出栈并入队;
⑥将所有元素出队并入栈即为所求。

答案解析

相似试题
  • 在一个具有n个单元的顺序栈中,假定以地址低端(即0单元)作为栈底,以top为栈顶指针,则当做出栈处理时,top变化为()。

    单选题查看答案

  • 在一个具有n个单元的顺序栈中,假定以地址低端(即下标为0的单元)作为栈底,以top作为栈顶指针,当出栈时,top的变化为()。

    单选题查看答案

  • 顺序栈S中top为栈顶指针,指向栈顶元素所在的位置,elem为存放栈的数组,则元素e进栈操作的主要语句为()。

    单选题查看答案

  • 向一个顺序栈S(栈顶指针为top)中插入元素x时,首先要()。

    单选题查看答案

  • 设sp()为一个顺序存储的栈,变量top只是栈顶元素的位置,能做入栈操作的条件是()。如要把栈顶元素弹出并送到x中,则需执行下列语句()。

    填空题查看答案

  • 在操作序列push(1)、push(2)、pop、push(5)、push(7)、pop、push(6)之后,栈顶元素和栈底元素分别是什么?(push(k)表示整数k入栈,pop表示栈顶元素出栈。)

    简答题查看答案

  • 设S()为一个顺序存储的栈,变量top只是栈顶位置,栈为空的条件是(),栈为满的条件是().

    填空题查看答案

  • 简述在顺序栈的栈顶插入一个元素的操作过程。

    简答题查看答案

  • 具有什么特征的数据结构被称为栈和队列?先进后出、栈顶、栈底、先进先出、队头、队尾的概念是什么?

    简答题查看答案