用两个栈模拟一个队列（C++）

用两个栈模拟一个队列（C++）

思路：

让栈A提供入队功能，栈B提供出队功能。

入队列：栈A。

出队列：如果栈B不为空，直接弹出栈B的栈顶数据；如果栈B为空，则依次弹出栈A的数据，放入栈B中，再弹出栈B的栈顶数据。

方法一：

#include#include#includeusing namespace std; templatestruct MyQueue{ void Enqueue(T t) { s1.push(t); } T Dequeue() { if(s2.empty()) { if(0 == s1.size()) { exit(1); } while(!s1.empty()) { s2.push(s1-()); s1.pop(); } } T retVal = s2-(); s2.pop(); return retVal; } stack s1; stack s2;}; intmain(){ MyQueue mq; int begin = 0; int end = 10; int i; for(i = begin; i < end; i++) { mq.Enqueue(i); } for(i = begin; i < end; i++) { cout< mq2; mq2.Enqueue(1.1f); mq2.Enqueue(2.2f); cout << mq2.Dequeue() << endl; MyQueue mq3; string s1 = "hello"; string s2 = "world"; mq3.Enqueue(s1); mq3.Enqueue(s2); cout << mq3.Dequeue() << endl; return 0;}

运行结果：

01 2 3 4 5 6 7 8 9

1.1

hello

Pressany key to continue

方法二：

#include using namespace std;struct Node{public: Node(int i):data(i),next(NULL){} int data; Node *next;};class Stack{public: Stack():top(NULL){} void Push(Node node); //入栈 int Pop(); //出栈 bool IsEmpty(); //是否为空 void Print(); //打印所有元素private: Node *top;};void Stack::Push(Node node){ Node *n = new Node(node.data); n->next = top; top = n;}int Stack::Pop(){ if (IsEmpty()) { cout << "Stack Empty!" << endl; exit(1); } else { int topVal = top->data; Node *temp = top; top = top->next; delete temp; return topVal; }}bool Stack::IsEmpty(){ if (NULL == top) { return 1; } else { return 0; }}void Stack::Print(){ if(IsEmpty()) { cout << "Inner Stack Empty!" << endl; } else { Node *node = top; while (node != NULL) { cout << node->data << " "; node = node->next; } cout << endl; }}class Queue{public: void Enqueue(Node node); //入队 int Dequeue(); //出队 bool IsEmpty(); //是否为空private: Stack s1; //用于入队 Stack s2; //用于出队};void Queue::Enqueue(Node node){ s1.Push(node); //只对s1进行进栈操作 cout << "Enqueue " << node.data << endl;}int Queue::Dequeue(){ if(s2.IsEmpty()) { if(s1.IsEmpty()) //s2和s1都为空 { cout << "Queue Empty! Can not be dequeued again!" << endl; exit(1); } else //s2为空s1不为空，把s1的所有元素都倒入s2中 { while(!s1.IsEmpty()) { int i = s1.Pop(); s2.Push(Node(i)); } } } return s2.Pop();}bool Queue::IsEmpty(){ if (s1.IsEmpty() && s2.IsEmpty()) { return 1; } else { return 0; }}int main(){ Queue q; q.Enqueue(Node(1)); q.Enqueue(Node(2)); q.Enqueue(Node(3)); cout << "Dequeue " << q.Dequeue() << endl; q.Enqueue(Node(4)); cout << "Dequeue " << q.Dequeue() << endl; cout << "Dequeue " << q.Dequeue() << endl; cout << "Dequeue " << q.Dequeue() << endl; return 0;}

运行结果：

Enqueue1

Enqueue2

Enqueue3

Dequeue1

Enqueue4

Dequeue2

Dequeue3

Dequeue4

Pressany key to continue

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。