通过队列实现栈

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

• void push(int x) 将元素 x 压入栈顶。
• int pop() 移除并返回栈顶元素。
• int top() 返回栈顶元素。
• boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

队列：先进先出

栈：后进先出

步骤：

1.基本结构的实现：

声明两个队列：qu1 和 qu2（调用java包）

构造方方法的实现：初始化两个队列qu1和qu2（调用LinkedList方法）

class MyStack {public   Queue<Integer> qu1;public   Queue<Integer> qu2;public MyStack() {qu1 = new LinkedList<>();qu2 = new LinkedList<>();}

2. push（入栈）方法的实现：

判断哪个队列不为空，不为空的队列通过offer方法将新元素插入到其中。

如果都为空，那就选择qu1队列进行插入。 （判断队列是否为空调用java包里的isEmpty方法）

具体代码如下：

public void push(int x) {
//判断哪个队列不为空，哪个不为空便插入哪个队列里if(!qu1.isEmpty()){ qu1.offer(x);}else if(!qu2.isEmpty()){qu2.offer(x);}else{qu1.offer(x);}}

3. 出栈（poll）方法的实现

假如qu1中有一组元素：按先进先出顺序插入1 2 3 4， 同时栈是后进后出

实现出栈，即将元素4出栈：

在队列中如何实现？：当qu1不为空时， 将qu1中的size-1 个元素通过队列pop（出队）方法移动到qu2中，结果如下图：

当qu2不为空时，方法一样，同上。

具体代码如下：

public int pop() { //出栈方法的实现if(empty()){return -1;}if(!qu1.isEmpty()){ //队列不为空int size = qu1.size();for(int i=0;i<size-1;i++) //将前size-1个元素尾插到空列表中{qu2.offer(qu1.poll()); //在qu1获取栈顶元素}return qu1.poll(); //返回qu1中仅剩的一个}else{int size = qu2.size();for(int i=0;i<size-1;i++){qu1.offer(qu2.poll());}return qu2.poll();}}

top方法的实现（获取栈顶元素）：

  在栈中，要得到的栈顶元素是4，则在两个队列中，

将不为空的队列里的元素全部通过for循环（pop方法），每次循环将栈顶元素赋给新建变量value（队列遵循先进先出），在通过另一个队列的offer方法插入到该空队列里，最后插入的元素即为出栈元素（栈遵循后进后出)，返回最后一个元素即可。具体代码如下：

public int top() {if(empty()){ //判断队列是否为空return -1;}if(!qu1.isEmpty()){int size = qu1.size();int val = 0;for(int i=0;i<size;i++){//将不为空的队列元素全部以出栈方式尾插到另一个队列里val = qu1.poll();qu2.offer(val);}return val;}else{
// qu2不为空int size = qu2.size();int val =0;for(int i=0;i<size;i++){val = qu2.poll();qu1.offer(val);}return val;}}

对于栈的判空方法：队列元素不为空。

public boolean empty() {return qu1.isEmpty() && qu2.isEmpty();}

到这里，这个问题已经被解决了，喜欢的老铁来个三连吧！