【数据结构】实现栈和队列

目录

  • 一、栈
    • 1.栈的概念及结构
      • （1）栈的概念
      • （2）栈的结构
    • 2.栈的实现
      • （1）类型和函数的声明
      • （2）初始化栈
      • （3）销毁
      • （4）入栈
      • （5）出栈
      • （6）检查是否为空
      • （7）获取栈的元素个数
      • （8）获取栈顶元素
  • 二、栈的全部代码
    • 1.Stack.h
    • 2Stack.c
    • 3.Test.c
  • 三、队列
    • 1.队列的概念及结构
      • （1）队列的概念
      • （2）队列的结构
    • 2.队列的实现
      • （1）类型和函数的声明
      • （2）初始化队列
      • （3）销毁
      • （4）入队
      • （5）出队
      • （6）获取头部元素
      • （7）获取队尾元素
      • （8）获取元素个数
      • （9）检查是否为空
  • 四、队列的全部代码
    • 1.Queue.h
    • 2.Queue.c
    • 3.Test.c

一、栈

1.栈的概念及结构

（1）栈的概念

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

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

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

（2）栈的结构

在这里插入图片描述

2.栈的实现

（1）类型和函数的声明

栈的结构与顺序表相同，也是用数组。因为栈的特点是出栈、入栈在同一位置，所以用数组尾插更方便。

typedef int STDataType;
typedef struct Stack
{
	STDataType* data;
	int top;
	int capacity;
}ST;
//初始化
void STInit(ST* ps);
//销毁
void STDestroy(ST* ps);
//入栈
void STPush(ST* ps, STDataType x);
//出栈
void STPop(ST* ps);
//检查是否为空
bool STEmpty(ST* ps);
//获取栈的元素个数
int STSize(ST* ps);
//获取栈顶元素
STDataType STTop(ST* ps);

（2）初始化栈

void STInit(ST* ps)
{
	assert(ps);
	ps->data = NULL;
	ps->capacity = 0;
	ps->top = 0;
}

（3）销毁

void STDestroy(ST* ps)
{
	assert(ps);
	free(ps->data);
	ps->data = NULL;
	ps->capacity = 0;
	ps->top = 0;
}

（4）入栈

void STPush(ST* ps, STDataType x)
{
	assert(ps);
	if (ps->top == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		STDataType* tmp = (STDataType*)realloc(ps->data, sizeof(STDataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		ps->data = tmp;
		ps->capacity = newcapacity;
	}
	ps->data[ps->top] = x;
	ps->top++;
}

（5）出栈

void STPop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);
	ps->top--;
}

（6）检查是否为空

bool STEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}

（7）获取栈的元素个数

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

（8）获取栈顶元素

STDataType STTop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);
	return ps->data[ps->top - 1];
}

二、栈的全部代码

1.Stack.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef int STDataType;
typedef struct Stack
{
	STDataType* data;
	int top;
	int capacity;
}ST;
//初始化
void STInit(ST* ps);
//销毁
void STDestroy(ST* ps);
//入栈
void STPush(ST* ps, STDataType x);
//出栈
void STPop(ST* ps);
//检查是否为空
bool STEmpty(ST* ps);
//获取栈的元素个数
int STSize(ST* ps);
//获取栈顶元素
STDataType STTop(ST* ps);

2Stack.c

#include "Stack.h"
//初始化
void STInit(ST* ps)
{
	assert(ps);
	ps->data = NULL;
	ps->capacity = 0;
	ps->top = 0;
}
//销毁
void STDestroy(ST* ps)
{
	assert(ps);
	free(ps->data);
	ps->data = NULL;
	ps->capacity = 0;
	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;
		STDataType* tmp = (STDataType*)realloc(ps->data, sizeof(STDataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		ps->data = tmp;
		ps->capacity = newcapacity;
	}
	ps->data[ps->top] = x;
	ps->top++;
}
//出栈
void STPop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);
	ps->top--;
}
//检查是否为空
bool STEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}
//获取栈的元素个数
int STSize(ST* ps)
{
	assert(ps);
	return ps->top;
}
//获取栈顶元素
STDataType STTop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);
	return ps->data[ps->top - 1];
}

3.Test.c

#include "Stack.h"
void test()
{
	ST st;
	STInit(&st);
	STPush(&st, 1);
	STPush(&st, 2);
	STPush(&st, 3);
	STPush(&st, 4);
	STPush(&st, 5);
	while (!STEmpty(&st))
	{
		printf("%d ", STTop(&st));
		STPop(&st);
	}

	STDestroy(&st);
}
int main()
{
	test();
	return 0;
}

在这里插入图片描述

三、队列

1.队列的概念及结构

（1）队列的概念

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

（2）队列的结构

