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

【数据结构】栈与队列

backend 2025/5/16 11:35:29

本文是小编巩固自身而作，如有错误，欢迎指出！

1.栈

1.1 概念与结构

栈：⼀种特殊的线性表，其只允许在固定的⼀端进⾏插⼊和删除元素操作。进⾏数据插⼊和删除操作的⼀端称为栈顶，另⼀端称为栈底。栈中的数据元素遵守后进先出的原则。

栈的实现⼀般可以使⽤数组或者链表实现，相对⽽⾔数组的结构实现更优⼀些。因为数组在尾上插⼊ 数据的代价⽐较⼩。（在之前我们学过，数组的尾插时间复杂度是O（1），而链表的复杂度是O（N））

1.2栈的实现

1.2.1栈的结构


//定义栈的结构
typedef int stdatatype;
struct Stack
{stdatatype* arr;int top;//指向栈顶int capacity;//栈的容量
};
typedef struct Stack ST;

这里的栈我们采用类似于顺序表的方式实现，一个栈包含如上码所示的三个内容。

1.2.2栈的初始化

和顺序表类似，将数组置空，数据置零。

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

 1.2.3入栈

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 fail");exit(1);}ps->arr = tmp;ps->capacity = newcapacity;}//栈未满ps->arr[ps->top++] = x;
}

 1.2.4出栈

void stackpop(ST* ps)//出栈
{assert(!stackempty(ps));//判空--ps->top;
}

在出栈时需要考虑是否为空的情况我们这里使用bool函数。

bool stackempty(ST* ps)
{assert(ps);return ps->top == 0;
}

 1.2.5取栈顶元素

stdatatype stacktop(ST* ps)//取栈顶元素
{assert(!stackempty(ps));return ps->arr[ps->top - 1];
}

1.2.6销毁栈 

void stackdestroy(ST* ps)//销毁栈
{if (ps->arr){free(ps->arr);ps->arr = NULL;ps->top = ps->capacity = 0;}
}

1.3完整代码实现

.h文件

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>//定义栈的结构
typedef int stdatatype;
struct Stack
{stdatatype* arr;int top;//指向栈顶int capacity;//栈的容量
};
typedef struct Stack ST;void stackinit(ST* ps);//栈初始化
void stackpush(ST* ps, stdatatype x);//入栈
void stackpop(ST* ps);//出栈
bool stackempty(ST* ps);//判空
stdatatype stacktop(ST* ps);//取栈顶元素
void stackdestroy(ST* ps);//销毁栈

.c文件 

#define _CRT_SECURE_NO_WARNINGS
#include"stack.h"void stackinit(ST* ps)//栈初始化
{ps->arr = NULL;ps->top = ps->capacity = 0;
}
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 fail");exit(1);}ps->arr = tmp;ps->capacity = newcapacity;}ps->arr[ps->top++] = x;
}
bool stackempty(ST* ps)
{assert(ps);return ps->top == 0;
}
void stackpop(ST* ps)//出栈
{assert(!stackempty(ps));//判空--ps->top;
}
stdatatype stacktop(ST* ps)//取栈顶元素
{assert(!stackempty(ps));return ps->arr[ps->top - 1];
}
void stackdestroy(ST* ps)//销毁栈
{if (ps->arr){free(ps->arr);ps->arr = NULL;ps->top = ps->capacity = 0;}
}

.c文件（测试） 

#define _CRT_SECURE_NO_WARNINGS
#include"stack.h"
void test01()
{ST st;stackinit(&st);stackpush(&st, 1);stackpush(&st, 2);stackpush(&st, 3);stackpush(&st, 4);stackpop(&st);while (!stackempty(&st)){int top = stacktop(&st);printf("%d ", top);stackpop(&st);}
}
int main()
{test01();return 0;
}

2.队列 

2.1概念与结构

概念：只允许在⼀端进⾏插⼊数据操作，在另⼀端进⾏删除数据操作的特殊线性表，队列具有先进先出。

队列也可以数组和链表的结构实现，使⽤链表的结构实现更优⼀些，因为如果使⽤数组的结构，出队 列在数组头上出数据，效率会比较低。  

2.2队列的实现

2.2.1队列的结构

typedef int QDdatatype;
//节点结构
typedef struct QueueNode
{QDdatatype data;struct QueueNode* next;
}QUnode;
//队列结构
typedef struct Queue
{struct QueueNode* phead;struct QueueNode* ptail;//int size;//有效数据的个数
}QU;

为了避免像一般单链表在尾部进行操作导致时间复杂度增加，我们相较于单链表多创建一个尾节点 。

2.2.2队列的初始化

void QUinit(QU* pq)//初始化
{assert(pq);pq->phead = pq->ptail = NULL;//pq->size = 0;
}

2.2.3入队--队尾

void QUpushi(QU* pq, QDdatatype x)//入队--队尾
{assert(pq);//队列为空QUnode* newnode = (QUnode*)malloc(sizeof(QUnode));if (newnode == NULL){perror("malloc fail");exit(1);}newnode->data = x;newnode->next = NULL;if (pq->phead == NULL){pq->phead = pq->ptail = newnode;}else{pq->ptail->next = newnode;pq->ptail = pq->ptail->next;}//pq->size++;
}

类似于链表中尾插。

2.2.4出队--队头

void QUpop(QU * pq)//出队--队头{assert(!QUempty(pq));//只有一个节点if (pq->phead == pq->ptail){free(pq->phead);pq->phead = pq->ptail = NULL;}else{QUnode* next = pq->phead->next;free(pq->phead);pq->phead = next;}/*pq->size--;*/}

在出队时就要考虑队列为空的情况

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

2.2.5 取头、尾数据

