1.定义队列

typedef struct node{

int data;  
struct node \* next;

}Node;
typedef struct linkQueue
{
Node * first;
Node * rear;

}Queue;

2.两个栈实现一个队列

　 类定义：

#include
#include

using namespace std;
template class CQueue
{
public:
CQueue();
~CQueue();
void appendTail(const T& node);
T deleteHead();
private:
stack stack1;
stack stack2;
};

　　具体实现：

template CQueue::CQueue()
{
cout<<"CQueue"< CQueue::~CQueue()
{
cout<<"~CQueue"< void CQueue::appendTail(const T& node)
{
stack1.push(node);
cout<<"appendTail"<<endl;

}
template T CQueue:: deleteHead()
{
if(stack2.size()<=0) { while(stack1.size()>0)
{
T& data = stack1.top();
stack1.pop();
stack2.push(data);
}
}
if(stack2.size()==0)
{
cout<<"deleteHead:error"<<endl;
return NULL;
}else
{
T & head = stack2.top();
stack2.pop();
return head;
}
cout<<"deleteHead"<<endl;
}

　　调用：

int main()
{
CQueue cq;
cq.appendTail(2);
cq.appendTail(3);
cq.appendTail(1);
int i = cq.deleteHead();
cout << "val: "<<i<< endl;
return 0;
}

　　运行结果：

　　val:2

3.栈的转置

将当前栈的最底元素移到栈顶，其他元素顺次下移一位，然后继续不包含该栈顶元素的子栈。终止条件：递归下去，直到栈为空。代码如下

/**采用递归方式实现栈的转置**/
void Move_bottom2top(stack& s)
{
if(s.empty()) return;
int top1 = s.top();
s.pop();
if(!s.empty())
{
Move_bottom2top(s);
int top2 = s.top();
s.pop();
s.push(top1);
s.push(top2);
return;
}
s.push(top1);
}

/**栈转置**/
void Reverse(stack & s)
{
if(s.empty())return;
Move_bottom2top(s);
int top = s.top();
s.pop();
Reverse(s);
s.push(top);
}

4.栈的排序

和栈的转置思想类似

/**采用递归方式实现栈的排序**/
void Move_min2top(stack &s)
{
if(s.empty())return;
int top1 = s.top();
s.pop();
if(!s.empty())
{
Move_min2top(s);
int top2 = s.top();
if(top1>top2)
{
s.pop();
s.push(top1);
s.push(top2);
return;
}
}
s.push(top1);
}

/**栈排序**/
void Sort(stack & s)
{
if(s.empty())return;
if(!s.empty())
{
Move_min2top(s);
int top = s.top();
s.pop();
Sort(s);
s.push(top);
}
}

5.两个队列实现栈

　　定义栈类

/**两个队列实现一个栈**/
template class CStack
{
public:
CStack();
~CStack();
T pop();
void push(T e);
private:
queue queue1;
queue queue2;
};

　　实现

　　Pop

template T CStack::pop()
{
cout<<"Pop:"<<endl;
if(!queue1.empty())
{
while(queue1.size()!=1)
{
int front = queue1.front();
queue1.pop();
queue2.push(front);
}
T val = queue1.front();
queue1.pop();
return val;
}
if(!queue2.empty())
{
while(queue2.size()!=1)
{
int front = queue2.front();
queue2.pop();
queue1.push(front);
}
T val = queue2.front();
queue2.pop();
return val;
}
cout<<"Pop:error stack is null"<<endl;
return NULL;
}

　　Push

templatevoid CStack::push(T e)
{
cout<<"push:"<<endl;
if(!queue1.empty())
{
queue1.push(e);
return;
}
if(!queue2.empty())
{
queue2.push(e);
return;
}
queue1.push(e);
}