C语言实现栈和队列

代码已经上传我的资源，需要可自取

94a1ff699ecf406eb681c1fb71f9070f.png

1.栈

1.1栈的概念及结构

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。 进行数据插入和删除操作的一端
称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈， 入数据在栈顶。
出栈：栈的删除操作叫做出栈。 出数据也在栈顶。

1.2栈的实现

栈的实现一般可以使用 数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。
结构
逻辑结构是一个单向进出的容器，物理结构是一个数组。我们是通过对逻辑结构想象来对物理结构进行改造和限制让物理结构变得具有逻辑结构的功能。这个也是数据结构中最重要的思想之一。
栈本质上是一个限制操作的顺序表。
结构定义也与顺序表一样 
// 支持动态增长的栈
typedef int STDataType;

typedef struct Stack
{
	STDataType* arr;
	int top;		// 栈顶
	int capacity;  // 容量 
}Stack;

功能的声明

// 初始化栈 
void StackInit(Stack* ps);
// 入栈 
void StackPush(Stack* ps, STDataType data);
// 出栈 
void StackPop(Stack* ps);
// 获取栈顶元素 
STDataType StackTop(Stack* ps);
// 获取栈中有效元素个数 
int StackSize(Stack* ps);
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
bool StackEmpty(Stack* ps);
// 销毁栈 
void StackDestroy(Stack* ps);

初始化与销毁

// 初始化栈 
void StackInit(Stack* ps) 
{
	assert(ps);

	ps->arr = NULL;
	ps->top = ps->capacity = 0;
}
// 销毁栈 
void StackDestroy(Stack* ps)
{
	assert(ps);

	free(ps->arr);
	ps->arr = NULL;
	ps->capacity = ps->top = 0;
}

入栈与出栈

入栈其实就是顺序表往末尾位置插入数据，出栈也是仅需要让控制数据个数size-1即可。

// 入栈 
void StackPush(Stack* ps, STDataType data)
{
	assert(ps);
	if (ps->capacity == ps->top)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDataType* newarr = (STDataType*)realloc(ps->arr,newcapacity * sizeof(STDataType));
		if (newarr == NULL)
		{
			perror("realloc fail");
			return;
		}
		ps->arr = newarr;
		ps->capacity = newcapacity;
	}
	ps->arr[ps->top] = data;
	ps->top++;
}
// 出栈 
void StackPop(Stack* ps)
{
	assert(ps);
	assert(ps->top > 0);
	ps->top--;
}

获取栈顶元素，即直接访问未尾元素即可。

// 获取栈顶元素 
STDataType StackTop(Stack* ps)
{
	assert(ps);
	assert(ps->top > 0);

	return ps->arr[ps->top - 1];
}


// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0
bool StackEmpty(Stack* ps)
{
	assert(ps);
	return ps->top==0;
}

2.队列

2.1队列的概念及结构

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为 队尾 出队列：进行删除操作的一端称为 队头

2.2队列的实现

队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构进出数据头和尾总有一个要移动数据，效率会比较低。而链表可以通过保存一个尾指针，来规避这个问题。
e349af12959a4fe29c2c9bba405b2bde.png
结构
因为这里是用链表实现队列，队列节点结构与链表一样，但下面定义的结构体又是什么回事呢？
我们在数据结构中往往是将数据在内存中用数组或指针连续在一起保存的，这些是在对内存中的操作，除此之外我们还会保留一个寻找（保存内存）信息，通过这个信息我们就能进行相应的操作或拿到我们想拿到的信息。
但是在顺序表结构中链表结构仅一个结点就足够了(再添加也不会优化太多)
而在队列中我们想的是最方便，最快速拿到我们想要的信息（队头，队尾，数据个数）就创建了下面这一个结构体。（其实也可以不创建结构体，而是单独创建这几个变量，但是这样的话调用就不方便，且过于累赘。 
typedef int QDataType;
// 链式结构：表示队列 
typedef struct QListNode
{
	struct QListNode* next;
	QDataType data;
}QNode;

// 队列的结构 
typedef struct Queue
{
	QNode* front;
	QNode* rear;
	int size;
}Queue;

功能声明 
// 初始化队列 
void QueueInit(Queue* q);
// 队尾入队列 
void QueuePush(Queue* q, QDataType data);
// 队头出队列 
void QueuePop(Queue* q);
// 获取队列头部元素 
QDataType QueueFront(Queue* q);
// 获取队列队尾元素 
QDataType QueueBack(Queue* q);
// 获取队列中有效元素个数 
int QueueSize(Queue* q);
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
bool QueueEmpty(Queue* q);
// 销毁队列 
void QueueDestroy(Queue* q);

