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

数据结构----栈和队列认识

news 2025/8/8 9:26:49

目录

栈（后进先出）

栈的实现

头文件

初始化

入栈

注意：

bool 判空

出栈----栈顶

注意

出栈顶元素，元素不会删除

注意：

获取栈中有效个数

销毁栈

源文件操作

用栈实现递归*

队列（先进先出）

队列实现

头文件（基本操作）：

结构

初始化

判空

入队----队尾

出队----队头

优势：

取队头队尾数据

优势：

销毁

栈（后进先出）

是⼀种特殊的线性表，其只允许在固定的⼀端进⾏插⼊和删除元素操作。进⾏数据插⼊和删除操作
的⼀端称为栈顶，另⼀端称为栈底。
压栈：栈的插⼊操作叫做进栈/压栈/⼊栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。

底层结构是由数组实现的，相对来说数组在尾结点插入快

逻辑结构和物理结构都是线性的

栈的实现

头文件

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
//定义栈的结构
typedef int STDataType;
typedef struct Stack
{STDataType* arr;int top;//有效数据个数int capacity;//容量
}ST;//初始化
void StackInit(ST* ps);//栈是否为空
bool STEmpty(ST* ps);//入栈----栈顶
void StackPush(ST* ps, STDataType x);//出栈----栈顶
void StackPop(ST* ps);//出栈顶数据
STDataType StackTop(ST* ps);
\ No newline at end of file
STDataType StackTop(ST* ps);//获取栈中有效元素个数
int StackSize(ST* ps);//栈是否为空
bool STEmpty(ST* ps);

初始化

//初始化
void StackInit(ST* ps)
{assert(ps);ps->arr = NULL;ps->top = ps->capacity = 0;
}

使用前先调用StackInit初始化栈，然后才能进行入栈等其他操作，否则可能会导致未定义行为。

入栈

//入栈----栈顶
void StackPush(ST* ps, STDataType x)
{if (ps->top == ps->capacity){//增容int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));if (tmp == NULL){perror("realloc");exit(1);}//空间申请成功ps->arr = tmp;ps->capacity = newCapacity;}ps->arr[ps->top++] = x;
}
  1. 首先检查栈是否已满（ps->top == ps->capacity）
  2. 如果栈满，则进行扩容操作：
    • 初始容量为 0 时，扩容到 4 个元素
    • 否则，按照 2 倍容量进行扩容
    • 使用realloc重新分配内存空间
    • 处理内存分配失败的情况（打印错误并退出程序）
  3. 将新元素x放入栈顶位置（ps->arr[ps->top]）
  4. 栈顶指针top自增，指向新的栈顶位置

注意：

  • ps指针不为空,一般断言一下。
  • 栈结构ST已经正确初始化
  • STDataType已经定义（通常是某种基本数据类型）

bool 判空

//栈是否为空
bool STEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}

为空则返回true,非空则是false

出栈----栈顶

//出栈----栈顶
void StackPop(ST* ps)
{assert(!STEmpty(ps));--ps->top;
}
  • 效率高，时间复杂度为 O (1)
  • 实现简洁，通过移动栈顶指针而非真正释放内存来 "删除" 元素

注意

  • 该函数依赖STEmpty函数来判断栈是否为空，需要确保STEmpty已正确实现
  • 出栈操作只是逻辑上移除元素（移动栈顶指针），并未真正释放内存，这是栈实现的常见做法
  • 调用前应确保栈不为空，否则assert会触发程序中断

出栈顶元素，元素不会删除


//出栈顶数据,元素不会删除
STDataType StackTop(ST* ps)
{assert(!STEmpty(ps));return ps->arr[ps->top - 1];}

注意：

  • 栈顶指针top指向的是下一个可以插入元素的位置，所以当前栈顶元素的索引是top - 1
  • 仅仅返回元素值，不修改top指针，因此元素不会被 "删除"
  • 依赖STEmpty函数判断栈是否为空，需要确保该函数已正确实现

获取栈中有效个数

//获取栈中有效元素个数
int StackSize(ST* ps)
{return ps->top;
}
  1. 直接返回栈顶指针top的值作为栈中有效元素的个数
  2. 这是因为栈的实现中top指针恰好表示了下一个可以插入元素的位置，同时也等于当前栈中元素的数量
  3. 时间复杂度为 O (1)，效率极高

销毁栈

void StackDestroy(ST* ps)
{assert(ps);free(ps->arr);  // 释放底层数组内存ps->arr = NULL; // 避免野指针ps->top = ps->capacity = 0; // 重置状态
}

