今天用C++实现了下两个栈模拟一个队列和两个队列模拟一个栈!代码可能有很多漏洞,如果读者发现问题,
可以及时反馈,非常感谢!!!
代码如下:
#include <iostream> #include <stdlib.h> #include <stack> #include <queue> using namespace std; #if 1 // *******两个栈实现一个队列******** typedef int ElemType; typedef struct { stack<ElemType>s1; //负责入队列 stack<ElemType>s2; //负责出队列 }SQueue; //判断队列是否为空 bool IsEmpty(SQueue &q) { if ((q.s1.empty()) && (q.s2.empty())) { return true; } return false; } // 入队列 void EnQueue(SQueue &q, ElemType e) { q.s1.push(e); } // 队列大小 int GetQueueSize(SQueue &q) { return q.s1.size() + q.s2.size(); } //出队列 void DeQueue(SQueue &q) { if (q.s2.empty()) { while (!q.s1.empty()) { q.s2.push(q.s1.top()); q.s1.pop(); } } if (!q.s2.empty()) { //队空 q.s2.pop(); //出队列 } } // 取队首先元素 ElemType GetFront(SQueue &q) { if (q.s2.empty()) { while (!q.s1.empty()) { q.s2.push(q.s1.top()); q.s1.pop(); } } if (q.s2.empty()) { //队空 throw; } return q.s2.top(); } int main() { SQueue sq; EnQueue(sq, 1); EnQueue(sq, 2); EnQueue(sq, 3); EnQueue(sq, 4); EnQueue(sq, 5); EnQueue(sq, 6); cout << GetFront(sq) << endl; DeQueue(sq); cout << GetFront(sq) << endl; DeQueue(sq); cout << GetFront(sq) << endl; DeQueue(sq); cout << GetFront(sq) << endl; cout << GetFront(sq) << endl; cout << GetQueueSize(sq) << endl; return 0; } #endif #if 1 // ****两个队列实现一个栈**** typedef int ElemType; typedef struct { queue<ElemType>q1; //入队 queue<ElemType>q2; //中转 }QStack; // 栈是否为空 bool IsEmpty(QStack s) { if (s.q1.empty()) { return true; } return false; } // 栈大小 int GetStackSize(QStack s) { return s.q1.size(); } //压栈 void Push(QStack &s, ElemType e) { s.q1.push(e); } //弹栈 void Pop(QStack &s) { if (!s.q1.empty()) { while (s.q1.size() != 1) { //队列q1的n-1个元素移动到q2 s.q2.push(s.q1.front()); s.q1.pop(); } s.q1.pop(); while (!s.q2.empty()) { s.q1.push(s.q2.front()); s.q2.pop(); } } } //取栈顶元素 int Top(QStack &s) { if (s.q1.empty()) { throw; //栈空 } while (!s.q1.empty()) { //队列q1的n个元素移动到q2 s.q2.push(s.q1.front()); s.q1.pop(); } ElemType tmp = s.q2.back(); //获取第n个元素 while (!s.q2.empty()) { s.q1.push(s.q2.front()); s.q2.pop(); } return tmp; } int main() { QStack qs; Push(qs, 1); Push(qs, 2); Push(qs, 3); Push(qs, 4); try { cout << Top(qs) << endl; Pop(qs); cout << Top(qs) << endl; Pop(qs); cout << Top(qs) << endl; Pop(qs); cout << Top(qs) << endl; Pop(qs); cout << "size:" << GetStackSize(qs) << endl; } catch (...) { } if (IsEmpty(qs)) { cout << "栈空" << endl; } else { cout << "栈非空" << endl; } return 0; } #endif // 1