MK
摩柯社区 - 一个极简的技术知识社区
AI 面试

C 语言实现堆栈深入讲解

2022-01-127.9k 阅读

堆栈的基本概念

什么是堆栈

堆栈（Stack）是一种重要的数据结构，它按照后进先出（Last In First Out，LIFO）的原则存储数据。想象一下一叠盘子，最后放上去的盘子会最先被拿走，这就是典型的后进先出模式，堆栈在计算机科学中有着广泛的应用，比如函数调用栈、表达式求值等场景。

堆栈在计算机系统中的作用

  1. 函数调用：在 C 语言中，每当一个函数被调用时，系统会在堆栈中为该函数分配空间，用于存储函数的局部变量、参数以及返回地址等信息。当函数执行完毕后，这些信息会从堆栈中弹出，函数返回调用者。
  2. 表达式求值：对于像算术表达式这样的计算，堆栈可以用来辅助操作符和操作数的处理。例如，后缀表达式（逆波兰表达式）的求值就可以借助堆栈高效完成。

C 语言实现堆栈的方式

基于数组的堆栈实现

  1. 定义堆栈结构体
#define MAX_SIZE 100
typedef struct {
    int data[MAX_SIZE];
    int top;
} Stack;

这里定义了一个 Stack 结构体，其中 data 数组用于存储堆栈中的元素，MAX_SIZE 定义了堆栈的最大容量，top 变量指示堆栈顶部的位置。 2. 初始化堆栈

void initStack(Stack *s) {
    s->top = -1;
}

初始化函数将 top 设为 -1，表示堆栈为空。 3. 判断堆栈是否为空

int isStackEmpty(Stack *s) {
    return s->top == -1;
}

通过检查 top 是否为 -1 来判断堆栈是否为空。 4. 判断堆栈是否已满

int isStackFull(Stack *s) {
    return s->top == MAX_SIZE - 1;
}

当 top 等于 MAX_SIZE - 1 时，说明堆栈已满。 5. 入栈操作

void push(Stack *s, int value) {
    if (isStackFull(s)) {
        printf("Stack is full. Cannot push.\n");
        return;
    }
    s->data[++(s->top)] = value;
}

入栈时先检查堆栈是否已满，若未满则将 top 加 1 并将值存入相应位置。 6. 出栈操作

int pop(Stack *s) {
    if (isStackEmpty(s)) {
        printf("Stack is empty. Cannot pop.\n");
        return -1; // 返回一个错误值
    }
    return s->data[(s->top)--];
}

出栈时先检查堆栈是否为空，若不为空则返回 top 位置的值，并将 top 减 1。 7. 获取栈顶元素

int peek(Stack *s) {
    if (isStackEmpty(s)) {
        printf("Stack is empty. Cannot peek.\n");
        return -1;
    }
    return s->data[s->top];
}

获取栈顶元素时同样先检查堆栈是否为空，若不为空则返回 top 位置的值。

基于链表的堆栈实现

  1. 定义链表节点结构体
typedef struct StackNode {
    int data;
    struct StackNode *next;
} StackNode;

这是链表节点的定义，每个节点包含一个数据域 data 和一个指向下一个节点的指针 next。 2. 定义堆栈结构体

typedef struct {
    StackNode *top;
} Stack;

堆栈结构体只包含一个指向栈顶节点的指针 top。 3. 初始化堆栈

void initStack(Stack *s) {
    s->top = NULL;
}

初始化时将 top 设为 NULL，表示堆栈为空。 4. 判断堆栈是否为空

int isStackEmpty(Stack *s) {
    return s->top == NULL;
}

通过检查 top 是否为 NULL 来判断堆栈是否为空。 5. 入栈操作

void push(Stack *s, int value) {
    StackNode *newNode = (StackNode *)malloc(sizeof(StackNode));
    newNode->data = value;
    newNode->next = s->top;
    s->top = newNode;
}

入栈时先创建一个新节点，将其数据域设为要入栈的值，然后将其 next 指针指向当前栈顶节点，最后更新 top 指针指向新节点。 6. 出栈操作

int pop(Stack *s) {
    if (isStackEmpty(s)) {
        printf("Stack is empty. Cannot pop.\n");
        return -1;
    }
    StackNode *temp = s->top;
    int value = temp->data;
    s->top = temp->next;
    free(temp);
    return value;
}

出栈时先检查堆栈是否为空，若不为空则保存栈顶节点的值，更新 top 指针指向栈顶节点的下一个节点，然后释放栈顶节点的内存。 7. 获取栈顶元素

int peek(Stack *s) {
    if (isStackEmpty(s)) {
        printf("Stack is empty. Cannot peek.\n");
        return -1;
    }
    return s->top->data;
}

