数据结构：详解【栈和队列】的实现

目录

  • 1. 栈
    • 1.1 栈的概念及结构
    • 1.2 栈的实现
    • 1.3 栈的功能
    • 1.4 栈的功能的实现
    • 1.5 完整代码
  • 2. 队列
    • 2.1 队列的概念及结构
    • 2.2 队列的实现
    • 2.3 队列的功能
    • 2.4 队列的功能的实现
    • 2.5 完整代码

1. 栈

1.1 栈的概念及结构

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

压栈：栈的插入操作叫做进栈/压栈/入栈。入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。

在这里插入图片描述
在这里插入图片描述

1.2 栈的实现

栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾插和头删的实际复杂度为O(1)，是非常合适的。

在这里插入图片描述

1.3 栈的功能

  • 初始化栈
  • 销毁栈
  • 入栈
  • 出栈
  • 获取栈顶元素
  • 获取栈内有效元素的个数
  • 判断栈内是否为空，如果为空返回非0结果，不为空返回0

1.4 栈的功能的实现

（1）定义一个动态增长的栈

typedef int STDataType;

typedef struct Stack
{
	STDataType* a;
	STDataType top;//定义栈顶
	size_t capacity;//栈的容量
}ST;

（2）初始化栈

void StackInit(ST* ps)
{
	//初始化空间
	 ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);
	if (ps->a == NULL)
	{
		printf("malloc fail!\n");
		return;
	}

	ps->top = 0;
	ps->capacity = 4;//初始化4个空间
}

（3）销毁栈

void StackDestory(ST* ps)
{
	free(ps->a);
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;
}

（4）入栈（相当于顺序表的尾插）

void StackPush(ST* ps, STDataType x)
{
	//插入数据之前判断是否增容
	if (ps->top == ps->capacity)
	{
		STDataType* tmp = (STDataType*)realloc(ps->a, ps->capacity * sizeof(STDataType) * 2);
		if (tmp == NULL)
		{
			printf("realloc fail!\n");
			return;
		}
		else
		{
			ps->a = tmp;
			ps->capacity *= 2;
		}
	}

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

（5）出栈（相当于顺序表的头删）

void StackPop(ST* ps)
{
	assert(ps);//断言，栈内为空则终止程序

	ps->top--;
}

（6）获取栈顶元素

STDataType StackTop(ST* ps)
{
	assert(ps);//断言，栈内为空则终止程序
	assert(ps->top > 0);

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

（7）获取栈内有效元素的个数

int StackSize(ST* ps)
{
	assert(ps);

	return ps->top;
}

（8）判断栈内是否为空，如果为空返回非0结果，不为空返回0

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

	return ps->top == 0;
}

1.5 完整代码

Stack.h

#define _CRT_SECURE_NO_WARNINGS 

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

typedef int STDataType;

typedef struct Stack
{
	STDataType* a;
	STDataType top;//定义栈顶
	size_t capacity;//栈的容量
}ST;

//初始化栈
void StackInit(ST* ps);

//销毁栈
void StackDestory(ST* ps);

//从栈顶插入数据
void StackPush(ST* ps, STDataType x);

//从栈顶删除数据
void StackPop(ST* ps);

//获取栈顶元素
STDataType StackTop(ST* ps);

//获取栈内有效元素个数
int StackSize(ST* ps);

//判断栈内是否为空，如果为空返回非0结果，不为空返回0
bool StackEmpty(ST* ps);

Stack.c

#define _CRT_SECURE_NO_WARNINGS 

#include "Stack.h"

void StackInit(ST* ps)
{
	//初始化空间
	 ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);
	if (ps->a == NULL)
	{
		printf("malloc fail!\n");
		return;
	}

	ps->top = 0;
	ps->capacity = 4;//初始化4个空间
}

void StackDestory(ST* ps)
{
	free(ps->a);
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;
}

