云服务器做网站上海广告推广

题目：用两个栈实现一个队列。队列的生命如下，请实现它的两个函数appendTail和deleteHead，分别完成在队列尾部插入结点和在队列头部删除结点的功能。template <typename T>class CQueue
{
public:CQueue(void);~CQueue(void);void appendtail(const T& node);T deleteHead();
private:stack<T> stack1;stack<T> stack2;
};

解题思路：

插入操作在stack1中进行，删除操作在stack2中进行，如果stack2为空，则将stack1中的所有元素转移到stack2中。

代码实例：

#include<iostream>
#include<stdlib.h>
#include<stack>
using namespace std;template <typename T>class CQueue
{
public:CQueue(void);~CQueue(void);void appendtail(const T& node);T deleteHead();
private:stack<T> stack1;stack<T> stack2;};//构造函数
template <typename T> CQueue<T>::CQueue(void)
{
}//析构函数
template <typename T> CQueue<T>::~CQueue(void)
{
}//插入元素
template <typename T> void CQueue<T>::appendtail(const T& node)
{stack1.push(node);
}//删除元素并返回
template <typename T> T CQueue<T>::deleteHead()
{if(stack2.size()<=0){while(stack1.size()>0){stack2.push(stack1.top());stack1.pop();}}if(stack2.size()==0)throw new exception("队列为空");T head=stack2.top();stack2.pop();return head;
}void main()
{CQueue<int> queue;queue.appendtail(1);queue.appendtail(2);queue.appendtail(3);queue.appendtail(4);int len=4;while(len>0){cout<<queue.deleteHead()<<endl;--len;}system("pause");
}

使用两个队列实现一个栈

参考文献：

http://hi.baidu.com/ozwarld/blog/item/ec9b52d4d48ce1dc50da4b0f.html

解法：

1. 有两个队列q1和q2，先往q1内插入a，b，c，这做的都是栈的push操作。
2. 现在要做pop操作，即要得到c，这时可以将q1中的a,b两个元素全部dequeue并存入q2中，这时q2中元素为a，b，对q1再做一次dequeue操作即可得到c。
3. 如果继续做push操作，比如插入d，f，则把d，f插入到q2中，
4. 此时若要做pop操作，则做步骤2
5. 以此类推，就实现了用两个队列来实现一个栈的目的。

注意在此过程中，新push进来的元素总是插入到非空队列中，空队列则用来保存pop操作之后的那些元素，那么此时空队列不为空了，原来的非空队列变为空了，总是这样循环。

对于push和pop操作，其时间为O(n).

代码实例

#include<iostream>
#include<stdlib.h>
#include<stack>
#include<queue>
using namespace std;template <typename T>class CStack
{
public:CStack(void){};~CStack(void){};void push(const T& node);T pop();
private:queue<T> queue1;queue<T> queue2;};//插入元素
template <typename T> void CStack<T>::push(const T& element)
{if(queue1.size()>0)//如果queue1不为空则往queue1中插入元素
        queue1.push(element);else if(queue2.size()>0)//如果queue2不为空则往queue2中插入元素
        queue2.push(element);else//如果两个队列都为空，则往queue1中插入元素
        queue1.push(element);}//删除元素
template <typename T> T CStack<T>::pop()
{if(queue1.size()==0)//如果queue1为空
    {while(queue2.size()>1)//保证queue2中有一个元素，将其余元素保存到queue1中
        {queue1.push(queue2.front());queue2.pop();}T& data=queue2.front();queue2.pop();return data;}else//如果queue2为空
    {while(queue1.size()>1)//保证queue2中有一个元素，将其余元素保存到queue1中
        {queue2.push(queue1.front());queue1.pop();}T& data=queue1.front();queue1.pop();return data;}}void main()
{CStack<int> stack;stack.push(1);stack.push(2);stack.push(3);stack.push(4);int len=4;while(len>0){cout<<stack.pop()<<" ";--len;}system("pause");
}