在这里插入图片描述

2.队列的实现

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

（1）类型和函数的声明

队列除了节点的结构体以外，还要再创建一个结构体，方便找到尾指针。

typedef int QDataType;
typedef struct QueueNode
{
	QDataType data;
	struct QueueNode* next;
}QNode;
typedef struct Queue
{
	QNode* head;
	QNode* tail;
	int size;
}Que;
//初始化
void QueInit(Que* pq);
//销毁
void QueDestroy(Que* pq);
//入队
void QuePush(Que* pq, QDataType x);
//出队
void QuePop(Que* pq);
//获取头部元素
QDataType QueFront(Que* pq);
//获取队尾元素
QDataType QueBack(Que* pq);
//获取元素个数
int QueSize(Que* pq);
//检查是否为空
bool QueEmpty(Que* pq);

（2）初始化队列

void QueInit(Que* pq)
{
	assert(pq);
	pq->head = NULL;
	pq->tail = NULL;
	pq->size = 0;
}

（3）销毁

void QueDestroy(Que* pq)
{
	assert(pq);
	QNode* cur = pq->head;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;
	pq->size = 0;
}

（4）入队

入队相当于尾插，因为只有一个入口插入节点，所以直接在这个函数创建一个新节点。分两种情况：刚开始没有节点尾插、已有节点再尾插。

void QuePush(Que* pq, QDataType x)
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	if (pq->tail == NULL)
	{
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
	pq->size++;
}

（5）出队

出队相当于头删。如果没有节点，就不能再删了，所以要断言检查是否为空。这里的头删也要分两种情况：只有一个节点、一个以上的节点。

void QuePop(Que* pq)
{
	assert(pq);
	assert(!QueEmpty(pq));
	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		QNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
	pq->size--;
}

（6）获取头部元素

QDataType QueFront(Que* pq)
{
	assert(pq);
	assert(!QueEmpty(pq));
	return pq->head->data;
}

（7）获取队尾元素

QDataType QueBack(Que* pq)
{
	assert(pq);
	assert(!QueEmpty(pq));
	return pq->tail->data;
}

（8）获取元素个数

int QueSize(Que* pq)
{
	assert(pq);
	return pq->size;
}

（9）检查是否为空

bool QueEmpty(Que* pq)
{
	assert(pq);
	return pq->head == NULL;
}

四、队列的全部代码

1.Queue.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef int QDataType;
typedef struct QueueNode
{
	QDataType data;
	struct QueueNode* next;
}QNode;
typedef struct Queue
{
	QNode* head;
	QNode* tail;
	int size;
}Que;
//初始化
void QueInit(Que* pq);
//销毁
void QueDestroy(Que* pq);
//入队
void QuePush(Que* pq, QDataType x);
//出队
void QuePop(Que* pq);
//获取头部元素
QDataType QueFront(Que* pq);
//获取队尾元素
QDataType QueBack(Que* pq);
//获取元素个数
int QueSize(Que* pq);
//检查是否为空
bool QueEmpty(Que* pq);

2.Queue.c

#include "Queue.h"
//初始化
void QueInit(Que* pq)
{
	assert(pq);
	pq->head = NULL;
	pq->tail = NULL;
	pq->size = 0;
}
//销毁
void QueDestroy(Que* pq)
{
	assert(pq);
	QNode* cur = pq->head;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;
	pq->size = 0;
}
//入队
void QuePush(Que* pq, QDataType x)
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	if (pq->tail == NULL)
	{
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
	pq->size++;
}
//出队
void QuePop(Que* pq)
{
	assert(pq);
	assert(!QueEmpty(pq));
	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		QNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
	pq->size--;
}
//获取头部元素
QDataType QueFront(Que* pq)
{
	assert(pq);
	assert(!QueEmpty(pq));
	return pq->head->data;
}
//获取队尾元素
QDataType QueBack(Que* pq)
{
	assert(pq);
	assert(!QueEmpty(pq));
	return pq->tail->data;
}
//获取元素个数
int QueSize(Que* pq)
{
	assert(pq);
	return pq->size;
}
//检查是否为空
bool QueEmpty(Que* pq)
{
	assert(pq);
	return pq->head == NULL;
}

3.Test.c

#include "Queue.h"
void test()
{
	Que q;
	QueInit(&q);
	QuePush(&q, 1);
	QuePush(&q, 2);
	QuePush(&q, 3);
	QuePush(&q, 4);
	QuePush(&q, 5);
	while (!QueEmpty(&q))
	{
		printf("%d ", QueFront(&q));
		QuePop(&q);
	}
	printf("\n");
	QueDestroy(&q);
}
int main()
{
	test();
	return 0;
}

在这里插入图片描述
在这里插入图片描述
感谢观看~

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

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