QDdatatype QUfront(QU* pq)//取头数据{assert(!QUempty(pq));return pq->phead->data;}QDdatatype QUback(QU* pq)//取尾数据{assert(!QUempty(pq));return pq->ptail->data;}

2.2.6销毁队列 

void QUdestroy(QU* pq)//销毁队列{assert(pq);QUnode* pcur = pq->phead;while (pcur){QUnode* next = pq->phead;free(pcur);pcur = next;}pq->phead = pq->ptail = NULL;/*pq->size = 0;*/}

 2.3完整代码实现

.h文件

#pragma once
#include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>
#include<assert.h>
typedef int QDdatatype;
//节点结构
typedef struct QueueNode
{QDdatatype data;struct QueueNode* next;
}QUnode;
//队列结构
typedef struct Queue
{struct QueueNode* phead;struct QueueNode* ptail;//int size;//有效数据的个数
}QU;
void QUinit(QU* pq);//初始化
void QUpushi(QU* pq, QDdatatype x);//入队--队尾
void QUpop(QU* pq);//出队--队头
bool QUempty(QU* pq);//队列判空
QDdatatype QUfront(QU* pq);//取头数据
QDdatatype QUback(QU* pq);//取尾数据
void QUdestroy(QU* pq);//销毁队列
int QUsize(QU* pq);//队列的有效元素

.c文件

#define _CRT_SECURE_NO_WARNINGS
#include"Queue.h"
void QUinit(QU* pq)//初始化
{assert(pq);pq->phead = pq->ptail = NULL;//pq->size = 0;
}
bool QUempty(QU* pq)//队列判空
{assert(pq);return pq->phead == NULL;
}
void QUpushi(QU* pq, QDdatatype x)//入队--队尾
{assert(pq);//队列为空QUnode* newnode = (QUnode*)malloc(sizeof(QUnode));if (newnode == NULL){perror("malloc fail");exit(1);}newnode->data = x;newnode->next = NULL;if (pq->phead == NULL){pq->phead = pq->ptail = newnode;}else{pq->ptail->next = newnode;pq->ptail = pq->ptail->next;}//pq->size++;
}void QUpop(QU * pq)//出队--队头{assert(!QUempty(pq));//只有一个节点if (pq->phead == pq->ptail){free(pq->phead);pq->phead = pq->ptail = NULL;}else{QUnode* next = pq->phead->next;free(pq->phead);pq->phead = next;}/*pq->size--;*/}QDdatatype QUfront(QU* pq)//取头数据{assert(!QUempty(pq));return pq->phead->data;}QDdatatype QUback(QU* pq)//取尾数据{assert(!QUempty(pq));return pq->ptail->data;}void QUdestroy(QU* pq)//销毁队列{assert(pq);QUnode* pcur = pq->phead;while (pcur){QUnode* next = pq->phead;free(pcur);pcur = next;}pq->phead = pq->ptail = NULL;/*pq->size = 0;*/}int QUsize(QU* pq)//队列的有效元素{/*assert(pq);QUnode* pcur = pq->phead;int size = 0;while (pcur){size++;pcur = pcur->next;}*//*return pq->size;*/}

.c文件（测试） 

#define _CRT_SECURE_NO_WARNINGS
#include"Queue.h"void test01()
{QU q;QUinit(&q);QUpushi(&q, 1);QUpushi(&q, 2);QUpushi(&q, 3);		QUpop(&q);int front = QUfront(&q);int back = QUback(&q);printf("%d\n", front);printf("%d\n", back);void QUdestroy(QU * pq);//销毁队列}
int main()
{test01();return 0;
}

 在具体实现思路都与之前的顺序表与链表相似，有不理解的可以看看前篇

顺序表

单链表

本次分享就到这里结束了，感谢阅读！

http://www.xdnf.cn/news/6534.html

相关文章：

  • Redis6为什么引入了多线程？
  • 20、工业协议转换与数据采集中间件 (模拟) - /数据与物联网组件/protocol-converter-middleware
  • std::deque 底层实现结构
  • 老字号焕新案例：天猫代运营如何让传统品牌年轻化破圈
  • SEO双核驱动：关键词与长尾词优化
  • JAVA:多线程使用哈希表
  • Web前端入门：JavaScript 的应用领域
  • [数据结构]7. 堆-Heap
  • undefined reference to vtable for DeviceAllocator‘
  • 【补充笔记】修复“NameError: name ‘ZhNormalizer‘ is not defined”的直接方法
  • Python基础
  • 吴恩达机器学习笔记：特征与多项式回归
  • springboot AOP中，通过解析SpEL 表达式动态获取参数值
  • 第二十五天打卡
  • GUI图形化演示
  • 【测试】用例篇
  • 免疫浸润分析
  • 哲学物理：太极图和莫比乌斯环有什么关系？
  • 【QT 项目部署指南】使用 Inno Setup 打包 QT 程序为安装包（超详细图文教程）
  • Vue3的基础知识
  • 【skywalking】index“:“skywalking_metrics-all“},“status“:404}
  • Ansys Zemax | 在 MATLAB 或 Python 中使用 ZOS-API 进行光线追迹的批次处理
  • TASK02【Datawhale 组队学习】使用 LLM API 开发应用
  • javascript —— ! 和 !! 的区别与作用
  • 傻子学编程之——数据库如何性能优化
  • 西瓜书【机器学习（周志华）】目录
  • [网络升级指南] 服务器网卡/带宽如何选？1GbE vs 10GbE vs 25GbE+ 性能与成本深度解析 (2025)
  • 香山新篇：海淀低密奢居的典范之作
  • 今日行情明日机会——20250515
  • OpenShift AI - 用 ModelCar 构建容器化模型，提升模型弹性扩展速度