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())