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

数据结构（学习）2024.8.8（栈，队列）

news 来源：原创 2024/9/20 7:57:43

今天学习的是线性表里面的栈和队列

链表的相关知识可以查看http://t.csdnimg.cn/NX464

顺序表的相关知识可以查看http://t.csdnimg.cn/5IMAZ

目录

栈

栈的定义

栈的特点

顺序栈

结构体

顺序栈的相关操作案例

链式栈

结构体

链式栈的相关操作案例

总结

队列

队列的定义

队列的特点

顺序队列(又称为循环队列)

结构体

顺序队列的相关操作案例

链式队列 

结构体

链式队列的相关操作案例

栈

栈的定义

        只能在一端进行插入和删除操作的线性表（又称为堆栈），进行插入和删除操作的一端称为栈顶，另一端称为栈底。

栈的特点

先进后出 FILO first in last out   LIFO

顺序栈

1.逻辑结构：线性结构
2.存储结构：顺序存储
3.操作：入栈、出栈

结构体

typedef struct seqstack
{
    int *data;  // 指向栈的存储位置
    int maxlen; // 保存栈的最大长度
    int top;    // 称为栈针，用的时候，心里面可以将按照顺序表里的last来使用， top 始终代表当前栈内最后一个有效元素的下标
} seqstack_t;

顺序栈的相关操作案例

头文件seqstack.h:

#ifndef _SEQSTACK_H_
#define _SEQSTACK_H_
#include <stdio.h>
#include <stdlib.h>
typedef struct seqstack
{int *data;  // 指向栈的存储位置int maxlen; // 保存栈的最大长度int top;    // 称为栈针，用的时候，心里面可以将按照顺序表里的last来使用// top 始终代表当前栈内最后一个有效元素的下标
} seqstack_t;
// 1.创建一个空的栈
seqstack_t *CreateEpSeqStack(int len); // len代表的是创建栈的时候的最大长度
// 2.判断是否为满,满返回1 未满返回0
int IsFullSeqStack(seqstack_t *p);
// 3.入栈
int PushStack(seqstack_t *p, int data); // data代表入栈的数据
// 4.判断栈是否为空
int IsEpSeqStack(seqstack_t *p);
// 5.出栈
int PopSeqStack(seqstack_t *p);
// 6. 清空栈
void ClearSeqStack(seqstack_t *p);
// 7. 获取栈顶数据(注意不是出栈操作，如果出栈，相当于删除了栈顶数据，只是将栈顶的数据获取到，不需要移动栈针)
int GetTopSeqStack(seqstack_t *p);
// 8. 求栈的长度
int LengthSeqStack(seqstack_t *p);
#endif

顺序栈函数seqstack.c:

#include "seqstack.h"// 1.创建一个空的栈
seqstack_t *CreateEpSeqStack(int len) // len代表的是创建栈的时候的最大长度
{// 1.开辟一个结构体类型大小的空间seqstack_t *p = (seqstack_t *)malloc(sizeof(seqstack_t));if (p == NULL){perror("CreateEpSeqStack函数创建结构体失败");return NULL;}// 2.初始化p->top = -1;p->maxlen = len;p->data = (int *)malloc(len * sizeof(int));if (p->data == NULL){perror("CreateEpSeqStack函数创建数据空间失败");free(p);p = NULL;return NULL;}return p;
}// 2.判断是否为满,满返回1 未满返回0
int IsFullSeqStack(seqstack_t *p)
{return p->top == p->maxlen - 1;
}// 3.入栈
int PushStack(seqstack_t *p, int data) // data代表入栈的数据
{// 1.容错判断(判满)if (IsFullSeqStack(p)){perror("PushStack函数出错\n");return -1;}// 2.移动指针p->top++;// 3.入栈p->data[p->top] = data;return 0;
}// 4.判断栈是否为空
int IsEpSeqStack(seqstack_t *p)
{return p->top == -1;
}// 5.出栈
int PopSeqStack(seqstack_t *p)
{// 1.容错判断(判空)if (IsEpSeqStack(p)){perror("PopSeqStack函数出错\n");return -1;}// 2.移动指针p->top--;// 3.出栈数据return p->data[p->top + 1];
}// 6. 清空栈
void ClearSeqStack(seqstack_t *p)
{p->top = -1;
}// 7. 获取栈顶数据(注意不是出栈操作，如果出栈，相当于删除了栈顶数据，只是将栈顶的数据获取到，不需要移动栈针)
int GetTopSeqStack(seqstack_t *p)
{while (!IsEpSeqStack(p)){return p->data[p->top];}return -1;
}// 8. 求栈的长度
int LengthSeqStack(seqstack_t *p)
{return p->top + 1;
}

