3.栈和队列（汇总版）

目录

1.栈（一端插和删）

2.队列（一端插另一段删）

2.1队列的概念及结构

2.2 队列的实现

队列的接口

1.初始化队列

2.销毁队列

3.插入元素

4.出队列（头删）

5.访问对头

6.访问队尾

7.判断队列是否为空

8.查看队列的元素个数

Queue整体代码：

Queue.h

Queue.c

test.c 

1.栈（一端插和删）

1.1栈的概念及结构

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

压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。

出栈：栈的删除操作叫做出栈。出数据也在栈顶。

【注意：】因为不知道什么时候出栈，所以顺序也是多变的

具体实现，可以看一下下面这个图片的演示 

关键的元素有

接下来就是我们的增删查改，通过接口来实现啦

主体：

// 静态
//typedef int STDataType;
// #define N 10
// typedef struct Stack
// {
//  STDataType _a[N];
//  int _top; // 栈顶
// }Stack;
//更多用的是下面的动态
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>

typedef int STDataType;
typedef struct stack
{
	STDataType* a;//栈底
	int top;  //栈顶
	int capacity; //容量
}ST;

//初始化栈
void STInit(ST* ps);
//销毁栈
void STDestory(ST* ps);
//入栈（压栈）
void STPush(ST* ps, STDataType x);
//出栈
void STPop(ST* ps);
//获取栈顶元素
STDataType STTop(ST* ps);
//获取栈中有效元素个数
int STSize(ST* ps);
//检测栈是否为空，如果为空返回非零结果，如果不为空返回0
bool STEmpty(ST* ps);

点拨： 

//入栈
ps->a[ps->top] = x;
ps->top++;
//出栈
ps->top--;
//获取栈顶元素
STDataType STTop(ST* ps)
{
	assert(ps);
	assert(!STEmpty(ps));
	return ps->a[ps->top - 1];
	//栈顶元素其实就是top前一位
	//这里注意栈为空时不能获取到元素
}

有一个小细节：栈顶初始化的选择会影响到栈，所以还是要通过接口来实现，如下

栈的灵魂就在于top，top++，top--,更多的还是在做题中去理解吧

2.队列（一端插另一段删）

2.1队列的概念及结构

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

入队列：进行插入操作的一端称为队尾

出队列：进行删除操作的一端称为队头

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

2.2 队列的实现

创建结构体QueueNode这个结构体是创建节点的，节点由数据和指向下一个节点的指针构成的

第二个结构体是创建指向节点的两个指针，对头指针head和队尾指针tail

typedef int QueueDataType;
 
typedef struct QueueNode
{
	struct QueueNode* next;
	QueueDataType data;
 
}QNode;
 
typedef struct Queue
{
 
	QNode* head;
	QNode* tail;
 
 
}Queue;

队列的接口

void QueueInit(Queue* pq);   //初始化队列
void QueueDestory(Queue* pq);    //销毁队列
 
void QueuePush(Queue* pq, QueueDataType x); //插入元素
void QueuePop(Queue* pq);   //出队列
 
QueueDataType QueueFront(Queue* pq);  //查看队头元素
QueueDataType QueueBack(Queue* pq);   //查看队尾元素
 
bool QueueEmpty(Queue* pq);  //检查队列是否为空
int QueueSize(Queue* pq);    //查看队列的长度

1.初始化队列

void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = pq->tail = NULL;
 
}

2.销毁队列

当队列不为空时，用一个代替对头往后访问的指针cur ，当cur不为空时，用一个新的节点del 接收cur指向的节点。将del节点释放并置为空，cur在往后走完成对队列的遍历，最后将对头指针和队尾指针都置为空指针

void QueueDestory(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->head;//再在其中定义Qnode引入
	while (cur)
	{
		QNode* del = cur;//暂存销毁
		cur = cur->next;//保留好进行后移
		free(del);
		del = NULL;//del对每个节点进行释放，保留了cur后移
 
	}
 
	pq->head = pq->tail = NULL;
 
}

3.插入元素

队列的性质插入元素只能是尾插，分为两种情况来看：1.队列为空 2.队列不为空

1. 队列为空时，先去malloc一个新节点，让对头和队尾都指向这个新节点

2. 当队列不为空时，malloc一个新节点，将新节点插入到tail指针的下一个位置，新的队尾指向新节点的下一个位置

void QueuePush(Queue* pq, QueueDataType x)
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode)); // 1.开辟一个新空间
	if (newnode == NULL)   
	{
		perror("malloc fail!!!");
		exit(-1);    //不成功直接退出程序
	}
	else
	{
		newnode->data = x;   //2. 将数据导入到新空间中
		newnode->next = NULL; //新节点指向空
 
	}
 
	//如果队列为空
	if (pq->head ==NULL&& pq->tail==NULL)//说明队列空
	{
		pq->head = pq->tail = newnode;  //都指向新节点
	}
	else
	{
		pq->tail->next = newnode;//3. 将tail的下一个定为new
		pq->tail = pq->tail->next;// tail后移
	}
 
}

