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

数据结构-栈

news 2025/12/1 19:04:19

一、了解栈

栈是一种线性数据结构，遵循“后进先出”（Last In, First Out，LIFO）的原则。也就是说，最后被压入栈中的元素最先被弹出。栈可以看作是一个只允许在一端进行插入和删除操作的集合。

栈的基本特性：

  1. 操作限制：

    • 压栈（Push）：将元素添加到栈顶。
    • 弹栈（Pop）：从栈顶移除元素并返回该元素。
    • 查看栈顶元素（Peek/Top）：返回栈顶元素但不移除它。

  2. 栈的状态：

    • 空栈：没有任何元素。
    • 满栈：达到栈的最大容量（在使用数组实现时）。

  3. 应用场景：

    • 函数调用（调用栈）
    • 表达式求值（如后缀表达式）
    • 括号匹配
    • 深度优先搜索（DFS）

总结

栈是一种简单而重要的数据结构，广泛应用于计算机科学和编程中，尤其是在管理函数调用、表达式求值和实现算法时。由于其特有的LIFO特性，栈能够有效地处理需要临时存储和后续访问的元素。

二、栈的顺序存储结构（C语言）

1. 栈的顺序存储结构

// 栈的顺序存储结构
#define MaxSize 50  // 定义一个常量 MaxSize，表示栈的最大容量为 50// 定义一个顺序栈的结构体 SqStack
typedef struct {int data[MaxSize]; // 用一个数组 data 来存储栈中的元素，大小为 MaxSizeint top;           // top 用于记录栈顶元素的索引，初始值通常为 -1 表示栈空
} SqStack; // SqStack 结构体类型的定义结束

2. 栈的初始化


// 初始化栈
void InitStack(SqStack* S) {S->top = -1; // 将栈顶指针初始化为 -1，表示栈为空
}

3. 判断栈为空


// 判断栈是否为空
bool StackEmpty(SqStack* S) {// 检查栈顶指针是否为 -1if (S->top == -1)return true; // 如果是，返回 true，表示栈为空elsereturn false; // 否则返回 false，表示栈不为空
}

4. 进栈


// 进栈操作
bool Push(SqStack* S, int e) {// 检查栈是否已满if (S->top == MaxSize - 1)return false; // 如果满了，返回 falseS->top++; // 栈顶指针增加S->data[S->top] = e; // 将元素 e 压入栈顶return true; // 返回 true，表示成功压入元素
}

5. 出栈


// 出栈操作
bool Pop(SqStack* S, int* e) {// 检查栈是否为空if (S->top == -1)return false; // 如果栈为空，返回 false*e = S->data[S->top]; // 将栈顶元素赋值给 eS->top--; // 栈顶指针减少，移除栈顶元素return true; // 返回 true，表示成功出栈
}

6. 读栈顶元素


// 读顶栈元素
bool GetTop(SqStack* S, int* e) {// 检查栈是否为空if (S->top == -1)return false; // 如果栈为空，返回 false*e = S->data[S->top]; // 将栈顶元素的值赋给 ereturn true; // 返回 true，表示成功获取栈顶元素
}

7. 销毁栈


// 销毁栈
void DestroyStack(SqStack* S) {S->top = -1; // 将栈顶指针设置为 -1，表示栈已被销毁
}

三、栈的链式存储结构（C语言）

1. 栈的链式存储结构


// 链表节点结构体定义
typedef struct LNode {int data;                // 节点存储的数据struct LNode* next;     // 指向下一个节点的指针
} LNode, * Linknode;          // Linknode 是指向 LNode 的指针类型

2. 栈的初始化


// 初始化链表（栈）-- 带头结点
bool InitStack(Linknode* LS) {// 为链表头节点分配内存(*LS) = (LNode*)malloc(sizeof(LNode));// 检查内存分配是否成功if ((*LS) == NULL) return false; // 如果分配失败，返回 false(*LS)->next = NULL; // 初始化头节点的 next 指针为 NULLreturn true;       // 返回 true，表示初始化成功
}

3. 判断栈为空

// 判断栈是否为空 -- 带头结点
bool StackEmpty(Linknode LS) {// 检查头结点是否为空// if (LS == NULL) return false; // 此行代码被注释掉，表示不考虑头结点为空的情况// 如果头结点的下一个节点为空，则栈为空if (LS->next == NULL) return true;elsereturn false; // 否则栈不为空
}

4. 进栈


// 进栈
bool Push(Linknode* LS, int e) {// 检查头结点是否为空，若为空则无法进栈if (*LS == NULL) return false;// 创建一个新的节点LNode* p;p = (LNode*)malloc(sizeof(LNode)); // 为新节点分配内存// 检查内存分配是否成功if (p == NULL) return false;// 将新节点的下一个指针指向当前栈顶元素p->next = (*LS)->next;// 更新头结点的下一个指针，使其指向新节点(*LS)->next = p;// 将新节点的数据域赋值为进栈的元素p->data = e;return true; // 返回成功进栈的标志
}

