感觉两个队列实现栈 比 两个栈实现队列 麻烦
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中的元素出队即可。
代码如下:
#!/usr/bin/env python3
# -*- coding: utf-8 -*- class Stack(object):
def __init__(self):
self.q1 = Queue()
self.q2 = Queue() def is_empty(self):
result = self.q1.is_empty() and self.q2.is_empty()
return result def push(self, elem):
if self.q2.is_empty():
self.q1.enqueue(elem)
elif self.q1.is_empty():
self.q2.enqueue(elem)
else:
self.q1.enqueue(elem) def pop(self):
if self.q1.is_empty() and self.q2.is_empty():
raise ValueError("Stack is Empty")
if self.q2.is_empty():
if self.q1.head.next is None:
return self.q1.dequeue()
while not self.q1.head.next is None:
self.q2.enqueue(self.q1.dequeue())
return self.q1.dequeue()
if self.q1.is_empty():
if self.q2.head.next is None:
return self.q2.dequeue()
while not self.q2.head.next is None:
self.q1.enqueue(self.q2.dequeue())
return self.q2.dequeue() class Node(object):
def __init__(self, elem, next_=None):
self.elem = elem
self.next = next_ class Queue(object):
def __init__(self):
self.head = None
self.rear = None def is_empty(self):
return self.head is None def enqueue(self, elem):
if self.is_empty():
self.head = Node(elem)
self.rear = self.head
else:
self.rear.next = Node(elem)
self.rear = self.rear.next def dequeue(self):
if self.is_empty():
raise ValueError("Queue is Empty")
if self.head.next is None:
e = self.head.elem
self.head = None
self.rear = None
return e
else:
e = self.head.elem
self.head = self.head.next
return e def peek(self):
if self.is_empty():
raise ValueError("Queue is Empty")
return self.head.elem def bianli(self):
p = self.head
li = []
while p:
li.append(p.elem)
p = p.next
return li if __name__ == "__main__":
s = Stack()
for i in range(5):
s.push(i)
while not s.is_empty():
print(s.pop())