【数据结构 - 栈】

栈

在数据结构的大家庭中，栈（Stack）是一种非常重要且实用的结构。今天，我们就来深入探讨一下如何用 C 语言实现栈，并理解其背后的工作原理。

一、栈的基本概念

栈是一种特殊的线性表，它遵循“后进先出”（Last In First Out，LIFO）的原则。这意味着最后进入栈的元素将首先被取出。

想象一下，栈就像一个只能从一端放入和取出物品的筒子，你把东西一个一个放进去，要拿出来时，只能先拿最后放进去的那个。

二、栈的操作

栈通常支持以下几种基本操作：

1. push：将元素压入栈顶。
2. pop：弹出栈顶元素。
3. peek：查看栈顶元素，但不弹出。
4. isEmpty：判断栈是否为空。

三、栈的实现方式

1.基于数组的实现

• 优点：访问速度快，操作简单。
• 缺点：可能存在空间浪费，数组大小固定时扩展不太灵活。
  以下是一个简单的数组实现栈的示例代码（c）：

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 100  // 栈的最大容量

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

// 初始化栈
void initStack(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 element) {
    if (isFull(stack)) {
        printf("Stack Overflow!\n");
        return;
    }
    stack->items[++stack->top] = element;
}

// 出栈操作
int pop(Stack *stack) {
    if (isEmpty(stack)) {
        printf("Stack Underflow!\n");
        return -1;
    }
    int element = stack->items[stack->top--];
    return element;
}

// 查看栈顶元素
int peek(Stack *stack) {
    if (isEmpty(stack)) {
        printf("Stack is empty!\n");
        return -1;
    }
    return stack->items[stack->top];
}

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

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

    printf("Top element: %d\n", peek(&stack));

    int poppedElement = pop(&stack);
    if (poppedElement!= -1) {
        printf("Popped element: %d\n", poppedElement);
    }

    printf("Top element after pop: %d\n", peek(&stack));

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

在上述代码中：

• 我们使用一个结构体 Stack 来表示栈，其中包含一个-整数数组 items 用于存储元素，以及一个整数 top 作为栈顶指针。
• initStack 函数用于初始化栈，将栈顶指针设置为 -1，表示栈为空。
• isEmpty 和 isFull 函数分别用于判断栈是否为空和已满。
• push 函数在栈未满的情况下，将元素压入栈顶。
• pop 函数在栈不为空的情况下，弹出栈顶元素并返回。
• peek 函数返回栈顶元素，但不弹出。
  2.基于链表的实现
• 优点：动态分配内存，不存在固定大小的限制。
• 缺点：访问特定元素需要遍历链表，效率相对较低。

四、栈的应用场景

栈在很多算法和程序中都有广泛的应用，例如：

1. 函数调用：在 C 语言中，函数的调用和返回就是通过栈来实现的。每次调用一个函数时，相关的参数、返回地址等信息都会被压入栈中，函数执行完毕后，这些信息会被弹出栈。
2. 表达式求值：在计算算术表达式时，如中缀表达式转后缀表达式，以及后缀表达式的求值过程中，栈可以用来存储操作数和运算符。
3. 括号匹配：检查表达式中的括号是否匹配，可以使用栈来辅助判断。
4. 回溯算法：在一些需要回溯的问题中，栈可以用来保存中间状态，以便进行回退操作。

五、总结

栈作为一种简单的数据结构，其“后进先出”的特性使其在很多场景中发挥着重要作用。通过理解和掌握栈的概念、操作和实现，我们能够更好地应对各种编程问题，并为更复杂的数据结构和算法的学习打下坚实的基础。
希望这篇文章能让您对数据结构中的栈有更清晰、更深入的理解。如果您有任何疑问或者建议，欢迎留言交流！