C语言数据结构-栈和队列

C语言数据结构-栈和队列

  • 1.栈
    • 1.1概念与结构
    • 1.2栈的实现
      • 1.2.1结构体定义
      • 1.2.2初始化
      • 1.2.3销毁
      • 1.2.4入栈
      • 1.2.5出栈
      • 1.2.6取栈顶处的元素
      • 1.2.7获取栈中有效的个数
  • 2.队列
    • 2.1概念与结构
    • 2.2队列的实现
      • 2.2.1结构体定义
      • 2.2.2入队列
      • 2.2.3判断是否为空
      • 2.2.4队列中的有效元素个数
      • 2.2.5删除结点
      • 2.2.6取对头数据
      • 2.2.7取队尾的数据
      • 2.2.8 销毁队列
  • 3.栈的源代码
  • 4.队列的源代码

1.栈

1.1概念与结构

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守先进后出或后进先出的原则。

栈不能实现任意位置的插入和删除。

栈底不进行任何的操作。

线性表：逻辑结构一定是线性的，物理结构不一定是线性的。

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

出栈：栈的删除操作叫做出栈。出数据也在栈顶。
在这里插入图片描述
栈的底层结构：
栈的实现一般可以使用数组或者链表，相对而言数组的结构实现更优一点。因为数组在尾上插入数据的代价比较小。

在这里插入图片描述

1.2栈的实现

接下来，使用数组来实现栈：

入栈：往栈顶的位置插入数据，所以栈顶需要++。栈顶就相当于当前数组的大小size，所以让size++，就就可以实现入栈。

出栈：size- -。

需要增容所以需要把当前数组的容量实时记录下来。

1.2.1结构体定义

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

typedef int STDataType;
//定义栈的数据结构
typedef struct Stack
{
	STDataType* arr;
	int top;//指向栈顶的位置
	int capacity;//空间的大小
}ST;

1.2.2初始化

void STInit(ST* pt)//传一级指针
{
	assert(pt);
	pt->arr = NULL;
	pt->top = pt->capacity = 0;
}

有初始化一定就会有销毁。

1.2.3销毁

void STDestroy(ST* pt)
{

	if (pt->arr != NULL)
		free(pt->arr);
	pt->arr = NULL;
	pt->top = pt->capacity = 0;
}

1.2.4入栈

在这里插入图片描述
首先我们需要判断数组是否已经满了。如果已经满了，我们需要增容。

//入栈--栈顶的位置插入
void STPush(ST* pt, STDataType x)
{
	//需要先判断空间够不够
	asser(pt);
	if (pt->top == pt->capacity)
	{
		//增容
		int newCapacity = pt->capacity == 0 ? 4 : 2 * pt->capacity;//判断capacity是否wei0，如果为0直接就增容4，如果不为0，就2倍的增容。
		STDataType* tmp = (STDataType*)realloc(pt->arr, newCapacity * sizeof(STDataType));
		//这里新定义一个tmp是为了防止arr增容失败，arr数组中的数据都会发生改变
		if (tmp == NULL)
		{
			perror("reail fail!\n");
			exit(1);
			//直接退出
		}
		pt->arr = tmp;
		pt->capacity = newCapacity;
	}
	//空间足够
	pt->arr[pt->top++] = x;
}

1.2.5出栈

在这里插入图片描述

void STPop(ST* pt)
{
	assert(!STEmpty(pt));
	pt->top=pt->arr[pt->top--];
}

1.2.6取栈顶处的元素

因为要的是元素，需要在数组中找到栈顶的元素，不能直接top-1，直接top-1后是top-1的值，不是top-1处数组中的值。

//取栈顶的元素，需要数组
void STFind(ST* ps)
{
	assert(!STEmpty(ps));
	//判断栈是否为空
	return ps->arr[ps->top-1];
}

1.2.7获取栈中有效的个数

直接返回top的值就可以

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

2.队列

2.1概念与结构

概念：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出的特点

入队列：进行插入操作的一端称为队尾
出队列进行删除操作的一端称为对头
在这里插入图片描述
队列底层结构：
队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。

选择链表为底层结构，那么在定义结构体时，就需要再把链表也结构体化一下。

假如入队列的顺序是1，2，3，4；那么出队列的顺序也是1，2，3，4.就像我们日常生活中的排队一样。先进先出，后进后出

2.2队列的实现

在这里插入图片描述
上面的方法是可行的，但是时间复杂度还是很高。我们还可以其他的办法：

