题目： 用两个栈实现一个队列。 请实现它的两个函数appendTail和deleteHead, 分别完成在队列尾部插入结点和在队列头部删除节点的功能

解法： 操作这两个“ 先进后出＂的栈实现一个“先进先出” 的队列Queue，具体看图

当stack2中不为空时，在stack2中的栈顶元素是最先进入队列的元素，可以弹出。如果 stack2为空时，我们把stack1中的元素逐个弹出并压入stack2。由于先进入队列的元素被压到stack1的底端，经过弹出和压入之后就处于stack2的顶端了，又可以直接弹出。

代码实现（牛客OJ）：

import java.util.Stack;

public class Solution {
    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.empty()) {
            if (stack1.empty()) {
                return 0;
            }
            while (!stack1.empty()) {
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }
}

以上，该题不具备复杂逻辑，仅需考虑数据结构特性。

扩展题

题目：用两个队列实现一个栈

主要思路：两个队列交替工作，拿三个元素:a,b,c举例，依次压入queue1，queue2为空，此时若想模拟栈的弹出，则只能将queue1的前两项a，b压入queue2，然后弹出queue1中的c即可，对于即将弹出的b来说也是同理，将queue2中的a压入queue1中，弹出queue2的b即可，若此时需压入新元素多个，则将其依次放在非空队列中并按上面的逻辑交替便可解该题。注：两个队列中至少一个为空，为啥捏？看图

代码：两个队列的实现

static Queue<Integer> queue1 = new ArrayDeque<Integer>();
static Queue<Integer> queue2 = new ArrayDeque<Integer>();

public static void push(int node) {
    if (queue1.size() > queue2.size()) {
        //queue1中有元素
        queue1.add(node);
    } else {
        //queue2中有元素
        queue2.add(node);
    }
}

public static int pop() {
    if (isEmpty()) {
        return -1;
    }
    if (queue1.size() > queue2.size()) {
        //将queue1中的元素添加至queue2 queue1仅保留一个元素 并返回queue1顶部元素
        return swapExceptTop(queue1, queue2);
    } else {
        return swapExceptTop(queue2, queue1);
    }
}

public static int swapExceptTop(Queue<Integer> orig, Queue<Integer> dest) {
    if (orig.isEmpty()) {
        return -1;
    }
    while (orig.size() != 1) {
        dest.add(orig.poll());
    }
    return orig.poll();
}

public static boolean isEmpty() {
    return queue1.isEmpty() && queue2.isEmpty();
}

精简版：一个队列的实现

static Queue<Integer> queue = new ArrayDeque<Integer>();

public static void push(int node) {
    queue.add(node);
}

public static int pop() {
    if (queue.isEmpty()) {
        return -1;
    }
    for (int i = 0; i < queue.size()-1; i++) {
        queue.add(queue.poll());
    }
    return queue.poll();
}

测试主函数：

public static void main(String[] args) {
    push(1);    push(2);
    push(3);    push(4);
    while (!queue.isEmpty()) {
        System.out.print(pop() + " ");
    }
}

以上。是剑指offer关于栈和队列的面试题。

若对新手不友好，可参看有注释的文章，如：https://cloud.tencent.com/developer/article/1163041