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

目录

  • 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;
}

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

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

leecode1793 | 好子数组的最大分数 ｜ 求给高度矩阵最大值

leecode1793 | 好子数组的最大分数 ｜ 求给高度矩阵最大值

题目我就不念了&#xff0c;就一个字难理解&#xff0c;给的题总是这么难懂&#xff0c;总感觉出题人的语文是体育老师教的&#xff1f; 还有就是思维转变&#xff0c;才能能好的理解&#xff1f;一味的钻牛角尖死理解&#xff0c;效果不好 思维的转变 >悟性&#xff1f;&am…
阅读更多...
使用远程工具连接Mysql

使用远程工具连接Mysql

&#xff08;若想要远程连接Mysql需要下面解决四个问题&#xff09; 1、目标地址 直接查询 2、端口号 3306 3、防火墙关闭 [rootlocalhost date]# systemctl stop firewalld.service 4、授权mysql数据库root用户权限&#xff08;因为mysql开始不允许其他IP访问&#xff0…
阅读更多...
Docker 学习笔记

Docker 学习笔记

Play With Docker一个免费使用的基于web界面的Docker环境 常用docker命令 可使用docker COMMAND --help查看命令的用法 Docker镜像相关 1、docker image pull&#xff1a;用于下载镜像&#xff0c;镜像从远程镜像仓库服务的仓库中下载&#xff0c;默认从Docker Hub的仓库中拉…
阅读更多...
ssm基于Vue.js的在线购物系统的设计与实现论文

ssm基于Vue.js的在线购物系统的设计与实现论文

摘 要 随着科学技术的飞速发展&#xff0c;各行各业都在努力与现代先进技术接轨&#xff0c;通过科技手段提高自身的优势&#xff1b;对于在线购物系统当然也不能排除在外&#xff0c;随着网络技术的不断成熟&#xff0c;带动了在线购物系统&#xff0c;它彻底改变了过去传统的…
阅读更多...
OKR与敏捷开发、精益创业等方法如何协同工作？

OKR与敏捷开发、精益创业等方法如何协同工作？

在快速变化的市场环境中&#xff0c;企业需要更加灵活和高效地应对各种挑战。目标与关键成果法&#xff08;OKR&#xff09;、敏捷开发以及精益创业等方法&#xff0c;作为现代企业管理的重要工具&#xff0c;各自在推动企业发展、提高团队效率、优化产品迭代等方面发挥着不可或…
阅读更多...
社科赛斯考研：二十二载岁月铸辉煌，穿越周期的生命力之源

社科赛斯考研：二十二载岁月铸辉煌，穿越周期的生命力之源

在考研培训行业的浩瀚海洋中&#xff0c;社科赛斯考研犹如一艘稳健的巨轮&#xff0c;历经二十二载风礼&#xff0c;依然破浪前行。在考研市场竞争白热化与学生对于考研机构要求越来越高的双重影响下&#xff0c;社科赛斯考研却以一种分蘖成长的姿态&#xff0c;扎根、壮大&…
阅读更多...
基于springboot的mysql实现读写分离

基于springboot的mysql实现读写分离

前言: 首先思考一个问题:在高并发的场景中,关于数据库都有哪些优化的手段&#xff1f;常用的有以下的实现方法:读写分离、加缓存、主从架构集群、分库分表等&#xff0c;在互联网应用中,大部分都是读多写少的场景,设置两个库,主库和读库,主库的职能是负责写,从库主要是负责读…
阅读更多...
2核4G服务器优惠价格和性能测试，2024年

2核4G服务器优惠价格和性能测试，2024年

阿里云2核4G服务器租用优惠价格&#xff0c;轻量2核4G服务器165元一年、u1服务器2核4G5M带宽199元一年、云服务器e实例30元3个月&#xff0c;活动链接 aliyunfuwuqi.com/go/aliyun 活动链接如下图&#xff1a; 阿里云2核4G服务器优惠价格 轻量应用服务器2核2G4M带宽、60GB高效…
阅读更多...
【原创】基于分位数回归的卷积长短期神经网络(CNN-QRLSTM)回归预测的MATLAB实现

【原创】基于分位数回归的卷积长短期神经网络(CNN-QRLSTM)回归预测的MATLAB实现

基于分位数回归的卷积长短期神经网络&#xff08;CNN-QRLSTM&#xff09;是一种用于时间序列预测的深度学习模型&#xff0c;结合了卷积神经网络&#xff08;CNN&#xff09;和长短期记忆网络&#xff08;LSTM&#xff09;&#xff0c;并采用分位数回归技术进行预测。 这个模型…
阅读更多...
YOLOV9训练自己的数据集

YOLOV9训练自己的数据集

