code前端网栈数据结构及相关面试题
作为一种基本的数据结构，栈的应用场合很多，比如函数递归、前后缀表达式的转换等。本文使用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：将栈顶元素弹出并返回。
- look：抓取栈顶元素，但不改变栈。
如图：
代码如下：
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]。 ？[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.
答案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），不满足主题的要求。
方案一：辅助堆栈法
要实现此功能，可以使用辅助堆栈来存储最小元素。这个解决方案简单而优雅。假设辅助栈的名称为minStack，栈顶元素是当前栈中最小的元素。这意味着
- 1）要获取当前堆栈中的最小元素，只需返回minStack的顶部元素即可。
- 2）每当进行入栈操作时，检查入栈的元素是否小于等于minStack顶元素。如果是，也将该元素推入 minStack。
- 3）执行pop操作时，检查pop元素是否等于当前最小值。如果它们相等，则应从 minStack 中删除该元素。
代码：
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 或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。
解决方案：解决pop序列的数量相对容易。分析这个问题的文章已经很多了，最终的答案是卡特兰数，也就是说n元素的pop序列总数等于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}，打印所有可能的弹出序列。
说明：这个有点困难，不仅要打印pop的数量，还需要打印所有的pop序列，并且需要使用回溯的方法。回溯法比简单的递归法要困难得多。稍后有时间我会单独写一篇文章。关于回溯的文章。出栈顺序与压栈和出栈的顺序有关。对于每个条目你都会面临两种情况：无论你是想先将元素放入原始堆栈还是先将它们压入堆栈，这里使用了两个堆栈。实现方式，其中stack stk用于模拟栈的入栈和出栈，栈输出用于存储从栈中取出的值。 请注意，输出条件是所有输入元素都已通过时。此时，stc堆栈和输出中可能有元素。必须首先从堆栈底部打印堆栈输出，然后从堆栈顶部打印堆栈输出。 。 还有一点是，当我们使用的dc的模拟栈为空时，这个分支就结束了。代码如下：
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);
}
复制代码作者：ssjhust
版权声明
本文仅代表作者观点，不代表Code前端网立场。
本文系作者Code前端网发表，如需转载，请注明页面地址。
