栈与队列

栈和队列是两种基本的数据结构，栈遵循后进先出（LIFO）原则，队列遵循先进先出（FIFO）原则。

面试题 03.01. 三合一

题目描述

三合一。描述如何只用一个数组来实现三个栈。

你应该实现 push(stackNum, value)、pop(stackNum)、isEmpty(stackNum)、peek(stackNum) 方法。stackNum 表示栈下标，value 表示压入的值。

构造函数会传入一个 stackSize 参数，代表每个栈的大小。

示例 1：

输入：
["TripleInOne", "push", "push", "pop", "pop", "pop", "isEmpty"]
[[1], [0, 1], [0, 2], [0], [0], [0], [0]]
输出：
[null, null, null, 1, -1, -1, true]

解题思路

将数组分成三段，每段对应一个栈。使用三个指针记录每个栈的当前位置。每个栈的范围是 [i * stackSize, (i + 1) * stackSize)。

Java 代码实现

class TripleInOne {
    private int[] arr;
    private int[] top;
    private int stackSize;

    public TripleInOne(int stackSize) {
        this.stackSize = stackSize;
        arr = new int[stackSize * 3];
        top = new int[3];
        top[0] = 0;
        top[1] = stackSize;
        top[2] = stackSize * 2;
    }
    
    public void push(int stackNum, int value) {
        if (top[stackNum] < (stackNum + 1) * stackSize) {
            arr[top[stackNum]++] = value;
        }
    }
    
    public int pop(int stackNum) {
        if (isEmpty(stackNum)) {
            return -1;
        }
        return arr[--top[stackNum]];
    }
    
    public int peek(int stackNum) {
        if (isEmpty(stackNum)) {
            return -1;
        }
        return arr[top[stackNum] - 1];
    }
    
    public boolean isEmpty(int stackNum) {
        return top[stackNum] == stackNum * stackSize;
    }
}

---

面试题 03.02. 栈的最小值

题目描述

请设计一个栈，除了常规栈支持的 pop 与 push 函数以外，还支持 min 函数，该函数返回栈元素中的最小值。执行 push、pop 和 min 操作的时间复杂度必须为 O(1)。

示例：

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.

解题思路

使用辅助栈来存储每个位置对应的最小值。每次 push 时，辅助栈 push 当前最小值；每次 pop 时，辅助栈也 pop。

Java 代码实现

class MinStack {
    private Stack<Integer> stack;
    private Stack<Integer> minStack;

    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();
    }
    
    public void push(int x) {
        stack.push(x);
        if (minStack.isEmpty() || x <= minStack.peek()) {
            minStack.push(x);
        } else {
            minStack.push(minStack.peek());
        }
    }
    
    public void pop() {
        stack.pop();
        minStack.pop();
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int getMin() {
        return minStack.peek();
    }
}

---

面试题 03.03. 堆盘子

题目描述

堆盘子。设想有一堆盘子，堆太高可能会倒下来。因此，在现实生活中，盘子堆到一定高度时，我们就会另外堆一堆盘子。请实现数据结构 SetOfStacks，模拟这种行为。SetOfStacks 由多个栈组成，并且在前一个栈填满时新建一个栈。此外，SetOfStacks.push() 和 SetOfStacks.pop() 应该和普通栈的操作方法相同（也就是说，pop()返回的值，应该跟只有一个栈时的情况一样）。

**进阶：**实现一个 popAt(int index) 方法，根据指定的子栈，执行 pop 操作。

示例 1：

输入：
["StackOfPlates", "push", "push", "pop", "pop", "pop"]
[[1], [1], [2], [], [], []]
输出：
[null, null, null, 2, 1, -1]

解题思路

使用 List<Stack<Integer>> 存储多个栈。push 时检查最后一个栈是否已满，如果满了就新建一个栈。pop 时从最后一个栈弹出，如果栈空了就删除该栈。

Java 代码实现

class StackOfPlates {
    private List<Stack<Integer>> stacks;
    private int cap;

    public StackOfPlates(int cap) {
        this.cap = cap;
        stacks = new ArrayList<>();
    }
    
    public void push(int val) {
        if (cap <= 0) return;
        if (stacks.isEmpty() || stacks.get(stacks.size() - 1).size() == cap) {
            stacks.add(new Stack<>());
        }
        stacks.get(stacks.size() - 1).push(val);
    }
    
    public int pop() {
        if (stacks.isEmpty()) return -1;
        int val = stacks.get(stacks.size() - 1).pop();
        if (stacks.get(stacks.size() - 1).isEmpty()) {
            stacks.remove(stacks.size() - 1);
        }
        return val;
    }
    
    public int popAt(int index) {
        if (index < 0 || index >= stacks.size()) return -1;
        int val = stacks.get(index).pop();
        if (stacks.get(index).isEmpty()) {
            stacks.remove(index);
        }
        return val;
    }
}

---

面试题 03.04. 化栈为队

题目描述

实现一个 MyQueue 类，该类用两个栈来实现一个队列。

