Python如何仅使用FIFO队列构建LIFO堆栈

Question

我有一个非常棘手的问题：如何仅使用FIFO队列构建LIFO堆栈？

所以我已经有了大部分代码，但正如您在下面看到的，我不知道如何对弹出功能

import queue
class MyLifo:
def __init__(self):
self.fifo = queue.Queue();
self.fifoAux = queue.Queue();
def isEmpty(self):
return self.fifo.empty()

def push(self, x):
self.fifo.put(x)
def pop(self):
### your code here.
### for testing the solution:
lifo = MyLifo()
i=0
while (i<30):
lifo.push(i)
i+=1
while (lifo.isEmpty() == False):
print(lifo.pop())


lifo.push(3)
lifo.push(5)
print(lifo.pop())
lifo.push(30)
print(lifo.pop())
print(lifo.pop())
print(lifo.pop())

有朋友可以帮忙吗？

Answer 1

因此更好的解决方案是使用queue.LifoQueue()。然而，由于这是一种实践，以下解决方案具有时间复杂度为O(1)的push函数和时间复杂度O(N)的pop函数，这意味着它通过N来创建队列中的现有元素。

import queue

class MyLifo:
def __init__(self):
self.fifo = queue.Queue()
def isEmpty(self):
return self.fifo.empty()
def push(self, x):
self.fifo.put(x)
def pop(self):
for _ in range(len(self.fifo.queue) - 1):
self.push(self.fifo.get())
return self.fifo.get()
lifo = MyLifo()
i = 0
while (i < 30):
lifo.push(i)
i += 1
while (lifo.isEmpty() == False):
print(lifo.pop(), end=" ")

输出：

29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0