源文件操作

#include"Stack.h"
void test1()
{ST st;StackInit(&st);StackPush(&st,1);StackPush(&st, 1);StackPush(&st, 2);StackPush(&st, 3);StackPush(&st,4);StackPush(&st, 4);StackPush(&st, 5);/*StackPop(&st);StackPop(&st);StackPop(&st);StackPop(&st);StackPop(&st);StackPop(&st);StackPop(&st);*//*while (!STEmpty(&st)){int top = StackTop(&st);printf("%d ", top);StackPop(&st);}*/int size = StackSize(&st);printf("%d\n", size);
}
int main()
{test1();return 0;
}

用栈实现递归*

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>// 定义栈结构
typedef int STDataType;
typedef struct Stack {STDataType* arr;int top;        // 栈顶指针，指向栈顶元素的下一个位置int capacity;   // 容量
} ST;// 栈的基本操作
void StackInit(ST* ps) {assert(ps);ps->arr = NULL;ps->top = ps->capacity = 0;
}void StackPush(ST* ps, STDataType x) {assert(ps);if (ps->top == ps->capacity) {int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));if (tmp == NULL) {perror("realloc");exit(1);}ps->arr = tmp;ps->capacity = newCapacity;}ps->arr[ps->top++] = x;
}void StackPop(ST* ps) {assert(ps);assert(ps->top > 0);ps->top--;
}STDataType StackTop(ST* ps) {assert(ps);assert(ps->top > 0);return ps->arr[ps->top - 1];
}int StackSize(ST* ps) {assert(ps);return ps->top;
}void StackDestroy(ST* ps) {assert(ps);free(ps->arr);ps->arr = NULL;ps->top = ps->capacity = 0;
}// 用栈模拟递归计算n的阶乘
int Factorial(int n) {if (n < 0) return -1; // 处理异常情况ST stack;StackInit(&stack);// 1. 模拟递归调用过程：将所有需要计算的数值入栈while (n > 1) {StackPush(&stack, n);n--;}// 2. 模拟递归返回过程：从栈顶开始计算int result = 1;while (StackSize(&stack) > 0) {result *= StackTop(&stack);StackPop(&stack);}StackDestroy(&stack);return result;
}int main() {int num = 5;int result = Factorial(num);printf("%d的阶乘是: %d\n", num, result); // 输出：5的阶乘是: 120return 0;
}

队列（先进先出）

只允许在⼀端进⾏插⼊数据操作，在另⼀端进⾏删除数据操作的特殊线性表
⼊队列：进⾏插⼊操作的⼀端称为队尾
出队列：进⾏删除操作的⼀端称为队头

队列实现

头文件（基本操作）：

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int QDataType;
//队列结点的结构
typedef struct QueueNode
{QDataType data;struct QueueNode* next;
}QueueNode;
//队列的结构
typedef struct Queue
{QueueNode* phead;QueueNode* ptail;//int size; //队列中有效数据个数
}Queue;//初始化
void QueueInit(Queue* pq);
//销毁队列
void QueueDestroy(Queue* pq);//入队——队尾
void QueuePush(Queue* pq, QDataType x);//出队——队头
void QueuePop(Queue* pq);
//队列判空
bool QueueEmpty(Queue* pq);
//队列有效元素个数
int QueueSize(Queue* pq);//取队头数据
QDataType QueueFront(Queue* pq);
//取队尾数据
QDataType QueueBack(Queue* pq);

结构

//队列结点的结构
typedef struct QueueNode
{QDataType data;struct QueueNode* next;
}QueueNode;
//队列的结构
typedef struct Queue
{QueueNode* phead;QueueNode* ptail;//int size; //队列中有效数据个数
}Queue;
  • 插入和删除操作效率高（队尾插入、队首删除均可在 O (1) 时间完成）
  • 不需要预先分配固定大小的内存，动态性好

初始化

//初始化
void QueueInit(Queue* pq)
{assert(pq);pq->phead = pq->ptail = NULL;//pq->size = 0;
}
  1. 使用assert(pq)确保传入的队列指针pq不为空，避免空指针操作
  2. 将队头指针phead和队尾指针ptail都初始化为NULL，表示初始状态下队列为空
  3. 注释掉的pq->size = 0用于初始化队列元素个数（如果保留size成员的话）

判空

/队列判空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->phead == NULL;
}

入队----队尾

