当前位置：首页 > news >正文

数据结构day4——栈

news 2025/7/2 12:12:46

一、栈的核心概念

什么是栈？

栈的核心特性

二、栈的基本操作

三、C 语言实现栈的两种方式

1. 顺序栈（基于数组实现）

实现代码

顺序栈的优缺点

2. 链式栈（基于链表实现）

实现代码

链式栈的优缺点

四、栈的典型应用场景

五、总结

栈（Stack）作为一种经典的线性数据结构，因其 "后进先出"（LIFO）的特性，在编程领域有着广泛的应用。无论是表达式求值、函数调用，还是括号匹配等场景，都能看到栈的身影。本文将带你用 C 语言从零实现栈，深入理解其工作原理与实际应用。

一、栈的核心概念

什么是栈？

栈是一种限定仅在表尾进行插入和删除操作的线性表。这里的 "表尾" 被称为栈顶（Top），另一端则称为栈底（Bottom）。

栈的核心特性

栈最显著的特点是后进先出（Last In First Out，LIFO）：

最后进入栈的元素，最先被取出
最先进入栈的元素，最后被取出

生活中的栈示例：

叠放的书本，只能从最上方取书
浏览器的历史记录，"后退" 功能总是返回上一个访问的页面
手机应用的任务栈，最近打开的应用最先被关闭

二、栈的基本操作

栈的操作围绕栈顶进行，主要包括以下几种：

操作名称	功能描述	时间复杂度
`initStack`	初始化栈	O(1)
`push`	向栈顶插入元素（入栈）	O(1)
`pop`	从栈顶移除元素（出栈）	O(1)
`peek`	获取栈顶元素（不删除）	O(1)
`isEmpty`	判断栈是否为空	O(1)
`isFull`	判断栈是否已满	O(1)
`size`	获取栈中元素个数	O(1)

三、C 语言实现栈的两种方式

在 C 语言中，栈通常有两种实现方式：基于数组的顺序栈和基于链表的链式栈。

1. 顺序栈（基于数组实现）

顺序栈使用固定大小的数组作为底层存储，实现简单且访问高效。

实现代码

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>#define MAX_SIZE 100  // 栈的最大容量// 栈的结构体定义
typedef struct {int data[MAX_SIZE];  // 存储栈元素的数组int top;             // 栈顶指针（-1表示空栈）
} Stack;// 初始化栈
void initStack(Stack *stack) {stack->top = -1;  // 空栈状态
}// 判断栈是否为空
bool isEmpty(Stack *stack) {return stack->top == -1;
}// 判断栈是否已满
bool isFull(Stack *stack) {return stack->top == MAX_SIZE - 1;
}// 入栈操作
bool push(Stack *stack, int value) {if (isFull(stack)) {printf("栈已满，无法入栈！\n");return false;}stack->data[++stack->top] = value;  // 先移动栈顶指针，再存入数据return true;
}// 出栈操作
bool pop(Stack *stack, int *value) {if (isEmpty(stack)) {printf("栈为空，无法出栈！\n");return false;}*value = stack->data[stack->top--];  // 先取出数据，再移动栈顶指针return true;
}// 获取栈顶元素
bool peek(Stack *stack, int *value) {if (isEmpty(stack)) {printf("栈为空，无法获取栈顶元素！\n");return false;}*value = stack->data[stack->top];return true;
}// 获取栈的大小
int size(Stack *stack) {return stack->top + 1;  // 栈顶索引+1即为元素个数
}// 打印栈中所有元素
void printStack(Stack *stack) {if (isEmpty(stack)) {printf("栈为空！\n");return;}printf("栈元素（从栈底到栈顶）：");for (int i = 0; i <= stack->top; i++) {printf("%d ", stack->data[i]);}printf("\n");
}// 主函数示例
int main() {Stack stack;initStack(&stack);int value;// 测试入栈push(&stack, 10);push(&stack, 20);push(&stack, 30);printStack(&stack);  // 输出：10 20 30// 测试获取栈顶元素if (peek(&stack, &value)) {printf("栈顶元素：%d\n", value);  // 输出：30}// 测试出栈if (pop(&stack, &value)) {printf("出栈元素：%d\n", value);  // 输出：30}printStack(&stack);  // 输出：10 20printf("栈的大小：%d\n", size(&stack));  // 输出：2printf("栈是否为空：%s\n", isEmpty(&stack) ? "是" : "否");  // 输出：否return 0;
}

