【数据结构】栈和队列--＞理解和实现（赋源码)

Toc

欢迎光临我的Blog，喜欢就点歌关注吧♥

前面介绍了顺序表、单链表、双向循环链表，基本上已经结束了链表的讲解，今天谈一下栈、队列。可以简单的说是前面学习的一特殊化实现，但是总体是相似的。

前言

  1. 栈是一种特殊的线性表，它只允许在一端进行插入和删除操作。这一端被称为栈顶，另一端被称为栈底。栈的特点是后进先出（LIFO），即最后进入的元素最先被移除。

  2. 队列是另一种特殊的线性表，它允许在一端进行插入操作，在另一端进行删除操作。插入操作的一端称为队尾，删除操作的一端称为队头。队列的特点是先进先出（FIFO），即最先进入的元素最先被移除。

栈和队列有各自的特点，严格讲用顺序表还是链表的实现都可以。但我们根据结构特点选择一个更加适合的结构进行是实现。

一、栈和队列的理解

对于栈的理解：

在这里插入图片描述

栈如同这个图一样，要是想拿出数据，必须从上面一个一个往下面拿。这也正是 LIFO 的体现。

对于队列的理解：

在这里插入图片描述

队列如同这个图一样，要是想拿出数据，必须前面一个一个往向后面拿。这也正是 FIFO 的体现。

二、栈的实现（顺组表）

2.1 栈的功能

//初始化
void STInit(ST* ps);
//压栈
void STpush(ST* ps, STDataType x);
//删除
void STPop(ST* ps);
//大小
int STSize(ST* ps);
//判空
bool STEmpty(ST* ps);
//出栈
STDataType STTop(ST* ps);
//检查容量
void CheckCapacity(ST* ps);
//销毁
void STDestroy(ST* ps);

2.2 栈结构体的定义及其初始化

结构体的定义

typedef int STDataType;

typedef struct stack
{
	STDataType* a;
	int top;
	int capacity;
}ST;

初始化（开辟空间）

void STInit(ST* ps)
{
	assert(ps);
	ps->a = (ST*)malloc(sizeof(ST)*4);
	if (ps->a == NULL)
	{
		perror("malloc fail");
		return;
	}
	
	ps->capacity = 4;
	ps->top = 0;
}

2.3 压栈（存储数据）

//压栈
void STpush(ST* ps,STDataType x)
{
	assert(ps);

	ps->a[ps->top] = x;
	ps->top++;
}

2,4 删除数据

在这里面删除数据是配合，栈顶出栈。每次拿出一个数据，就要减少一个数据。

void STPop(ST* ps)
{
	assert(ps);
	assert(!STEmpty(ps));

	ps->top--;
}

2.5 计算栈内元个数

//大小
int STSize(ST* ps)
{
	assert(ps);

	return ps->top;
}

2.6 判断栈内是否为空

这里运用 bool 类型直接返回，比较方便。

bool STEmpty(ST* ps)
{
	assert(ps);

	return ps->top == 0;
}

2.7 出栈

//出栈
STDataType STTop(ST* ps)
{
	assert(ps);

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

2.8 增加容量

//检查容量
void CheckCapacity(ST*ps)
{
	assert(ps);
	if (ps->top == ps->capacity)
	{
		ST* tmp = (ST*)realloc(ps->a, sizeof(ST) * (ps->capacity) * 2);
		if (tmp == NULL)
		{
			perror("malloc fail");
			return;
		}
		ps->capacity *= 2;
		ps->a = tmp;
	}
}

2.9 销毁栈

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

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

三、队列的实现（单链表）

3.1 队列的功能

//初始化
void QueueInit(Queue* ps);
//销毁
void QueueDestroy(Queue* ps);
//入队
void QueuePush(Queue* ps, QDataType x);
//删除
void QueuePop(Queue* ps);
//大小
int QueueSize(Queue* ps);
//判空队
bool QueueEmpty(Queue* ps);
//出队头
QDataType QueueTop(Queue* ps);
//出队尾
QDataType QueueBack(Queue* ps);

3.2 队列的结构体定义以及初始化

结构体定义

定义两个结构体，第一个为存放数据，第二个结构体为两个指针，分别指向头和尾

typedef int QDataType;

typedef struct QNode
{
	struct QNode* next;
	QDataType data;

}QNode;

typedef struct Queue
{
	QNode*head;
	QNode*tail;
	 
	int szie;
}Queue;

初始化

//初始化
void QueueInit(Queue* ps)
{
	assert(ps);

	ps->head = ps->tail = NULL;

	ps->szie = 0;

}

3.3 队列销毁

//销毁
void QueueDestroy(Queue* ps)
{
	assert(ps);
	QNode* cur = ps->head;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}

	ps->head = ps->tail = NULL;
	ps->szie = 0;
}