获取栈顶元素时先检查堆栈是否为空，若不为空则返回 top 指向节点的数据域。

堆栈应用场景

函数调用栈的模拟

在 C 语言程序运行过程中，函数调用栈负责管理函数调用和返回。我们可以通过自己实现的堆栈来模拟这一过程。

#include <stdio.h>
#define MAX_SIZE 100
typedef struct {
    int data[MAX_SIZE];
    int top;
} Stack;

void initStack(Stack *s) {
    s->top = -1;
}

int isStackEmpty(Stack *s) {
    return s->top == -1;
}

int isStackFull(Stack *s) {
    return s->top == MAX_SIZE - 1;
}

void push(Stack *s, int value) {
    if (isStackFull(s)) {
        printf("Stack is full. Cannot push.\n");
        return;
    }
    s->data[++(s->top)] = value;
}

int pop(Stack *s) {
    if (isStackEmpty(s)) {
        printf("Stack is empty. Cannot pop.\n");
        return -1;
    }
    return s->data[(s->top)--];
}

void simulateFunctionCall() {
    Stack callStack;
    initStack(&callStack);

    // 模拟函数调用
    push(&callStack, 1); // 假设函数1的相关信息入栈
    push(&callStack, 2); // 假设函数2的相关信息入栈

    // 模拟函数返回
    printf("Popping from call stack: %d\n", pop(&callStack));
    printf("Popping from call stack: %d\n", pop(&callStack));
}

int main() {
    simulateFunctionCall();
    return 0;
}

在这个示例中，我们通过 Stack 结构体和相关操作函数模拟了函数调用栈的基本操作，即函数调用时信息入栈，函数返回时信息出栈。

表达式求值

  1. 后缀表达式求值 后缀表达式（逆波兰表达式）是一种不需要括号来确定运算优先级的表达式表示方法。例如，对于中缀表达式 3 + 4 * 2，其对应的后缀表达式为 3 4 2 * +。我们可以利用堆栈来对后缀表达式进行求值。
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>

#define MAX_SIZE 100
typedef struct {
    int data[MAX_SIZE];
    int top;
} Stack;

void initStack(Stack *s) {
    s->top = -1;
}

int isStackEmpty(Stack *s) {
    return s->top == -1;
}

int isStackFull(Stack *s) {
    return s->top == MAX_SIZE - 1;
}

void push(Stack *s, int value) {
    if (isStackFull(s)) {
        printf("Stack is full. Cannot push.\n");
        return;
    }
    s->data[++(s->top)] = value;
}

int pop(Stack *s) {
    if (isStackEmpty(s)) {
        printf("Stack is empty. Cannot pop.\n");
        return -1;
    }
    return s->data[(s->top)--];
}

int evaluatePostfix(char *postfix) {
    Stack s;
    initStack(&s);

    for (int i = 0; postfix[i] != '\0'; i++) {
        if (isdigit(postfix[i])) {
            push(&s, postfix[i] - '0');
        } else {
            int operand2 = pop(&s);
            int operand1 = pop(&s);
            switch (postfix[i]) {
                case '+':
                    push(&s, operand1 + operand2);
                    break;
                case '-':
                    push(&s, operand1 - operand2);
                    break;
                case '*':
                    push(&s, operand1 * operand2);
                    break;
                case '/':
                    if (operand2 != 0) {
                        push(&s, operand1 / operand2);
                    } else {
                        printf("Division by zero error.\n");
                        return -1;
                    }
                    break;
            }
        }
    }
    return pop(&s);
}

int main() {
    char postfix[] = "342*+";
    int result = evaluatePostfix(postfix);
    if (result != -1) {
        printf("The result of postfix evaluation is: %d\n", result);
    }
    return 0;
}

在这个代码中，我们遍历后缀表达式，遇到数字则将其入栈，遇到操作符则从栈中弹出两个操作数进行运算，并将结果入栈，最后栈顶元素即为表达式的值。

  1. 中缀表达式转换为后缀表达式 要将中缀表达式转换为后缀表达式，也可以借助堆栈。操作符需要根据其优先级和堆栈的状态来决定何时入栈和出栈。
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>

#define MAX_SIZE 100
typedef struct {
    char data[MAX_SIZE];
    int top;
} Stack;

void initStack(Stack *s) {
    s->top = -1;
}

int isStackEmpty(Stack *s) {
    return s->top == -1;
}

int isStackFull(Stack *s) {
    return s->top == MAX_SIZE - 1;
}

void push(Stack *s, char value) {
    if (isStackFull(s)) {
        printf("Stack is full. Cannot push.\n");
        return;
    }
    s->data[++(s->top)] = value;
}

