用两个栈实现队列

Posted on In Views: Waline: Views: Symbols count in article: 522 Reading time ≈ 1 mins.

题解方法

  • 栈

栈

  • 一个栈作为输入栈，当 appendTail 操作时 push 数据
  • 一个栈作为输出栈，当 deleteHead 操作时，若该栈为空，则将输入栈的所有数据出栈并入输出栈，此时该栈的出栈顺序满足 deleteHead 要求

核心代码

栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public void appendTail(int value) {
    inStack.push(value);
}

public int deleteHead() {
    // 如果 outStack 为空，将 inStack 中的元素全部压入 outStack
    if (outStack.isEmpty()) {
        while (!inStack.isEmpty()) {
            outStack.push(inStack.pop());
        }
    }
    // 如果 outStack 仍为空，说明 inStack 也为空，返回 -1
    if (outStack.isEmpty()) {
        return -1;
    }
    else {
        return outStack.pop();
    }
}

题目来源

剑指 Offer 09. 用两个栈实现队列 - 力扣（LeetCode）