主函数main.c:

#include "seqstack.h"int main(int argc, char const *argv[])
{int data;seqstack_t *p = CreateEpSeqStack(5);PushStack(p, 1);PushStack(p, 2);PushStack(p, 3);printf("目前栈里的数据为：\n");for (int i = 0; i < LengthSeqStack(p); i++){printf("%d ", GetTopSeqStack(p));}printf("\n");printf("请输入你要插入的数据：\n");scanf("%d", &data);PushStack(p, data);printf("出栈操作：\n");while (!IsEpSeqStack(p)){printf("出栈的数据为：%d ", PopSeqStack(p));}printf("\n");free(p->data);p->data = NULL;free(p);p = NULL;return 0;
}

链式栈

1.逻辑结构：线性结构
2.存储结构：链式存储
3.操作：入栈、出栈

结构体

typedef struct linkstack
{
    datatype data;          // 数据域
    struct linkstack *next; // 指针域
} linkstack_t;

链式栈的相关操作案例

头文件linkstack.h:

#ifndef _LINKSTACK_H_
#define _LINKSTACK_H_
#include <stdio.h>
#include <stdlib.h>
// 入栈和出栈只在第一个节点位置操作
typedef int datatype;
typedef struct linkstack
{datatype data;          // 数据域struct linkstack *next; // 指针域
} linkstack_t;// 1.创建一个空的栈
void CreateEpLinkStack(linkstack_t **ptop);
// 2.入栈   data是入栈的数据
// 参数上之所以采用二级指针，因为我们要随着入栈添加新的节点作为头，top需要永远指向当前链表的头，
// 那么修改main函数中的top，我们采用地址传递
int PushLinkStack(linkstack_t **ptop, datatype data);
// 3.判断栈是否为空
int IsEpLinkStack(linkstack_t *top);
// 4.出栈
datatype PopLinkStack(linkstack_t **ptop);
// 5.清空栈
void ClearLinkStack(linkstack_t **ptop); // 用二级指针，是因为清空后需要将main函数中的top变为NULL
// 6.求栈的长度
int LengthLinkStack(linkstack_t *top); // 用一级指针，是因为我只是求长度，不需要修改main函数中top指针的指向
// 7.获取栈顶数据,不是出栈,不需要移动main函数中的top，所以用一级指针
datatype GetTopLinkStack(linkstack_t *top);
#endif

链式栈函数linkstack.c:

#include "linkstack.h"// 1.创建一个空的栈
void CreateEpLinkStack(linkstack_t **ptop)
{*ptop = NULL;
}// 2.入栈
// data是入栈的数据
// 参数上之所以采用二级指针，因为我们要随着入栈添加新的节点作为头，top需要永远指向当前链表的头，那么修改main函数中的top，我们采用地址传递
int PushLinkStack(linkstack_t **ptop, datatype data)
{// 1.创建一个新节点，并初始化linkstack_t *pnew = (linkstack_t *)malloc(sizeof(linkstack_t));if (pnew == NULL){perror("PushLinkStack函数出错\n");return -1;}pnew->data = data;pnew->next = NULL;// 2.将新节点插到无头单向链表中pnew->next = *ptop;// 3.移动栈针，栈针永远指向无头单向链表的第一个节点*ptop = pnew;return 0;
}// 3.判断栈是否为空
int IsEpLinkStack(linkstack_t *top)
{return top == NULL;
}// 4.出栈     *ptop-->top
datatype PopLinkStack(linkstack_t **ptop)
{// 1.容错判断(判空)if (IsEpLinkStack(*ptop)){perror("PopLinkStack函数出错\n");return -1;}// 2.定义pdel指向被删除节点linkstack_t *pdel = *ptop;// 3.定义一个变量temp保存出栈数据datatype temp = pdel->data; // datatype temp = (*ptop)->data;// 4.移动指针*ptop = pdel->next; // *ptop = (*ptop)->next;// 5.释放被删除节点free(pdel);pdel = NULL;return temp;
}// 5.清空栈
void ClearLinkStack(linkstack_t **ptop) // 用二级指针，是因为清空后需要将main函数中的top变为NULL
{while (!(IsEpLinkStack(*ptop))){PopLinkStack(ptop);}
}// 6.求栈的长度
int LengthLinkStack(linkstack_t *top) // 用一级指针，是因为只是求长度，不需要修改main函数中top指针的指向
{int len = 0;while (top != NULL){top = top->next;len++;}return len;
}// 7.获取栈顶数据,不是出栈,不需要移动main函数中的top，所以用一级指针
datatype GetTopLinkStack(linkstack_t *top)
{if (IsEpLinkStack(top)){perror("GetTopLinkStack函数出错\n");return -1;}return top->data;
}

