剑指 Offer 09. 用两个栈实现队列

问题描述

用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )

解题思路

• 定义两个栈，头栈和尾栈。
• 每次添加元素都从尾栈压入。
• 每次删除头元素，分为三种情况：
  • 如果头栈非空，则从头栈直接pop。
  • 如果头栈为空，尾栈也为空，则直接返回 -1 。
  • 如果头栈为空，尾栈不为空，则将尾栈元素依次pop出去，并将其压入头栈。最后返回头栈第一个元素。这样就保证了先进先出的原则。

class CQueue {
    private Stack<Integer> stackHead;
    private Stack<Integer> stackTail;

    public CQueue() {
        stackHead = new Stack<>();
        stackTail = new Stack<>();
    }

    public void appendTail(int value) {
        stackTail.push(value);
    }

    public int deleteHead() {
        if (!stackHead.isEmpty()) {
            return stackHead.pop();
        }
        if (stackTail.isEmpty()) {
            return -1;
        }
        while (!stackTail.isEmpty()) {
            stackHead.push(stackTail.pop());
        }
        return stackHead.pop();
    }
}