数据结构和算法面试题系列-栈

这个系列是我多年前找工作时对数据结构和算法总结，其中有基础部分，也有各大公司的经典的面试题，最早发布在CSDN。现整理为一个系列给需要的朋友参考，如有错误，欢迎指正。本系列完整代码地址在 这里 。

0 概述

栈作为一种基本的数据结构，在很多地方有运用，比如函数递归，前后缀表达式转换等。本文会用C数组来实现栈结构(使用链表实现可以参见链表那一节，使用头插法构建链表即可)，并对常见的几个跟栈相关的面试题进行分析，本文代码在 这里 。

1 定义

我们使用结构体来定义栈，使用柔性数组来存储元素。几个宏定义用于计算栈的元素数目及栈是否为空和满。

typedef struct Stack {
    int capacity;
    int top;
    int items[];
} Stack;

#define SIZE(stack) (stack->top + 1)
#define IS_EMPTY(stack) (stack->top == -1)
#define IS_FULL(stack) (stack->top == stack->capacity - 1)
复制代码

2 基本操作

栈主要有三种基本操作：

• push：压入一个元素到栈中。
• pop：弹出栈顶元素并返回。
• peek：取栈顶元素，但是不修改栈。

如图所示：

代码如下：

Stack *stackNew(int capacity)
{
    Stack *stack = (Stack *)malloc(sizeof(*stack) + sizeof(int) * capacity);
    if (!stack) {
        printf("Stack new failed\n");
        exit(E_NOMEM);
    }

    stack->capacity = capacity;
    stack->top = -1;
    return stack;
}

void push(Stack *stack, int v)
{
    if (IS_FULL(stack)) {
        printf("Stack Overflow\n");
        exit(E_FULL);
    }
    stack->items[++stack->top] = v;
}

int pop(Stack *stack)
{
    if (IS_EMPTY(stack)) {
        printf("Stack Empty\n");
        exit(E_EMPTY);
    }

    return stack->items[stack->top--];
}

int peek(Stack *stack)
{
    if (IS_EMPTY(stack)) {
        printf("Stack Empty\n");
        exit(E_EMPTY);
    }
    return stack->items[stack->top];
}

复制代码

3 栈相关面试题

3.1 后缀表达式求值

题：已知一个后缀表达式 6 5 2 3 + 8 * + 3 + * ，求该后缀表达式的值。

解：后缀表达式也叫逆波兰表达式，其求值过程可以用到栈来辅助存储。则其求值过程如下：

• 1）遍历表达式，遇到的数字首先放入栈中，此时栈为 [6 5 2 3] 。
• 2）接着读到 + ，则弹出3和2，计算 3 + 2 ，计算结果等于 5 ，并将 5 压入到栈中，栈为 [6 5 5] 。
• 3）读到 8 ，将其直接放入栈中， [6 5 5 8] 。
• 4）读到 * ，弹出 8 和 5 ，计算 8 * 5 ，并将结果 40 压入栈中，栈为 [6 5 40] 。而后过程类似，读到 + ，将 40 和 5 弹出，将 40 + 5 的结果 45 压入栈，栈变成 [6 45] ，读到3，放入栈 [6 45 3] ...以此类推，最后结果为 288 。

代码:

int evaluatePostfix(char *exp)
{
    Stack* stack = stackNew(strlen(exp));
    int i;
 
    if (!stack) {
        printf("New stack failed\n");
        exit(E_NOMEM);
    }
 
    for (i = 0; exp[i]; ++i) {
        // 如果是数字，直接压栈
        if (isdigit(exp[i])) {
            push(stack, exp[i] - '0');
        } else {// 如果遇到符号，则弹出栈顶两个元素计算，并将结果压栈
            int val1 = pop(stack);
            int val2 = pop(stack);
            switch (exp[i])
            {
                case '+': push(stack, val2 + val1); break;
                case '-': push(stack, val2 - val1); break;
                case '*': push(stack, val2 * val1); break;
                case '/': push(stack, val2/val1);   break;
            }
        }
    }

    return pop(stack); 
}
复制代码

3.2 栈逆序

题：给定一个栈，请将其逆序。

解1：如果不考虑空间复杂度，完全可以另外弄个辅助栈，将原栈数据全部 pop 出来并 push 到辅助栈即可。