4.出队列（头删）

出队列也分为两种情况：1.队列有一个节点   2.队列有多个节点

void QueuePop(Queue* pq)//队列特性  头删
{
	assert(pq);
	assert(!QueueEmpty(pq));
	//一个节点
	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
 
	else//很多节点
	{
		QNode* del = pq->head;//del暂存然后销毁
		pq->head = pq->head->next;//保留起来好进行后移
		free(del);
		del = NULL;
	}
 
}

5.访问对头

访问得有元素，需要判断队列是否为空

QueueDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
 
	return pq->head->data;
}

6.访问队尾

访问得保证队列有元素，需要判断队列是否为空

QueueDataType QueueBack(Queue* pq)
{
    assert(pq);
    assert(!QueueEmpty);
 
 
    return pq->tail->data;
}

7.判断队列是否为空

bool QueueEmpty(Queue* pq)
{
    return pq->head == NULL;   //空返回1  有元素0
 
}

8.查看队列的元素个数

查看队列元素的个数得保证队列有元素，生成一个新的指针接受队头指针，代替头指针往后访问队列,返回n 的数值就是队列的元素个数。

int QueueSize(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty);
 
 
	int n = 0;
	QNode* cur = pq->head;
	while (cur)
	{
		++n;
		cur = cur->next;
	}
 
	return n;
}

Queue整体代码：

Queue.h

#include<stdio.h>
#include<stdbool.h>
#include<assert.h>
#include<stdlib.h>
 
typedef int QueueDataType;
 
typedef struct QueueNode
{
	struct QueueNode* next;
	QueueDataType data;
 
}QNode;
 
typedef struct Queue
{
 
	QNode* head;
	QNode* tail;
 
 
}Queue;
 
 
void QueueInit(Queue* pq);
void QueueDestory(Queue* pq);
 
void QueuePush(Queue* pq, QueueDataType x);
void QueuePop(Queue* pq);
 
QueueDataType QueueFront(Queue* pq);
QueueDataType QueueBack(Queue* pq);
 
bool QueueEmpty(Queue* pq);
int QueueSize(Queue* pq);

Queue.c

#include "Queue.h"
 
 
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = pq->tail = NULL;
 
}
void QueueDestory(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->head;
	while (cur)
	{
		QNode* del = cur;
		cur = cur->next;
		free(del);
		del = NULL;
 
	}
 
	pq->head = pq->tail = NULL;
 
 
}
 
void QueuePush(Queue* pq, QueueDataType x)
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail!!!");
		exit(-1);
	}
	else
	{
		newnode->data = x;
		newnode->next = NULL;
 
	}
 
	//如果队列为空
	if (pq->head ==NULL&& pq->tail==NULL)//说明队列空
	{
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = pq->tail->next;
	}
 
 
 
}
 
 
 
void QueuePop(Queue* pq)//队列特性  头删
{
	assert(pq);
	assert(!QueueEmpty(pq));
	//一个节点
	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
 
	else//很多节点
	{
		QNode* del = pq->head;
		pq->head = pq->head->next;
		free(del);
		del = NULL;
	}
 
 
 
 
}
 
QueueDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
 
	return pq->head->data;
}
 
 
QueueDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty);
 
 
	return pq->tail->data;
}
 
bool QueueEmpty(Queue* pq)
{
	return pq->head == NULL;   //空返回1  有元素0
 
}
int QueueSize(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty);
 
 
	int n = 0;
	QNode* cur = pq->head;
	while (cur)
	{
		++n;
		cur = cur->next;
	}
 
	return n;
 
 
}

test.c 

#include"Queue.h"
 
void testqueue()
{
	Queue q;
	QueueInit(&q);
 
	QueuePush(&q, 555);
	QueuePush(&q, 666);
	QueuePush(&q, 777);
 
	QueuePush(&q, 1);
	
	 
 
	while (!QueueEmpty(&q))
	{
 
		printf("%d", QueueFront(&q));
 
		QueuePop(&q);
 
		printf("\n");
	}
 
 
 
	QueueDestory(&q);
}
 
 
 
int main()
{
 
 
	testqueue();
 
	return 0;
}

//书摘：问题的出现不是让你止步不前，而是为你指明方向

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

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

相关文章

基于springboot实现的疫情网课管理系统

基于springboot实现的疫情网课管理系统

