[剑指offer]用两个堆栈实现队列
题目描述
用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
解题思路：首先需要了解栈和队列两种结构的性质。
queue是一种”先进先出”的数据结构，他在对尾插入元素，在队头删除元素，他既可以取到自己的队头元素，也可以取到自己的队尾元素；
stack是一种”先进后出”的数据结构，他对元素的插入和删除都是在栈顶完成的；他不可以取自己栈底的元素；只能去取自己栈顶的元素；
所以将队列元素存储到堆栈1时，出来的顺序是相反的，为此我们可以再引入一个栈2，将栈1的数据存入，使得数据再次逆序，由此得到与队列相同的输出。
步骤：
1、入队:将新元素push入栈A;
2、出队:
(1)判断栈B是否为空；
(2)如果不为空，则将栈A中所有元素依次pop出并push到栈B；
(3)将栈B的栈顶元素pop出；
class Solution
{
public:
void push(int node) {
stack1.push(node); //将队列数据存入堆栈1
}
int pop() {
//判断栈1和栈2是否为空，为空显示
if(stack1.empty() && stack2.empty()) {
cout << "The queue is empty"<<endl;
}
//用栈1存放数据，用栈2将数据的顺序恢复成原始顺序
//当栈2不为空的时候，输出其中的数据
if(stack2.empty()) {
while(!stack1.empty()) { //当栈2为空的时候，将栈1的数据逐个存入栈2
int data=stack1.top();
stack2.push(data);
stack1.pop();
}
}
int head=stack2.top(); //将栈2的数据pop出来
stack2.pop();
return head;
}
private:
stack<int> stack1;
stack<int> stack2;
};
延伸：
题目描述
用两个队列实现栈
解题思路：实现栈的插入，删除，和返回栈顶元素三个方法即可；
（1）插入：每次找不为空的队列进行插入，这样就不存在确定的辅助队列和主队列之说，两个队列交替存储数据；这样效率更高；
（2）删除；每次先找到不为空的队列，然后将这个队列当做主队列，将另一个辅助队列，将主队列的数据依次取队头元素插入辅助队列，直到主队列剩下一个元素；然后利用栈的头删功能将次元素删除；O(n)
（3）返回栈顶元素：那个队列不为空，就取那个队列的队尾返回；这就是栈的栈顶元素。
//用两个队列实现栈
class Stack
{
public:
void Push(int node)//插入
{
if (q1.empty()&&q2.empty())//两个队列都为空
{
q1.push(node);//向q1种插入元素
}
else if(!q1.empty())//q1不为空，q2为空
{
q1.push(node);//向q1中插入元素
}
else//q1为空，q2不为空
{
q2.push(node);//向q2中插入元素
}
}
void Pop()//删除
{
//if (q1.empty()&&q2.empty())//q1,q2为空
//{
// cout<<"无元素"<<endl;
//}
/*else*/
if (!q1.empty())//q1不为空，q2为空
{
while (q1.size()>1)//转移元素到q2,q1中留下一个删除
{
q2.push(q1.front());
q1.pop();
}
q1.pop();//q1中留下一个删除
}
else
//q2不为空，q1为空
{
while (q2.size()>1)//转移元素到q1,q2中留下一个删除
{
q1.push(q2.front());
q2.pop();
}
q2.pop();//q2中留下一个删除
}
}
private:
//两个队列成员
queue<int> q1;
queue<int> q2;
};