数据结构——栈和队列（C语言实现）

写在前面：

        栈和队列是两种重要的线性结构。其也属于线性表，只是操作受限，本节主要讨论的是栈和队列的定义、表示方法以及C语言实现。

一、栈和队列的定义与特点

栈：是限定仅在表尾进行插入和删除的线性表。对栈来说，表尾有着特殊的含义，称为栈顶，表头称为栈底，不含元素的空表称为空栈；

栈的特点就是：按后进先出的原则进行的，栈又称为后进先出的线性表；

      与栈相反的是队列，队列是一种先进先出的特点。它只允许在标的一段进行插入，在另一端进行删除。允许插入的一段称为队尾，允许删除的一段称为队头。

二、栈

2.1顺序栈

        顺序栈是指利用顺序存储结构实现的栈，即利用一组地址连续的存储单元依次存放在自栈底到栈顶的数据元素。

        设指针top指向栈顶元素在顺序表中的位置，base指针指向栈底元素在顺序栈中的位置。

2.1.1初始化

typedef struct Node
{int *base;int *top;int stacksize;
}Node;
//初始化栈
void  InitStack(Node *S)
{S->base = (int *)malloc(sizeof(int)*MAXSIZE);S->top = S->base ;
}

初始化，创建一个结构体类型，其中变量为栈顶指针、栈底指针，以及栈的最大空间；

使栈顶和栈底都指向空间的基地址；

2.1.2入栈

int PushStack(Node* S,int data)
{if (S->top - S->base == MAXSIZE){return -1;}	else{*(S->top) = data;(S->top)++;}
}

判断栈是否满，不满将新元素压入栈顶，栈顶指针+1； 

2.1.3出栈

int PopStack(Node * S)
{if (S->top == S->base)return -1;else{(S->top)--;int i = *(S->top);return i;}
}

判断栈顶是否为空，若不为空，栈顶指针减1，栈顶元素出栈； 

2.1.4 打印

void PrintStack(Node S)
{int len = (S.top-S.base);for (int i = 0; i < len; i++){(S.top)--;printf("%d->", *(S.top));}printf("NULL\n");
}

先计算栈的空间长度，再依次从栈顶打印除栈的元素； 

2.1.5案例 

#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE  5typedef struct Node
{int *base;int *top;int stacksize;
}Node;
//初始化栈
void  InitStack(Node *S)
{S->base = (int *)malloc(sizeof(int)*MAXSIZE);S->top = S->base ;
}
//入栈//判断栈是否满了
int PushStack(Node* S,int data)
{if (S->top - S->base == MAXSIZE){return -1;}else{*(S->top) = data;(S->top)++;}
}
//出栈//判断栈是否为空
int PopStack(Node * S)
{if (S->top == S->base)return -1;else{(S->top)--;int i = *(S->top);return i;}
}
//打印
void PrintStack(Node S)
{int len = (S.top-S.base);for (int i = 0; i < len; i++){(S.top)--;printf("%d->", *(S.top));}printf("NULL\n");
}int  main()
{Node S;InitStack(&S);PushStack(&S, 1);PrintStack(S);PushStack(&S, 2);PrintStack(S);PushStack(&S, 3);PrintStack(S);PushStack(&S, 4);PrintStack(S);PushStack(&S, 5);PrintStack(S);int i = PopStack(&S);printf("delete:%d\n",i);i = PopStack(&S);printf("delete:%d\n", i);PrintStack(S);return 0;
}

运行结果： 

2.2链栈 

链栈是指采用链式存储结构实现的栈，通常采用单链表实现；

2.2.1初始化 

//新建结点
typedef struct Node
{int data;struct Node* next;
}Node;
//初始化
Node * StackIint()
{Node * head = (Node *)malloc(sizeof(Node));head->data=0;head->next = NULL;return head;
}

 初始化，首先创建一个结构体代表一个节点，然后创建一个空栈，即只有头结点的链表。

 2.2.2入栈

void push(Node * node,int data)
{Node * S = (Node *)malloc(sizeof(Node));S->data = data;S->next = node->next;node->next = S;node->data++;	
}

和链表的头插法一样，为入栈元素动态分配一个结点空间； 