char pop(Stack *s) {
    if (isStackEmpty(s)) {
        printf("Stack is empty. Cannot pop.\n");
        return '\0';
    }
    return s->data[(s->top)--];
}

int precedence(char op) {
    if (op == '+' || op == '-')
        return 1;
    if (op == '*' || op == '/')
        return 2;
    return 0;
}

void infixToPostfix(char *infix, char *postfix) {
    Stack s;
    initStack(&s);
    int j = 0;

    for (int i = 0; infix[i] != '\0'; i++) {
        if (isdigit(infix[i])) {
            postfix[j++] = infix[i];
        } else if (infix[i] == '(') {
            push(&s, infix[i]);
        } else if (infix[i] == ')') {
            while (!isStackEmpty(&s) && s.data[s.top] != '(') {
                postfix[j++] = pop(&s);
            }
            pop(&s); // 弹出 '('
        } else {
            while (!isStackEmpty(&s) && precedence(infix[i]) <= precedence(s.data[s.top])) {
                postfix[j++] = pop(&s);
            }
            push(&s, infix[i]);
        }
    }
    while (!isStackEmpty(&s)) {
        postfix[j++] = pop(&s);
    }
    postfix[j] = '\0';
}

int main() {
    char infix[] = "3+4*2/(1-5)";
    char postfix[MAX_SIZE];
    infixToPostfix(infix, postfix);
    printf("Infix: %s\nPostfix: %s\n", infix, postfix);
    return 0;
}

在这个代码中，我们根据操作符的优先级和括号的匹配情况，将中缀表达式转换为后缀表达式。

堆栈实现的性能分析

基于数组的堆栈性能

  1. 空间复杂度：基于数组的堆栈在初始化时就分配了固定大小的空间，空间复杂度为 $O(MAX_SIZE)$。如果实际使用的元素数量远小于 MAX_SIZE，会造成空间浪费。
  2. 时间复杂度：入栈和出栈操作的时间复杂度均为 $O(1)$，因为它们只涉及对数组特定位置的访问和 top 变量的更新。

基于链表的堆栈性能

  1. 空间复杂度：基于链表的堆栈按需分配内存，空间复杂度为 $O(n)$，其中 n 是堆栈中实际元素的数量。但由于每个节点需要额外的指针空间，所以在存储相同数量元素时，链表可能会占用更多的内存。
  2. 时间复杂度：入栈和出栈操作的时间复杂度也为 $O(1)$，因为它们主要涉及指针的操作。不过，由于链表节点的动态内存分配和释放，在频繁操作时可能会有一定的性能开销。

堆栈实现的注意事项

数组堆栈的注意事项

  1. 堆栈溢出：由于数组大小固定，如果在使用过程中没有正确检查堆栈是否已满就进行入栈操作，会导致堆栈溢出，这可能会破坏其他内存区域的数据，引发程序崩溃等严重问题。
  2. 初始化问题：在使用数组堆栈之前，必须正确初始化 top 变量为 -1，否则后续的操作可能会得到错误的结果。

链表堆栈的注意事项

  1. 内存管理：链表堆栈需要手动管理内存，即创建节点时使用 malloc 分配内存，节点不再使用时使用 free 释放内存。如果忘记释放内存，会导致内存泄漏，随着程序运行，内存消耗会不断增加。
  2. 空指针检查：在对链表堆栈进行操作时，必须仔细检查 top 是否为 NULL，特别是在出栈和获取栈顶元素操作时，否则可能会导致空指针引用错误，使程序崩溃。

高级堆栈操作与扩展

多重堆栈的实现

有时候，在一个程序中可能需要多个堆栈。我们可以通过多种方式实现多重堆栈，例如在一个数组中划分多个区域来实现多个堆栈，或者使用多个链表来分别实现不同的堆栈。

  1. 基于数组的多重堆栈
#define MAX_SIZE 100
#define STACKS 3

typedef struct {
    int data[MAX_SIZE];
    int top[STACKS];
    int bounds[STACKS + 1];
} MultiStack;

void initMultiStack(MultiStack *ms) {
    for (int i = 0; i < STACKS; i++) {
        ms->top[i] = ms->bounds[i] - 1;
    }
    ms->bounds[STACKS] = MAX_SIZE;
}

int isMultiStackFull(MultiStack *ms, int stackNum) {
    return ms->top[stackNum] == ms->bounds[stackNum + 1] - 1;
}

int isMultiStackEmpty(MultiStack *ms, int stackNum) {
    return ms->top[stackNum] == ms->bounds[stackNum] - 1;
}

void multiPush(MultiStack *ms, int stackNum, int value) {
    if (isMultiStackFull(ms, stackNum)) {
        printf("Stack %d is full. Cannot push.\n", stackNum);
        return;
    }
    ms->data[++(ms->top[stackNum])] = value;
}