初始化与销毁
与单链表差不多，销毁队列节点时记得要一个一个销毁 

// 初始化队列 
void QueueInit(Queue* q)
{
	assert(q);
	q->front = q->rear = NULL;
	q->size = 0;
}

// 销毁队列 
void QueueDestroy(Queue* q)
{
	assert(q);
	QNode* cur = q->front;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	q->front = q->rear = NULL;
	q->size = 0;
}

入队：申请节点+简单单链表尾插操作

// 队尾入队列 
void QueuePush(Queue* q, QDataType data)
{
	assert(q);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail!");
		return;
	}
	newnode->next = NULL;
	newnode->data = data;

	if (q->rear==NULL)
	{
		q->front = newnode;
		q->rear = newnode;
	}
	else
	{
		q->rear->next = newnode;
		q->rear = newnode;
	}
	q->size++;
}

出队：单链表头删

// 队头出队列 
void QueuePop(Queue* q)
{
	assert(q);
	assert(q->size);

	if (q->front->next ==NULL)
	{
		free(q->front);
		q->front = q->rear = NULL;
	}
	else
	{
		QNode* next = q->front->next;
		free(q->front);
		q->front = next;
	}
	q->size--;
}

获取头部/尾部/数据个数

这个的时候我们刚刚创建结构体的好处就体现出来了。各种信息直接调用。

// 获取队列头部元素 
QDataType QueueFront(Queue* q)
{
	assert(q);
	assert(q->front);
	return q->front->data;
}

// 获取队列队尾元素 
QDataType QueueBack(Queue* q)
{
	assert(q);
	assert(q->size);
	return q->rear->data;
}

// 获取队列中有效元素个数 
int QueueSize(Queue* q)
{
	assert(q);
	return q->size;
}

判空。判断是否为空。是就返回真，不是就返回假。

// 检测队列是否为空，如果为空返回非0 ，如果非空返回0 
bool QueueEmpty(Queue* q)
{
	assert(q);
	return q->size==0;
}

3.循环队列

附oj链接:622. 设计循环队列 - 力扣（LeetCode）

实际中我们有时还会使用一种队列叫循环队列。如生产者消费者模型时可以就会使用循环队列。环形队列可以使用数组实现，也可以使用循环链表实现。
但是采用数组的话能随机访问，并且物理空间也是连续的，更加符合队列的线性逻辑结构。故往往采用数组实现。
循环队列中的判满条件有两类，一个是通过定义记数器来记录数组中的元素。另外一个则是通过多申请一个空间，当尾＋1==头时为满。校招中往往采用第二种，本文也采用第二个方法。
定义循环队列结点的结构:k为存储数据个数。 
typedef struct 
{
	int* arr;
	int head;
	int tail;
	int k;
} MyCircularQueue;

65266ae1f1f9457a870ceb1a89af153f.png

各方法声明如下 
//构造器，设置队列长度为 k 。
MyCircularQueue* myCircularQueueCreate(int k);

//向循环队列插入一个元素。如果成功插入则返回真。
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value);

//从循环队列中删除一个元素。如果成功删除则返回真。
bool myCircularQueueDeQueue(MyCircularQueue* obj);

//从队首获取元素。如果队列为空，返回 -1 
int myCircularQueueFront(MyCircularQueue* obj);

//获取队尾元素。如果队列为空，返回 - 1 。
int myCircularQueueRear(MyCircularQueue* obj);

//检查循环队列是否为空。
bool myCircularQueueIsEmpty(MyCircularQueue* obj);

//检查循环队列是否已满。
bool myCircularQueueIsFull(MyCircularQueue* obj);

//
void myCircularQueueFree(MyCircularQueue* obj);

初始化:先给申请一个结点，再给结点中的数组申请k+1个空间。

销毁:先将数组销毁，再销毁节点。

MyCircularQueue* myCircularQueueCreate(int k) 
{
	MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
	if (obj == NULL)
	{
		perror("malloc fail!");
		return NULL;
	}
	obj->arr=(int*)malloc(sizeof(int) * (k+1));
	obj->head = obj->tail =0;
	obj->k = k;
	return obj;
}


void myCircularQueueFree(MyCircularQueue* obj) 
{
	free(obj->arr);
	free(obj);
	obj = NULL;
}

判空:头==尾

判满:若尾+1不超过看+1判断条件为尾+1=头，若超过尾则是变成0，

两个加一起也就是(尾+1)对(k+1)取模即可。

bool myCircularQueueIsEmpty(MyCircularQueue* obj) 
{
	return obj->head == obj->tail;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) 
{
	return (obj->tail + 1)%(obj->k+1) == obj->head;
}

