栈和队列互相变换

栈的特点是先进后出（FILO），队列的特点是先进先出（FIFO）。清除特点的前提下，两者可以互相实现。

队列实现栈

1、双队列法：使用两个队列，Q1为主要队列，Q2为辅助队列。

方案1：入队时的时间复杂度为O(n).

入栈操做：首先将元素入队到Q2,再将Q1的全部元素依次出队并入队到Q2，此时Q2的前端元素就是新入栈的元素，将Q1和Q2的身份互换，则Q1的元素即为栈内元素。

出栈操做：由于每次Q1的队头保留的是新入栈的元素，保证栈的后入先出，即出队Q1队首元素即可。

**栈顶元素：**获取Q1队首元素即可。

**判空操做:**判空Q1即可。

class queue2stack{
	public:
	    queue<int>q1;
		queue<int>q2;
        queue2stack(){
		}
	void push(int x){//入栈
		q2.push(x);
		while(!q1.empty()){
			q2.push(q1.front());
			q1.pop();
		}
		swap(q1,q2);
	}
	void pop(){//出栈
		q1.pop();
	}
	int get_top(){//栈顶元素
		return q1.front();
	}
	bool isempty(){//判空
		return q1.empty();
	}
	int size(){//栈的元素个数
		return q1.size();
	}
};

2、单队列

**入栈操做：**首先获得入栈前的元素个数n,然后将元素入队到队列，再将队列中的前n个元素（除了新入栈的元素之外的全部元素）依次出队并入队到队列，此时队列的前端的元素即为新入栈的元素。

**出栈操做：**由于每次操做保证了队列的前端为栈顶元素，因此出栈操做和获得首元素的操做只需获取队列的首元素即可。

class queue2stack{
	public:
	    queue<int>q;
        queue2stack(){	
		}
	void push(int x){
         int n=q.size();
         q.push(x);
         while(n--){
         	int t=q.front();
         	q.pop();
         	q.push(t);
		 }
	}
	void pop(){
         q.pop();
	}
	int get_top(){
		return q.front();
	}
	bool isempty(){
		return q.empty();
	}
	int size(){
		return q.size();
	}
};

栈实现队列《经典双栈法》

由于队列的特点是先进先出，所以需要两个栈。

**入队操做：**先将主栈元素全部弹入辅助栈，再将数据入栈到主栈，再把辅助栈中的元素依次弹入主栈。

**出队操做：**后加的元素沉在栈底，先进的元素在栈顶，因此直接弹栈即可。

class stack2queue{
	public:
	stack<int>s1;
    stack<int>s2;
	stack2queue(){}
	void push(int x){
		while(!s1.empty()){
			s2.push(s1.top());
			s1.pop();
		}
		s1.push(x);
		while(!s2.empty()){
			s1.push(s2.top());
			s2.pop();
		}
	}
	void pop(){
		s1.pop();
	}
	int top(){
		return s1.top();
	}
	int size(){
		return s1.size();
	}
	bool empty(){
		return s1.empty();
	}
};