2.2.3出栈

//判断是否为栈空
int isEmpty(Node * node)
{if (node->data == 0 || node->next == NULL)return 1;elsereturn 0;
}
//出栈
int pop(Node * node)
{if (isEmpty(node))return -1;else{Node *S = node->next;int i = S->data;node->next = S->next;free(S);node->data--;return i;}
}

        出栈，出栈前需要判断其栈是否为空，如果为空就无法进行出栈。出栈时需要把栈顶元素进行输出，并且释放栈顶空间。

2.2.4取栈顶元素

//判断是否为栈空
int isEmpty(Node * node)
{if (node->data == 0 || node->next == NULL)return 1;elsereturn 0;
}
//获取栈元素
int getvalue(Node * node)
{if (isEmpty(node)){return -1;}else{return(node->next->data);}
}

与出栈一样，需要判断栈是否为空，如果不为空，则输出栈顶元素；

2.2.5案例

#include <stdio.h>
#include <stdlib.h>typedef struct Node
{int data;struct Node* next;
}Node;//初始化
Node * StackIint()
{Node * head = (Node *)malloc(sizeof(Node));head->data=0;head->next = NULL;return head;
}//判断是否为栈空
int isEmpty(Node * node)
{if (node->data == 0 || node->next == NULL)return 1;elsereturn 0;
}
//获取栈元素int getvalue(Node * node)
{if (isEmpty(node)){return -1;}else{return(node->next->data);}
}//出栈
int pop(Node * node)
{if (isEmpty(node))return -1;else{Node *S = node->next;int i = S->data;node->next = S->next;free(S);node->data--;return i;}
}//入栈
void push(Node * node,int data)
{Node * S = (Node *)malloc(sizeof(Node));S->data = data;S->next = node->next;node->next = S;node->data++;	
}
void printStack(Node * node)
{Node * S = node->next;while (S){printf("%d->", S->data);S = S->next;}printf("NULL\n");
}
int main()
{Node * S = StackIint();push(S, 1);push(S, 2);push(S, 3);push(S, 4);printStack(S);int i=pop(S);printf(" top data:%d\n", i);printStack(S);return 0;
}

运行结果：

三、队列

        有与栈结构相同，队列也有两种存储表示，顺序表示与链式表示；

3.1顺序队列（循环队列）

        在顺序队列中。除了设置一组地址连续的存储空间依次存放元素外，另外需要两个正向变量，分别指示队列头元素和队列尾元素的位置。

        在初始化空队列时，令front=rear=0;每当插入新的队列尾元素时，尾指针rear增1；每当删除队列头元素时，头指针front增1；在非空队列中，头指针始终指向队列头元素，而尾指针始终指向尾元素的下一个位置。但是这种操作会使得队列的指针最终越界处理，围殴了限制这种越界处理，我们提出循环队列的形式；

        循环队列的头尾以及队列元素之间的关系不变，只是在循环队列中，头指针、尾指针，依次环状增1的操作可以取模进行运算。通过取模运算，头指针和尾指针可以在顺序变种以头尾衔接的方式“循环”移动；

        对于循环队列 种，不能以头指针、尾指针的值是否相等来判断，队列的空间是“满”还是“空”，采取的方式是：

        少用一个元素空间，即队列空间为m时，有m-1个元素就认为时队满，这样设置的意义在于：当头尾指针相等时，队列为空，当尾指针加1等于头指针时，则认为队列满；

队空条件：front==rear;

队满条件：（rear+1）%MAXQSIZE==front;

3.1.1初始化

//新建一个结构体
typedef struct Queue
{int front;int rear;int data[MAXSIZE];
}Queue;
//1、初始化队列
Queue * initQueue()
{Queue * Q = (Queue *)malloc(sizeof(Queue));Q->front = Q->rear = 0;return Q;
}

创建一个结构体类型，结构体类型中有三个元素：数据数组、头指针地址、尾指针地址。然后初始化创建一个空队列；

3.1.2入队

//判断是否队满
int isFULL(Queue * Q)
{if ((Q->rear +1) % MAXSIZE == Q->front){return 1;}else{return 0;}
}//入队
int  enQueue(Queue * Q, int data)
{if (isFULL(Q)){return -1;}else{Q->data[Q->rear] = data;Q->rear = (Q->rear + 1) % MAXSIZE;return 1;}
}