队尾入队:

直接在尾部插入，若超过尾巴则取模修正。

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) 
{
	if (myCircularQueueIsFull(obj))
	{
		return false;
	}
	obj->arr[obj->tail] = value;
	obj->tail++;
	obj->tail = (obj->tail) % (obj->k + 1);
	return true;
}

出队:头+1，若走到数组末尾刚取模修正。 
bool myCircularQueueDeQueue(MyCircularQueue* obj) 
{
	if (myCircularQueueIsEmpty(obj))
	{
		return false;
	}
	obj->head++;
	obj->head = obj->head % (obj->k + 1);
	return true;
}

查看队头队尾:队头直接查看，若是队尾的话，在数组头部则查查数组末尾元素，其他则是查看尾的前一个元素。综合起来就是查看(tail-1+k+1)%(k+1); 
int myCircularQueueFront(MyCircularQueue* obj) 
{
	if (myCircularQueueIsEmpty(obj))
	{
		return -1;
	}
	return obj->arr[obj->head];
}

int myCircularQueueRear(MyCircularQueue* obj) 
{
	if (myCircularQueueIsEmpty(obj))
	{
		return -1;
	}
	int tmp = (obj->tail+ obj->k ) % (obj->k + 1);
	return obj->arr[tmp];
}

完

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

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

Python实现贝叶斯优化器(Bayes_opt)优化简单循环神经网络分类模型(SimpleRNN分类算法)项目实战

Python实现贝叶斯优化器(Bayes_opt)优化简单循环神经网络分类模型(SimpleRNN分类算法)项目实战

说明：这是一个机器学习实战项目（附带数据代码文档视频讲解），如需数据代码文档视频讲解可以直接到文章最后关注获取。 1.项目背景 贝叶斯优化器 (BayesianOptimization) 是一种黑盒子优化器，用来寻找最优参数。 贝叶斯…
阅读更多...
Linux资源与网络请求

Linux资源与网络请求

参数说明： d : 改变显示的更新速度，或是在交谈式指令列( interactive command)按 sq : 没有任何延迟的显示速度，如果使用者是有 superuser 的权限，则 top 将会以最高的优先序执行c : 切换显示模式，共有两种模式&#…
阅读更多...
软件测试岗位，职业前景到底怎样？

软件测试岗位，职业前景到底怎样？

最近经常被问到软件测试这个行业的前景，网上也有大量唱衰测试这个行业的声音，很多选择职业方向的同学对是否要进入这个职业也非常迷茫。 所以开一贴来聊一聊秋草对软件测试这个岗位的要求以及对其前景的看法。 软件测试到底是个什么样的岗位&#xff1…
阅读更多...
如何学习cuda编程？

如何学习cuda编程？

第一本cuda教材: CUDA By Example​ developer.nvidia.com/cuda-example 配套网课： Udacity CS344: Intro to Parallel Programming​ developer.nvidia.com/udacity-cs344-intro-parallel-programming 记得做网课作业。 然后就靠项目上手了。 我当时实习时候的项…
阅读更多...
ProTable样式缺失

ProTable样式缺失