示例：

MyQueue queue = new MyQueue();
queue.push(1);
queue.push(2);
queue.peek();  // 返回 1
queue.pop();   // 返回 1
queue.empty(); // 返回 false

解题思路

使用两个栈：一个入栈 inStack，一个出栈 outStack。

• push 操作：直接 push 到 inStack
• pop/peek 操作：如果 outStack 为空，将 inStack 的所有元素 pop 并 push 到 outStack，然后从 outStack 操作

Java 代码实现

class MyQueue {
    private Stack<Integer> inStack;
    private Stack<Integer> outStack;

    public MyQueue() {
        inStack = new Stack<>();
        outStack = new Stack<>();
    }
    
    public void push(int x) {
        inStack.push(x);
    }
    
    public int pop() {
        if (outStack.isEmpty()) {
            while (!inStack.isEmpty()) {
                outStack.push(inStack.pop());
            }
        }
        return outStack.pop();
    }
    
    public int peek() {
        if (outStack.isEmpty()) {
            while (!inStack.isEmpty()) {
                outStack.push(inStack.pop());
            }
        }
        return outStack.peek();
    }
    
    public boolean empty() {
        return inStack.isEmpty() && outStack.isEmpty();
    }
}

---

面试题 03.05. 栈排序

题目描述

栈排序。编写程序，对栈进行排序使最小元素位于栈顶。最多只能使用一个其他的临时栈存放数据，但不得将元素复制到别的数据结构（如数组）中。该栈支持如下操作：push、pop、peek 和 isEmpty。当栈为空时，peek 返回 -1。

示例 1：

输入：
["SortedStack", "push", "push", "peek", "pop", "peek"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 1, 1, 2]

解题思路

使用辅助栈来帮助排序。push 时，将栈中比当前值小的元素先移到辅助栈，插入当前值后再移回来。这样可以保证栈中的元素始终是有序的（栈顶最小）。

Java 代码实现

class SortedStack {
    private Stack<Integer> stack;
    private Stack<Integer> helper;

    public SortedStack() {
        stack = new Stack<>();
        helper = new Stack<>();
    }
    
    public void push(int val) {
        while (!stack.isEmpty() && stack.peek() < val) {
            helper.push(stack.pop());
        }
        stack.push(val);
        while (!helper.isEmpty()) {
            stack.push(helper.pop());
        }
    }
    
    public void pop() {
        if (!stack.isEmpty()) {
            stack.pop();
        }
    }
    
    public int peek() {
        return stack.isEmpty() ? -1 : stack.peek();
    }
    
    public boolean isEmpty() {
        return stack.isEmpty();
    }
}

---

面试题 03.06. 动物收容所

题目描述

动物收容所。有家动物收容所只收容狗与猫，且严格遵守"先进先出"的原则。在收养该收容所的动物时，收养人只能收养所有动物中"最老"（由其进入收容所的时间长短而定）的动物，或者可以挑选猫或狗（同时必须收养此类动物中"最老"的）。换言之，收养人不能自由挑选想收养哪只动物。请创建适用于这个系统的数据结构，实现各种操作方法，如 enqueue、dequeueAny、dequeueDog 和 dequeueCat。允许使用 Java 内置的 LinkedList 数据结构。

示例 1：

输入：
["AnimalShelf", "enqueue", "enqueue", "dequeueCat", "dequeueDog", "dequeueAny"]
[[], [[0, 0]], [[1, 0]], [], [], []]
输出：
[null, null, null, [0, 0], [-1, -1], [1, 0]]

解题思路

使用两个队列分别存储狗和猫，每个元素记录其编号和进入顺序。dequeueAny 时比较两个队列队首的进入顺序，返回较早的那个。

Java 代码实现

class AnimalShelf {
    private LinkedList<int[]> dogs;
    private LinkedList<int[]> cats;
    private int order;

    public AnimalShelf() {
        dogs = new LinkedList<>();
        cats = new LinkedList<>();
        order = 0;
    }
    
    public void enqueue(int[] animal) {
        if (animal[1] == 0) {
            cats.add(new int[]{animal[0], order++});
        } else {
            dogs.add(new int[]{animal[0], order++});
        }
    }
    
    public int[] dequeueAny() {
        if (dogs.isEmpty() && cats.isEmpty()) {
            return new int[]{-1, -1};
        }
        if (dogs.isEmpty()) {
            return dequeueCat();
        }
        if (cats.isEmpty()) {
            return dequeueDog();
        }
        if (dogs.peek()[1] < cats.peek()[1]) {
            return dequeueDog();
        } else {
            return dequeueCat();
        }
    }
    
    public int[] dequeueDog() {
        if (dogs.isEmpty()) {
            return new int[]{-1, -1};
        }
        return new int[]{dogs.poll()[0], 1};
    }
    
    public int[] dequeueCat() {
        if (cats.isEmpty()) {
            return new int[]{-1, -1};
        }
        return new int[]{cats.poll()[0], 0};
    }
}