设顺序栈S中有2n个元素，从栈顶到栈底的元素依次为a2n，a2n-1，…，a1，要求通过一个循环队列重新排列栈中元素，使得从栈顶到栈底的元素依次为a2n，a2n-2，…，a2，a2n-1，a2n-3，…，a1，请设计算法实现该操作，要求空间复杂度和时间复杂度均为O（n）。
正确答案:操作步骤为：
①将所有元素出栈并入队；
②依次将队列元素出队，如果是偶数结点，则再入队，如果是奇数结点，则入栈；
③将奇数结点出栈并入队；
④将偶数结点出队并入栈；
⑤将所有元素出栈并入队；
⑥将所有元素出队并入栈即为所求。
①将所有元素出栈并入队；
②依次将队列元素出队，如果是偶数结点，则再入队，如果是奇数结点，则入栈；
③将奇数结点出栈并入队；
④将偶数结点出队并入栈；
⑤将所有元素出栈并入队；
⑥将所有元素出队并入栈即为所求。
答案解析:有
微信扫一扫手机做题