感觉两个队列实现栈 比 两个栈实现队列 麻烦
1. 栈为空:当两个队列都为空的时候,栈为空
2. 入栈操作:当队列 2 为空的时候,将元素入队到队列 1;当队列 1 位空的时候,将元素入队到队列 2;
如果队列 1 和 队列 2 都为空的时候,那就选择入队到队列 1.
3. 出队操作:当两个队列都为空的时候,引发错误 "栈为空";
当队列 2 位空的时候,如果队列 1 中只有一个元素,则直接将队列 1 中的元素出队;
如果队列 1 不止一个元素的时候,就将队列 1 的元素出队然后入队到队列 2,知道队列 1 中只有一个元素,然后将队列 1 中的元素出队即可。
当队列 1 位空的时候,如果队列 2 中只有一个元素,则直接将队列 2 中的元素出队;
如果队列 2 不止一个元素的时候,就将队列 2 的元素出队然后入队到队列 1,知道队列 2 中只有一个元素,然后将队列 2 中的元素出队即可。
代码如下:
- 1 #!/usr/bin/env python3
- 2 # -*- coding: utf-8 -*-
- 3
- 4 class Stack(object):
- 5 def __init__(self):
- 6 self.q1 = Queue()
- 7 self.q2 = Queue()
- 8
- 9 def is_empty(self):
- 10 result = self.q1.is_empty() and self.q2.is_empty()
- 11 return result
- 12
- 13 def push(self, elem):
- 14 if self.q2.is_empty():
- 15 self.q1.enqueue(elem)
- 16 elif self.q1.is_empty():
- 17 self.q2.enqueue(elem)
- 18 else:
- 19 self.q1.enqueue(elem)
- 20
- 21 def pop(self):
- 22 if self.q1.is_empty() and self.q2.is_empty():
- 23 raise ValueError("Stack is Empty")
- 24 if self.q2.is_empty():
- 25 if self.q1.head.next is None:
- 26 return self.q1.dequeue()
- 27 while not self.q1.head.next is None:
- 28 self.q2.enqueue(self.q1.dequeue())
- 29 return self.q1.dequeue()
- 30 if self.q1.is_empty():
- 31 if self.q2.head.next is None:
- 32 return self.q2.dequeue()
- 33 while not self.q2.head.next is None:
- 34 self.q1.enqueue(self.q2.dequeue())
- 35 return self.q2.dequeue()
- 36
- 37
- 38 class Node(object):
- 39 def __init__(self, elem, next_=None):
- 40 self.elem = elem
- 41 self.next = next_
- 42
- 43 class Queue(object):
- 44 def __init__(self):
- 45 self.head = None
- 46 self.rear = None
- 47
- 48 def is_empty(self):
- 49 return self.head is None
- 50
- 51 def enqueue(self, elem):
- 52 if self.is_empty():
- 53 self.head = Node(elem)
- 54 self.rear = self.head
- 55 else:
- 56 self.rear.next = Node(elem)
- 57 self.rear = self.rear.next
- 58
- 59 def dequeue(self):
- 60 if self.is_empty():
- 61 raise ValueError("Queue is Empty")
- 62 if self.head.next is None:
- 63 e = self.head.elem
- 64 self.head = None
- 65 self.rear = None
- 66 return e
- 67 else:
- 68 e = self.head.elem
- 69 self.head = self.head.next
- 70 return e
- 71
- 72 def peek(self):
- 73 if self.is_empty():
- 74 raise ValueError("Queue is Empty")
- 75 return self.head.elem
- 76
- 77 def bianli(self):
- 78 p = self.head
- 79 li = []
- 80 while p:
- 81 li.append(p.elem)
- 82 p = p.next
- 83 return li
- 84
- 85 if __name__ == "__main__":
- 86 s = Stack()
- 87 for i in range(5):
- 88 s.push(i)
- 89 while not s.is_empty():
- 90 print(s.pop())
来源: http://www.bubuko.com/infodetail-1957065.html