void StackPush(ST* ps, STDataType x)
{
	//插入数据之前判断是否增容
	if (ps->top == ps->capacity)
	{
		STDataType* tmp = (STDataType*)realloc(ps->a, ps->capacity * sizeof(STDataType) * 2);
		if (tmp == NULL)
		{
			printf("realloc fail!\n");
			return;
		}
		else
		{
			ps->a = tmp;
			ps->capacity *= 2;
		}
	}

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


void StackPop(ST* ps)
{
	assert(ps);//断言，栈内为空则终止程序

	ps->top--;
}

STDataType StackTop(ST* ps)
{
	assert(ps);//断言，栈内为空则终止程序
	assert(ps->top > 0);

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

int StackSize(ST* ps)
{
	assert(ps);

	return ps->top;
}

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

	return ps->top == 0;
}

Test.c

#define _CRT_SECURE_NO_WARNINGS 

#include "Stack.h"

void StackTest()
{
	ST st;
	StackInit(&st);
	StackPush(&st, 1);
	StackPush(&st, 2);
	StackPush(&st, 3);
	StackPush(&st, 4);

	//打印栈内的数据，由于不能破坏栈的特性，所以不能遍历
	while (!StackEmpty(&st))
	{
		printf("%d ", StackTop(&st));
		StackPop(&st);
	}

	StackDestory(&st);
}

int main()
{
	StackTest();

	return 0;
}

2. 队列

2.1 队列的概念及结构

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

2.2 队列的实现

队列也可以数组和链表的结构实现，使用单链表的结构实现更优一些。
因为如果使用数组的结构，出队列在数组头上出数据，这时需要挪动数据，时间复杂度为O(n)，效率会比较低。
而单链表的尾插和头删的时间复杂度为O（1），十分合适。
在这里插入图片描述

2.3 队列的功能

  • 初始化队列
  • 销毁队列
  • 入队列
  • 出队列
  • 获取队列头部元素
  • 获取队列尾部元素
  • 获取队列中有效元素的个数
  • 判断队列是否为空，为空返回非0，不为空返回0

2.4 队列的功能的实现

（1）定义一个队列

typedef int QTDataType;

typedef struct QNode
{
	struct QNode* next;
	QTDataType data;
}QNode;

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

（2）初始化队列

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

（3）销毁队列

void QueueDestory(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->head;
	while (cur)
	{
		cur = cur->next;
		free(cur);
	}
	pq->head = pq->tail = NULL;
}

（4）入队列(相当于单链表的尾插）

void QueuePush(Queue* pq, QTDataType x)
{
	assert(pq);

	QNode* newnode = (QTDataType*)malloc(sizeof(QTDataType));
	if (newnode == NULL)
	{
		printf("malloc fail!\n");
		return;
	}

	newnode->data = x;
	newnode->next = NULL;

	//第一个结点
	if (pq->tail == NULL)
	{
		pq->head = pq->tail = newnode;
	}
	//多个节点
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}

}

（5）出队列（相当于单链表的头删）

void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->head);

	//只有一个节点
	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;
	}
}

（6）获取队列头部元素

QTDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->head);

	return pq->head->data;
}

（7）获取队列尾部元素

QTDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->head);

	return pq->tail->data;
}

（8）获取队列中有效元素的个数

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

	return size;
}

（9）判断队列是否为空，为空返回非0，不为空返回0

int QueueEmpty(Queue* pq)
{
	assert(pq);

	return pq->head == NULL;
}

2.5 完整代码

Queue.h

#pragma once

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

typedef int QTDataType;

typedef struct QNode
{
	struct QNode* next;
	QTDataType data;
}QNode;

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

//初始化队列
void QueueInit(Queue* pq);

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

//队尾入队列
void QueuePush(Queue* pq, QTDataType x);

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

//获取队列头部元素
QTDataType QueueFront(Queue* pq);

//获取队列尾部元素
QTDataType QueueBack(Queue* pq);

//判断队列是否为空，为空返回非0，不为空返回0
int QueueEmpty(Queue* pq);

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

Queue.c

#define _CRT_SECURE_NO_WARNINGS 

#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)
	{
		cur = cur->next;
		free(cur);
	}
	pq->head = pq->tail = NULL;
}

void QueuePush(Queue* pq, QTDataType x)
{
	assert(pq);

	QNode* newnode = (QTDataType*)malloc(sizeof(QTDataType));
	if (newnode == NULL)
	{
		printf("malloc fail!\n");
		return;
	}

	newnode->data = x;
	newnode->next = NULL;

	//第一个结点
	if (pq->tail == NULL)
	{
		pq->head = pq->tail = newnode;
	}
	//多个节点
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}

}

void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->head);

	//只有一个节点
	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;
	}
}

int QueueEmpty(Queue* pq)
{
	assert(pq);

	return pq->head == NULL;
}

QTDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->head);

	return pq->head->data;
}

QTDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->head);

	return pq->tail->data;
}

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

	return size;
}

Test.c

#define _CRT_SECURE_NO_WARNINGS 

#include "Queue.h"

void QueueTest()
{
	Queue q;
	QueueInit(&q);
	
	QueuePush(&st, 1);
	QueuePush(&st, 2);
	QueuePush(&st, 3);
	QueuePush(&st, 4);
	
    //打印队列内的数据，由于不能破坏队列的特性，所以不能遍历
	while (!QueueEmpty(&st))
	{
		printf("%d ", QueueFront(&st));
		QueuePop(&st);
	}

	QueueDestory(&q);

}


int main()
{
	QueueTest();

	return 0;
}

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

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

