数据结构面试题：栈与队列

1. 只用一个数组来实现三个栈

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

和许多问题一样，这个问题的解法基本上取决于你要对栈支持到什么程度。若每个栈分配固定大小的空间，就能满足需要，那么照做便是。不过，这么做的话，有可能其中一个栈的空间不够用了，而同时其他的栈却几乎是空的。另一种做法是弹性处理栈的空间分配，但这么一来，这个问题的复杂度又会大大增加。

方法1：固定分割

我们可以将整个数组划分为三等份，将每个栈的增长限制在各自的空间里。注意：记号“[”表示包含端点，“(”表示不包含端点。

• 栈1，使用[0, n/3)。
• 栈2，使用[n/3, 2n/3)。
• 栈3，使用[2n/3, n)。

下面是该解法的实现代码。

int stackSize = 100;
int[] buffer = new int [stackSize * 3];
int[] stackPointer = {-1, -1, -1}; // 用于追踪栈顶元素的指针

void push(int stackNum, int value) throws Exception {
    /* 检查有无空闲空间*/
    if (stackPointer[stackNum] + 1 >= stackSize) { // 最后一个元素
        throw new Exception(“Out of space.”);
    }
    /* 栈指针自增，然后更新栈顶元素的值*/
    stackPointer[stackNum]++;
    buffer[absTopOfStack(stackNum)] = value;
}

int pop(int stackNum) throws Exception {
    if (stackPointer[stackNum] == -1) {
        throw new Exception(“Trying to pop an empty stack.”);
    }
    int value = buffer[absTopOfStack(stackNum)]; // 获取栈顶元素的值
    buffer[absTopOfStack(stackNum)] = 0; // 清零指定索引元素的值
    stackPointer[stackNum]--; // 指针自减
    return value;
}

int peek(int stackNum) {
    int index = absTopOfStack(stackNum);
    return buffer[index];
}

boolean isEmpty(int stackNum) {
    return stackPointer[stackNum] == -1;
}

/* 返回栈“stackNum”栈顶元素的索引，绝对量*/
int absTopOfStack(int stackNum) {
    return stackNum * stackSize + stackPointer[stackNum];
}

如果知道与这些栈的使用情况相关的更多信息，就可以对上面的算法做相应的改进。例如，若预估Stack 1的元素比Stack 2多很多，那么，就可以给Stack 1多分配一点空间，给Stack 2少分配一些空间。

方法2：弹性分割

第二种做法是允许栈块的大小灵活可变。当一个栈的元素个数超出其初始容量时，就将这个栈扩容至许可的容量，必要时还要搬移元素。

此外，我们会将数组设计成环状的，最后一个栈可能从数组末尾开始，环绕到数组开头。

请注意，这种解法的代码远比面试中常见的要复杂得多。你可以试着提供伪码，或是其中某几部分的代码，但要完整实现的话，难度就有点大了。

/* StackData是个简单的类，存放每个栈相关的数据，
 * 但并未存放栈的实际元素*/
public class StackData {
    public int start;
    public int pointer;
    public int size = 0;
    public int capacity;
    public StackData(int _start, int _capacity) {
        start = _start;
        pointer = _start - 1;
        capacity = _capacity;
    }

    public boolean isWithinStack(int index, int total_size) {
        /* 注意：如果栈回绕了，首部（右侧）回绕到
         * 左边*/
        if (start <= index && index < start + capacity) {
            // 不回绕，或回绕时的“首部”（右侧）
            return true;
        } else if (start + capacity > total_size &&
                index < (start + capacity) % total_size) {
            // 回绕时的尾部（左侧）
            return true;
        }
        return false;
    }
}

public class QuestionB {
    static int number_of_stacks = 3;
    static int default_size = 4;
    static int total_size = default_size * number_of_stacks;
    static StackData [] stacks = {new StackData(0, default_size),
            new StackData(default_size, default_size),
            new StackData(default_size * 2, default_size)};
    static int [] buffer = new int [total_size];

    public static void main(String [] args) throws Exception {
        push(0, 10);
        push(1, 20);
        push(2, 30);
        int v = pop(0);
        ...
    }

    public static int numberOfElements() {
        return stacks[0].size + stacks[1].size + stacks[2].size;
    }

    public static int nextElement(int index) {
        if (index + 1 == total_size) 
            return 0;
        else 
            return index + 1;
    }

    public static int previousElement(int index) {
        if (index == 0) 
            return total_size - 1;
        else 
            return index - 1;
    }

    public static void shift(int stackNum) {
        StackData stack = stacks[stackNum];
        if (stack.size >= stack.capacity) {
            int nextStack = (stackNum + 1) % number_of_stacks;
            shift(nextStack); // 腾出若干空间
            stack.capacity++;
        }

        // 以相反顺序搬移元素
        for (int i = (stack.start + stack.capacity - 1) % total_size;
                stack.isWithinStack(i, total_size);
            i = previousElement(i)) {
            buffer[i] = buffer[previousElement(i)];
        }

        buffer[stack.start] = 0;
        stack.start = nextElement(stack.start); // 移动栈的起始位置
        stack.pointer = nextElement(stack.pointer); // 移动指针
        stack.capacity--; // 恢复到原先的容量
    }

    /* 搬移到其他栈上，以扩大栈的容量*/
    public static void expand(int stackNum) {
        shift((stackNum + 1) % number_of_stacks);
        stacks[stackNum].capacity++;
    }

    public static void push(int stackNum, int value)
            throws Exception {
        StackData stack = stacks[stackNum];
        /* 检查空间够不够*/
        if (stack.size >= stack.capacity) {
            if (numberOfElements() >= total_size) { // 全部都满了
                throw new Exception(“Out of space.”);
            } else { // 只是需要搬移元素
                expand(stackNum);
            }
        }
        /* 找出顶端元素在数组中的索引值，并加1，
         * 并增加栈指针*/
        stack.size++;
        stack.pointer = nextElement(stack.pointer);
        buffer[stack.pointer] = value;
    }

    public static int pop(int stackNum) throws Exception {
        StackData stack = stacks[stackNum];
        if (stack.size == 0) {
            throw new Exception(“Trying to pop an empty stack.”);
        }
        int value = buffer[stack.pointer];
        buffer[stack.pointer] = 0;
        stack.pointer = previousElement(stack.pointer);
        stack.size--;
        return value;
    }

    public static int peek(int stackNum) {
        StackData stack = stacks[stackNum];
        return buffer[stack.pointer];
    }

    public static boolean isEmpty(int stackNum) {
        StackData stack = stacks[stackNum];
        return stack.size == 0;
    }
}

遇到类似的问题，应该力求编写清晰、可维护的代码，这很重要。你应该引入额外的类，比如这里使用了StackData，并将大块代码独立为单独的方法。当然，这个建议同样适用于真正的软件开发。

2. 设计一个栈实现pop、push和min三个方法

请设计一个栈，除pop与push方法，还支持min方法，可返回栈元素中的最小值。push、pop和min三个方法的时间复杂度必须为O(1)。

既然是最小值，就不会经常变动，只有在更小的元素加入时，才会改变。

一种解法是在Stack类里添加一个int型的minValue。当minValue出栈时，我们会搜索整个栈，找出新的最小值。可惜，这不符合入栈和出栈操作时间为O(1)的要求。

为进一步理解这个问题，下面用一个简短的例子加以说明：

push(5); // 栈为{5}，最小值为5
push(6); // 栈为{6, 5}，最小值为5
push(3); // 栈为{3, 6, 5}，最小值为3
push(7); // 栈为{7, 3, 6, 5}，最小值为3
pop(); // 弹出7，栈为{3, 6, 5}，最小值为3
pop(); // 弹出3，栈为{6, 5}，最小值为5

注意观察，当栈回到之前的状态（{6, 5}）时，最小值也回到之前的状态（5），这就导出了我们的第二种解法。

只要记下每种状态的最小值，我们就能轻易获取最小值。实现很简单，每个结点记录当前最小值即可。这么一来，要找到min，直接查看栈顶元素就能得到最小值。

当一个元素入栈时，该元素会记下当前最小值，将min记录在自身数据结构的min成员中。

public class StackWithMin extends Stack<NodeWithMin> {
    public void push(int value) {
        int newMin = Math.min(value, min());
        super.push(new NodeWithMin(value, newMin));
    }

    public int min() {
        if (this.isEmpty()) {
            return Integer.MAX_VALUE; // 错误值
        } else {
            return peek().min;
        }
    }
}

class NodeWithMin {
    public int value;
    public int min;
    public NodeWithMin(int v, int min){
        value = v;
        this.min = min;
    }
}

但是，这种做法有个缺点：当栈很大时，每个元素都要记录min，就会浪费大量空间。还有没有更好的做法？

利用额外的栈来记录这些min，我们也许可以比之前做得更好一点。

public class StackWithMin2 extends Stack<Integer> {
    Stack<Integer> s2;
    public StackWithMin2() {
        s2 = new Stack<Integer>();
    }

    public void push(int value){
        if (value <= min()) {
            s2.push(value);
        }
        super.push(value);
    }

    public Integer pop() {
        int value = super.pop();
        if (value == min()) {
            s2.pop();
        }
        return value;
    }

    public int min() {
        if (s2.isEmpty()) {
            return Integer.MAX_VALUE;
        } else {
            return s2.peek();
        }
    }
}

为什么这么做可以节省空间？假设有个很大的栈，而第一个元素刚好是最小值。对于第一种解法，我们需要记录n个整数，其中n为栈的大小。不过，对于第二种解法，我们只需存储几项数据：第二个栈（只有一个元素），以及栈本身数据结构的若干成员。

3. 实现SetOfStacks

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

进阶

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

在这个问题中，根据题意，数据结构应该类似如下：

class SetOfStacks {
    ArrayList<Stack> stacks = new ArrayList<Stack>();
    public void push(int v) { ... }
    public int pop() { ... }
}

其中push()的行为必须跟单一栈的一样，这就意味着push()要对栈数组的最后一个栈调用push()。不过，这里处理起来必须小心一点：若最后一个栈被填满，就需新建一个栈。实现代码大致如下：

public void push(int v) {
    Stack last = getLastStack();
    if (last != null && !last.isFull()) { // 添加到最后一个栈中
        last.push(v);
    } else { // 必须新建一个栈
        Stack stack = new Stack(capacity);
        stack.push(v);
        stacks.add(stack);
    }
}

那么，pop()该怎么做？它的行为与push()类似，也就是说，应该操作最后一个栈。若最后一个栈为空（执行出栈操作后），就必须从栈数组中移除这个栈。

public int pop() {
    Stack last = getLastStack();
    int v = last.pop();
    if (last.size == 0) stacks.remove(stacks.size() - 1);
        return v;
}

进阶：实现popAt(int index)

这个实现起来有点棘手，不过，我们可以设想一个“推入”动作。从栈1弹出元素时，我们需要移出栈2的栈底元素，并将其推到栈1中。随后，将栈3的栈底元素推入栈2，将栈4的栈底元素推入栈3，等等。

你可能会指出，何必执行“推入”操作，有些栈不填满不是也挺好的。而且，这还会改善时间复杂度（元素很多时尤其明显），但是，若之后有人假定所有的栈（最后一个栈除外）都是填满的，就可能会让我们陷入棘手的境地。这个问题并没有“标准答案”，你应该跟面试官讨论种做法的优劣。

public class SetOfStacks {
    ArrayList<Stack> stacks = new ArrayList<Stack>();
    public int capacity;
    public SetOfStacks(int capacity) {
        this.capacity = capacity;
    }

    public Stack getLastStack() {
        if (stacks.size() == 0) 
            return null;
        return stacks.get(stacks.size() - 1);
    }

    public void push(int v) { /* 参看之前的代码*/ }
    public int pop() { /* 参看之前的代码*/ }
    public boolean isEmpty() {
        Stack last = getLastStack();
        return last == null || last.isEmpty();
    }

    public int popAt(int index) {
        return leftShift(index, true);
    }

    public int leftShift(int index, boolean removeTop) {
        Stack stack = stacks.get(index);
        int removed_item;
        if (removeTop) 
            removed_item = stack.pop();
        else 
            removed_item = stack.removeBottom();
        if (stack.isEmpty()) {
            stacks.remove(index);
        } else if (stacks.size() > index + 1) {
            int v = leftShift(index + 1, false);
            stack.push(v);
        }
        return removed_item;
    }
}

public class Stack {
    private int capacity;
    public Node top, bottom;
    public int size = 0;

    public Stack(int capacity) { this.capacity = capacity; }
    public boolean isFull() { return capacity == size; }

    public void join(Node above, Node below) {
        if (below != null) below.above = above;
        if (above != null) above.below = below;
    }

    public boolean push(int v) {
        if (size >= capacity) 
            return false;
        size++;
        Node n = new Node(v);
        if (size == 1) 
            bottom = n;
        join(n, top);
        top = n;
        return true;
    }

    public int pop() {
        Node t = top;
        top = top.below;
        size--;
        return t.value;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public int removeBottom() {
        Node b = bottom;
        bottom = bottom.above;
        if (bottom != null) 
            bottom.below = null;
        size--;
        return b.value;
    }
}

这个问题在概念上并不是很难，但要完整实现需要编写大量代码。面试官一般不会要求你写出全部代码。

解决这类问题，有个很好的策略，就是尽量将代码分离出来，写成独立的方法，比如popAt可以调用的leftShift。这样一来，你的代码就会更加清晰，而你在处理细节之前，也有机会先铺设好代码的骨架。