5. 出栈


// 出栈
bool Pop(Linknode* LS, int* e) {// 检查栈是否为空，如果栈指针为空，返回falseif ((*LS) == NULL) return false;// 检查栈是否只有一个元素（即栈顶元素），如果是，返回falseif ((*LS)->next == NULL) return false;// 获取栈顶元素的指针LNode* p = (*LS)->next;// 将栈顶指针指向下一个元素(*LS)->next = p->next;// 将栈顶元素的值赋给e*e = p->data;// 释放栈顶元素的内存free(p);// 返回true，表示成功出栈return true;
}

6. 读栈顶元素


// 读栈顶元素
bool GetTop(Linknode* S, int* e) {// 检查栈是否为空，如果栈指针为空，返回falseif ((*S) == NULL) return false;// 检查栈是否只有一个元素（即栈顶元素），如果是，返回falseif ((*S)->next == NULL) return false;// 将栈顶元素的值赋给e*e = (*S)->next->data;// 返回true，表示成功获取栈顶元素return true;
}

7. 销毁栈


// 销毁栈
void DestroyStack(Linknode* S) {// 检查栈是否为空，如果栈指针为空，直接返回if ((*S) == NULL) return;LNode* p;// 循环释放栈中的所有元素while ((*S)->next != NULL) {p = (*S)->next;       // 获取当前栈顶元素的指针(*S)->next = p->next; // 将栈顶指针指向下一个元素free(p);             // 释放当前栈顶元素的内存}// 释放栈的头节点free(*S);// 将指针重置为 NULL，避免悬空指针*S = NULL;
}

四、总代码（C语言）

1. 顺序栈

#include <stdio.h>
#include <stdbool.h>// 栈的顺序存储结构
#define MaxSize 50  // 定义一个常量 MaxSize，表示栈的最大容量为 50// 定义一个顺序栈的结构体 SqStack
typedef struct {int data[MaxSize]; // 用一个数组 data 来存储栈中的元素，大小为 MaxSizeint top;           // top 用于记录栈顶元素的索引，初始值通常为 -1 表示栈空
} SqStack; // SqStack 结构体类型的定义结束// 初始化栈
void InitStack(SqStack* S) {S->top = -1; // 将栈顶指针初始化为 -1，表示栈为空
}// 判断栈是否为空
bool StackEmpty(SqStack* S) {// 检查栈顶指针是否为 -1if (S->top == -1)return true; // 如果是，返回 true，表示栈为空elsereturn false; // 否则返回 false，表示栈不为空
}// 进栈操作
bool Push(SqStack* S, int e) {// 检查栈是否已满if (S->top == MaxSize - 1)return false; // 如果满了，返回 falseS->top++; // 栈顶指针增加S->data[S->top] = e; // 将元素 e 压入栈顶return true; // 返回 true，表示成功压入元素
}// 出栈操作
bool Pop(SqStack* S, int* e) {// 检查栈是否为空if (S->top == -1)return false; // 如果栈为空，返回 false*e = S->data[S->top]; // 将栈顶元素赋值给 eS->top--; // 栈顶指针减少，移除栈顶元素return true; // 返回 true，表示成功出栈
}// 读顶栈元素
bool GetTop(SqStack* S, int* e) {// 检查栈是否为空if (S->top == -1)return false; // 如果栈为空，返回 false*e = S->data[S->top]; // 将栈顶元素的值赋给 ereturn true; // 返回 true，表示成功获取栈顶元素
}// 销毁栈
void DestroyStack(SqStack* S) {S->top = -1; // 将栈顶指针设置为 -1，表示栈已被销毁
}// int main() {return 0;
}

