用队列实现栈
代码
#include<iostream> #include<stdexcept> using namespace std; template<typename T> class Queue { private: struct Node { T data; Node* next; Node(T x) :data(x), next(NULL) {} }; Node* first; Node* rear; int size; public: Queue() :first(NULL), rear(NULL), size(0) {} ~Queue(); void enqueue(T x); T dequeue(); T getFirst() const; int getSize() const; bool empty() const; }; template<typename T> Queue<T>::~Queue() { while (first) { Node* curr = first; first = first->next; delete curr; } } template<typename T> void Queue<T>::enqueue(T x) { if (rear == NULL) {//必须讨论队列长度为0的情况 rear = new Node(x); first = rear; } else { rear->next = new Node(x); rear = rear->next; } size++; } template<typename T> T Queue<T>::dequeue() { if (first == NULL) {//这里的判空语句只能用first不能用Size? throw std::underflow_error("queue is empty!"); } T result = first->data; Node* curr = first;//必须释放删除节点的内存 first = first->next; delete curr; size--;//一定不要忘记更新size if (size == 0) { rear = NULL; }//size为0后，代表所有的内存都被释放啦，那rear指向的内存当然也被释放啦，一定要置空rear，否则会变成野指针。 return result; } template<typename T> T Queue<T>::getFirst() const { if (size == 0) { throw std::underflow_error("queue is empty!"); } return first->data; } template<typename T> int Queue<T>::getSize() const {//返回值类型为int而不是T return size; } template<typename T> bool Queue<T>::empty() const { return size == 0; } class MyStack { private: Queue<int> q1; Queue<int> q2; public: MyStack() {} void push(int x) { q1.enqueue(x); } int pop() { while (q1.getSize() > 1) { q2.enqueue(q1.dequeue()); } int result = q1.dequeue(); while (!q2.empty()) { q1.enqueue(q2.dequeue()); } return result; } int top() { while (q1.getSize() > 1) { q2.enqueue(q1.dequeue()); } int result = q1.dequeue(); q2.enqueue(result); while (!q2.empty()) { q1.enqueue(q2.dequeue()); } return result; } bool empty() { return q1.empty();//由于q2每次执行完都为空，所以只需要判断q1是否为空即可 } }; int main() { return 0; }解释
首先利用链表来实现队列，首先是队列的类的实现，由于要利用链表来实现这个队列，所以成员变量不仅要包含指向头节点和尾节点的结构体指针first和rear,节点的数量size,还包含节点实现的结构体Node,结构体内部包含这个节点的数据域和指针域，以及结构体的构造函数，然后是公共权限的构造函数、析构函数、入队、出队、获取队首元素，获取队列的长度，判断队列是否为空。
template<typename T> class Queue { private: struct Node { T data; Node* next; Node(T x) :data(x), next(NULL) {} }; Node* first; Node* rear; int size; public: Queue() :first(NULL), rear(NULL), size(0) {} ~Queue(); void enqueue(T x); T dequeue(); T getFirst() const; int getSize() const; bool empty() const; };然后是具体函数的实现，首先是析构函数，经过模板声明和函数声明，在函数内部，利用while循环，遍历链表的每一个节点，同时利用curr指针暂存队首节点，不断释放链表的内存。
template<typename T> Queue<T>::~Queue() { while (first) { Node* curr = first; first = first->next; delete curr; } }然后是入队函数，首先经过模板声明和函数声明，函数内部，首先判断rear指针是否指向NULL，因为这代表链表长度为0，然后我们就让尾节点指向一个新申请出来的内存，内存存储的值为即将入队的元素，然后让first也指向这个内存，如果rear没有指向NULL，也就是这个链表内尚有元素，我们就直接让rear的后继节点指针指向新申请的内存，然后让rear向后偏移一个位置，让它指向最后一个元素，最后在判断语句外面，长度+1.
template<typename T> void Queue<T>::enqueue(T x) { if (rear == NULL) {//必须讨论队列长度为0的情况 rear = new Node(x); first = rear; } else { rear->next = new Node(x); rear = rear->next; } size++; }然后是出队函数，首先经过模板声明和函数声明，函数内部，首先判断first是否指向NULL，这代表链表为空，若为空则抛出异常，否则我们利用result变量暂存队首节点的数据，然后利用结构体指针curr暂存队首节点，然后偏移first,然后释放curr指向的内存，同时让链表的长度-1，然后判断链表的长度是否为0，若为0则使rear指针置为空，因为size为0后，代表所有的内存都被释放啦，那rear指向的内存当然也被释放啦，一定要置空rear，否则会变成野指针。最后返回result.
template<typename T> T Queue<T>::dequeue() { if (first == NULL) {//这里的判空语句只能用first不能用Size?都可以，只不过first更加保险 throw std::underflow_error("queue is empty!"); } T result = first->data; Node* curr = first;//必须释放删除节点的内存 first = first->next; delete curr; size--;//一定不要忘记更新size if (size == 0) { rear = NULL; }//size为0后，代表所有的内存都被释放啦，那rear指向的内存当然也被释放啦，一定要置空rear，否则会变成野指针。 return result; }然后是返回队首元素、返回队列长度、判断是否为空的函数，三个函数都要添加const,代表函数内部不会改变成员变量，这里我多嘴一句，即便是函数内部途中改变了成员变量，也不行。
template<typename T> T Queue<T>::getFirst() const { if (size == 0) { throw std::underflow_error("queue is empty!"); } return first->data; } template<typename T> int Queue<T>::getSize() const {//返回值类型为int而不是T return size; } template<typename T> bool Queue<T>::empty() const { return size == 0; }然后是栈的类的实现部分，首先是类的实现，这个实现的是int类型的栈q1和q2，所以成员变量用的是int类型的两个队列，然后是毫无作为的构造函数，因为前面队列的实现中已经都做了初始化，
然后是入栈函数，具体实现是将元素压入q1的队列中。
class MyStack { private: Queue<int> q1; Queue<int> q2; public: MyStack() {} void push(int x) { q1.enqueue(x); }然后是出栈的函数，函数内部具体实现是，首先将q1中元素依次压入q2中，直到q1中只剩1个元素，然后result暂存q1的最后一个元素，并让q1弹出最后一个元素，然后再把q2中的元素全部压入q1中，我们规定，q2在每次函数结束后必须置空，最后返回result.
int pop() { while (q1.getSize() > 1) { q2.enqueue(q1.dequeue()); } int result = q1.dequeue(); while (!q2.empty()) { q1.enqueue(q2.dequeue()); } return result; }然后是获取栈顶元素，跟出栈的函数差不多，区别在于q1的最后一个元素也要传入q2中。
最后是判断是否为空的函数，由于q2每次执行完都为空，所以我们只需要判断q1即可.
int top() { while (q1.getSize() > 1) { q2.enqueue(q1.dequeue()); } int result = q1.dequeue(); q2.enqueue(result); while (!q2.empty()) { q1.enqueue(q2.dequeue()); } return result; } bool empty() { return q1.empty();//由于q2每次执行完都为空，所以只需要判断q1是否为空即可 } };