int multiPop(MultiStack *ms, int stackNum) {
    if (isMultiStackEmpty(ms, stackNum)) {
        printf("Stack %d is empty. Cannot pop.\n", stackNum);
        return -1;
    }
    return ms->data[(ms->top[stackNum])--];
}

在这个代码中，我们通过一个数组 data 来存储多个堆栈的数据，top 数组记录每个堆栈的栈顶位置，bounds 数组划分每个堆栈在 data 数组中的区域。 2. 基于链表的多重堆栈

typedef struct StackNode {
    int data;
    struct StackNode *next;
} StackNode;

typedef struct {
    StackNode *top;
} Stack;

typedef struct {
    Stack stacks[STACKS];
} MultiStack;

void initMultiStack(MultiStack *ms) {
    for (int i = 0; i < STACKS; i++) {
        ms->stacks[i].top = NULL;
    }
}

int isMultiStackEmpty(MultiStack *ms, int stackNum) {
    return ms->stacks[stackNum].top == NULL;
}

void multiPush(MultiStack *ms, int stackNum, int value) {
    StackNode *newNode = (StackNode *)malloc(sizeof(StackNode));
    newNode->data = value;
    newNode->next = ms->stacks[stackNum].top;
    ms->stacks[stackNum].top = newNode;
}

int multiPop(MultiStack *ms, int stackNum) {
    if (isMultiStackEmpty(ms, stackNum)) {
        printf("Stack %d is empty. Cannot pop.\n", stackNum);
        return -1;
    }
    StackNode *temp = ms->stacks[stackNum].top;
    int value = temp->data;
    ms->stacks[stackNum].top = temp->next;
    free(temp);
    return value;
}

这里通过一个 MultiStack 结构体包含多个 Stack 结构体，每个 Stack 结构体是一个基于链表的堆栈。

可动态扩展的堆栈

  1. 基于数组的动态扩展堆栈
#define INITIAL_SIZE 10
typedef struct {
    int *data;
    int top;
    int capacity;
} Stack;

void initStack(Stack *s) {
    s->data = (int *)malloc(INITIAL_SIZE * sizeof(int));
    s->top = -1;
    s->capacity = INITIAL_SIZE;
}

void expandStack(Stack *s) {
    s->capacity *= 2;
    s->data = (int *)realloc(s->data, s->capacity * sizeof(int));
}

int isStackFull(Stack *s) {
    return s->top == s->capacity - 1;
}

void push(Stack *s, int value) {
    if (isStackFull(s)) {
        expandStack(s);
    }
    s->data[++(s->top)] = value;
}

int pop(Stack *s) {
    if (s->top == -1) {
        printf("Stack is empty. Cannot pop.\n");
        return -1;
    }
    return s->data[(s->top)--];
}

在这个代码中，当堆栈满时，通过 realloc 函数将数组大小翻倍，实现动态扩展。 2. 基于链表的动态扩展堆栈 由于链表本身就是按需分配内存，所以从某种意义上说，基于链表的堆栈已经是动态的。但如果希望在链表的实现上进行进一步优化，比如在特定条件下合并或分割链表节点以提高内存使用效率，可以通过更复杂的算法来实现。例如，可以在链表长度达到一定阈值时，将多个小节点合并为一个大节点，减少内存碎片。

typedef struct StackNode {
    int data[10]; // 假设每个节点存储10个元素
    struct StackNode *next;
    int count;
} StackNode;

typedef struct {
    StackNode *top;
} Stack;

void initStack(Stack *s) {
    s->top = NULL;
}

void push(Stack *s, int value) {
    if (s->top == NULL || s->top->count == 10) {
        StackNode *newNode = (StackNode *)malloc(sizeof(StackNode));
        newNode->count = 0;
        newNode->next = s->top;
        s->top = newNode;
    }
    s->top->data[s->top->count++] = value;
}

int pop(Stack *s) {
    if (s->top == NULL) {
        printf("Stack is empty. Cannot pop.\n");
        return -1;
    }
    int value = s->top->data[--(s->top->count)];
    if (s->top->count == 0) {
        StackNode *temp = s->top;
        s->top = s->top->next;
        free(temp);
    }
    return value;
}

在这个改进的链表堆栈实现中，每个节点可以存储多个元素，当节点满时创建新节点，当节点为空时释放节点，以此来优化内存使用。

通过以上对 C 语言实现堆栈的深入讲解，包括基本概念、实现方式、应用场景、性能分析、注意事项以及高级扩展等方面，相信读者对堆栈这一重要的数据结构在 C 语言中的应用有了全面且深入的理解。无论是在简单的程序设计还是复杂的系统开发中，熟练掌握堆栈的原理和实现都能为解决实际问题提供有力的工具。