跳到主要内容

C 语言栈实现

介绍​

栈（Stack）是一种常见的数据结构，遵循后进先出（LIFO, Last In First Out）的原则。栈的操作主要包括入栈（Push）和出栈（Pop），以及查看栈顶元素（Peek）等。栈在计算机科学中有着广泛的应用，例如函数调用栈、表达式求值、括号匹配等。

本文将逐步讲解如何在C语言中实现栈，并通过代码示例和实际案例帮助你理解栈的工作原理。

栈的基本操作​

栈的核心操作包括：

  1. Push：将元素添加到栈顶。
  2. Pop：移除并返回栈顶元素。
  3. Peek：查看栈顶元素但不移除。
  4. IsEmpty：检查栈是否为空。
  5. IsFull：检查栈是否已满（针对固定大小的栈）。

栈的实现​

1. 定义栈结构​

在C语言中，栈可以通过数组或链表实现。这里我们使用数组来实现一个固定大小的栈。

c
#define MAX_SIZE 100  // 定义栈的最大容量

typedef struct {
    int data[MAX_SIZE];  // 存储栈元素的数组
    int top;            // 栈顶指针
} Stack;

2. 初始化栈​

初始化栈时，将栈顶指针 top 设置为 -1，表示栈为空。

c
void initialize(Stack *stack) {
    stack->top = -1;
}

3. 检查栈是否为空​

如果栈顶指针 top 为 -1，则栈为空。

c
int isEmpty(Stack *stack) {
    return stack->top == -1;
}

4. 检查栈是否已满​

如果栈顶指针 top 等于 MAX_SIZE - 1，则栈已满。

c
int isFull(Stack *stack) {
    return stack->top == MAX_SIZE - 1;
}

5. 入栈操作​

将元素添加到栈顶，并更新栈顶指针。

c
void push(Stack *stack, int value) {
    if (isFull(stack)) {
        printf("栈已满，无法入栈！\n");
        return;
    }
    stack->data[++stack->top] = value;  // 先增加top，再赋值
}

6. 出栈操作​

移除并返回栈顶元素，同时更新栈顶指针。

c
int pop(Stack *stack) {
    if (isEmpty(stack)) {
        printf("栈为空，无法出栈！\n");
        return -1;  // 返回一个错误值
    }
    return stack->data[stack->top--];  // 先返回值，再减少top
}

7. 查看栈顶元素​

返回栈顶元素但不移除。

c
int peek(Stack *stack) {
    if (isEmpty(stack)) {
        printf("栈为空，无栈顶元素！\n");
        return -1;  // 返回一个错误值
    }
    return stack->data[stack->top];
}

代码示例​

以下是一个完整的栈实现示例：

c
#include <stdio.h>

#define MAX_SIZE 100

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

void initialize(Stack *stack) {
    stack->top = -1;
}

int isEmpty(Stack *stack) {
    return stack->top == -1;
}

int isFull(Stack *stack) {
    return stack->top == MAX_SIZE - 1;
}

void push(Stack *stack, int value) {
    if (isFull(stack)) {
        printf("栈已满，无法入栈！\n");
        return;
    }
    stack->data[++stack->top] = value;
}

int pop(Stack *stack) {
    if (isEmpty(stack)) {
        printf("栈为空，无法出栈！\n");
        return -1;
    }
    return stack->data[stack->top--];
}

int peek(Stack *stack) {
    if (isEmpty(stack)) {
        printf("栈为空，无栈顶元素！\n");
        return -1;
    }
    return stack->data[stack->top];
}

int main() {
    Stack stack;
    initialize(&stack);

    push(&stack, 10);
    push(&stack, 20);
    push(&stack, 30);

    printf("栈顶元素: %d\n", peek(&stack));  // 输出: 30

    printf("出栈元素: %d\n", pop(&stack));   // 输出: 30
    printf("出栈元素: %d\n", pop(&stack));   // 输出: 20

    printf("栈顶元素: %d\n", peek(&stack));  // 输出: 10

    return 0;
}

输出结果：

栈顶元素: 30
出栈元素: 30
出栈元素: 20
栈顶元素: 10

实际应用场景​

1. 函数调用栈​

在程序执行过程中，函数调用是通过栈来管理的。每次调用函数时，当前函数的上下文（如局部变量、返回地址等）会被压入栈中；函数返回时，上下文会从栈中弹出。

2. 表达式求值​

栈可以用于计算后缀表达式（逆波兰表达式）。例如，表达式 3 4 + 5 * 可以通过栈来计算：

  1. 将 3 和 4 入栈。
  2. 遇到 + 时，弹出 4 和 3，计算 3 + 4 = 7，将 7 入栈。
  3. 将 5 入栈。
  4. 遇到 * 时，弹出 5 和 7，计算 7 * 5 = 35，将 35 入栈。

3. 括号匹配​

栈可以用于检查表达式中的括号是否匹配。例如，表达式 {[()]} 是合法的，而 {[()} 是不合法的。

总结​

栈是一种简单但强大的数据结构，广泛应用于计算机科学的各个领域。通过本文的学习，你应该已经掌握了如何在C语言中实现栈，并理解了栈的基本操作和实际应用。

附加资源与练习​

  1. 练习：尝试用链表实现栈，并与数组实现的栈进行比较。
  2. 扩展：实现一个支持动态扩容的栈（当栈满时，自动扩大容量）。
  3. 挑战：使用栈实现一个简单的计算器，支持加减乘除运算。
提示

如果你对栈的实现有任何疑问，欢迎在评论区留言，我们会尽快为你解答！