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()。但是，由于这是一种实践，因此以下解决方案具有 push 时间复杂度 O(1) 和 pop 时间复杂度 O(N) 的函数，这意味着它会遍历 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

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

Python how to build a LIFO stack using only FIFO queues

python

queue

fifo

python-3.x

lifo