欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2024-03-16 14:56:04
...

这个系列是我多年前找工作时对数据结构和算法总结,其中有基础部分,也有各大公司的经典的面试题,最早发布在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)读到 *,弹出 85 ,计算 8 * 5,并将结果 40 压入栈中,栈为 [6 5 40]。而后过程类似,读到 +,将 405 弹出,将 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) 的时间。但是这样的话,为了建最小堆 pushpop 操作就需要 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);
}
复制代码

参考资料