首先判断队列是否满，如果没满进行入队，并且操作的都是尾指针； 

3.1.3出队

int isNULL(Queue * Q)
{if (Q->rear == Q->front){return 1;}else{return 0;}
}int deQueue(Queue * Q)
{if (isNULL(Q)){return -1;}else{int e = Q->data[Q->front];Q->front = (Q->front + 1) % MAXSIZE;return e;}
}

首先判断是否队列为空，如果没有为空，就从队头出队，操作的都是队头指针；

3.1.4打印队列

void printfQueue(Queue * Q)
{//要知道队列当前有多少个元素int len = (MAXSIZE + Q->rear - Q->front) % MAXSIZE;int index = Q->front;for (int i =0; i <len; i++){printf("%d->", Q->data[index]);index = (index + 1) % MAXSIZE;}printf("NULL\n");
}

进行队列元素的遍历，然后依次进行打印； 

3.1.5案例 

#include <stdio.h>
#include <stdlib.h>#define MAXSIZE 6
//新建一个结构体
typedef struct Queue
{int front;int rear;int data[MAXSIZE];
}Queue;
//1、初始化队列
Queue * initQueue()
{Queue * Q = (Queue *)malloc(sizeof(Queue));Q->front = Q->rear = 0;return Q;
}int isFULL(Queue * Q)
{if ((Q->rear +1) % MAXSIZE == Q->front){return 1;}else{return 0;}
}
//2、入队
int  enQueue(Queue * Q, int data)
{if (isFULL(Q)){return -1;}else{Q->data[Q->rear] = data;Q->rear = (Q->rear + 1) % MAXSIZE;return 1;}
}
//3、出队
int isNULL(Queue * Q)
{if (Q->rear == Q->front){return 1;}else{return 0;}
}int deQueue(Queue * Q)
{if (isNULL(Q)){return -1;}else{int e = Q->data[Q->front];Q->front = (Q->front + 1) % MAXSIZE;return e;}
}
//4、打印队列
void printfQueue(Queue * Q)
{//要知道队列当前有多少个元素int len = (MAXSIZE + Q->rear - Q->front) % MAXSIZE;int index = Q->front;for (int i =0; i <len; i++){printf("%d->", Q->data[index]);index = (index + 1) % MAXSIZE;}printf("NULL\n");
}
int main()
{Queue * Q = initQueue();enQueue(Q, 1);printfQueue(Q);enQueue(Q, 2);printfQueue(Q);enQueue(Q, 3);printfQueue(Q);enQueue(Q, 4);printfQueue(Q);int i = deQueue(Q);printf(" delete	Queue:%d\n",i);printfQueue(Q);i = deQueue(Q);printf(" delete	Queue:%d\n",i);printfQueue(Q);return 0;
}

 运行结果：

3.2链队

3.2.1初始化

//定义结构体类型
typedef struct Node
{int data;struct Node* next;
}Node;
//初始化
Node * QueueInit()
{Node * head = (Node *)malloc(sizeof(Node));head->data = 0;head->next = NULL;return head;
}

与栈操作相同，先创建一个结构类型，再创建一个空的队列，只含有一个头结点的队列。 

3.2.2入队

//入队
void Queueen(Node *Q,int data)
{Node * node = (Node *)malloc(sizeof(Node));node->data = data;Node * q = Q;while (q->next != NULL){q = q->next;}node->next = q->next;q->next = node;Q->data++;
}

入队操作和链表的尾插法是一样的，需要再队尾进行插入； 

3.2.3出队

//判断
int isEmpty(Node * Q)
{if (Q->data)return 1;elsereturn 0;
}
//出队
int dequeue(Node * Q)
{if (isEmpty(Q)){Node * node = Q->next;int i = node->data;Q->next = node->next;free(node);Q->data--;return i;}else{return -1;}
}

        出队，首先要判断队列是否为空，而且还有遵循先进先出的原则。 

3.2.4打印队列

