python队列和栈操作，两个栈实现队列，两个队列实现栈-蒲公英云

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

参考：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())