解2：如果在面试中遇到这个题目，那肯定是希望你用更好的方式实现。可以先实现一个在栈底插入元素的函数，然后便可以递归实现栈逆序了，不需要用辅助栈。

* 在栈底插入一个元素
 */
void insertAtBottom(Stack *stack, int v)
{
    if (IS_EMPTY(stack)) {
        push(stack, v);
    } else {
        int x = pop(stack);
        insertAtBottom(stack, v);
        push(stack, x);
    }
}

/**
 * 栈逆序
 */
void stackReverse(Stack *stack)
{
    if (IS_EMPTY(stack))
        return;

    int top = pop(stack);
    stackReverse(stack);
    insertAtBottom(stack, top);
}
复制代码

3.3 设计包含min函数的栈

题：设计一个栈，使得push、pop以及min（获取栈中最小元素）能够在常数时间内完成。

分析：刚开始很容易想到一个方法，那就是额外建立一个最小二叉堆保存所有元素，这样每次获取最小元素只需要 O(1) 的时间。但是这样的话，为了建最小堆 push 和 pop 操作就需要 O(lgn) 的时间了（假定栈中元素个数为n），不符合题目的要求。

解1：辅助栈方法

那为了实现该功能，可以使用辅助栈使用一个辅助栈来保存最小元素，这个解法简单不失优雅。设该辅助栈名字为 minStack ，其栈顶元素为当前栈中的最小元素。这意味着

• 1）要获取当前栈中最小元素，只需要返回 minStack 的栈顶元素即可。
• 2）每次执行 push 操作时，检查 push 的元素是否小于或等于 minStack 栈顶元素。如果是，则也push 该元素到 minStack 中。
• 3）当执行 pop 操作的时候，检查 pop 的元素是否与当前最小值相等。如果相等，则需要将该元素从minStack 中 pop 出去。

代码：

void minStackPush(Stack *orgStack, Stack *minStack, int v)
{
    if (IS_FULL(orgStack)) {
        printf("Stack Full\n");
        exit(E_FULL);
    }

    push(orgStack, v);
    if (IS_EMPTY(minStack) || v < peek(minStack)) {
        push(minStack, v);
    }
}

int minStackPop(Stack *orgStack, Stack *minStack)
{
    if (IS_EMPTY(orgStack)) {
        printf("Stack Empty\n");
        exit(E_EMPTY);
    }

    if (peek(orgStack) == peek(minStack)) {
        pop(minStack);
    }
    return pop(orgStack);
}

int minStackMin(Stack *minStack)
{
    return peek(minStack);
}
复制代码

示例：

假定有元素 3，4，2，5，1 依次入栈 orgStack ，辅助栈 minStack 中元素为 3，2，1 。

解2：差值法

另外一种解法利用存储差值而不需要辅助栈，方法比较巧妙：

• 栈顶多出一个空间用于存储栈最小值。
• push 时压入的是当前元素与压入该元素前的栈中最小元素(栈顶的元素)的差值，然后通过比较当前元素与当前栈中最小元素大小，并将它们中的较小值作为新的最小值压入栈顶。
• pop 函数执行的时候，先 pop 出栈顶的两个值，这两个值分别是当前栈中最小值 min 和最后压入的元素与之前栈中最小值的差值 delta 。根据 delta < 0 或者 delta >= 0 来获得之前压入栈的元素的值和该元素出栈后的新的最小值。
• min 函数则是取栈顶元素即可。

代码：

void minStackPushUseDelta(Stack *stack, int v)
{
    if (IS_EMPTY(stack)) { // 空栈，直接压入v两次
        push(stack, v);
        push(stack, v);
    } else { 
       int oldMin = pop(stack); // 栈顶保存的是压入v之前的栈中最小值
       int delta = v - oldMin; 
       int newMin = delta < 0 ? v : oldMin;
       push(stack, delta); // 压入 v 与之前栈中的最小值之差
       push(stack, newMin); // 最后压入当前栈中最小值
   }
}