//入队——队尾
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));if (newnode == NULL){perror("malloc fail");exit(1);}newnode->data = x;newnode->next = NULL;if (pq ->phead!= NULL)//队列非空{pq->ptail->next = newnode;pq->ptail = newnode;}else//队列为空{pq->phead = pq->ptail = newnode;}//size++;
}
  1. 当队列为空时（phead为NULL），新节点既是队头也是队尾
  2. 当队列非空时，将新节点链接到当前队尾节点（ptail）的next，然后更新ptail指向新节点

出队----队头

//出队——队头
void QueuePop(Queue* pq)
{assert(!QueueEmpty(pq));if (pq->phead == pq->ptail)//只有一个节点，头尾都置为空{free(pq->phead);pq->phead=pq->ptail = NULL;}else{QueueNode* next = pq->phead->next;free(pq->phead);pq->phead = next;}
}
  1. 分两种情况处理：
    • 当队列中只有一个节点时（pq->phead == pq->ptail）：
      • 释放该节点内存
      • 将phead和ptail都置为NULL，保持空队列状态
    • 当队列中有多个节点时：
      • 先保存头节点的下一个节点指针
      • 释放头节点内存
      • 更新phead指向保存的下一个节点

优势：

  • 正确维护了队列的头指针和尾指针状态
  • 避免了内存泄漏（释放了被移除节点的内存）
  • 处理了队列从有元素变为空的边界情况

若包含size,size--保持数量一致

取队头队尾数据

//取队头数据
QDataType QueueFront(Queue* pq)
{assert(!QueueEmpty(pq));return pq->phead->data;
}//取队尾数据
QDataType QueueBack(Queue* pq)
{assert(!QueueEmpty(pq));return pq->ptail->data;}

优势：

  • 时间复杂度都是 O (1)，效率很高
  • 仅获取元素值，不会修改队列的结构和状态
  • 依赖QueueEmpty函数判断队列是否为空，保持了代码的一致性
  • 符合队列 "先进先出" 的特性，分别提供了访问两端元素的接口

销毁

//销毁队列
void QueueDestroy(Queue* pq)
{assert（pq);QueueNode* pcur = pq->phead;while (pcur){QueueNode* next = pcur->next;free(pcur);pcur = next;}pq->phead = pq->ptail =NULL;//pq->size =0;
}

销毁队列是一个通用操作，即使队列为空（初始状态或已清空），也应该允许调用QueueDestroy，这样可以避免在调用销毁函数前还需要手动判断队列是否为空。

允许对空队列进行销毁

  • 当队列为空时，pcur初始为NULL，循环不会执行，直接重置phead和ptail
  • 当队列非空时，循环释放所有节点，最后重置指针

http://www.lryc.cn/news/613093.html

相关文章：

  • 深度学习-卷积神经网络CNN-1×1卷积层
  • 仓库管理系统-21-前端之入库和出库管理
  • Windows中安装rustup-init.exe以及cargo build报错443
  • 零基础-动手学深度学习-9.3. 深度循环神经网络
  • 流程图使用规范
  • Android 之 面试八股文
  • GCC与NLP实战：编译技术赋能自然语言处理
  • 解决GitHub无法打开
  • idea开发工具中git如何忽略编译文件build、gradle的文件？
  • 复杂井眼测量中，陀螺定向和磁通门定向哪个更胜一筹？
  • 幕后英雄 —— Background Scripts (Service Worker)
  • 浅析 Berachain v2 ，对原有 PoL 机制进行了哪些升级？
  • 我的世界Java版1.21.4的Fabric模组开发教程(十七)自定义维度
  • 比较一下XGBoost与LSTM、GRU、Transformer数据格式方面的核心区别
  • 零基础-动手学深度学习-9.1. 门控循环单元（GRU）及代码实现
  • Docker国内可用镜像列表（长期免费）
  • 接入小甲鱼数字人API教程【详解】
  • Next.js 样式：CSS 模块、Sass 等
  • ENSP 中静态路由负载分担
  • vue3接收SSE流数据进行实时渲染日志
  • RabbitMQ-日常运维命令
  • CS231n2017 Assignment3 RNN、LSTM部分
  • 3深度学习Pytorch-神经网络--全连接神经网络、数据准备（构建数据类Dataset、TensorDataset 和数据加载器DataLoader）
  • PID基础知识
  • 关于其他副脑类 GPTs 市场现状及研究报告
  • mysql全屏终端全量、部分备份、恢复脚本
  • Python面试题及详细答案150道（16-30） -- 数据结构篇
  • 分布式微服务--GateWay(过滤器及使用Gateway注意点)
  • 告别YAML，在SpringBoot中用数据库配置替代配置文件
  • word生成问题总结