在这里插入图片描述
这种方法只需要将链表改造一下就可以了。

2.2.1结构体定义

由于队列是由链表构成的，所以在结构体定义时，需要将链表中的头结点和尾节点定义出来，队列是由数据域和指针域组成的，也是需要定义出来的。

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

//定义队列结点结构体
typedef int STDataType;
typedef struct QueueNode
{
	STDataType data;
	struct QUeuNOde* next;
}QN;

struct Queue 
{
	QN* phead;
	QN* ptail;
};

2.2.2入队列

在这里插入图片描述

void QueuPush(Queue* pq,STDataType x)
{
	assert(pq);
	//创建一个新节点
	//在队尾插
	QN* newnode = (QN*)malloc(sizeof(QN));
	if (newnode == NULL)
	{
		perror("malloc fail!\n");
		exit(1);
	}
	newnode->data = x;
	newnode->next = NULL;

	//队列为空
	if (pq->phead == NULL)
	{
		pq->phead = pq->ptail = newnode;
	}
	else {
		pq->ptail->next = newnode;
		pq->ptail = pq->ptail->next;//让ptail往后走
	}
}

2.2.3判断是否为空

bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->phead == NULL;
}

2.2.4队列中的有效元素个数

int QueueSize(Queue* pq)
{
	QN* pcur = pq->phead;
	int size;
	while (pcur)
	{
		size++;//++后向后遍历直到找到pcur为空的时候
		pcur = pcur->next;
	}
	return size;
}

2.2.5删除结点



void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	//只有一个结点
	if (pq->phead == pq->ptail)
	{
		free(pq->phead);
		pq->phead = pq->ptail = NULL;
	}
	//多个结点
	else {
		QN* next = pq->phead->next;
		free(pq->phead);
		next = next->next;
		pq->phead = next;
		pq->phead = pq->ptail = NULL;
	}
	pq->size--;
}

2.2.6取对头数据

返回的是头结点的数据

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

2.2.7取队尾的数据

//取队尾的数据
STDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->ptail->data;
}

2.2.8 销毁队列

//销毁队列
void QueueDestroy(Queue* pq)
{
	asser(pq);
	QN* pcur = pq->phead;
	while (pcur)
	{
		QN* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	pq->phead = pq->ptail = NULL；
	pq->size = 0;
}

3.栈的源代码

Stack.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"
void STInit(ST* ps)//传一级指针
{
	assert(ps);
	ps->arr = NULL;
	ps->top = ps->capacity = 0;
}
void STDestroy(ST* ps)
{
	if (ps->arr != NULL)
		free(ps->arr);
	ps->arr = NULL;
	ps->top = ps->capacity= 0;
}

bool STEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
	//如果他们两个相等返回的是真，下面的函数需要用！来接收
}

//入栈--栈顶的位置插入
void STPush(ST* ps, STDataType x)
{
	//需要先判断空间够不够
	assert(ps);
	if (ps->top == ps->capacity)
	{
		//增容
		int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;//判断capacity是否wei0，如果为0直接就增容4，如果不为0，就2倍的增容。
		STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));
		//这里新定义一个tmp是为了防止arr增容失败，arr数组中的数据都会发生改变
		if (tmp == NULL)
		{
			perror("realloc fail!\n");
			exit(1);
			//直接退出
		}
		ps->arr = tmp;
		ps->capacity = newCapacity;
	}
	//空间足够
	ps->arr[ps->top++] = x;
}

void STPop(ST* ps)
{
	assert(!STEmpty(ps));
	--ps->top;
}
//取栈顶的元素，需要数组
STDataType STFind(ST* ps)
{
	assert(!STEmpty(ps));
	//判断栈是否为空
	return ps->arr[ps->top-1];
}

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

Stack.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

typedef int STDataType;
//定义栈的数据结构
typedef struct Stack
{
	STDataType* arr;
	int top;//指向栈顶的位置
	int capacity;
}ST;

//初始化
void STInit(ST* ps);//传一级指针

//销毁
void STDestroy(ST* ps);

//判断栈是否为空
bool STEmpty(ST* ps);

//入栈
void STPush(ST* ps,STDataType x);

//出栈
void STPop(ST* ps);

//取栈顶的元素
STDataType STFind(ST* ps);