int minStackPopUseDelta(Stack *stack)
{
    int min = pop(stack);
    int delta = pop(stack);
    int v, oldMin;

    if (delta < 0) { // 最后压入的元素比min小，则min就是最后压入的元素
        v = min;
        oldMin = v - delta;
    } else { // 最后压入的值不是最小值，则min为oldMin。
        oldMin = min;
        v = oldMin + delta;
    }

    if (!IS_EMPTY(stack)) { // 如果栈不为空，则压入oldMin
        push(stack, oldMin);
    }
    return v;
}

int minStackMinUseDelta(Stack *stack)
{
    return peek(stack);
}
复制代码

示例：

push(3): [3 3] 
push(4): [3 1 3] 
push(2): [3 1 -1 2] 
push(5): [3 1 -1 3 2] 
push(1): [3 1 -1 3 -1 1] 

min(): 1，pop(): 1，[3 1 -1 3 2]
min(): 2，pop(): 5，[3 1 -1 2] 
min(): 2，pop(): 2，[3 1 3] 
min(): 3，pop(): 4，[3 3] 
min(): 3，pop(): 3，[ ]
复制代码

3.4 求出栈数目和出栈序列

求出栈数目

题：已知一个入栈序列，试求出所有可能的出栈序列数目。例如入栈序列为 1，2，3 ，则可能的出栈序列有5种： 1 2 3，1 3 2 ，2 1 3，2 3 1，3 2 1 。

解：要求解出栈序列的数目，还算比较容易的。已经有很多文章分析过这个问题，最终答案就是卡特兰数，也就是说 n 个元素的出栈序列的总数目等于 C(2n, n) - C(2n, n-1) = C(2n, n) / (n+1) ，如 3 个元素的总的出栈数目就是 C(6, 3) / 4 = 5 。

如果不分析求解的通项公式，是否可以写程序求出出栈的序列数目呢？答案是肯定的，我们根据当前栈状态可以将 出栈一个元素 和 入栈一个元素 两种情况的总的数目相加即可得到总的出栈数目。

/**
 * 计算出栈数目
 * - in：目前栈中的元素数目
 * - out：目前已经出栈的元素数目
 * - wait：目前还未进栈的元素数目
 */
int sumOfStackPopSequence(Stack *stack, int in, int out, int wait)
{
    if (out == stack->capacity) { // 元素全部出栈了，返回1
        return 1;
    } 

    int sum = 0;

    if (wait > 0) // 进栈一个元素
        sum += sumOfStackPopSequence(stack, in + 1, out, wait - 1);

    if (in > 0) // 出栈一个元素
        sum += sumOfStackPopSequence(stack, in - 1, out + 1, wait);

    return sum;
}
复制代码

求所有出栈序列

题：给定一个输入序列 input[] = {1, 2, 3} ，打印所有可能的出栈序列。

解：这个有点难，不只是出栈数目，需要打印所有出栈序列，需要用到回溯法，回溯法比简单的递归要难不少，后面有时间再单独整理一篇回溯法的文章。出栈序列跟入栈出栈的顺序有关，对于每个输入，都会面对两种情况: 是先将原栈中元素出栈还是先入栈 ，这里用到两个栈来实现，其中栈 stk 用于模拟入栈出栈，而栈 output 用于存储出栈的值。 注意退出条件是当遍历完所有输入的元素，此时栈 stk 和 output 中都可能有元素，需要先将栈 output 从栈底开始打印完，然后将栈 stk 从栈顶开始打印即可。 另外一点就是，当我们使用的模拟栈 stk 为空时，则这个分支结束。代码如下：

void printStackPopSequence(int input[], int i, int n, Stack *stk, Stack *output)
{
    if (i >= n) {
        stackTraverseBottom(output); // output 从栈底开始打印
        stackTraverseTop(stk); // stk 从栈顶开始打印
        printf("\n");
        return;
    }   

    push(stk, input[i]);
    printStackPopSequence(input, i+1, n, stk, output);
    pop(stk);

    if (IS_EMPTY(stk))
        return;

    int v = pop(stk);
    push(output, v); 
    printStackPopSequence(input, i, n, stk, output);
    push(stk, v); 
    pop(output);
}
复制代码

参考资料

• www.techiedelight.com/stack-imple…
• www.geeksforgeeks.org/stack-set-4…
• www.geeksforgeeks.org/reverse-a-s…
• blog.csdn.net/yysdsyl/art…