//打印队列
void printQueue(Node * node)
{Node* p = node->next;while (p){printf("%d->", p->data);p = p->next;}printf("NULL\n");
}

遍历队列，然后打印，同链表操作基本一致； 

3.2.5案例

#include <stdio.h>
#include <stdlib.h>//定义结构体类型
typedef struct Node
{int data;struct Node* next;
}Node;
//初始化
Node * QueueInit()
{Node * head = (Node *)malloc(sizeof(Node));head->data = 0;head->next = NULL;return head;
}
//入队
void Queueen(Node *Q,int data)
{Node * node = (Node *)malloc(sizeof(Node));node->data = data;Node * q = Q;while (q->next != NULL){q = q->next;}node->next = q->next;q->next = node;Q->data++;
}
//判断
int isEmpty(Node * Q)
{if (Q->data)return 1;elsereturn 0;
}
//出队
int dequeue(Node * Q)
{if (isEmpty(Q)){Node * node = Q->next;int i = node->data;Q->next = node->next;free(node);Q->data--;return i;}else{return -1;}
}//打印队列
void printQueue(Node * node)
{Node* p = node->next;while (p){printf("%d->", p->data);p = p->next;}printf("NULL\n");
}int main()
{Node * Q = QueueInit();Queueen(Q, 1);printQueue(Q);Queueen(Q, 2);printQueue(Q);Queueen(Q, 3);printQueue(Q);Queueen(Q, 4);printQueue(Q);Queueen(Q, 5);printQueue(Q);int i = dequeue(Q);printf("delete queue:%d\n", i);printQueue(Q);return 0;
}

运行结果： 

四、总结

        本次主要介绍了两个特殊的线性表：栈和队列；

1、栈是限定仅在表尾进行插入或者删除的线性表，又称为后进先出的线性表。栈有两种存储结构表示方式，顺序表示（顺序栈）和链式表示（链栈）；栈的主要操作是入栈和出栈，注意入栈和出栈时需要分别判断栈满和栈空；

2、队列是一种先入先出的线性表，它只允许在表的一端进行插入，在另一端删除元素。队列也有两种存储表示，顺序表示（循环队列）和链式表示（链队）。队列主要的操作是进队和出队，对于顺序的循环队列的进队和出队需要注意判断队满或队空。凡是涉及到队头和队尾指针的都要对其进行求模；

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://xiahunao.cn/news/3246811.html

如若内容造成侵权/违法违规/事实不符，请联系瞎胡闹网进行投诉反馈，一经查实，立即删除！

相关文章

ABAP小白开发操作手册+（六）创建维护视图及事件

ABAP小白开发操作手册+（六）创建维护视图及事件

目录 开发类型&#xff1a; 开发申请&#xff1a; 开发步骤&#xff1a; 1、创建后台表 2、生成维护视图 3、隐藏自带字段 4、事件代码编写 5、配置事务代码 6、其它个性化需求 6.1、修改维护视图字段的可见长度 6.2、根据后台表查看对应维护视图的事务代码 代码如下…
阅读更多...
Modbus通讯接口选择分析

Modbus通讯接口选择分析

Modbus通讯接口选择分析 Modbus通讯接口的选择涉及到多个方面的考量&#xff0c;包括但不限于通讯距离、数据传输速率、成本、设备兼容性以及应用场景等。下面将从这些角度出发&#xff0c;对Modbus通讯接口的选择进行详细的分析。 Ip67防水面板法兰插座 通讯距离 Modbus通讯…
阅读更多...
卸载docker简单且ok的方法

卸载docker简单且ok的方法

杀死所有容器 docker kill $(docker ps -a -q) 删除所有容器 docker rm $(docker ps -a -q) 删除所有镜像 docker rmi $(docker images -q) 停止docker服务 systemctl stop docker 查看安装列表 yum list installed|grep docker 依次卸载已安装的docker yum -y remove docke…
阅读更多...
【iOS】——ARC源码探究

【iOS】——ARC源码探究

一、ARC介绍 ARC的全称Auto Reference Counting. 也就是自动引用计数。使用MRC时开发者不得不花大量的时间在内存管理上&#xff0c;并且容易出现内存泄漏或者release一个已被释放的对象&#xff0c;导致crash。后来&#xff0c;Apple引入了ARC。使用ARC&#xff0c;开发者不再…
阅读更多...
《昇思25天学习打卡营第25天|第10天》