相关文章

如何看待腾讯 QQ 浏览器抄袭 Arc

如何看待腾讯 QQ 浏览器抄袭 Arc

今天在 Reddit 的帖子上看到&#xff0c;QQ 浏览器抄袭了 Arc 而且还是 Arc 官方发布的 It looks very similar lol 看起来也太像了&#xff0c;笑死我了 稍微震惊了一下&#xff0c;带着疑惑&#xff0c;打开了 QQ 浏览器官网页 点击下载 ⬇️ 下载后打开 翻找了下&#xff0…
阅读更多...
2004-2022年各省化学需氧量数据（无缺失）

2004-2022年各省化学需氧量数据（无缺失）

2004-2022年各省化学需氧量数据&#xff08;无缺失&#xff09; 1、2004-2022年 2、范围&#xff1a;31省 3、指标&#xff1a;化学需氧量 4、来源&#xff1a;各省年鉴、国家统计局、环境年鉴 5、指标解释&#xff1a;化学需氧量(COD)排放量指工业废水中COD排放量与生活污…
阅读更多...
java 泛型（下）

java 泛型（下）

本篇文章主要说明的是类型通配符、可变参数、可变参数的使用等。 在学习之前&#xff0c;希望能对泛型有个大概了解&#xff0c;可参考链接 java 泛型&#xff08;上&#xff09;-CSDN博客 也希望对泛型类、泛型接口、泛型方法有个大概的认识及使用&#xff0c;可参考链接 j…
阅读更多...
【保姆级教程】YOLOv8_Track多目标跟踪，快速运行

【保姆级教程】YOLOv8_Track多目标跟踪，快速运行

一、YOLOV8环境准备 1.1 下载安装最新的YOLOv8代码 仓库地址&#xff1a; https://github.com/ultralytics/ultralytics1.2 配置环境 pip install -r requirements.txt -i https://pypi.tuna.tsinghua.edu.cn/simple二、下载测试视频&#xff0c;预训练权重 测试视频 链接&am…
阅读更多...
nuc980下 RTL8188EUS_wifi移植过程

nuc980下 RTL8188EUS_wifi移植过程

我使用的nuc980型号为NUC980DK61YC&#xff0c;内核版本为"linux 4.4.115" &#xff0c;以下过程是在自己单片机上移植的过程&#xff0c;仅供参考&#xff0c;不同配置环境可能会有不同的坑需要踩&#xff0c;希望会对各位小伙伴有帮助。 1.驱动添加与调整 注意&a…
阅读更多...
[综述笔记]A Survey on Deep Learning for Neuroimaging-Based Brain Disorder Analysis

[综述笔记]A Survey on Deep Learning for Neuroimaging-Based Brain Disorder Analysis

论文网址&#xff1a;Frontiers | A Survey on Deep Learning for Neuroimaging-Based Brain Disorder Analysis (frontiersin.org) 英文是纯手打的&#xff01;论文原文的summarizing and paraphrasing。可能会出现难以避免的拼写错误和语法错误&#xff0c;若有发现欢迎评论…
阅读更多...
NET 自定义控件

NET 自定义控件

如果添加 Category&#xff0c; 自定义控件&#xff0c;会放在杂项中
阅读更多...
03-Java面试题八股文-----java基础——10题

03-Java面试题八股文-----java基础——10题

41、HashMap 的长度为什么是 2 的 N 次方呢&#xff1f; 为了能让 HashMap 存数据和取数据的效率高&#xff0c;尽可能地减少 hash 值的碰撞&#xff0c;也就是说尽量把数据能均匀的分配&#xff0c;每个链表或者红黑树长度尽量相等。 我们首先可能会想到 % 取模的操作来实现。…
阅读更多...
6 修改主机名和HOSTS文件

6 修改主机名和HOSTS文件

后期我们会配置多台服务器&#xff0c;那么每台服务器我们都会给定一个主机名&#xff0c;方便后期通过主机名进行访问。主机名的修改我们可以在安装操作系统时对其修改&#xff0c;如果忘记了&#xff0c;就可以修改配置文件完成&#xff0c;像后期我们进行虚拟机克隆后&#…
阅读更多...
Unity Toggle与Toggle Group的妙用

Unity Toggle与Toggle Group的妙用

Toggle与Toggle Group结合使用&#xff0c;妙处多多。 因为在同一Toggle Group内只有一个Toggle可以被选中&#xff0c;那么对于我们要创建单选按钮组、游戏的一些开关、暗夜模式、筛选不同显示内容等功能都非常好用。 比如我要实现通过点击不同按钮,从而筛选显示不同内容&am…
阅读更多...
基于springboot的“漫画之家”系统

基于springboot的“漫画之家”系统

