python队列和栈操作，两个栈实现队列，两个队列实现栈

迈不过友情╰ 2022-05-06 11:30 271阅读 0赞

参考：[http://docs.python.org/2/tutorial/datastructures.html\#more-on-lists的官方代码][http_docs.python.org_2_tutorial_datastructures.html_more-on-lists]  
**栈**

>>> stack = [3, 4, 5]
    >>> stack.append(6)
    >>> stack.append(7)
    >>> stack
    [3, 4, 5, 6, 7]
    >>> stack.pop()
    7
    >>> stack
    [3, 4, 5, 6]
    >>> stack.pop()
    6
    >>> stack.pop()
    5
    >>> stack
    [3, 4]

**队列**

>>> from collections import deque
    >>> queue = deque(["Eric", "John", "Michael"])
    >>> queue.append("Terry")           # Terry arrives
    >>> queue.append("Graham")          # Graham arrives
    >>> queue.popleft()                 # The first to arrive now leaves
    >>> queue.pop(0)   #与popleft()效果一样
    'Eric'
    >>> queue.pop(0)                # The second to arrive now leaves
    'John'
    >>> queue                           # Remaining queue in order of arrival
    deque(['Michael', 'Terry', 'Graham'])

**使用两个栈实现一个队列**  
插入：插入到stack1  
删除：如果stack2为空，将stack1pop之后push到stack2，如果stack2不为空，则直接popstack2

class Solution:
        def __init__(self):
            self.stack1 = []
            self.stack2 = []
        def push(self, node):
            self.stack1.append(node)
        def pop(self):
            if self.stack2 == []:
                while self.stack1 != []:
                    self.stack2.append(self.stack1.pop())
            return self.stack2.pop()
    sol = Solution()
    sol.push(1)
    sol.push(2)
    print(sol.pop())
    sol.push(3)
    print(sol.pop())
    print(sol.pop())

输出：

1
    2
    3

**两个队列实现一个栈**  
插入：保证一个队列为空，一个不为空，插入的时候，插入到不为空的队列，保证进入的先后顺序  
删除：将不为空的队列全部搬入到为空的队列只剩下最后一个元素，然后删除这个元素，就能再先进先出的基础上实现先进后出

class Solution:
        def __init__(self):
            self.queue1 = []
            self.queue2 = []
        def insert(self, x):
            if self.queue1 == []:
                self.queue2.append(x)
            elif self.queue2 == []:
                self.queue1.append(x)
        def delete(self):
            if self.queue2 == []:
                while len(self.queue1) != 1:
                    self.queue2.append(self.queue1.pop(0))
                return self.queue1.pop(0)
            elif self.queue1 == []:
                while len(self.queue2) != 1:
                    self.queue1.append(self.queue2.pop(0))
                return self.queue2.pop(0)
    sol = Solution()
    sol.insert(1)
    sol.insert(2)
    sol.insert(3)
    print(sol.delete())
    print(sol.delete())
    sol.insert(5)
    print(sol.delete())
    print(sol.delete())

输出：

3
    2
    5
    1

[http_docs.python.org_2_tutorial_datastructures.html_more-on-lists]: http://docs.python.org/2/tutorial/datastructures.html#more-on-lists%E7%9A%84%E5%AE%98%E6%96%B9%E4%BB%A3%E7%A0%81