3.4 入队（插入数据）

//入队
void QueuePush(Queue* ps,QDataType x)
{
	assert(ps);

	QNode* newcode = (QNode*)malloc(sizeof(QNode));
	if (newcode == NULL)
	{
		perror("malloc fail");
		return ;
	}
	newcode->next = NULL;
	newcode->data = x;

	if (ps->head == NULL)
	{
		ps->head = ps->tail = newcode;
		
	}
	else

	{
		
		ps->tail->next = newcode;
		ps->tail = newcode;
	}

	ps->szie++;

}

3.5 删除数据（头删）

//删除
void QueuePop(Queue* ps)
{
	assert(ps);
	assert(ps->head != NULL);
	assert(!QueueEmpty(ps));

	if (ps->head->next == NULL)
	{
		free(ps->head);
		ps->head = ps->tail = NULL;
	}
	else
	{
		QNode* next = ps->head->next;
		free(ps->head);
		ps->head = next;

	}
	ps->szie--;
}

3.6 计算队列元素个数

//大小
int QueueSize(Queue* ps)
{
	assert(ps);

	return ps->szie;
}

3.7 判断是否队列为空

//判空队
bool QueueEmpty(Queue* ps)
{
	assert(ps);

	return ps->szie == 0;
}

3.8 出队（头）

//出队头
QDataType QueueTop(Queue* ps)
{
	assert(ps);
	assert(!QueueEmpty(ps));

	return ps->head->data;
}

3.9 出队（尾）

//出队尾
QDataType QueueBack(Queue* ps)
{
	assert(ps);

	return ps->tail->data;
}

四、栈和队列的源码

栈

Stack.h

#pragma once

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


typedef int STDataType;

typedef struct stack
{
	STDataType* a;
	int top;
	int capacity;
}ST;

//初始化
void STInit(ST* ps);
//压栈
void STpush(ST* ps, STDataType x);
//删除
void STPop(ST* ps);
//大小
int STSize(ST* ps);
//判空
bool STEmpty(ST* ps);
//出栈
STDataType STTop(ST* ps);
//检查容量
void CheckCapacity(ST* ps);
//销毁
void STDestroy(ST* ps);

Stack.c

#define _CRT_SECURE_NO_WARNINGS


#include "stack.h"


