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

【数据结构】栈和队列--＞理解和实现（赋源码)

news 来源：原创 2024/9/29 19:31:00

Toc

欢迎光临我的Blog，喜欢就点歌关注吧♥

前面介绍了顺序表、单链表、双向循环链表，基本上已经结束了链表的讲解，今天谈一下栈、队列。可以简单的说是前面学习的一特殊化实现，但是总体是相似的。

前言

  1. 栈是一种特殊的线性表，它只允许在一端进行插入和删除操作。这一端被称为栈顶，另一端被称为栈底。栈的特点是后进先出（LIFO），即最后进入的元素最先被移除。

  2. 队列是另一种特殊的线性表，它允许在一端进行插入操作，在另一端进行删除操作。插入操作的一端称为队尾，删除操作的一端称为队头。队列的特点是先进先出（FIFO），即最先进入的元素最先被移除。

栈和队列有各自的特点，严格讲用顺序表还是链表的实现都可以。但我们根据结构特点选择一个更加适合的结构进行是实现。

一、栈和队列的理解

对于栈的理解：

在这里插入图片描述

栈如同这个图一样，要是想拿出数据，必须从上面一个一个往下面拿。这也正是 LIFO 的体现。

对于队列的理解：

在这里插入图片描述

队列如同这个图一样，要是想拿出数据，必须前面一个一个往向后面拿。这也正是 FIFO 的体现。

二、栈的实现（顺组表）

2.1 栈的功能

//初始化
void STInit(ST* ps);
//压栈
void STpush(ST* ps, STDataType x);
//删除
void STPop(ST* ps);
//大小
int STSize(ST* ps);
//判空
bool STEmpty(ST* ps);
//出栈
STDataType STTop(ST* ps);
//检查容量
void CheckCapacity(ST* ps);
//销毁
void STDestroy(ST* ps);

2.2 栈结构体的定义及其初始化

结构体的定义

typedef int STDataType;typedef struct stack
{STDataType* a;int top;int capacity;
}ST;

初始化（开辟空间）

void STInit(ST* ps)
{assert(ps);ps->a = (STDataType*)malloc(sizeof(STDataType)*4);if (ps->a == NULL){perror("malloc fail");return;}ps->capacity = 4;ps->top = 0;
}

2.3 压栈（存储数据）

//压栈
void STpush(ST* ps,STDataType x)
{assert(ps);ps->a[ps->top] = x;ps->top++;
}

2,4 删除数据

在这里面删除数据是配合，栈顶出栈。每次拿出一个数据，就要减少一个数据。

void STPop(ST* ps)
{assert(ps);assert(!STEmpty(ps));ps->top--;
}

2.5 计算栈内元个数

//大小
int STSize(ST* ps)
{assert(ps);return ps->top;
}

2.6 判断栈内是否为空

这里运用 bool 类型直接返回，比较方便。

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

2.7 出栈

//出栈
STDataType STTop(ST* ps)
{assert(ps);return ps->a[ps->top-1];
}

2.8 增加容量

//检查容量
void CheckCapacity(ST*ps)
{assert(ps);if (ps->top == ps->capacity){ST* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * (ps->capacity) * 2);if (tmp == NULL){perror("malloc fail");return;}ps->capacity *= 2;ps->a = tmp;}
}

2.9 销毁栈

//销毁
void STDestroy(ST* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->capacity = 0;ps->top = 0;
}

三、队列的实现（单链表）

3.1 队列的功能

//初始化
void QueueInit(Queue* ps);
//销毁
void QueueDestroy(Queue* ps);
//入队
void QueuePush(Queue* ps, QDataType x);
//删除
void QueuePop(Queue* ps);
//大小
int QueueSize(Queue* ps);
//判空队
bool QueueEmpty(Queue* ps);
//出队头
QDataType QueueTop(Queue* ps);
//出队尾
QDataType QueueBack(Queue* ps);

3.2 队列的结构体定义以及初始化

结构体定义

定义两个结构体，第一个为存放数据，第二个结构体为两个指针，分别指向头和尾

typedef int QDataType;typedef struct QNode
{struct QNode* next;QDataType data;}QNode;typedef struct Queue
{QNode*head;QNode*tail;int szie;
}Queue;

初始化

//初始化
void QueueInit(Queue* ps)
{assert(ps);ps->head = ps->tail = NULL;ps->szie = 0;}

3.3 队列销毁

//销毁
void QueueDestroy(Queue* ps)
{assert(ps);QNode* cur = ps->head;while (cur){QNode* next = cur->next;free(cur);cur = next;}ps->head = ps->tail = NULL;ps->szie = 0;
}

3.4 入队（插入数据）

//入队
void QueuePush(Queue* ps,QDataType x)
{assert(ps);QNode* newcode = (QNode*)malloc(sizeof(QNode));if (newcode == NULL){perror("malloc fail");return ;}newcode->next = NULL;newcode->data = x;if (ps->head == NULL){ps->head = ps->tail = newcode;}else{ps->tail->next = newcode;ps->tail = newcode;}ps->szie++;}