主函数main.c:

#include "linkstack.h"int main(int argc, char const *argv[])
{linkstack_t *p = NULL;for (int i = 1; i <= 5; i++){PushLinkStack(&p, i);}printf("栈的长度为：%d\n", LengthLinkStack(p));while (!(IsEpLinkStack(p))){printf("%d ", PopLinkStack(&p));}printf("\n");ClearLinkStack(&p);return 0;
}

总结

顺序栈和链式栈的区别

(1)存储结构不同，顺序栈相当于数组，连续的，链式栈 链表非连续的 
(2)顺序栈的长度受限制，而链栈不会

队列

顺序队列(循环队列) 和 链式队列 

队列的定义

只允许在两端进行插入和删除操作的线性表，在队尾插入，在队头删除 插入的一端，被称为"队尾"，删除的一端被称为"队头"。

在队列操作过程中，为了提高效率，以调整指针代替队列元素的移动，并将数组作为循环队列的操作空间。

队列的特点

先进先出 FIFO  first in first out

后进后出 LILO  last

顺序队列(又称为循环队列)

1.逻辑结构: 线性结构

2.存储结构：顺序存储结构

3.操作：入列，出列

结构体

 #define N 5

typedef int datatype;

typedef struct

{

datatype data[N];

int rear;  //存数据端  rear 后面

int front; //取数据端  front 前面

}sequeue_t;//sequence 顺序  queue队列

 注意：

循环队列中，假设数组的元素个数为N，那么循环队列中存储最多的数据个数为N-1个

原因：舍去数组上的一个存储位置,用于判断队列是否为满

顺序队列的相关操作案例

头文件sequeue.h:

#ifndef _SEQUEUE_H_
#define _SEQUEUE_H_
#include <stdio.h>
#include <stdlib.h>
#define N 5
typedef int datatype;
typedef struct
{datatype data[N]; // 循环队列的数组int rear;         // 存数据端 rear 后面int front;        // 取数据端 front 前面
} sequeue_t;
// 1.创建一个空的队列
sequeue_t *CreateEmptySequeue();
// 2.入列 data代表入列的数据
int InSequeue(sequeue_t *p, datatype data);
// 3.判断队列是否为满
int IsFullSequeue(sequeue_t *p);
// 4.判断队列是否为空
int IsEmptySequeue(sequeue_t *p);
// 5.出列
datatype OutSequeue(sequeue_t *p);
// 6.求队列的长度
int LengthSequeue(sequeue_t *p);
// 7.清空队列函数
void ClearSequeue(sequeue_t *p);
#endif

顺序队列函数sequeue.c:

#include "sequeue.h"
// 1.创建一个空的队列
sequeue_t *CreateEmptySequeue()
{// 1.开辟一个结构体大小的空间sequeue_t *p = (sequeue_t *)malloc(sizeof(sequeue_t));if (p == NULL){perror("CreateEmptySequeue函数报错\n");return NULL;}// 2.初始化p->rear = p->front = 0;return p;
}// 2.入列 data代表入列的数据
int InSequeue(sequeue_t *p, datatype data)
{// 1.判满if (IsFullSequeue(p)){perror("InSequeue函数出错\n");return -1;}// 2.将数据入列p->data[p->rear] = data;p->rear = (p->rear + 1) % N;return 0;
}// 3.判断队列是否为满
int IsFullSequeue(sequeue_t *p)
{return (p->rear + 1) % N == p->front;
}// 4.判断队列是否为空
int IsEmptySequeue(sequeue_t *p)
{return p->rear == p->front;
}// 5.出列
datatype OutSequeue(sequeue_t *p)
{// 1.判空if (IsEmptySequeue(p)){perror("OutSequeue函数出错\n");return -1;}// 2.出列// 取出数据datatype temp = p->data[p->front];// 移动头指针p->front = (p->front + 1) % N;return temp;
}
// 6.求队列的长度
int LengthSequeue(sequeue_t *p)
{// // 1.方法一// if (p->rear >= p->front)// {//     return p->rear - p->front;// }// else// {//     return p->rear - p->front + N;// }// 2.方法二return (p->rear - p->front + N) % N;
}
// 7.清空队列函数
void ClearSequeue(sequeue_t *p)
{p->front = p->rear;
}