顺序栈的优缺点

优点：实现简单，元素访问速度快（数组随机访问特性）
缺点：
- 容量固定，无法动态扩容（可能溢出）
- 内存利用率不高（可能浪费空间）

2. 链式栈（基于链表实现）

链式栈使用链表节点存储元素，可动态调整大小，内存利用率更高。

实现代码

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>// 链表节点结构体
typedef struct Node {int data;               // 节点数据struct Node *next;      // 指向下一个节点的指针
} Node;// 栈的结构体（链式栈）
typedef struct {Node *top;  // 栈顶指针（指向链表头节点）int size;   // 栈中元素个数
} LinkedStack;// 初始化栈
void initLinkedStack(LinkedStack *stack) {stack->top = NULL;stack->size = 0;
}// 判断栈是否为空
bool isLinkedStackEmpty(LinkedStack *stack) {return stack->top == NULL;
}// 入栈操作
void pushLinkedStack(LinkedStack *stack, int value) {// 创建新节点Node *newNode = (Node *)malloc(sizeof(Node));if (newNode == NULL) {printf("内存分配失败！\n");return;}newNode->data = value;newNode->next = stack->top;  // 新节点指向当前栈顶stack->top = newNode;        // 更新栈顶指针stack->size++;
}// 出栈操作
bool popLinkedStack(LinkedStack *stack, int *value) {if (isLinkedStackEmpty(stack)) {printf("栈为空，无法出栈！\n");return false;}Node *temp = stack->top;*value = temp->data;stack->top = stack->top->next;  // 更新栈顶指针free(temp);                     // 释放节点内存stack->size--;return true;
}// 获取栈顶元素
bool peekLinkedStack(LinkedStack *stack, int *value) {if (isLinkedStackEmpty(stack)) {printf("栈为空，无法获取栈顶元素！\n");return false;}*value = stack->top->data;return true;
}// 打印栈中元素
void printLinkedStack(LinkedStack *stack) {if (isLinkedStackEmpty(stack)) {printf("栈为空！\n");return;}printf("栈元素（从栈顶到栈底）：");Node *current = stack->top;while (current != NULL) {printf("%d ", current->data);current = current->next;}printf("\n");
}// 销毁栈（释放所有节点内存）
void destroyLinkedStack(LinkedStack *stack) {Node *temp;while (stack->top != NULL) {temp = stack->top;stack->top = stack->top->next;free(temp);}stack->size = 0;
}// 主函数示例
int main() {LinkedStack stack;initLinkedStack(&stack);int value;// 测试入栈pushLinkedStack(&stack, 100);pushLinkedStack(&stack, 200);pushLinkedStack(&stack, 300);printLinkedStack(&stack);  // 输出：300 200 100// 测试获取栈顶元素if (peekLinkedStack(&stack, &value)) {printf("栈顶元素：%d\n", value);  // 输出：300}// 测试出栈if (popLinkedStack(&stack, &value)) {printf("出栈元素：%d\n", value);  // 输出：300}printLinkedStack(&stack);  // 输出：200 100printf("栈的大小：%d\n", stack.size);  // 输出：2// 销毁栈destroyLinkedStack(&stack);return 0;
}

链式栈的优缺点

优点：
- 容量动态调整，无固定大小限制
- 内存利用率高（按需分配）
缺点：
- 实现相对复杂
- 每个节点需要额外存储指针，内存开销略大
- 访问速度不如顺序栈（链表顺序访问特性）

四、栈的典型应用场景

表达式求值：编译器使用栈处理数学表达式（如后缀表达式转换与计算）

括号匹配：检查代码中的括号是否正确配对（如()、[]、{}）

// 括号匹配示例函数
bool isParenthesesValid(char *str) {Stack stack;initStack(&stack);int i = 0;while (str[i] != '\0') {if (str[i] == '(' || str[i] == '[' || str[i] == '{') {push(&stack, str[i]);  // 左括号入栈} else if (str[i] == ')' || str[i] == ']' || str[i] == '}') {if (isEmpty(&stack)) return false;  // 右括号多了char top;pop(&stack, &top);// 检查括号是否匹配if ((str[i] == ')' && top != '(') ||(str[i] == ']' && top != '[') ||(str[i] == '}' && top != '{')) {return false;}}i++;}return isEmpty(&stack);  // 左括号是否多了
}