leetcode-用队列实现栈

225. 用队列实现栈

我们先简单了解下栈与队列的区别：

1. 操作方式：栈是一种后进先出(Last In First Out, LIFO)的数据结构，只允许在栈顶进行插入和删除操作。而队列是一种先进先出(First In First Out, FIFO)的数据结构，规定在队尾插入元素，在队首删除元素。
2. 使用场景：由于栈具有后进先出的特性，它常用于程序的执行过程中，如执行函数调用的时候保存临时变量和返回地址的场合。队列则因其先进先出的特点，经常用于排队等待处理的任务，如打印任务队列、线程池任务队列等场合。
3. 性能考量：在大多数编程语言中，栈通常有更高效的内存分配机制，例如在C语言中的局部变量就是存储在栈上的。队列则需要更多的管理来维护元素的插入和删除顺序。

题解：

1. 使用双端队列
2. 使用两个队列in_que和out_que实现栈的功能，其实out_que起到是备份的作用，把in_que最后面的元素以外的元素备份到out_que中，然后弹出最后面的元素，再把其他元素从out_que导回到in_que。

from collections import deque


class MyStack:

    def __init__(self):
        self.in_que = deque()
        self.out_que = deque()


    def push(self, x: int) -> None:
        self.in_que.append(x)


    def pop(self) -> int:
        if self.empty():
            return None
        for _ in range(len(self.in_que) - 1):
            self.out_que.append(self.in_que.popleft())
        self.in_que, self.out_que = self.out_que, self.in_que
        return self.out_que.popleft()


    def top(self) -> int:
        if self.empty():
            return None
        return self.in_que[-1]
    
    def empty(self) -> bool:
        return not self.que

题目中要求是使用双队列来实现，其实单队列也是可以的

from collections import deque

class MyStack:

    def __init__(self):
        self.que = deque()

    def push(self, x: int) -> None:
        self.que.append(x)


    def pop(self) -> int:
        if self.empty():
            return None
        for i in range(len(self.que) - 1):
            self.que.append(self.que.popleft())
        return self.que.popleft()


    def top(self) -> int:
        if self.empty():
            return None
        return self.que[-1]


    def empty(self) -> bool:
        return not self.que