主函数main.c:

#include "sequeue.h"int main(int argc, char const *argv[])
{sequeue_t *p = CreateEmptySequeue();for (int i = 0; i < 4; i++){InSequeue(p, i);}printf("顺序队列的长度为：%d\n", LengthSequeue(p));OutSequeue(p);OutSequeue(p);OutSequeue(p);InSequeue(p, 10);printf("顺序队列的长度为：%d\n", LengthSequeue(p));while (!IsEmptySequeue(p)){printf("%d ", OutSequeue(p));}printf("\n");printf("清空顺序队列\n");ClearSequeue(p);free(p);p = NULL;return 0;
}

链式队列 

1.逻辑结构: 线性结构

2.存储结构：链式存储

3.操作：入列 、出列

结构体

typedef struct node

{

datatype data;//数据域

struct node *next;//指针域

}linkqueue_node_t,*linkqueue_list_t;

typedef struct//将队列头指针和尾指针封装到一个结构体里

{

linkqueue_list_t front;//相当于队列的头指针

linkqueue_list_t rear;//相当于队列的尾指针

//有了链表的头指针和尾指针，那么我们就可以操作这个链表

}linkqueue_t; 

链式队列的相关操作案例

头文件linkqueue.h:

#ifndef _LINKQUEUE_H_
#define _LINKQUEUQ_H_#include <stdio.h>
#include <stdlib.h>
typedef int datatype;
typedef struct node
{datatype data;     // 数据域struct node *next; // 指针域
} linkqueue_node_t, *linkqueue_list_t;// linkqueue_list_t p === linkqueue_node_t *
typedef struct // 将队列头指针和尾指针封装到一个结构体里
{linkqueue_list_t front; // 相当于队列的头指针linkqueue_list_t rear;  // 相当于队列的尾指针// 有了链表的头指针和尾指针，那么我们就可以操作这个链表
} linkqueue_t;
// 1.创建一个空的队列
linkqueue_t *CreateEmptyLinkQueue();
// 2.入列 data代表入列的数据
int InLinkQueue(linkqueue_t *p, datatype data);
// 3.出列
datatype OutLinkQueue(linkqueue_t *p);
// 4.判断队列是否为空
int IsEmptyLinkQueue(linkqueue_t *p);
// 5.求队列长度的函数
int LengthLinkQueue(linkqueue_t *p);
// 6.清空队列
void ClearLinkQueue(linkqueue_t *p);
#endif

链式队列函数linkqueue.c:

#include "linkqueue.h"
// 1.创建一个空的队列
linkqueue_t *CreateEmptyLinkQueue()
{// 1.创建存放头尾指针的空间linkqueue_t *p = (linkqueue_t *)malloc(sizeof(linkqueue_t));if (p == NULL){perror("CreateEmptyLinkQueue函数创建存放头尾指针的空间出错\n");return NULL;}// 2.初始化p->front = p->rear = (linkqueue_list_t)malloc(sizeof(linkqueue_node_t));if (p->front == NULL){perror("CreateEmptyLinkQueue函数创建链表结构体的空间出错\n");return NULL;}p->front->next = NULL;return p;
}// 2.入列 data代表入列的数据
int InLinkQueue(linkqueue_t *p, datatype data)
{// 1.开辟一个节点并初始化存放数据linkqueue_list_t pnew = (linkqueue_list_t)malloc(sizeof(linkqueue_node_t));if (pnew == NULL){perror("InLinkQueue函数出错\n");return -1;}pnew->next = NULL;pnew->data = data;// 2.数据入队p->rear->next = pnew;// 3.移动尾指针p->rear = pnew;return 0;
}// 3.出列
datatype OutLinkQueue(linkqueue_t *p)
{// 1.判空if (IsEmptyLinkQueue(p)){perror("OutLinkQueue函数出错\n");return -1;}// 2.出列数据// (1)定义pdel指向头节点linkqueue_list_t pdel = p->front;// (2)移动头指针p->front = p->front->next;// (3)释放头节点free(pdel);pdel = NULL;// (4)出队数据return p->front->data;
}// 4.判断队列是否为空
int IsEmptyLinkQueue(linkqueue_t *p)
{return p->rear == p->front;
}// 5.求队列长度的函数
int LengthLinkQueue(linkqueue_t *p)
{int len = 0;linkqueue_list_t q = p->front;while (q->next!= NULL){q = q->next;len++;}return len;
}// 6.清空队列
void ClearLinkQueue(linkqueue_t *p)
{while (!IsEmptyLinkQueue(p)){OutLinkQueue(p);}
}