相关文章

高忆管理：药店零售概念回落，开开实业走低，此前7日大涨超80%

高忆管理：药店零售概念回落，开开实业走低，此前7日大涨超80%

药店零售概念18日盘中大幅下挫&#xff0c;到发稿&#xff0c;华人健康跌逾11%&#xff0c;漱玉布衣、塞力医疗跌超9%&#xff0c;重药控股、浙江震元、榜首医药等跌超7%&#xff0c;药易购跌超6%&#xff0c;开开实业跌超3%。 值得注意的是&#xff0c;开开实业此前7个交易日斩…
阅读更多...
【应用层】网络基础 -- HTTP协议

【应用层】网络基础 -- HTTP协议

再谈协议HTTP协议认识URLurlencode和urldecodeHTTP协议格式HTTP的方法HTTP的状态码HTTP常见HeaderHTTP周边会话保持 再谈协议 协议是一种 “约定”. socket api的接口&#xff0c;在读写数据时&#xff0c;都是按 “字符串” 的方式来发送接收的(tcp是以字节流的方式发送的&am…
阅读更多...
vue项目配置git提交规范

vue项目配置git提交规范

vue项目配置git提交规范 一、背景介绍二、husky、lint-staged、commitlint/cli1.husky2.lint-staged3.commitlint/cli 三、具体使用1.安装依赖2.运行初始化脚本3.在package.json中配置lint-staged4.根目录新增 commitlint.config.js 4.提交测试1.提示信息格式错误时2.eslint校验…
阅读更多...
sql递归查询

sql递归查询

一、postgresql 递归sql with recursive p as(select t1.* from t_org_test t1 where t1.id2union allselect t2.*from t_org_test t2 join p on t2.parent_idp.id) select id,name,parent_id from p; sql中with xxxx as () 是对一个查询子句做别名&#xff0c;同时数据库会对…
阅读更多...
c++ day2

c++ day2

#include <iostream>using namespace std; /*void row(int &p,int &q)//引用 {int t;tp;pq;qt; }*/ /*struct ab {string name;// int &age; }; void add(int a,int b) {cout << ab<< endl; } void add(float a,float b) {cout << ab <…
阅读更多...
四、pikachu之文件包含

四、pikachu之文件包含

文章目录 1、文件包含漏洞概述1.1 文件包含漏洞1.2 相关函数1.3 文件包含漏洞分类 2、File Inclusion(local)3、File Inclusion(remote) 1、文件包含漏洞概述 1.1 文件包含漏洞 文件包含漏洞&#xff1a;在web后台开发中&#xff0c;程序员往往为了提高效率以及让代码看起来更…
阅读更多...
C语言编写图形界面 | 移动小球示例

C语言编写图形界面 | 移动小球示例

文章目录 其他文章最终结果设计过程定义小球的属性窗口过程函数绘制小球空格回弹小球碰壁 完整代码 其他文章 部分知识可以查看如下文章&#xff1a; C语言编写注册窗口 最终结果 先放一下本篇文章最终结果展示图吧&#xff0c;如图&#xff0c;一个绿色的小球&#xff0c;在…
阅读更多...
centos7安装JDK

centos7安装JDK

1.将JDK压缩包复制到/opt/software路径下 2.解压JDK到/opt/module目录下 [rootkb135 software]# tar -zxvf jdk-8u381-linux-x64.tar.gz -C /opt/module 3.配置环境变量 修改profile文件 vim /etc/profile 添加环境变量 #JAVA_HOME export JAVA_HOME/opt/module/jdk1.8.0_…
阅读更多...
【BUG】Docker启动MySQL报错

【BUG】Docker启动MySQL报错

个人主页&#xff1a;金鳞踏雨 个人简介&#xff1a;大家好&#xff0c;我是金鳞&#xff0c;一个初出茅庐的Java小白 目前状况&#xff1a;22届普通本科毕业生&#xff0c;几经波折了&#xff0c;现在任职于一家国内大型知名日化公司&#xff0c;从事Java开发工作 我的博客&am…
阅读更多...
隧道HTTP具备的条件

隧道HTTP具备的条件

作为一名专业的爬虫代理供应商&#xff0c;我们都知道使用代理是保证爬虫的高效性和稳定性的重要手段之一。而隧道代理则是近年来备受推崇的一种代理形式&#xff0c;它通过将请求通过隧道传输&#xff0c;可以有效地隐藏爬虫的真实IP地址&#xff0c;提高爬虫的反爬能力。 在…
阅读更多...
Java编程的未来：2023年值得关注的五个趋势

Java编程的未来：2023年值得关注的五个趋势