//初始化
void STInit(ST* ps)
{
	assert(ps);
	ps->a = (ST*)malloc(sizeof(ST)*4);
	if (ps->a == NULL)
	{
		perror("malloc fail");
		return;
	}
	
	ps->capacity = 4;
	ps->top = 0;
}
//销毁
void STDestroy(ST* ps)
{
	assert(ps);

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

//检查容量
void CheckCapacity(ST*ps)
{
	assert(ps);
	if (ps->top == ps->capacity)
	{
		ST* tmp = (ST*)realloc(ps->a, sizeof(ST) * (ps->capacity) * 2);
		if (tmp == NULL)
		{
			perror("malloc fail");
			return;
		}
		ps->capacity *= 2;
		ps->a = tmp;
	}
}

//压栈
void STpush(ST* ps,STDataType x)
{
	assert(ps);

	ps->a[ps->top] = x;
	ps->top++;
}

//删除
void STPop(ST* ps)
{
	assert(ps);
	assert(!STEmpty(ps));

	ps->top--;
}

//判空
bool STEmpty(ST* ps)
{
	assert(ps);

	return ps->top == 0;
}

//出栈
STDataType STTop(ST* ps)
{
	assert(ps);

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

//大小
int STSize(ST* ps)
{
	assert(ps);

	return ps->top;
}

test.c

#define _CRT_SECURE_NO_WARNINGS


#include "stack.h"

void teststack()
{
	ST st;
	STInit(&st);

	STpush(&st, 1);
	STpush(&st, 2);
	STpush(&st, 3);
	STpush(&st, 4);
	STpush(&st, 5);

	printf("%d", STSize(&st));
	printf("\n");

	while (!STEmpty(&st))
	{
		printf("%d ", STTop(&st));
		STPop(&st);
	}
	printf("\n");
	printf("%d", STSize(&st));

	STDestroy(&st);

}



int main()
{
	teststack();

	return 0;
}

队列

Queue.h

#pragma once

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

typedef int QDataType;

typedef struct QNode
{
	struct QNode* next;
	QDataType data;

}QNode;

typedef struct Queue
{
	QNode*head;
	QNode*tail;
	 
	int szie;
}Queue;


//单链表的实现，FIFO

//初始化
void QueueInit(Queue* ps);
//销毁
void QueueDestroy(Queue* ps);
//入队
void QueuePush(Queue* ps, QDataType x);
//删除
void QueuePop(Queue* ps);
//大小
int QueueSize(Queue* ps);
//判空队
bool QueueEmpty(Queue* ps);
//出队头
QDataType QueueTop(Queue* ps);
//出队尾
QDataType QueueBack(Queue* ps);

Queue.c

#define _CRT_SECURE_NO_WARNINGS

#include "queue.h"



//初始化
void QueueInit(Queue* ps)
{
	assert(ps);

	ps->head = ps->tail = NULL;

	ps->szie = 0;

}

//销毁
void QueueDestroy(Queue* ps)
{
	assert(ps);
	QNode* cur = ps->head;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}

	ps->head = ps->tail = NULL;
	ps->szie = 0;
}

//入队
void QueuePush(Queue* ps,QDataType x)
{
	assert(ps);

	QNode* newcode = (QNode*)malloc(sizeof(QNode));
	if (newcode == NULL)
	{
		perror("malloc fail");
		return ;
	}
	newcode->next = NULL;
	newcode->data = x;

	if (ps->head == NULL)
	{
		ps->head = ps->tail = newcode;
		
	}
	else

	{
		
		ps->tail->next = newcode;
		ps->tail = newcode;
	}

	ps->szie++;

}

//删除
void QueuePop(Queue* ps)
{
	assert(ps);
	assert(ps->head != NULL);
	assert(!QueueEmpty(ps));

	if (ps->head->next == NULL)
	{
		free(ps->head);
		ps->head = ps->tail = NULL;
	}
	else
	{
		QNode* next = ps->head->next;
		free(ps->head);
		ps->head = next;

	}
	ps->szie--;
}

//大小
int QueueSize(Queue* ps)
{
	assert(ps);

	return ps->szie;
}

//判空队
bool QueueEmpty(Queue* ps)
{
	assert(ps);

	return ps->szie == 0;
}

//出队头
QDataType QueueTop(Queue* ps)
{
	assert(ps);
	assert(!QueueEmpty(ps));

	return ps->head->data;
}

//出队尾
QDataType QueueBack(Queue* ps)
{
	assert(ps);

	return ps->tail->data;
}

test.c

#define _CRT_SECURE_NO_WARNINGS

#include "queue.h"



void testQueue()
{
	Queue s;
	QueueInit(&s);

	QueuePush(&s, 1);
	QueuePush(&s, 2);
	QueuePush(&s, 3);
	QueuePush(&s, 4);

	

	//printf("%d ", QueueTop(&s));
	//QueuePop(&s);
	//printf("%d ", QueueTop(&s));
	//QueuePop(&s);	
	//printf("%d ", QueueTop(&s));
	//QueuePop(&s);	
	//printf("%d ", QueueTop(&s));
	//QueuePop(&s);
	//printf("\n");

	while (!(QueueEmpty(&s)))
	{
		printf("%d ", QueueTop(&s));
		QueuePop(&s);
	}


	QueueDestroy(&s);

}

int main()
{
	testQueue();


	return 0;
}

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

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

相关文章

flask_sqlalchemy时间缓存导致datetime.now()时间不变问题

flask_sqlalchemy时间缓存导致datetime.now()时间不变问题

问题是这样的&#xff0c;项目在本地没什么问题&#xff0c;但是部署到服务器过一阵子发现&#xff0c;这个时间会在某一刻定死不变。 重启uwsgi后&#xff0c;发现第一条数据更新到了目前最新时间&#xff0c;过了一会儿再次发送也变了时间&#xff0c;但是再过几分钟再发就会…
阅读更多...
【全开源】JAVA打车小程序APP打车顺风车滴滴车跑腿源码微信小程序打车源码

【全开源】JAVA打车小程序APP打车顺风车滴滴车跑腿源码微信小程序打车源码

&#xff1a;构建便捷出行新体验 一、引言&#xff1a;探索打车系统小程序源码的重要性 在数字化快速发展的今天&#xff0c;打车系统小程序已成为我们日常生活中不可或缺的一部分。它以其便捷、高效的特点&#xff0c;极大地改变了我们的出行方式。而背后的关键&#xff0c;…
阅读更多...
啵啵啵啵啵啵啵啵啵啵啵啵啵啵啵

啵啵啵啵啵啵啵啵啵啵啵啵啵啵啵

欢迎关注博主 Mindtechnist 或加入【智能科技社区】一起学习和分享Linux、C、C、Python、Matlab&#xff0c;机器人运动控制、多机器人协作&#xff0c;智能优化算法&#xff0c;滤波估计、多传感器信息融合&#xff0c;机器学习&#xff0c;人工智能等相关领域的知识和技术。关…
阅读更多...
swaggerHole：针对swaggerHub的公共API安全扫描工具

swaggerHole：针对swaggerHub的公共API安全扫描工具

关于swaggerHole swaggerHole是一款针对swaggerHub的API安全扫描工具&#xff0c;该工具基于纯Python 3开发&#xff0c;可以帮助广大研究人员检索swaggerHub上公共API的相关敏感信息&#xff0c;整个任务过程均以自动化形式实现&#xff0c;且具备多线程特性和管道模式。 工具…
阅读更多...
增加强制索引依然慢

增加强制索引依然慢

版本: 阿里云RDS MySQL 8.0.25 线上数据库CPU达到100%, 定位到如下SQL EXPLAIN SELECT ssd.goods_no,ssd.goods_name,ssd.goods_spec,ssd.goods_unit,ssd.create_time,w.warehouse_name,sb.batch_no,swl.warehouse_region_location_name,sc.customer_name AS goodsOwnerName,s…
阅读更多...
如何在MySQL中实现upsert：如果不存在则插入？

如何在MySQL中实现upsert：如果不存在则插入？

目录 1 使用 REPLACE 2 使用 INSERT ... ON DUPLICATE KEY UPDATE 使用 INSERT IGNORE 有效会导致 MySQL 在尝试执行语句时忽略执行错误 INSERT 。这意味着 包含 索引或 字段 INSERT IGNORE 中重复值的语句 不会 产生错误&#xff0c;而只是完全忽略该特定 命令。其明显目的是…
阅读更多...
2048小游戏的菜鸡实现方法

2048小游戏的菜鸡实现方法

# 2048小游戏的实现与分析 2048是一款非常受欢迎的数字滑块游戏&#xff0c;其目标是通过滑动和合并相同数字的方块来创建一个值为2048的方块。下面&#xff0c;我们将通过分析一个C语言实现的2048小游戏的源代码&#xff0c;来探索如何用编程实现这款游戏。 ## 游戏概述 20…
阅读更多...
指针（初阶1）

指针（初阶1）

一.指针是什么 通俗的讲&#xff0c;指针就是地址&#xff0c;其存在的意义就像宾馆房间的序号一样是为了更好的管理空间。 如下图&#xff1a; 如上图所示&#xff0c;指针就是指向内存中的一块空间&#xff0c;也就相当于地址 二.一个指针的大小是多少 之前我们学习过&#x…
阅读更多...
Springboot注意点

Springboot注意点

1.Usermapper里加param注解 2.RequestParam 和 RequestBody的区别&#xff1a; RequestParam 和 RequestBody的区别&#xff1a; RequestParam 和 RequestBody 是Spring框架中用于处理HTTP请求的两个不同的注 get请求一般用url传参数&#xff0c;所以参数名和参数的值就在ur…
阅读更多...
LCM — Least Common Multiple 最小公倍数

LCM — Least Common Multiple 最小公倍数

因为任何一个数都可以表示为若干个质数幂的乘积。 比如75 3*5*5&#xff0c;即 2^0 * 3^1 * 5^2 * 7^0 ... 那么对于两个数来说&#xff0c;gcd就是他们取每个质数的较小幂的乘积&#xff0c;lcm则相反。显然&#xff0c;这些幂加起来就是他们乘积。 gcd(a,b) * lcm(a,b) a…
阅读更多...
立创·天空星开发板-GD32F407VE-USART

立创·天空星开发板-GD32F407VE-USART

本文以 立创天空星开发板-GD32F407VET6-青春版 作为学习的板子&#xff0c;记录学习笔记。 立创天空星开发板-GD32F407VE-USART 基础通信概念同步通信 & 异步通信串行通信 & 并行通信双工 & 单工通讯速率码元 串口通信数据帧 串口封装 基础通信概念 通信协议是网络…
阅读更多...
本地运行ChatTTS

本地运行ChatTTS

TTS 是将文字转为语音的模型&#xff0c;最近很火的开源 TTS 项目&#xff0c;本地可以运行&#xff0c;运行环境 M2 Max&#xff0c;差不多每秒钟 4&#xff5e;&#xff5e;5 个字。本文将介绍如何在本地运行 ChatTTS。 下载源码 首先下载源代码 git clone https://github…
阅读更多...
WPF中读取Excel文件的内容

WPF中读取Excel文件的内容

演示效果 实现方案 1.首先导入需要的Dll(这部分可能需要你自己搜一下) Epplus.dll Excel.dll ICSharpCode.SharpZipLib.dll 2.在你的解决方案的的依赖项->添加引用->浏览->选择1中的这几个Dll点击确定。(添加依赖) 3.然后看代码内容 附上源码 using Excel; usi…
阅读更多...
TypeScript环境安装与VScode编辑器的使用

TypeScript环境安装与VScode编辑器的使用

说明大背景环境&#xff0c;我用的是window10系统。 1.安装node.js 。 去官网下载安装包。 虽然我去的是官网&#xff0c;但是不知为何下载了个不知名的东西&#xff0c;后来又找了个链接才下载正确了。 实际上就是一个.msi的文件。我用的版本&#xff1a;node-v18.19.0-x6…
阅读更多...
【第四节】C/C++数据结构之树与二叉树

【第四节】C/C++数据结构之树与二叉树

目录 一、基本概念与术语 二、树的ADT 三、二叉树的定义和术语 四、平衡二叉树 4.1 解释 4.2 相关经典操作 4.3 代码展示 一、基本概念与术语 树(Tree)是由一个或多个结点组成的有限集合T。其中: 1 有一个特定的结点&#xff0c;称为该树的根(root)结点&#xff1b; 2 …
阅读更多...
GPT-4o：突出优势 和 应用场景

GPT-4o：突出优势 和 应用场景

还是大剑师兰特&#xff1a;曾是美国某知名大学计算机专业研究生&#xff0c;现为航空航海领域高级前端工程师&#xff1b;CSDN知名博主&#xff0c;GIS领域优质创作者&#xff0c;深耕openlayers、leaflet、mapbox、cesium&#xff0c;canvas&#xff0c;webgl&#xff0c;ech…
阅读更多...
centos官方yum源不可用 解决方案（随手记）

centos官方yum源不可用 解决方案（随手记）

昨天用yum安装软件的时候&#xff0c;就报错了 [rootop01 ~]# yum install -y net-tools CentOS Stream 8 - AppStream 73 B/s | 38 B 00:00 Error: Failed to download metadata for repo appstream: Cannot prepare internal mirrorlis…
阅读更多...
从零开始：疾控中心实验室装修攻略，让你的实验室一步到位！

从零开始：疾控中心实验室装修攻略，让你的实验室一步到位！

在当今充满挑战和变化的世界中&#xff0c;疾病的控制和预防成为了人类生存与发展的重要课题。而疾控中心作为防控疾病的核心机构&#xff0c;其疾控中心实验室设计建设显得尤为重要。下面广州实验室装修公司小编将分享疾控中心实验室设计建设方案&#xff0c;为疾病防控工作提…
阅读更多...
“冻干”凭什么好吃不肥喵？既能当零食又可做主食的冻干分享

“冻干”凭什么好吃不肥喵？既能当零食又可做主食的冻干分享

近年来&#xff0c;冻干猫粮因其高品质而备受喜爱&#xff0c;吸引了无数猫主人的目光&#xff0c;像我这样的资深养猫人早已开始选择冻干喂养。但新手养猫的人&#xff0c;可能会感到迷茫&#xff1a;冻干猫粮到底是什么&#xff1f;冻干可以一直当主食喂吗&#xff1f; 一、…
阅读更多...
TqdmWarning: IProgress not found. Please update jupyter and ipywidgets.

TqdmWarning: IProgress not found. Please update jupyter and ipywidgets.

jupyter notebook报错 在pycharm的terminal中 安装完成后就不会再报错了
阅读更多...
最新文章

Copyright @ 2022~2023