2. 链栈

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>// 链表节点结构体定义
typedef struct LNode {int data;                // 节点存储的数据struct LNode* next;     // 指向下一个节点的指针
} LNode, * Linknode;          // Linknode 是指向 LNode 的指针类型// 初始化链表（栈）-- 带头结点
bool InitStack(Linknode* LS) {// 为链表头节点分配内存(*LS) = (LNode*)malloc(sizeof(LNode));// 检查内存分配是否成功if ((*LS) == NULL) return false; // 如果分配失败，返回 false(*LS)->next = NULL; // 初始化头节点的 next 指针为 NULLreturn true;       // 返回 true，表示初始化成功
}// 判断栈是否为空 -- 带头结点
bool StackEmpty(Linknode LS) {// 检查头结点是否为空// if (LS == NULL) return false; // 此行代码被注释掉，表示不考虑头结点为空的情况// 如果头结点的下一个节点为空，则栈为空if (LS->next == NULL) return true;elsereturn false; // 否则栈不为空
}// 进栈
bool Push(Linknode* LS, int e) {// 检查头结点是否为空，若为空则无法进栈if (*LS == NULL) return false;// 创建一个新的节点LNode* p;p = (LNode*)malloc(sizeof(LNode)); // 为新节点分配内存// 检查内存分配是否成功if (p == NULL) return false;// 将新节点的下一个指针指向当前栈顶元素p->next = (*LS)->next;// 更新头结点的下一个指针，使其指向新节点(*LS)->next = p;// 将新节点的数据域赋值为进栈的元素p->data = e;return true; // 返回成功进栈的标志
}// 出栈
bool Pop(Linknode* LS, int* e) {// 检查栈是否为空，如果栈指针为空，返回falseif ((*LS) == NULL) return false;// 检查栈是否只有一个元素（即栈顶元素），如果是，返回falseif ((*LS)->next == NULL) return false;// 获取栈顶元素的指针LNode* p = (*LS)->next;// 将栈顶指针指向下一个元素(*LS)->next = p->next;// 将栈顶元素的值赋给e*e = p->data;// 释放栈顶元素的内存free(p);// 返回true，表示成功出栈return true;
}// 读栈顶元素
bool GetTop(Linknode* S, int* e) {// 检查栈是否为空，如果栈指针为空，返回falseif ((*S) == NULL) return false;// 检查栈是否只有一个元素（即栈顶元素），如果是，返回falseif ((*S)->next == NULL) return false;// 将栈顶元素的值赋给e*e = (*S)->next->data;// 返回true，表示成功获取栈顶元素return true;
}// 销毁栈
void DestroyStack(Linknode* S) {// 检查栈是否为空，如果栈指针为空，直接返回if ((*S) == NULL) return;LNode* p;// 循环释放栈中的所有元素while ((*S)->next != NULL) {p = (*S)->next;       // 获取当前栈顶元素的指针(*S)->next = p->next; // 将栈顶指针指向下一个元素free(p);             // 释放当前栈顶元素的内存}// 释放栈的头节点free(*S);// 将指针重置为 NULL，避免悬空指针*S = NULL;
}// 示例用法
int main() {Linknode stack;if (InitStack(&stack)) {printf("Stack initialized successfully.\n");}else {printf("Failed to initialize stack.\n");}// 记得释放内存free(stack);return 0;
}

五、总结

        栈是一种重要的线性数据结构，遵循“后进先出”（LIFO）的原则，具有压栈、弹栈和查看栈顶元素等基本操作。栈的应用广泛，包括函数调用的管理、表达式求值、括号匹配和深度优先搜索等。栈可以通过顺序存储结构（如数组）或链式存储结构（如链表）实现。顺序栈通过一个固定大小的数组来存储元素，使用一个索引记录栈顶位置，具有简单高效的特性，但容易出现栈满的情况。链式栈则通过动态分配内存的链表节点来实现，能够灵活地使用内存，避免栈满的情况，但在访问和管理节点时相对复杂。栈的基本操作包括初始化、判断是否为空、进栈、出栈、获取栈顶元素和销毁栈等。通过这些操作，栈能够有效地管理临时数据，支持多种算法和应用场景。总体而言，栈是计算机科学中不可或缺的基础数据结构之一。


http://www.mrgr.cn/news/1329.html

相关文章：

  • 【9.2 python中的参数传递】
  • ardupilot开发 --- 故障保护 篇
  • git的学习教程
  • OD C卷 - 小扇和小船的数字游戏
  • Linux：进程的概念，进程相关函数
  • 硬件I2C和软件I2C（模拟I2C）的区别
  • Therabody™明星产品TheragunⓇ筋膜枪，以科技健康助力舞台高光时刻
  • GO语言如何抗住火影忍者手游的高并发
  • QT C++上位机软件开发，相比较C#上位机软件开发，有哪些特点和区别
  • IOPaint部署，在服务器Ubuntu22.04系统下——点动科技
  • 学习文件IO，让你从操作系统内核的角度去理解输入和输出（理论篇）
  • 使用百度文心智能体创建AI旅游助手
  • Spring中事务（面试常考）
  • STM32初识
  • 记一次Jenkins项目构建耗时优化
  • MT7621+MT7915(MT7905)+MT7975 (W7621A6G-SDK)编译固件与升级固件方法
  • 深入解析UDP协议与TCP协议：它们的区别与应用场景
  • XML外部实体注入
  • 大白话解析：深入浅出大模型RAG模块全解析
  • C++引用和指针的区别还分不清楚？