在使用Ant Design Pro开发页面时，想要引用ProComponents组件中的ProTable表格，引入官方文档的案例发现缺少样式 官方文档地址ProTable - 高级表格 - ProComponents (ant.design) 引入的是第一个Demos 样式预览： 代码 import { EllipsisO…
阅读更多...
今天不分享技术，分享秋天的故事

今天不分享技术，分享秋天的故事

引言 这个爱情故事好像是个悲剧，你说的是婚姻。爱情没有悲剧，对爱者而言，爱情怎么会是悲剧呢。对春天而言，秋天是它的悲剧吗。结尾是什么，等待，之后呢，没有之后。或者说，等待的结果…
阅读更多...
Spring Cloud微服务

Spring Cloud微服务

Spring Cloud 是一个专注于微服务架构的一站式解决方案，它通过整合多个优秀的开源框架和工具，为开发者提供了构建、管理和维护微服务系统所需的全方位支持。以下是关于 Spring Cloud 微服务的详细介绍： 基本概念 微服务架构：微服务…
阅读更多...
图像处理算法的形式

图像处理算法的形式

一 基本功能形式 按图像处理的输出形式，图像处理的基本功能可分为三种形式。 1）单幅图像 -------->单幅图像 2）多幅图像-------->单幅图像 3）单(或多)幅图像------->数字或符号符 二 几种具体算法形式 1.局部处理 …
阅读更多...
搭建 mongodb 副本集，很详细

搭建 mongodb 副本集，很详细

搭建 mongodb 副本集，很详细 一、前言二、创建用户1、创建 root 用户2、创建测试用户3、修改用户密码 三、修改配置文件（主节点）1、开启登录认证2、加上副本集3、最终配置文件 四、副本节点1、创建副本节点目录2、编辑配置文件3、启动副本节点…
阅读更多...
力扣283-- 移动零

力扣283-- 移动零

开始做梦的地方 力扣283 ： 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。请注意 ，必须在不复制数组的情况下原地对数组进行操作。 何解？ 1，暴力枚举&#xff1a…
阅读更多...
JS面试八股文（一）

JS面试八股文（一）

😊JS面试八股文（一） 1.JS由哪三部分组成？2.JS有哪些内置对象？3.操作数组的方法有哪些？4.JS对数据类型的检测方式有哪些？5.说一下闭包，闭包有什么特点？6.前端的内存泄漏怎…
阅读更多...
adb常见指令以及问题解决

adb常见指令以及问题解决

1.屏幕截图 问题： /system/bin/sh: pull: not found 最后是一个美元符号$，则表示不是以root身份运行； 最后是一个井号#，则表示是以root身份运行。 解决方案： 直接退出，在PC端使用adb pull，而…
阅读更多...
Spring Boot实现的动态化酒店住宿管理系统

Spring Boot实现的动态化酒店住宿管理系统

1系统概述 1.1 研究背景 随着计算机技术的发展以及计算机网络的逐渐普及，互联网成为人们查找信息的重要场所，二十一世纪是信息的时代，所以信息的管理显得特别重要。因此，使用计算机来管理酒店客房管理系统的相关信息成为必然。开发…
阅读更多...
软件设计师考试大纲整理

软件设计师考试大纲整理

为了防止出题者不按常理出牌，此文档为根据上午题大纲自行整理的扩展知识，并非考试常考题 此文档为根据上午题大纲自行整理的扩展知识，并非考试常考题 此文档为根据上午题大纲自行整理的扩展知识，并非考试常考题 闲暇时间了解知…
阅读更多...
Web高级开发实验：EL基本运算符与数据访问

Web高级开发实验：EL基本运算符与数据访问

一、实验目的 掌握EL的定义，即Expression Language，用于提高编程效率。学习和掌握在开发环境中创建Java文件，并在jsp文件中使用EL表达式去调用其中的方法与属性等。 二、实验所用方法 上机实操 三、实验步骤及截图 1、创建javaweb项目&a…
阅读更多...
力扣刷题（sql）--零散知识点（1）

力扣刷题（sql）--零散知识点（1）

通过一段时间的刷题，感觉自己的sql能力逐渐上去，所以不会像前三道题一样讲那么详细了，这里主要会讲到一些特殊的知识点和方法。另外，我的建议是做完一个题有好的想法赶紧记录下来，不要想着最后汇总，不然会懒…
阅读更多...
基于SSM平面设计课程在线学习系统的设计

基于SSM平面设计课程在线学习系统的设计

管理员账户功能包括：系统首页，个人中心，学生管理，教师管理，课程类型管理，课程学习管理，试题讲解管理，作业信息管理 前台账号功能包括：系统首页，个人中心&…
阅读更多...
Vue3实现获取验证码按钮倒计时效果

Vue3实现获取验证码按钮倒计时效果

Vue3实现获取验证码按钮倒计时效果 效果描述：用户点击获取验证码按钮，发送请求给后端，按钮失效，并且开始倒计时60秒；在此期间，用户无法再次点击按钮，即使用户刷新页面，倒计时依然存在…
阅读更多...
Java项目实战II基于微信小程序的马拉松报名系统（开发文档+数据库+源码）

Java项目实战II基于微信小程序的马拉松报名系统（开发文档+数据库+源码）

目录 一、前言 二、技术介绍 三、系统实现 四、文档参考 五、核心代码 六、源码获取 全栈码农以及毕业设计实战开发，CSDN平台Java领域新星创作者，专注于大学生项目实战开发、讲解和毕业答疑辅导。获取源码联系方式请查看文末 一、前言 马拉松运动…
阅读更多...
XQT_UI 组件｜01｜颜色

XQT_UI 组件｜01｜颜色

介绍 XColor 是一个用于处理颜色的类，提供了获取颜色和样式的方法。它可以与 Qt 的 UI 组件结合使用，以便在应用程序中实现丰富的颜色效果。 安装 确保你已经在项目中包含了 xqt_color_palette.hpp 和相关的头文件。 #include "xqt_color_palet…
阅读更多...
最新文章

Copyright @ 2022~2023