《昇思25天学习打卡营第25天|第10天》

今天是打卡的第十天&#xff0c;今天开始学应用实践中的LLM原理和实践&#xff0c;今天学的是基于MindSpore实现BERT对话情绪识别。最先了解的是BERT模型的简介&#xff08;来自变换器的双向编码器表征量&#xff08;Bidirectional Encoder Representations from Transformers&…
阅读更多...
代码随想录算法训练营第22天 | 题目：回溯算法part01 理论基础、77. 组合 、 216.组合总和III 、 17.电话号码的字母组合

代码随想录算法训练营第22天 | 题目：回溯算法part01 理论基础、77. 组合 、 216.组合总和III 、 17.电话号码的字母组合

代码随想录算法训练营第22天 | 题目&#xff1a;回溯算法part01 理论基础、77. 组合 、 216.组合总和III 、 17.电话号码的字母组合 文章来源&#xff1a;代码随想录 理论基础&#xff1a;代码随想录&#xff1a;回溯算法 模板&#xff1a; void backtracking(参数) {if (终止…
阅读更多...
Spring MVC 的常用注解

Spring MVC 的常用注解

RequestMapping 和 RestController注解 上面两个注解&#xff0c;是Spring MCV最常用的注解。 RequestMapping &#xff0c; 他是用来注册接口的路由映射。 路由映射&#xff1a;当一个用户访问url时&#xff0c;将用户的请求对应到某个方法或类的过程叫做路由映射。 Reques…
阅读更多...
【Linux】将IDEA项目部署到云服务器上，让其成为后台进程(保姆级教学，满满的干货~~)

【Linux】将IDEA项目部署到云服务器上，让其成为后台进程(保姆级教学，满满的干货~~)

目录 部署项目到云服务器什么是部署一、 创建MySQL数据库二、 修改idea配置项三、 数据打包四、 部署云服务器五、开放端口号六 、 验证程序 部署项目到云服务器 什么是部署 ⼯作中涉及到的"环境" 开发环境:开发⼈员写代码⽤的机器.测试环境:测试⼈员测试程序使⽤…
阅读更多...
【HarmonyOS】HarmonyOS NEXT学习日记：二、ArkTs语法

【HarmonyOS】HarmonyOS NEXT学习日记：二、ArkTs语法

【HarmonyOS】HarmonyOS NEXT学习日记&#xff1a;二、ArkTs语法 众所周知TS是JS的超集,而ArkTs则可以理解为是Ts的超集。他们的基础都基于JS&#xff0c;所以学习之前最好就JS基础。我的学习重点也是放在ArkTs和JS的不同点上。 文章主要跟着官方文档学习&#xff0c;跳过了一…
阅读更多...
21天学通C++：第十三、十四章节

21天学通C++：第十三、十四章节

第十三章&#xff1a;类型转换运算符 类型转换是一种机制&#xff0c;让程序员能够暂时或永久性改变编译器对对象的解释。注意&#xff0c;这并不意味着程序员改变了对象本身&#xff0c;而只是改变了对对象的解释。可改变对象解释方式的运算符称为类型转换运算符。 为何需要…
阅读更多...
追溯源码观察HashMap底层原理

追溯源码观察HashMap底层原理

引言&#xff08;Map的重要性&#xff09; 从事Java的小伙伴&#xff0c;在面试的时候几乎都会被问到Map&#xff0c;Map都被盘包浆了。Map是键值集合&#xff0c;使用的场景有很多比如缓存、数据索引、数据去重等场景&#xff0c;在算法中也经常出现&#xff0c;因为在Map中获…
阅读更多...
论文《Revisiting Heterophily For Graph Neural Networks》笔记

论文《Revisiting Heterophily For Graph Neural Networks》笔记

【ACM】作者从聚合后节点相似性的角度重新审视异配性&#xff0c;并定义了新的同质性度量方法。基于聚合相似度度量这一指标&#xff0c;作者提出了一种新的框架&#xff0c;称为自适应信道混合&#xff08;Adaptive Channel Mixing&#xff0c;ACM&#xff09;&#xff0c;它通…
阅读更多...
【青书学堂】2024年第一学期 生产与运作管理(高起专) 作业