//获取栈中有效的个数
int STSize(ST* ps);

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"
void test()
{
	ST st;
	STInit(&st);
	STPush(&st, 1);
	STPush(&st, 2);
	STPush(&st, 3);
	STPush(&st, 4);
	STPush(&st, 5);
	STFind(&st);
	while (!STEmpty(&st))
	{
		//取栈顶元素
		STDataType top = STFind(&st);
		printf("%d ", top);
		STPop(&st);
	}
	STDestroy(&st);
}
int main()
{
	test();
	return 0;
}

4.队列的源代码

Queue.vc

#define _CRT_SECURE_NO_WARNINGS 1

#include"Queue.h"


void QueuInit(Queue* pq)
{
	assert(pq);
	pq->phead = pq->ptail = NULL;//队列中只有头和尾
	pq->size = 0;
}

//判断是否为空
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->phead == NULL;
}

//队列中的有效元素个数
int QueueSize(Queue* pq)
{
	//QN* pcur = pq->phead;
	//int size=0;
	//while (pcur)
	//{
	//	size++;//++后向后遍历直到找到pcur为空的时候
	//	pcur = pcur->next;
	//}
	/*return size;*/
	return pq->size;//时间复杂度降低了
}

void QueuPush(Queue* pq,STDataType x)
{
	assert(pq);
	//创建一个新节点
	//在队尾插
	QN* newnode = (QN*)malloc(sizeof(QN));
	if (newnode == NULL)
	{
		perror("malloc fail!\n");
		exit(1);
	}
	newnode->data = x;
	newnode->next = NULL;

	//队列为空
	if (pq->phead == NULL)
	{
		pq->phead = pq->ptail = newnode;
	}
	else {
		pq->ptail->next = newnode;
		pq->ptail = pq->ptail->next;//让ptail往后走
	}
	pq->size++;
}


void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	//只有一个结点
	if (pq->phead == pq->ptail)
	{
		free(pq->phead);
		pq->phead = pq->ptail = NULL;
	}
	//多个结点
	else {
		QN* next = pq->phead->next;
		free(pq->phead);
		next = next->next;
		pq->phead = next;
		pq->phead = pq->ptail = NULL;
	}
	pq->size--;
}

//取对头数据
STDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->phead->data;
}