1.代码下载地址GitHub - WongKinYiu/yolov9: Implementation of paper - YOLOv9: Learning What You Want to Learn Using Programmable Gradient Information 2.准备自己的数据集 这里数据集我以SAR数据集为例 具体的下载链接如下所示&#xff1a; 链接&#xff1a;https:/…
阅读更多...
面试题小结

面试题小结

一、什么是虚拟dom 描述真实dom的js对象。 二、DOM操作——怎样添加、移除、移动、复制、创建和查找节点 &#xff08;1&#xff09;创建新节点 createDocumentFragment() //创建一个DOM片段 createElement() //创建一个具体的元素 createTextNode() //创建一个文本节…
阅读更多...
全栈的自我修养 ———— uniapp中加密方法

全栈的自我修养 ———— uniapp中加密方法

直接按部就班一步一步来 一、首先创建一个js文件填入AES二、创建加密解密方法三、测试 一、首先创建一个js文件填入AES 直接复制以下内容 /* CryptoJS v3.1.2 code.google.com/p/crypto-js (c) 2009-2013 by Jeff Mott. All rights reserved. code.google.com/p/crypto-js/wi…
阅读更多...
SpringCloud入门(1) Eureka Ribbon Nacos

SpringCloud入门(1) Eureka Ribbon Nacos

这里写目录标题 认识微服务SpringCloud 服务拆分和远程调用服务拆分案例实现远程调用 RestTemplate Eureka注册中心Eureka的结构和作用搭建eureka-server服务注册服务发现 Ribbon负载均衡 LoadBalancedLoadBalancerIntercepor源码解析负载均衡策略饥饿加载 Nacos注册中心安装与…
阅读更多...
【NLP】从变形金刚到Transfomer 01

【NLP】从变形金刚到Transfomer 01

Transformer是一种非常强大的模型&#xff0c;在自然语言处理&#xff08;NLP&#xff09;领域里引起了一场革命。 "从变形金刚到技术革命家&#xff0c;Transformer不再仅是儿时屏幕上的英雄。&#x1f916;✨ 在今天的AI领域&#xff0c;它变身成为自然语言处理的超级英…
阅读更多...
通过Anaconda安装Python会得到的重要文件夹

通过Anaconda安装Python会得到的重要文件夹

E:\Anaconda\路径下 Scripts 文件夹&#xff1a;该文件夹包含了可执行的Python脚本文件&#xff0c;例如pip和conda等命令行工具。【pip3.exe和django-admin.exe等】Lib 文件夹&#xff1a;该文件夹包含了Python的标准库和其他第三方库的源代码文件。【Lib下面的site-packages…
阅读更多...
PID算法原理分析及优化

PID算法原理分析及优化

今天为大家介绍一下经典控制算法之一的PID控制方法。PID控制方法从提出至今已有百余年历史&#xff0c;其由于结构简单、易于实现、鲁棒性好、可靠性高等特点&#xff0c;在机电、冶金、机械、化工等行业中应用广泛。 在大学期间&#xff0c;参加的智能汽车竞赛中就使用到了PI…
阅读更多...
Word文档密码设置：Python设置、更改及移除Word文档密码

Word文档密码设置：Python设置、更改及移除Word文档密码

给Word文档设置打开密码是常见的Word文档加密方式。为Word文档设置打开密码后&#xff0c;在打开该文档时&#xff0c;需要输入密码才能预览及编辑&#xff0c;为Word文档中的信息提供了有力的安全保障。如果我们需要对大量的Word文档进行加密、解密处理&#xff0c;Python是一…
阅读更多...
Python对象类型判断与函数重载

Python对象类型判断与函数重载

1. 判断对象类型 通过type函数可以知道对象的类型&#xff0c;示例代码如下&#xff1a; x Hello s type(x) print s x Hello s type(x) print s 2. 函数重载 在写函数时&#xff0c;时常遇到需要应付不同的参数类型以及不同的参数数量的情况。 在C中&#xff0c;通常定义多…
阅读更多...
安达发|化工涂料利用APS生产计划排程系统能改善什么问题

安达发|化工涂料利用APS生产计划排程系统能改善什么问题

化工涂料企业利用APS生产计划排程系统可以改善多个方面的问题&#xff1a; 1. 提高生产效率&#xff1a;APS系统能够根据订单需求和产能状况进行中长期排程&#xff0c;统一协调各分厂或车间的生产活动&#xff0c;从而实现均衡生产&#xff0c;减少因生产计划不合理导致的资源…
阅读更多...
Ubuntu 安装 KVM 虚拟化

Ubuntu 安装 KVM 虚拟化

1. Ubuntu 安装 KVM 虚拟化 KVM 是 Linux 内核中一个基于 hypervisor 的虚拟化模块&#xff0c;它允许用户在 Linux 操作系统上创建和管理虚拟机。 如果机器的CPU不支持硬件虚拟化扩展&#xff0c;是无法使用KVM(基于内核的虚拟机)直接创建和运行虚拟机的。此时最多只能使用…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023