将队列中元素移入栈

[!Tip]

本节源代码见Github链接🔗

问题描述

给定一个含有n个元素的队列Q，现要求把Q中的元素移到栈S（初始为空）中，使得Q的队首元素保存在栈顶且其他元素按照在Q中的顺序保存在S中。利用队列的出队和入队操作以及栈的入栈和出栈操作，设计一个时间复杂度为O(n)的有效算法，并且算法的额外空间开销为常数。

核心思路

将队列Q中元素依次移入栈S中，此时展示元素顺序与队列中元素顺序时相反。再将栈S中元素依次移入队列Q中，此时队列Q中元素顺序与初始顺序相反。再将队列Q中元素顺序依次移入栈S中，此时栈S中元素顺序与队列Q中元素初始顺序相同。

时间复杂度

出栈时间复杂度为O(n)，每次移动元素的时间复杂度都是O(n)。

空间复杂度

空间复杂度为O(1)，用于保存临时变量。