3.5 删除数据（头删）

//删除
void QueuePop(Queue* ps)
{assert(ps);assert(ps->head != NULL);assert(!QueueEmpty(ps));if (ps->head->next == NULL){free(ps->head);ps->head = ps->tail = NULL;}else{QNode* next = ps->head->next;free(ps->head);ps->head = next;}ps->szie--;
}

3.6 计算队列元素个数

//大小
int QueueSize(Queue* ps)
{assert(ps);return ps->szie;
}

3.7 判断是否队列为空

//判空队
bool QueueEmpty(Queue* ps)
{assert(ps);return ps->szie == 0;
}

3.8 出队（头）

//出队头
QDataType QueueTop(Queue* ps)
{assert(ps);assert(!QueueEmpty(ps));return ps->head->data;
}

3.9 出队（尾）

//出队尾
QDataType QueueBack(Queue* ps)
{assert(ps);return ps->tail->data;
}

四、栈和队列的源码

栈

Stack.h

#pragma once#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>typedef int STDataType;typedef struct stack
{STDataType* a;int top;int capacity;
}ST;//初始化
void STInit(ST* ps);
//压栈
void STpush(ST* ps, STDataType x);
//删除
void STPop(ST* ps);
//大小
int STSize(ST* ps);
//判空
bool STEmpty(ST* ps);
//出栈
STDataType STTop(ST* ps);
//检查容量
void CheckCapacity(ST* ps);
//销毁
void STDestroy(ST* ps);

Stack.c

#define _CRT_SECURE_NO_WARNINGS#include "stack.h"//初始化
void STInit(ST* ps)
{assert(ps);ps->a = (STDataType*)malloc(sizeof(STDataType*)*4);if (ps->a == NULL){perror("malloc fail");return;}ps->capacity = 4;ps->top = 0;
}
//销毁
void STDestroy(ST* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->capacity = 0;ps->top = 0;
}//检查容量
void CheckCapacity(ST*ps)
{assert(ps);if (ps->top == ps->capacity){ST* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * (ps->capacity) * 2);if (tmp == NULL){perror("malloc fail");return;}ps->capacity *= 2;ps->a = tmp;}
}//压栈
void STpush(ST* ps,STDataType x)
{assert(ps);ps->a[ps->top] = x;ps->top++;
}//删除
void STPop(ST* ps)
{assert(ps);assert(!STEmpty(ps));ps->top--;
}//判空
bool STEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}//出栈
STDataType STTop(ST* ps)
{assert(ps);return ps->a[ps->top-1];
}//大小
int STSize(ST* ps)
{assert(ps);return ps->top;
}

test.c

#define _CRT_SECURE_NO_WARNINGS#include "stack.h"void teststack()
{ST st;STInit(&st);STpush(&st, 1);STpush(&st, 2);STpush(&st, 3);STpush(&st, 4);STpush(&st, 5);printf("%d", STSize(&st));printf("\n");while (!STEmpty(&st)){printf("%d ", STTop(&st));STPop(&st);}printf("\n");printf("%d", STSize(&st));STDestroy(&st);}int main()
{teststack();return 0;
}

队列

Queue.h

#pragma once#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>typedef int QDataType;typedef struct QNode
{struct QNode* next;QDataType data;}QNode;typedef struct Queue
{QNode*head;QNode*tail;int szie;
}Queue;//单链表的实现，FIFO//初始化
void QueueInit(Queue* ps);
//销毁
void QueueDestroy(Queue* ps);
//入队
void QueuePush(Queue* ps, QDataType x);
//删除
void QueuePop(Queue* ps);
//大小
int QueueSize(Queue* ps);
//判空队
bool QueueEmpty(Queue* ps);
//出队头
QDataType QueueTop(Queue* ps);
//出队尾
QDataType QueueBack(Queue* ps);

Queue.c

#define _CRT_SECURE_NO_WARNINGS#include "queue.h"//初始化
void QueueInit(Queue* ps)
{assert(ps);ps->head = ps->tail = NULL;ps->szie = 0;}//销毁
void QueueDestroy(Queue* ps)
{assert(ps);QNode* cur = ps->head;while (cur){QNode* next = cur->next;free(cur);cur = next;}ps->head = ps->tail = NULL;ps->szie = 0;
}//入队
void QueuePush(Queue* ps,QDataType x)
{assert(ps);QNode* newcode = (QNode*)malloc(sizeof(QNode));if (newcode == NULL){perror("malloc fail");return ;}newcode->next = NULL;newcode->data = x;if (ps->head == NULL){ps->head = ps->tail = newcode;}else{ps->tail->next = newcode;ps->tail = newcode;}ps->szie++;}//删除
void QueuePop(Queue* ps)
{assert(ps);assert(ps->head != NULL);assert(!QueueEmpty(ps));if (ps->head->next == NULL){free(ps->head);ps->head = ps->tail = NULL;}else{QNode* next = ps->head->next;free(ps->head);ps->head = next;}ps->szie--;
}//大小
int QueueSize(Queue* ps)
{assert(ps);return ps->szie;
}//判空队
bool QueueEmpty(Queue* ps)
{assert(ps);return ps->szie == 0;
}//出队头
QDataType QueueTop(Queue* ps)
{assert(ps);assert(!QueueEmpty(ps));return ps->head->data;
}//出队尾
QDataType QueueBack(Queue* ps)
{assert(ps);return ps->tail->data;
}

