栈的特性：先进后出

讯享网
队列的特性：先进先出

解析：使用两个栈来实现一个队列，其实就是组合两个栈，来实现队列，栈是先进后出，队列是先进先出，可使用以下操作使用栈来实现队列：

一、入队列：

把需要存放的元素插入到栈1中

代码：

void push(const T&data){ stack1.push(data); }

二、出队列：

把栈1中的元素依次插入到栈2中

ps：此时栈顶元素就是需要出队列的元素
代码：

讯享网void Pop() { //如果两个栈都是空栈，此时说明队列是空的 if (stack1.empty() && stack2.empty()) cout << "this queue is empty" << endl; //如果栈2中有元素，那出队列就出栈2中的 if (!stack2.empty()){ stack2.pop(); } //此时表明栈2已是空栈，再要出队列的话，那就需要把栈1中的所有元 //素入栈到栈2中，注意一定要是栈1中的所有元素都入栈到栈2中 else{ while (stack1.size() > 0){ stack2.push(stack1.top()); stack1.pop(); } stack2.pop(); } }

有返回值的Pop函数（此返回值为队头元素）：

T&Pop() { T head; //如果两个栈都是空栈，此时说明队列是空的 if (stack1.empty() && stack2.empty()) cout << "this queue is empty" << endl; //如果栈2中有元素，那出队列就出栈2中的 if (!stack2.empty()){ head = stack2.top(); stack2.pop(); } //此时表明栈2已是空栈，再要出队列的话，那就需要把栈1中的所有元 //素入栈到栈2中,注意一定要是栈1中的所有元素都入栈到栈2中 else{ while (stack1.size() > 0){ stack2.push(stack1.top()); stack1.pop(); } head = stack2.top(); stack2.pop(); } return head; }

三、获取队头元素

队列的队头位于栈2的栈顶
只要栈2不空，那就返回栈2的栈顶元素
如果栈2为空，那就把栈1中的所有元素全部压入栈2中，再取栈顶

讯享网T&Front()//获取队头元素，此时队头位于栈2的栈顶 { assert(!stack1.empty() || !stack2.empty()); if (stack2.empty()){ while (!stack1.empty()){ stack2.push(stack1.top()); stack1.pop(); } } return stack2.top(); }

源代码

#include<iostream> #include<stack> #include<assert.h> using namespace std; template<class T> class Queue { public: //入队列 void push(const T&data){ stack1.push(data); } //出队列 void Pop() { //如果两个栈都是空栈，此时说明队列是空的 if (stack1.empty() && stack2.empty()) cout << "this queue is empty" << endl; //如果栈2中有元素，那出队列就出栈2中的 if (!stack2.empty()){ stack2.pop(); } //此时表明栈2已是空栈，再要出队列的话，那就需要把栈1中的所有元 //素入栈到栈2中,注意一定要是栈1中的所有元素都入栈到栈2中 else{ while (stack1.size() > 0){ stack2.push(stack1.top()); stack1.pop(); } stack2.pop(); } } T&Front()//获取队头元素，此时队头位于栈2的栈顶 { assert(!stack1.empty() || !stack2.empty()); if (stack2.empty()){ while (!stack1.empty()){ stack2.push(stack1.top()); stack1.pop(); } } return stack2.top(); } private: stack<T> stack1; stack<T> stack2; }; void TestQueue() { Queue<int> q; q.push(1); q.push(2); q.push(3); q.push(4); q.push(5); cout << "队头为:> "<<q.Front() << endl; q.Pop(); q.Pop(); q.Pop(); cout << "队头为:> " << q.Front() << endl; q.push(6); q.push(7); q.push(8); q.push(9); q.Pop(); q.Pop(); q.Pop(); cout << "队头为:> " << q.Front() << endl; } int main() { TestQueue(); system("pause"); return 0; }

运行结果：

Pop函数中返回队头元素时的源代码

讯享网#include<iostream> #include<stack> #include<assert.h> using namespace std; template<class T> class Queue { public: //入队列 void push(const T&data){ stack1.push(data); } //出队列 T&Pop() { T head; //如果两个栈都是空栈，此时说明队列是空的 if (stack1.empty() && stack2.empty()) cout << "this queue is empty" << endl; //如果栈2中有元素，那出队列就出栈2中的 if (!stack2.empty()){ head = stack2.top(); stack2.pop(); } //此时表明栈2已是空栈，再要出队列的话，那就需要把栈1中的所有元 //素入栈到栈2中,注意一定要是栈1中的所有元素都入栈到栈2中 else{ while (stack1.size() > 0){ stack2.push(stack1.top()); stack1.pop(); } head = stack2.top(); stack2.pop(); } return head; } T&Front()//获取队头元素，此时队头位于栈2的栈顶 { assert(!stack1.empty() || !stack2.empty()); if (stack2.empty()){ while (!stack1.empty()){ stack2.push(stack1.top()); stack1.pop(); } } return stack2.top(); } private: stack<T> stack1; stack<T> stack2; }; void TestQueue() { Queue<int> q; q.push(1); q.push(2); q.push(3); q.push(4); q.push(5); cout <<"队头为:> "<< q.Pop() << endl; cout << "队头为:> " << q.Pop() << endl; } int main() { TestQueue(); system("pause"); return 0; }

ps:是先返回队头，然后在Pop的，所以第一次输出队头为1，第二次输出队头为2