提问人：teewhy 提问时间：12/7/2022 最后编辑：teewhy 更新时间：12/7/2022 访问量：198
使用空队列反转队列
reverse a queue using an empty queue
问：
我有一个队列 [3,2,1]，我想只使用入队和出队函数来反转它。我的最后一个队列应该是 [1,2,3]。
我无法声明任何局部变量。我只有 2 个队列，一个是空的，另一个有数据。我想仅使用空队列反转包含数据的队列。我无权访问队列的指针。
我只有 1 个全局变量，但我无法声明局部变量，否则可以通过递归轻松完成。而且我也没有偷看和弹回功能。只有 enqueue、dequeue、length、empty 和 front。
这可能吗？
queue1 = [3,2,1]
queue2 = []
final result
queue1 = [1,2,3]
queue2 = []
答：
0赞
trincot
12/7/2022
#1
使用一个全局变量似乎至关重要。因此，让它成为一个可用于循环的数字。
这个想法是旋转（dequeue + enqueue），直到它（最初）第一个元素。那么这个可以转移到 .现在看起来它最初是，但没有最后一个元素。重复此过程，直到它为空。queue1queue2queue1
这将在 queue2 中给出所需的结果。由于要求在 queue1 中获取结果，我们可以首先将所有元素从 queue1 移动到 queue2 中，除了最后一个元素。然后我们可以在 queue2 上应用上述过程，并将所需的元素传输到 queue1。
global i
reverse(queue1):
queue2 = new Queue()
repeat queue1.length-1 times:
queue2.equeue(queue1.dequeue())
repeat until queue2.empty():
for i = queue2.length-1 downto 1:
queue2.equeue(queue2.dequeue())
queue1.enqueue(queue2.dequeue())
以下是可运行的 JavaScript 代码片段中的实现 （ = enqueue， = dequeue）：pushshift
let i; // One global variable
let queue1 = [];
let queue2 = [];
// Populate the first queue
for (i = 1; i <= 5; i++) {
queue1.push(i);
}
console.log(...queue1);
// Start of the reversal algorithm
// Move all but the last element to the other queue
while (queue1.length > 1) {
queue2.push(queue1.shift());
}
while (queue2.length > 0) {
// Rotate queue2 to bring last element at the front
for (i = queue2.length-1; i > 0; i--) {
queue2.push(queue2.shift());
}
// Move that front element to the first queue
queue1.push(queue2.shift());
}
// End of the algorithm. Print the result
console.log(...queue1);
评论