【青书学堂】2024年第一学期 生产与运作管理(高起专) 作业

【青书学堂】2024年第一学期 生产与运作管理(高起专) 作业 为了方便日后复习&#xff0c;青书学堂成人大专试题整理。 若有未整理的课程&#xff0c;请私信我补充&#xff0c;欢迎爱学习的同学们收藏点赞关注&#xff01;文章内容仅限学习使用&#xff01;&#xff01;&#xf…
阅读更多...
Linux的前台进程和后台进程（守护进程）

Linux的前台进程和后台进程（守护进程）

前台进程 前台进程就是在某个终端中运行的进程&#xff0c;在该终端中通过运行命令运行起该进程&#xff0c;一旦该终端关闭&#xff0c;进程也就随之消失。 后台进程 后台进程顾名思义就是在后台运行的进程&#xff0c;与前台进程不同的是&#xff0c;它不受某一个终端控制…
阅读更多...
VBA学习(21)：遍历文件夹（和子文件夹）中的文件

VBA学习(21)：遍历文件夹（和子文件夹）中的文件

很多时候&#xff0c;我们都想要遍历文件夹中的每个文件&#xff0c;例如在工作表中列出所有文件名、对每个文件进行修改。VBA给我们提供了一些方式&#xff1a;&#xff08;1&#xff09;Dir函数&#xff1b;&#xff08;2&#xff09;File System Object。 使用Dir函数 Dir…
阅读更多...
国内新能源汽车芯片自给，承认差距，任重道远

国内新能源汽车芯片自给，承认差距，任重道远

【科技明说 &#xff5c; 科技热点关注】 据近日工信部电子五所元器件与材料研究院高级副院长罗道军表示&#xff0c;中国拥有最大的新能源车产能&#xff0c;芯片用量也是越来越多。但是芯片的自给率目前不到10%&#xff0c;是结构性的短缺。 中国拥有最大新能源车产能&#…
阅读更多...
超详细信息收集篇

超详细信息收集篇

1 域名信息收集 1.1 域名是什么 域名&#xff08;英语&#xff1a;Domain Name&#xff09;&#xff0c;又称网域&#xff0c;是由一串用点分隔的名字组成的 Internet 上某一台 计算机 或计算机组的名称&#xff0c;用于在数据传输时对计算机的定位标识&#xff08;有时也指地…
阅读更多...
STM32（六）：STM32指南者-定时器实验

STM32（六）：STM32指南者-定时器实验

目录 一、基本概念1、常规定时器2、内核定时器 二、基本定时器实验1、实验说明2、编程过程&#xff08;1&#xff09;配置LED&#xff08;2&#xff09;配置定时器&#xff08;3&#xff09;设定中断事件&#xff08;4&#xff09;主函数计数 3、工程代码 三、通用定时器实验实…
阅读更多...
开放式蓝牙耳机哪个牌子实惠又好用？五款黑马产品任你选

开放式蓝牙耳机哪个牌子实惠又好用？五款黑马产品任你选

近几年兴起的开放式蓝牙耳机&#xff0c;具有佩戴舒适稳固、不影响使用者判断外界环境等优点&#xff0c;十分适合在户外环境下使用&#xff0c;因此受到了众多健身人士的喜爱。那么该如何挑选到一款适合自己的开放式耳机呢&#xff1f;开放式蓝牙耳机哪个牌子实惠又好用&#…
阅读更多...
2024计算机毕设选题技巧|论文写作指南|更多成品项目

2024计算机毕设选题技巧|论文写作指南|更多成品项目

&#x1f4bb; 芋圆带你做毕设&#xff1a;你的毕设好帮手 &#x1f44b; 博主介绍&#xff1a; 我是芋圆&#xff0c;全网粉丝20W&#xff0c;CSDN计算机领域优质创作者&#xff0c;博客之星、掘金/华为云/阿里云等平台优质作者。大学期间&#xff0c;我不仅协助指导老师进行毕…
阅读更多...
最新文章

Copyright @ 2022~2023