主函数main.c：

#include "linkqueue.h"int main(int argc, char const *argv[])
{linkqueue_t *p = CreateEmptyLinkQueue();InLinkQueue(p, 1);InLinkQueue(p, 2);InLinkQueue(p, 3);printf("链式队列的长度为：%d\n", LengthLinkQueue(p));printf("%d ", OutLinkQueue(p));printf("%d ", OutLinkQueue(p));printf("%d ", OutLinkQueue(p));printf("\n");printf("清空链式队列\n");ClearLinkQueue(p);free(p->front);p->front = NULL;free(p);p = NULL;return 0;
}

相关文章：

  • 北京网站建设多少钱？
  • 辽宁网页制作哪家好_网站建设
  • 高端品牌网站建设_汉中网站制作
  • 【物联网】（防水篇）电子产品如何做到IPX7级别的防水？
  • 【C++ 面试 - 基础题】每日 3 题（十三）
  • 趋动科技联合超聚变，让超融合彻底释放算力潜能
  • 单例模式（懒汉模式，饿汉模式）
  • PostgreSQL 触发器
  • uniapp h5本地预览pdf教程 （含白屏|跨域解决方案）
  • C++ primer plus 第17 章 输入、输出和文件：文件输入和输出03:文件模式:二进制文件
  • 图解大顶堆的构建、排序过程
  • 猫头虎 分享已解决Bug || 504 Gateway Timeout 解决方案
  • 手绘图系列 06 | 您一上Google就能接触到的Tries
  • FPGA设计之跨时钟域（CDC）设计篇（5）----同步FIFO的两种设计方法（计数器法/高位扩展法 | 手撕代码）
  • ArcGIS Pro 3.1学习之旅 ----day01 Arcgis pro安装
  • 苍穹外卖day12（day15）---数据统计——Excel报表（项目完结）
  • 使用FFmpeg实现摄像头RTMP实时推流
  • clickhouse安装部署问题求大佬看看
  • 2019年如何成为全栈工程师？
  • Brief introduction of how to 'Call, Apply and Bind'
  • canvas实际项目操作，包含：线条，圆形，扇形，图片绘制，图片圆角遮罩，矩形，弧形文字...
  • CSS实用技巧
  • HTTP那些事
  • JavaScript学习总结——原型
  • Less 日常用法
  • python学习笔记－类对象的信息
  • React的组件模式
  • 二维平面内的碰撞检测【一】
  • 码农张的Bug人生 - 见面之礼
  • 如何解决微信端直接跳WAP端
  • 一道面试题引发的“血案”
  • HanLP分词命名实体提取详解
  • 没有任何编程基础可以直接学习python语言吗？学会后能够做什么？ ...
  • ​Spring Boot 分片上传文件
  • # 利刃出鞘_Tomcat 核心原理解析（二）
  • ## 基础知识
  • #stm32驱动外设模块总结w5500模块
  • #window11设置系统变量#
  • #数学建模# 线性规划问题的Matlab求解
  • （2）nginx 安装、启停
  • （3）(3.2) MAVLink2数据包签名(安全)
  • （C#）if (this == null)？你在逗我，this 怎么可能为 null！用 IL 编译和反编译看穿一切
  • (vue)el-tabs选中最后一项后更新数据后无法展开
  • (ZT)薛涌：谈贫说富
  • （黑马出品_高级篇_01）SpringCloud+RabbitMQ+Docker+Redis+搜索+分布式
  • （简单有案例）前端实现主题切换、动态换肤的两种简单方式
  • （论文阅读笔记）Network planning with deep reinforcement learning
  • (欧拉)openEuler系统添加网卡文件配置流程、(欧拉)openEuler系统手动配置ipv6地址流程、(欧拉)openEuler系统网络管理说明
  • (算法)大数的进制转换
  • (未解决)jmeter报错之“请在微信客户端打开链接”
  • （一）硬件制作--从零开始自制linux掌上电脑（F1C200S) ＜嵌入式项目＞
  • （转）winform之ListView
  • (转)视频码率,帧率和分辨率的联系与区别
  • .java 指数平滑_转载：二次指数平滑法求预测值的Java代码
  • .NET 5.0正式发布，有什么功能特性(翻译)
  • .NET Core 控制台程序读 appsettings.json 、注依赖、配日志、设 IOptions
  • .NET国产化改造探索（一）、VMware安装银河麒麟
  • .net与java建立WebService再互相调用