test.c

#define _CRT_SECURE_NO_WARNINGS#include "queue.h"void testQueue()
{Queue s;QueueInit(&s);QueuePush(&s, 1);QueuePush(&s, 2);QueuePush(&s, 3);QueuePush(&s, 4);//printf("%d ", QueueTop(&s));//QueuePop(&s);//printf("%d ", QueueTop(&s));//QueuePop(&s);	//printf("%d ", QueueTop(&s));//QueuePop(&s);	//printf("%d ", QueueTop(&s));//QueuePop(&s);//printf("\n");while (!(QueueEmpty(&s))){printf("%d ", QueueTop(&s));QueuePop(&s);}QueueDestroy(&s);}int main()
{testQueue();return 0;
}

相关文章：

  • width: 100%和 width: 100vw这两种写法有什么区别
  • 大模型参加高考，同写2024年高考作文，及格分（通义千问、Kimi、智谱清言、Gemini Advanced、Claude-3-Sonnet、GPT-4o）
  • 2024年安全现状报告
  • 【Postman接口测试】第四节.Postman接口测试项目实战（中）
  • Vue项目安装axios报错npm error code ERESOLVE npm error ERESOLVE could not resolve解决方法
  • selenium中，如何使用选择框
  • stack和queue的模拟实现
  • 代码随想录算法训练营第二十二天
  • VCS基本仿真
  • 线性代数|机器学习-P9向量和矩阵范数
  • 目标检测数据集 - 智能零售柜商品检测数据集下载「包含VOC、COCO、YOLO三种格式」
  • MacOS M系列芯片一键配置多个不同版本的JDK
  • SpringBoot+Vue幼儿园管理系统（前后端分离）
  • tomcat-valve通过servlet处理请求
  • HTTPS和TCP
  • 【RocksDB】TransactionDB源码分析
  • 10个最佳ES6特性 ES7与ES8的特性
  • Git的一些常用操作
  • HTML5新特性总结
  • JDK9: 集成 Jshell 和 Maven 项目.
  • js写一个简单的选项卡
  • Markdown 语法简单说明
  • Python 反序列化安全问题（二）
  • Python 基础起步 (十) 什么叫函数？
  • Tornado学习笔记（1）
  • ------- 计算机网络基础
  • 将回调地狱按在地上摩擦的Promise
  • 开年巨制！千人千面回放技术让你“看到”Flutter用户侧问题
  • 如何胜任知名企业的商业数据分析师？
  • 入口文件开始，分析Vue源码实现
  • #gStore-weekly | gStore最新版本1.0之三角形计数函数的使用
  • （Oracle）SQL优化基础（三）：看懂执行计划顺序
  • (vue)el-cascader级联选择器按勾选的顺序传值,摆脱层级约束
  • （第9篇）大数据的的超级应用——数据挖掘-推荐系统
  • （二）Kafka离线安装 - Zookeeper下载及安装
  • （附源码）python旅游推荐系统 毕业设计 250623
  • (转)Mysql的优化设置
  • (自适应手机端)响应式新闻博客知识类pbootcms网站模板 自媒体运营博客网站源码下载
  • *算法训练（leetcode）第四十五天 | 101. 孤岛的总面积、102. 沉没孤岛、103. 水流问题、104. 建造最大岛屿
  • .Net 6.0--通用帮助类--FileHelper
  • .Net Attribute详解(上)-Attribute本质以及一个简单示例
  • .net framework profiles /.net framework 配置
  • .net 获取url的方法
  • .NET（C#、VB）APP开发——Smobiler平台控件介绍：Bluetooth组件
  • .NetCore部署微服务（二）
  • .NET程序集编辑器/调试器 dnSpy 使用介绍
  • .Net接口调试与案例
  • .NET中的十进制浮点类型,徐汇区网站设计
  • /etc/fstab和/etc/mtab的区别
  • @angular/cli项目构建--Dynamic.Form
  • [ IO.File ] FileSystemWatcher
  • [ vulhub漏洞复现篇 ] JBOSS AS 4.x以下反序列化远程代码执行漏洞CVE-2017-7504
  • [ vulhub漏洞复现篇 ] Jetty WEB-INF 文件读取复现CVE-2021-34429
  • [2019.2.28]BZOJ4033 [HAOI2015]树上染色
  • [4.9福建四校联考]