C++两个栈实现一个队列和两个队列实现一个栈

         今天用C++实现了下两个栈模拟一个队列和两个队列模拟一个栈!代码可能有很多漏洞，如果读者发现问题，

可以及时反馈，非常感谢！！！

        代码如下:

[cpp] view plain copy

print?

1. #include <iostream>  
2. #include <stdlib.h>  
3. #include <stack>  
4. #include <queue>  
5. using namespace std;  
6.   
7. #if 1  
8. //  *******两个栈实现一个队列********  
9. typedef int ElemType;  
10. typedef struct {  
11.    stack<ElemType>s1;  //负责入队列  
12.    stack<ElemType>s2;  //负责出队列  
13. }SQueue;  
14.   
15. //判断队列是否为空  
16. bool IsEmpty(SQueue &q) {  
17.    if ((q.s1.empty()) && (q.s2.empty())) {  
18.       return true;  
19.    }  
20.    return false;  
21. }  
22.   
23. // 入队列  
24. void EnQueue(SQueue &q, ElemType e) {  
25.    q.s1.push(e);  
26. }  
27.   
28. //  队列大小  
29. int GetQueueSize(SQueue &q) {  
30.    return q.s1.size() + q.s2.size();  
31. }  
32.   
33. //出队列  
34. void DeQueue(SQueue &q) {  
35.    if (q.s2.empty()) {  
36.       while (!q.s1.empty()) {  
37.         q.s2.push(q.s1.top());  
38.         q.s1.pop();  
39.       }  
40.    }  
41.    if (!q.s2.empty()) {  //队空  
42.        q.s2.pop();  //出队列  
43.    }  
44. }  
45.   
46. //  取队首先元素  
47. ElemType GetFront(SQueue &q) {  
48.     if (q.s2.empty()) {  
49.       while (!q.s1.empty()) {  
50.         q.s2.push(q.s1.top());  
51.         q.s1.pop();  
52.       }  
53.    }  
54.    if (q.s2.empty()) {  //队空  
55.       throw;  
56.    }  
57.    return q.s2.top();  
58. }  
59.   
60. int main() {  
61.   SQueue sq;  
62.   EnQueue(sq, 1);  
63.   EnQueue(sq, 2);  
64.   EnQueue(sq, 3);  
65.   EnQueue(sq, 4);  
66.   EnQueue(sq, 5);  
67.   EnQueue(sq, 6);  
68.   cout << GetFront(sq) << endl;  
69.   DeQueue(sq);  
70.   
71.   cout << GetFront(sq) << endl;  
72.   DeQueue(sq);  
73.   
74.   cout << GetFront(sq) << endl;  
75.   DeQueue(sq);  
76.   cout << GetFront(sq) << endl;  
77.   cout << GetFront(sq) << endl;  
78.   
79.   cout << GetQueueSize(sq) << endl;  
80.   return 0;  
81. }  
82. #endif  
83.   
84. #if 1  
85. //  ****两个队列实现一个栈****  
86. typedef int ElemType;  
87. typedef struct {  
88.    queue<ElemType>q1;  //入队  
89.    queue<ElemType>q2;  //中转  
90. }QStack;  
91.   
92. // 栈是否为空  
93. bool IsEmpty(QStack s) {  
94.     if (s.q1.empty()) {  
95.         return true;  
96.     }  
97.     return false;  
98. }  
99.   
100. // 栈大小  
101. int GetStackSize(QStack s) {  
102.    return s.q1.size();  
103. }  
104. //压栈  
105. void Push(QStack &s, ElemType e) {  
106.    s.q1.push(e);  
107. }  
108.   
109. //弹栈  
110. void Pop(QStack &s) {  
111.     if (!s.q1.empty()) {  
112.        while (s.q1.size() != 1) {  //队列q1的n-1个元素移动到q2  
113.          s.q2.push(s.q1.front());  
114.          s.q1.pop();  
115.        }  
116.        s.q1.pop();  
117.        while (!s.q2.empty()) {  
118.          s.q1.push(s.q2.front());  
119.          s.q2.pop();  
120.        }  
121.     }  
122. }  
123.   
124. //取栈顶元素  
125. int Top(QStack &s) {  
126.    if (s.q1.empty()) {  
127.       throw;  //栈空  
128.    }  
129.    while (!s.q1.empty()) {  //队列q1的n个元素移动到q2  
130.      s.q2.push(s.q1.front());  
131.      s.q1.pop();  
132.    }  
133.    ElemType tmp = s.q2.back();  //获取第n个元素  
134.    while (!s.q2.empty()) {  
135.      s.q1.push(s.q2.front());  
136.      s.q2.pop();  
137.    }  
138.    return tmp;  
139. }  
140.   
141. int main() {  
142.     QStack qs;  
143.     Push(qs, 1);  
144.     Push(qs, 2);  
145.     Push(qs, 3);  
146.     Push(qs, 4);  
147.     try {  
148.         cout << Top(qs) << endl;  
149.         Pop(qs);  
150.         cout << Top(qs) << endl;  
151.         Pop(qs);  
152.         cout << Top(qs) << endl;  
153.         Pop(qs);  
154.         cout << Top(qs) << endl;  
155.         Pop(qs);  
156.         cout << "size:" << GetStackSize(qs) << endl;  
157.     }  catch (...) {  
158.   
159.     }  
160.     if (IsEmpty(qs)) {  
161.         cout << "栈空" << endl;  
162.     } else {  
163.        cout << "栈非空" << endl;  
164.     }  
165.    return 0;  
166. }  
167. #endif // 1