//取队尾的数据
STDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->ptail->data;
}
//销毁队列
void QueueDestroy(Queue* pq)
{
	asser(pq);
	QN* pcur = pq->phead;
	while (pcur)
	{
		QN* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	pq->phead = pq->ptail = NULL; 
	pq->size = 0;
}

Queue.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
//定义队列结点结构体
typedef int STDataType;
typedef struct QueueNode
{
	STDataType data;
	struct QUeuNOde* next;
}QN;
//定义队列的结构
typedef struct Queue //typedef是去掉关键词struct
{
	QN* phead;
	QN* ptail;
	int size;
}Queue;

void QueuInit(Queue* pq);

//入队列
void QueuPush(Queue* pq ,STDataType x);

//出队
void QueuePop(Queue* pq);

//判断是否为空
bool QueueEmpty(Queue* pq);

//队列中的有效元素个数
int QueueSize(Queue* pq);

//取对头数据
STDataType QueueFront(Queue* pq);

//取队尾的数据
STDataType QueueBack(Queue* pq);

//销毁队列
void QueueDestroy(Queue* pq);

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"

void test()
{
	Queue q;
	QueuInit(&q);
	QueuPush(&q, 1);
	QueuPush(&q, 2);
	QueuPush(&q, 3);
	QueuPush(&q, 4);
	//while (QueueSize(&q))
	//{
	//	printf("%d\n", QueueSize(&q));
	//	QueuePop(&q);
	//}
	//printf("%d\n", QueueSize(&q));
	printf("phead:%d\n", QueueFront(&q));
	printf("ptail:%d\n", QueueBack(&q));
	QueueDestroy(&q);
}
int main()
{
	test();
	return 0;
}

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

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

相关文章

[CTF/网络安全] 攻防世界 upload1 解题详析

[CTF/网络安全] 攻防世界 upload1 解题详析

[CTF/网络安全] 攻防世界 upload1 解题详析 考察文件上传&#xff0c;具体原理及姿势不再赘述。 姿势 在txt中写入一句话木马<?php eval($_POST[qiu]);?> 回显如下&#xff1a; 查看源代码&#xff1a; Array.prototype.contains function (obj) { var i this.…
阅读更多...
TiDB 优化器丨执行计划和 SQL 算子解读最佳实践

TiDB 优化器丨执行计划和 SQL 算子解读最佳实践

作者&#xff1a; TiDB社区小助手 原文来源&#xff1a; https://tidb.net/blog/5edb7933 导读 在数据库系统中&#xff0c;查询优化器是数据库管理系统的核心组成部分&#xff0c;负责将用户的 SQL 查询转化为高效的执行计划&#xff0c;因而会直接影响用户体感的性能与稳…
阅读更多...
监控视频汇聚平台：Liveweb视频监控管理平台方案详细介绍

监控视频汇聚平台：Liveweb视频监控管理平台方案详细介绍

Liveweb国标视频综合管理平台是一款以视频为核心的智慧物联应用平台。它基于分布式、负载均衡等流媒体技术进行开发&#xff0c;提供广泛兼容、安全可靠、开放共享的视频综合服务。该平台具备多种功能&#xff0c;包括视频直播、录像、回放、检索、云存储、告警上报、语音对讲、…
阅读更多...
10个Word自动化办公脚本

10个Word自动化办公脚本

在日常工作和学习中&#xff0c;我们常常需要处理Word文档&#xff08;.docx&#xff09;。 Python提供了强大的库&#xff0c;如python-docx&#xff0c;使我们能够轻松地进行文档创建、编辑和格式化等操作。本文将分享10个使用Python编写的Word自动化脚本&#xff0c;帮助新…
阅读更多...
ROS VSCode调试方法

ROS VSCode调试方法

VSCode 调试 Ros文档 1.编译参数设置 cd catkin_ws catkin_make -DCMAKE_BUILD_TYPEDebug2.vscode 调试插件安装 可在扩展中安装(Ctrl Shift X): 1.ROS 2.C/C 3.C Intelliense 4.Msg Language Support 5.Txt Syntax 3.导入已有或者新建ROS工作空间 3.1 导入工作…
阅读更多...
排序学习整理（1）

排序学习整理（1）

1.排序的概念及运用 1.1概念 排序&#xff1a;所谓排序&#xff0c;就是使⼀串记录&#xff0c;按照其中的某个或某些关键字的大小&#xff0c;递增或递减的排列起来的操作&#xff0c;以便更容易查找、组织或分析数据。 1.2运用 购物筛选排序 院校排名 1.3常见排序算法 2.实…
阅读更多...
TYUT设计模式大题

TYUT设计模式大题

对比简单工厂&#xff0c;工厂方法&#xff0c;抽象工厂模式 比较安全组合模式和透明组合模式 安全组合模式容器节点有管理子部件的方法&#xff0c;而叶子节点没有&#xff0c;防止在用户在叶子节点上调用不适当的方法&#xff0c;保证了的安全性&#xff0c;防止叶子节点暴露…
阅读更多...
指针与引用错题汇总

指针与引用错题汇总

int *p[3]; // 定义一个包含 3 个指向 int 的指针的数组int a 10, b 20, c 30; p[0] &a; // p[0] 指向 a p[1] &b; // p[1] 指向 b p[2] &c; // p[2] 指向 c // 访问指针所指向的值 printf("%d %d %d\n", *p[0], *p[1], *p[2]); // 输出: 10 20 30…
阅读更多...
uniapp中scrollview配合swiper实现一个简单的tab标签页

uniapp中scrollview配合swiper实现一个简单的tab标签页

<template><view class"tab-container"><!-- Tab 标签滚动容器 --><scroll-view scroll-x"true" class"tab-scroll" scroll-with-animation"true"><view class"tab-list"><viewv-for"…
阅读更多...
opengl 三角形

opengl 三角形

最后效果&#xff1a; OpenGL version: 4.1 Metal 不知道为啥必须使用VAO 才行。 #include <glad/glad.h> #include <GLFW/glfw3.h>#include <iostream> #include <vector>void framebuffer_size_callback(GLFWwindow *window, int width, int heigh…
阅读更多...
Qml-TabBar类使用

Qml-TabBar类使用

Qml-TabBar类使用 TabBar的概述 TabBar继承于Container 由TabButton进行填充&#xff0c;可以与提供currentIndex属性的任何容器或布局控件一起使用&#xff0c;如StackLayout 或 SwipeView&#xff1b;contentHeight : real:TabBar的内容高度&#xff0c;用于计算标签栏的隐…
阅读更多...
Windows常用DOS指令（附案例）

Windows常用DOS指令（附案例）

文章目录 1.dir 查看当前目录2.cd 进入指定目录3.md 创建指定目录4.cd> 创建指定文件5.rd 删除指定空目录6.del 删除指定文件7.copy 复制文件8.xcopy 批量复制9.ren 改名10.type 在命令行空窗口打开文件11.cls 清空DOS命令窗口12.chkdsk 检查磁盘使用情况13.time 显示和设置…
阅读更多...
YOLOv11 NCNN安卓部署

YOLOv11 NCNN安卓部署

YOLOv11 NCNN安卓部署 前言 yolov11 NCNN安卓部署 目前的帧率可以稳定在20帧左右&#xff0c;下面是这个项目的github地址&#xff1a;https://github.com/gaoxumustwin/ncnn-android-yolov11 上面的检测精度很低时因为这个模型只训练了5个epoch&#xff0c;使用3090训练一个…
阅读更多...
C++内存对齐

C++内存对齐

在 C 中&#xff0c;内存对齐 是一种编译器和硬件协作的机制&#xff0c;用于将数据存储在内存中时按照一定的规则进行排列&#xff0c;以提高数据访问的效率。其目的是确保数据在内存中的地址满足硬件对齐要求&#xff0c;并优化 CPU 访问速度。 C 中内存对齐的基本概念 对齐单…
阅读更多...
365天深度学习训练营-第P6周：VGG-16算法-Pytorch实现人脸识别

365天深度学习训练营-第P6周：VGG-16算法-Pytorch实现人脸识别

&#x1f368; 本文为&#x1f517;365天深度学习训练营中的学习记录博客&#x1f356; 原作者&#xff1a;K同学啊 文为「365天深度学习训练营」内部文章 参考本文所写记录性文章&#xff0c;请在文章开头带上「&#x1f449;声明」 &#x1f37a;要求&#xff1a; 保存训练过…
阅读更多...
SAP SD学习笔记15 - 返品处理流程2 - 参照请求传票（发票）来生成返品传票

SAP SD学习笔记15 - 返品处理流程2 - 参照请求传票（发票）来生成返品传票

上一章讲了返品处理&#xff08;退货处理&#xff09;的流程。 SAP SD学习笔记14 - 返品处理&#xff08;退货处理&#xff09;的流程以及系统实操&#xff0c;比如 返品传票&#xff1b;请求Block标记&#xff1b;收到退货之后的处理&#xff0c;请求传票的登录_sap 销售返品…
阅读更多...
Flutter 1.1：下载Flutter环境

Flutter 1.1：下载Flutter环境

1、在AS中下载Flutter插件 在setting的Plugins中下载Flutter&#xff0c;如图所示&#xff0c;可以直接进行搜索查找 2、下载flutter的sdk源代码 flutter中文文档学习 通过Git下载SDK源代码 git clone -b stable https://github.com/flutter/flutter.git3、配置系统变量 3…
阅读更多...
电子应用设计方案-31：智能AI音响系统方案设计

电子应用设计方案-31：智能AI音响系统方案设计

智能 AI 音响系统方案设计 一、引言 智能 AI 音响作为一种新兴的智能家居设备&#xff0c;通过融合语音识别、自然语言处理、音频播放等技术&#xff0c;为用户提供便捷的语音交互服务和高品质的音乐体验。本方案旨在设计一款功能强大、性能稳定、用户体验良好的智能 AI 音响系…
阅读更多...
损失函数分类

损失函数分类

1. NLLLoss&#xff08;负对数似然损失&#xff09; 定义&#xff1a; 直接对预测的概率 p(yi) 的负对数求平均。通常配合 Softmax 使用&#xff0c;输入为对数概率。 优点&#xff1a; 对离散分类问题效果良好。更灵活&#xff0c;用户可以自行计算 Softmax。 缺点&#x…
阅读更多...
聊聊Flink：这次把Flink的触发器(Trigger)、移除器(Evictor)讲透

聊聊Flink：这次把Flink的触发器(Trigger)、移除器(Evictor)讲透

一、触发器(Trigger) Trigger 决定了一个窗口&#xff08;由 window assigner 定义&#xff09;何时可以被 window function 处理。 每个 WindowAssigner 都有一个默认的 Trigger。 如果默认 trigger 无法满足你的需要&#xff0c;你可以在 trigger(…) 调用中指定自定义的 tr…
阅读更多...
最新文章

Copyright @ 2022~2023