目录 背景 技术简介 系统简介 界面浏览 背景 随着科技的不断进步&#xff0c;计算机已经变成了人们日常生活和工作不可或缺的工具。在这样的环境下&#xff0c;互联网技术被广泛运用于各个领域&#xff0c;以提升工作和生活的效率&#xff0c;推动了网络信息技术的迅猛发展…
阅读更多...
物联网和工业物联网的区别——青创智通

物联网和工业物联网的区别——青创智通

工业物联网解决方案-工业IOT-青创智通 物联网&#xff08;IoT&#xff09;和工业物联网&#xff08;IIoT&#xff09;作为现代科技的重要分支&#xff0c;正在逐渐渗透到我们的日常生活和工业生产中。它们的应用范围广泛&#xff0c;涵盖了从智能家居到自动化工厂的多个领域。…
阅读更多...
基于SSM的土家风景文化管理平台（有报告）。Javaee项目。ssm项目。

基于SSM的土家风景文化管理平台（有报告）。Javaee项目。ssm项目。

演示视频&#xff1a; 基于SSM的土家风景文化管理平台&#xff08;有报告&#xff09;。Javaee项目。ssm项目。 项目介绍&#xff1a; 采用M&#xff08;model&#xff09;V&#xff08;view&#xff09;C&#xff08;controller&#xff09;三层体系结构&#xff0c;通过Spri…
阅读更多...
python_BeautifulSoup爬取汽车评论数据

python_BeautifulSoup爬取汽车评论数据

爬取的网站&#xff1a; 完整代码在文章末尾 https://koubei.16888.com/57233/0-0-0-2 使用方法&#xff1a; from bs4 import BeautifulSoup 拿到html后使用find_all()拿到文本数据&#xff0c;下图可见&#xff0c;数据标签为&#xff1a; content_text soup.find_all…
阅读更多...
微信群发技巧有哪几种？

微信群发技巧有哪几种？

群发是指通过微信平台对特定受众进行大规模信息发布的过程&#xff0c;如节日祝福、活动促销等。随着科技的不断发展&#xff0c;群发的定义已不再仅限于手机信息群发或短信群发。如今&#xff0c;微信内置的群发功能也被广泛应用。 一、微信群发的操作步骤 1. 进入微信&…
阅读更多...
Matlab 双目相机标定（内置函数）

Matlab 双目相机标定（内置函数）

文章目录 一、简介二、实现代码三、实现效果参考资料一、简介 相机标定的目的就是要找到从世界坐标转换为图像坐标所用到的投影P矩阵各个系数（即相机的内参与外参）。具体过程如下所述： 1、首先我们需要获取一个已知图形的图像（这里我们使用MATLAB所提供的数据）。 2、找到同…
阅读更多...
基于Springboot的疫情物资管理系统（有报告）。Javaee项目，springboot项目。

基于Springboot的疫情物资管理系统（有报告）。Javaee项目，springboot项目。

演示视频&#xff1a; 基于Springboot的疫情物资管理系统&#xff08;有报告&#xff09;。Javaee项目&#xff0c;springboot项目。 项目介绍&#xff1a; 采用M&#xff08;model&#xff09;V&#xff08;view&#xff09;C&#xff08;controller&#xff09;三层体系结构…
阅读更多...
Java项目：70 ssm小学生课外知识学习网站+vue

Java项目：70 ssm小学生课外知识学习网站+vue

作者主页&#xff1a;舒克日记 简介&#xff1a;Java领域优质创作者、Java项目、学习资料、技术互助 文中获取源码 项目介绍 管理员&#xff1b;首页、个人中心、医护人员管理、科室管理、病人管理、病房管理、病人信息管理、病历管理、医嘱管理、手术安排管理、药品信息管理、…
阅读更多...
@MapperScan注解使用

@MapperScan注解使用

要了解MapperScan注解得先去了解Mapper注解 1、Mapper注解&#xff1a; 作用&#xff1a;在接口类上添加了Mapper&#xff0c;在编译之后会生成相应的接口实现类 添加位置&#xff1a;接口类上面 如果想要每个接口都要变成实现类&#xff0c;那么需要在每个接口类上加上Mappe…
阅读更多...
C++小白学力扣之977.有序数组的平方

C++小白学力扣之977.有序数组的平方

题目介绍 思路分析 首先&#xff0c;我们拿到一个数组题&#xff0c;根据题目。我们就能确定我们要运用什么方法来解答它&#xff0c;一般有两种方法&#xff0c;第一种是大家都能想到的的&#xff0c;暴力求解法&#xff0c;本题&#xff0c;如果使用暴力法&#xff0c;就是将…
阅读更多...
最新文章

Copyright @ 2022~2023