开发语言&#xff1a;Java 框架&#xff1a;springboot JDK版本&#xff1a;JDK1.8 服务器&#xff1a;tomcat7 数据库&#xff1a;mysql 5.7&#xff08;一定要5.7版本&#xff09; 数据库工具&#xff1a;Navicat11 开发软件&#xff1a;eclipse/myeclipse/idea Maven…
阅读更多...
证明力引导算法forceatlas2为什么不是启发式算法

证明力引导算法forceatlas2为什么不是启发式算法

一、基本概念 吸引力 F a ( n i ) ∑ n j ∈ N c t d ( n i ) ω i , j d E ( n i , n j ) V i , j \displaystyle \bm{F}_a(n_i) \sum_{n_j \in \mathcal{N}_{ctd}(n_i)} \omega_{i,j} \; d_E(n_i,n_j) \bm{V}_{i,j} Fa​(ni​)nj​∈Nctd​(ni​)∑​ωi,j​dE​(ni​,nj​…
阅读更多...
【StarRocks系列】 Trino 方言支持

【StarRocks系列】 Trino 方言支持

我们在之前的文章中&#xff0c;介绍了 Doris 官方提供的两种方言转换工具&#xff0c;分别是 sql convertor 和方言 plugin。StarRocks 目前同样也提供了类似的方言转换功能。本文我们就一起来看一下这个功能的实现与 Doris 相比有何不同。 一、Trino 方言验证 我们可以通过…
阅读更多...
C语言 | Leetcode C语言题解之第73题矩阵置零

C语言 | Leetcode C语言题解之第73题矩阵置零

题目&#xff1a; 题解&#xff1a; void setZeroes(int** matrix, int matrixSize, int* matrixColSize) {int m matrixSize;int n matrixColSize[0];int flag_col0 false;for (int i 0; i < m; i) {if (!matrix[i][0]) {flag_col0 true;}for (int j 1; j < n; j…
阅读更多...
C++:多继承虚继承

C++:多继承虚继承

在C中&#xff0c;虚继承&#xff08;Virtual Inheritance&#xff09;是一种特殊的继承方式&#xff0c;用于解决菱形继承&#xff08;Diamond Inheritance&#xff09;问题。菱形继承指的是一个类同时继承自两个或更多个具有共同基类的类&#xff0c;从而导致了多个实例同一个…
阅读更多...
20240507最新 ubuntu20.04安装ros noetic

20240507最新 ubuntu20.04安装ros noetic

ubuntu20.04安装ros 主要参考博客 【ROS】在 Ubuntu 20.04 安装 ROS 的详细教程_ubuntu20.04安装ros-CSDN博客 出现问题 1.ubuntu20.04 更换清华源报错 ubuntu20.04 更换清华源报错_gvfs metadata is not supported. fallback to teplme-CSDN博客 &#xff1f;&#xff1f…
阅读更多...
汽车 - 什么是车轮抱死

汽车 - 什么是车轮抱死

车轮抱死分为两种情况&#xff0c;一种是车辆故障层面&#xff0c;另一种是驾驶过程中的物理现象。我们先来说最通俗的刹车车轮抱死吧。 刹车制动车轮抱死 车轮停止轴向转动就是抱死&#xff0c;有速度的情况下抱死车轮&#xff0c;如果车辆的惯性动能大于轮胎抓地力&#xff0…
阅读更多...
Springboot集成Mybatispuls操作mysql数据库-03

Springboot集成Mybatispuls操作mysql数据库-03

MyBatis-Plus&#xff08;简称MP&#xff09;是一个MyBatis的增强工具&#xff0c;在MyBatis的基础上只做增强而不做改变。它支持所有MyBatis原生的特性&#xff0c;因此引入MyBatis-Plus不会对现有的MyBatis构架产生任何影响。MyBatis-Plus旨在简化开发、提高效率&#xff0c;…
阅读更多...
基于FPGA的去雾算法

基于FPGA的去雾算法

去雾算法的原理是基于图像去模糊的原理&#xff0c;通过对图像中的散射光进行估计和去除来消除图像中的雾霾效果。 去雾算法通常分为以下几个步骤&#xff1a; 1. 导引滤波&#xff1a;首先使用导引滤波器对图像进行滤波&#xff0c;目的是估计图像中散射光的强度。导引滤波器…
阅读更多...
MATLAB绘制蒸汽压力和温度曲线

MATLAB绘制蒸汽压力和温度曲线

蒸汽压力与温度之间的具体关系公式一般采用安托因方程&#xff08;Antoine Equation&#xff09;&#xff0c;用于描述纯物质的蒸汽压与温度之间的关系。安托因方程的一般形式如下&#xff1a; [\log_{10} P A - \frac{B}{C T}] 其中&#xff0c; (P) 是蒸汽压&#xff08…
阅读更多...
安卓view坐标系

安卓view坐标系

目录 一、getX、 getRawX、 getTranslationX 等的图形表示二、 getX、 getRawX、 getTranslationX 意义的文字描述 一、getX、 getRawX、 getTranslationX 等的图形表示 坐标系&#xff1a; 视图坐标系&#xff1a; 二、 getX、 getRawX、 getTranslationX 意义的文字描述 …
阅读更多...
【吊打面试官系列】Java高并发篇 - volatile 变量和 atomic 变量有什么不同？

【吊打面试官系列】Java高并发篇 - volatile 变量和 atomic 变量有什么不同？

大家好&#xff0c;我是锋哥。今天分享关于 【volatile 变量和 atomic 变量有什么不同&#xff1f;】面试题&#xff0c;希望对大家有帮助&#xff1b; volatile 变量和 atomic 变量有什么不同&#xff1f; Volatile 变量可以确保先行关系&#xff0c;即写操作会发生在后续的读…
阅读更多...
Vue 插槽

Vue 插槽

Vue插槽是一种特殊的语法&#xff0c;用于在组件中定义可复用的模板部分。它允许开发者在组件的标记中声明一个或多个插槽&#xff0c;然后在使用该组件时&#xff0c;可以根据自己的需求将内容插入到这些插槽中。 Vue插槽分为默认插槽和具名插槽两种。 默认插槽 语法 组件…
阅读更多...
中国科技大航海时代，“掘金”一带一路

中国科技大航海时代，“掘金”一带一路

文&#xff5c;白 鸽 编&#xff5c;王一粟 “这不就是90年代的内地吗&#xff1f;” 在深度考察完沙特市场后&#xff0c;华盛集团联合创始人兼CEO张霆对镜相工作室感慨道。 在张霆看来&#xff0c;沙特落后的基建&#xff08;意味着大量创新空间&#xff09;、刚刚开放…
阅读更多...
18.Blender 渲染工程、打光方法及HDR贴图导入

18.Blender 渲染工程、打光方法及HDR贴图导入

HDR环境 如何导入Blender的HDR环境图 找到材质球信息 在右上角&#xff0c;点击箭头&#xff0c;展开详细部分 点击材质球&#xff0c;会出现下面一列材质球&#xff0c;将鼠标拖到第二个材质球&#xff0c;会显示信息 courtyard.exr 右上角打开已渲染模式 左边这里选择世界…
阅读更多...
01、JMS规范介绍

01、JMS规范介绍

01、JMS规范介绍 在我们正式学习Kafka之前&#xff0c;先来了解下JMS&#xff0c;因为这可以在一定程度上帮助你更加深入的理解和学习Kafka。 1、 JMS简介 JMS&#xff0c;全称Java Mesage Service&#xff0c;即Java消息服务应用程序接口&#xff0c;是一个Java平台中关于面…
阅读更多...
HIVE统计WordCount

HIVE统计WordCount

HIVE WORDCOUNT 目录 HIVE WORDCOUNT 一、WORDCOUNT 1.我们先创建一个新的数据库 2.创建表并插入数据 3.统计WORDCOUNT 4.UNION ALL 用法 5.WITH AS 用法 1.WORDCOUNT 1&#xff09;我们先创建一个新的数据库 create database learn3;use learn3; 2&#xff09;创建表…
阅读更多...
产品推荐 | 基于 Virtex UltraScale+ XCVU3P的FACE-VPXSSD-3PA 存储板

产品推荐 | 基于 Virtex UltraScale+ XCVU3P的FACE-VPXSSD-3PA 存储板

01 产品概述 FACE&#xff08;FPGA Algorithm aCceleration Engine&#xff09;FPGA算法加速开发引擎是基于FPGA可编程器件构建的一系列算法加速开发引擎平台。FACE-VPXSSD-3PA存储平台是FACE系列中的一员。该平台板载2组2GB 64bit DDR4、2路QSFP28光接口、4个NVME SSD M.2接口…
阅读更多...
yum常用命令与lrzsz的在线安装

yum常用命令与lrzsz的在线安装

yum命令 yum&#xff08; Yellow dog Updater, Modified&#xff09;是一个在 Fedora 和 RedHat 以及 SUSE 中的 Shell 前端软件包管理器。 基于 RPM 包管理&#xff0c;能够从指定的服务器自动下载 RPM 包并且安装&#xff0c;可以自动处理依赖性关系&#xff0c;并且一次安装…
阅读更多...
设备驱动中device_create函数与sys/devices目录

设备驱动中device_create函数与sys/devices目录

当调用device_create时parent参数为空时&#xff0c;新添加的设备位于sys/devices//sys/devices/virtual目录 以下面代码的为例 my_newcharled.myclass class_create(THIS_MODULE,dtled); my_newcharled.mydevice device_create(my_newcharled.myclass,NULL,my_newcharled.ne…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站