面试题：两个队列实现一个栈

面试中，经常出现让你手写两个队列实现一个栈，或者两个栈实现一个队列的问题，很是头疼！

我们在前一篇米扑博客介绍了：两个栈实现一个队列

今天我们先探讨下：两个队列如何实现一个栈？

一、栈的特性

1、先进后出

2、进出都在栈顶

3、栈的实现有数组、链表

4、栈的应用场景有递归、深度遍历、函数名参数压栈等

二、队列的特性

1、先进先出

2、进在队尾，出在队头

3、队列的实现有数组、链表

4、队列的应用场景有消息队列、层次遍历等

三、两个栈实现一个队列

若用两个栈实现一个队列，思路如下：

Java 代码实现：

import java.util.Stack;

public class Stack2Queue {
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();

    public void push(int node) {
        stack1.push(node);
    }

    public int pop() {
        if(stack2.size()<=0){
            while(stack1.size()>0){
                /*int data = stack1.peek();//查看栈顶元素，但不移除它
                stack1.pop();//弹出栈顶元素
                stack2.push(data);//压入
                 */                             
                stack2.push(stack1.pop());
            }
        }

        if(stack2.isEmpty()){
            try {
                throw new Exception("queue is empty.");
            } catch (Exception e) {
            }
        }
        /**
         * int head = stack2.peek();
         * stack2.pop();
         */
        int head = stack2.pop();
        return head;
    }
}

详见米扑博客：两个栈实现一个队列

四、两个队列实现一个栈

如上图，注意两个队列的元素切换，解题思路：

1、一个队列加入元素，弹出元素时，需要把队列中的元素转移放到另外一个队列中，删除最后一个元素

2、两个队列始终保持只有一个队列是有数据，每次删除栈顶元素时，都需要转移一次队列的前(n-1)个元素

Java 代码实现（一）：

import java.util.ArrayDeque;
import java.util.Queue;

public class Queue2Stack {
    Queue<Integer> queue1 = new ArrayDeque<>();
    Queue<Integer> queue2 = new ArrayDeque<>();

    public void push(int node) {
        // 两个栈都为空时，优先考虑queue1
        if (queue1.isEmpty() && queue2.isEmpty()) {
            queue1.add(node);
            return;
        }

        // 如果queue1为空，queue2有元素，直接放入queue2
        if (queue1.isEmpty()) {
            queue2.add(node);
            return;
        }

        if (queue2.isEmpty()) {
            queue1.add(node);
            return;
        }
    }

    public int pop() {
        // 两个栈都为空时，没有元素可以弹出
        if (queue1.isEmpty() && queue2.isEmpty()) {
            try {
                throw new Exception("stack is empty");
            } catch (Exception e) {
            }
        }
        // 如果queue1为空，queue2有元素， 将queue2的元素依次放入queue1中，直到最后一个元素，我们弹出。
        if (queue1.isEmpty()) {
            while (queue2.size()>1) {
                queue1.add(queue2.poll());
            }
            return queue2.poll();
        }

        if (queue2.isEmpty()) {
            while (queue1.size()>1) {
                queue2.add(queue1.poll());
            }
            return queue1.poll();
        }

        return (Integer) null;
    }

    public static void main(String[] args) {
        Queue2Stack stack = new Queue2Stack();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        stack.push(5);
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
    }
}

Java 代码实现（二）：

import java.util.LinkedList;
import java.util.Queue;
 
/**
 * 两个队列实现一个栈
 * 1、一个队列加入元素，弹出元素时，需要把队列中的元素转移放到另外一个队列中，删除最后一个元素
 * 2、两个队列始终保持只有一个队列是有数据，每次删除栈顶元素时，都需要转移一次队列的前(n-1)个元素
 */
public class StackByQueue<T> {
	private Queue<T> queue1 = new LinkedList<>();
	private Queue<T> queue2 = new LinkedList<>();
	
	// 压栈，入栈非空的队列 
	public boolean push(T t) {
		/*
		// 此写法不严谨, 若queue2不为空, 应该向queue2队尾添加新元素, 此处判断不可以偷懒
		if (!queue1.isEmpty()) {
			return queue1.offer(t);
		} else {
			return queue2.offer(t);
		}
		*/

		// 正确的严谨写法
		if (queue1.isEmpty() && queue2.isEmpty()) {
			return queue1.offer(t);
		} 
		else if (queue1.isEmpty()) {
			return queue2.offer(t);
		} 
		else if (queue2.isEmpty()) {
			return queue1.offer(t);
		}
	}
	
	// 弹出并删除元素 
	public T pop() {
		if (queue1.isEmpty() && queue2.isEmpty()) {
			throw new RuntimeException("queue is empty");
		}
		if (!queue1.isEmpty() && queue2.isEmpty()) {
			while (queue1.size() > 1) {	// 保留队列的最后一个(队尾)元素
				queue2.offer(queue1.poll());
			}
			return queue1.poll();
		}

		if (queue1.isEmpty() && !queue2.isEmpty()) {
			while (queue2.size() > 1) {	// 保留队列的最后一个(队尾)元素
				queue1.offer(queue2.poll());
			}
			return queue2.poll();
		}
		return null;
	}
	
	@Override
	public String toString() {
		return this.queue1.toString() + ", " +this.queue2.toString();
	}
	
	// 主函数
	public static void main(String[] args) {
		StackByQueue<Integer> stack = new StackByQueue<>();
		stack.push(1);
		stack.push(2);
		stack.push(3);
		stack.pop();
		System.out.println(stack);
		stack.push(4);
		stack.push(5);
		stack.pop();
		System.out.println(stack);
	}
}

参考推荐：

LeetCode 19. 删除链表的倒数第 N 个结点

LeetCode 543. 二叉树的直径 (任意两结点最长距离)

LeetCode 206 反转链表（推荐先看）

LeetCode 2. 两链表整数相加生成一个和的新链表（含变异改进算法）

经典排序算法的复杂度分析

10大程序员基础实用算法

面试最常用的10大算法