准备好进入Java编程这个不断发展的创新世界了吗&#xff1f;二十多年来&#xff0c;Java一直是编程世界不可或缺的一部分&#xff0c;其重要性始终没有改变。随着企业软件解决方案中对Java的需求持续增长&#xff0c;这一编程语言保持了其作为跨各种设备和集成系统创建复杂软件…
阅读更多...
iOS开发之查看静态库(.a/.framework)中包含的.o文件和函数符号（ar，nm命令）

iOS开发之查看静态库(.a/.framework)中包含的.o文件和函数符号（ar，nm命令）

.a/.framework其实是把编译生成的.o文件&#xff0c;打包成一个.a/.framework文件。a的意思是archive/归档的意思。 查看静态库.a文件包含的内容用下面的命令解压&#xff1a; ar x xxx.a 用ar命令打包静态库&#xff1a; 参数r是将后面的*.o或者*.a文件添加到目标文件中 参数…
阅读更多...
《数字图像处理-OpenCV/Python》连载（2）目录

《数字图像处理-OpenCV/Python》连载（2）目录

《数字图像处理-OpenCV/Python》连载&#xff08;2&#xff09;目录 本书京东优惠购书链接&#xff1a;https://item.jd.com/14098452.html 本书CSDN独家连载专栏&#xff1a;https://blog.csdn.net/youcans/category_12418787.html 第一部分 OpenCV-Python的基本操作 第1章 …
阅读更多...
5款黑科技软件，觉得有用的自行搜索下载

5款黑科技软件，觉得有用的自行搜索下载

分享是一种神奇的东西&#xff0c;它使快乐增大&#xff0c;它使悲伤减小&#xff0c;坚持分享一些好用的软件给大家&#xff0c;今天继续为大家带来五款神器软件。 屏幕共享——Deskreen ​ Deskreen是一款可以将你的电脑屏幕无线投射到任何设备上的软件&#xff0c;只要你的…
阅读更多...
python WSGI和ASGI的区别

python WSGI和ASGI的区别

用户到我们web应用中间经过的相关协议&#xff0c;具体介绍和pyhton相关的WSGI和ASGI&#xff0c;我先把结论列出来&#xff0c;详细描述请看下面介绍&#xff01; 请大家先记住这张图&#xff0c;带着问题和整个框架去看比较易于了解 CGI&#xff0c;WSGI&#xff0c;ASGI、…
阅读更多...
做不做软测都能学的技能，一招化解磁盘空间不足！

做不做软测都能学的技能，一招化解磁盘空间不足！

如&#xff0c;我有一台服务器&#xff0c;磁盘空间为 50g 现在&#xff0c;使用了一段时间之后&#xff0c;磁盘空间不够了 磁盘空间不够&#xff0c;这个时候&#xff0c;如果你再执行某些写入磁盘的操作就会报错&#xff0c;无法执行。 测试服务器磁盘空间不够&#xff0c;…
阅读更多...
HTTP与RPC的取舍

HTTP与RPC的取舍

HTTP与RPC的取舍 HTTP和RPC都是常用的网络通信协议&#xff0c;它们各有优劣。选择何种协议&#xff0c;主要取决于应用的需求和场景。 HTTP和RPC都有各自的优点和缺点&#xff0c;首先我们对两种协议进行一个总结。 HTTP协议图 HTTP的优点&#xff1a; 广泛的支持&#xff1…
阅读更多...
基于C++的QT实现贪吃蛇小游戏

基于C++的QT实现贪吃蛇小游戏

文章目录&#xff1a; 一&#xff1a;效果演示 二&#xff1a;实现思路 三&#xff1a;代码实现 widget.h widget.cpp main.cpp 一&#xff1a;效果演示 效果图◕‿◕✌✌✌ 代码下载 二&#xff1a;实现思路 通过按键控制蛇的移动&#xff0c;每吃一个商品蛇身就会加长…
阅读更多...
【TypeScript】声明文件

【TypeScript】声明文件

在 TypeScript 中&#xff0c;声明文件&#xff08;Declaration Files&#xff09;用于描述已有 JavaScript 代码库的类型信息&#xff0c;以便在 TypeScript 项目中使用这些代码库时获得类型支持。 当你在 TypeScript 项目中引用外部 JavaScript 模块或库时&#xff0c;可能会…
阅读更多...
uniapp离线打包apk - Android Studio

uniapp离线打包apk - Android Studio

uniapp 离线打包 基于uni-app的andiord 离线打包 开发工具及所需要的jar包​1.将下载的App离线SDK解压打开&#xff0c;找到HBuilder-Integrate-AS &#xff0c;在Android Studio打开2.打开HBuilder X&#xff0c;发行->原生app本地打包->生成本地打包app资源3.在“HBuil…
阅读更多...
最新文章

Copyright @ 2022~2023