【数据结构】栈和队列超详解！(Stack Queue)

文章目录

  • 前言
  • 一、栈
    • 1、栈的基本概念
    • 2、栈的实现（数组实现）
    • 3、栈的基本操作
      • 3.1 栈的结构设计
      • 3.2 栈常见的基本函数接口
    • 4、栈的实现
      • 4.1 初始化栈
      • 4.2 栈的销毁
      • 4.3 入栈
      • 4.4 出栈
      • 4.5 判空
      • 4.6 长度
      • 4.7 获取栈顶元素
  • 完整代码
      • Stack.h
      • Stack.c
      • Test.c
  • 二、队列
    • 1、队列的结构及概念
    • 2、队列的实现（单链表实现）
      • 1、队列的链式结构设计
      • 2、常用的功能接口
        • 2.1、初始化队列
        • 2.2、销毁队列
        • 2.3、入队列
        • 2.4、出队列
        • 2.5、获取队列头部元素
        • 2.6、获取队列尾部元素
        • 2.7、判空
        • 2.8、获取有效元素个数
    • 完整代码
      • Queue.h
      • Queue.c
      • Test.c

前言

在这里插入图片描述

一、栈

1、栈的基本概念

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

在这里插入图片描述

2、栈的实现（数组实现）

栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小
在这里插入图片描述

3、栈的基本操作

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

3.1 栈的结构设计

typedef int STDataType;//方便修改类型
typedef struct Stack
{STDataType* a;int top;int capacity;
}ST;

3.2 栈常见的基本函数接口

//初始化
void STInit(ST* pst);
//销毁栈
void STDestroy(ST* pst);
//入栈
void STPush(ST* pst, STDataType x);
//出栈
void STPop(ST* pst);
//判空
bool STEmpty(ST* pst);
//长度
int STSize(ST* pst);
//栈顶
STDataType STTop(ST* pst);

4、栈的实现

4.1 初始化栈

//初始化
void STInit(ST* pst)
{assert(pst);pst->a = NULL;pst->top = 0;//指向栈顶下一个元素,若等于-1则指向栈顶元素，两种任选pst->capacity = 0;
}

4.2 栈的销毁

//销毁栈
void STDestroy(ST* pst)
{assert(pst);tree(pst->a);pst->a = NULL;pst->top = 0;pst->capacity = 0;
}

4.3 入栈

在这里插入图片描述
代码：

void STPush(ST* pst, STDataType x)
{assert(pst);//判断栈是否已满，满了就扩容if (pst->top == pst->capacity){//使用三目运算符进行第一次开辟空间和后续扩容空间int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * newcapacity);//判断realloc是否开辟成功if (tmp == NULL){perror("realloc fail");return;}//赋新值pst->a = tmp;pst->capacity = newcapacity;}//插入pst->a[pst->top] = x;pst->top++;
}

4.4 出栈

在这里插入图片描述
代码：

//出栈
void STPop(ST* pst)
{assert(pst);assert(pst->top > 0);pst->top--;
}

4.5 判空

//判空
bool STEmpty(ST* pst)
{assert(pst);  //返回值为0为假，非零为真return pst->top == 0;
}

4.6 长度

//长度
int STSize(ST* pst)
{assert(pst);return pst->top;
}

4.7 获取栈顶元素

注意：若栈顶指针初始化为pst->top = 0，即栈顶指针指向栈顶元素的下一个位置，则入栈操作变为pst->a[pst->top++]，出栈操作为pst->a[- -pst->top]。因为栈顶指针若初始化为 0 时，则栈顶指针始终指向顺序栈将要入栈的位置，也就是栈顶指针的下标就是入栈元素的下标。

//栈顶
STDataType STTop(ST* pst)
{assert(pst);return pst->a[pst->top - 1];
}

完整代码

Stack.h

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>typedef int STDataType;
typedef struct Stack
{STDataType* a;int top;int capacity;
}ST;//初始化
void STInit(ST* pst);
//销毁栈
void STDestroy(ST* pst);
//入栈
void STPush(ST* pst, STDataType x);
//出栈
void STPop(ST* pst);
//判空
bool STEmpty(ST* pst);
//长度
int STSize(ST* pst);
//栈顶
STDataType STTop(ST* pst);

Stack.c

#include"Stack.h"//初始化
void STInit(ST* pst)
{assert(pst);pst->a = NULL;pst->top = 0;//指向栈顶下一个元素pst->capacity = 0;
}
//销毁栈
void STDestroy(ST* pst)
{assert(pst);tree(pst->a);pst->a = NULL;pst->top = 0;pst->capacity = 0;
}
//入栈
void STPush(ST* pst, STDataType x)
{assert(pst);if (pst->top == pst->capacity){int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * newcapacity);if (tmp == NULL){perror("realloc fail");return;}pst->capacity = newcapacity;pst->a = tmp;}pst->a[pst->top] = x;pst->top++;	
}
//出栈
void STPop(ST* pst)
{assert(pst);assert(pst->top > 0);pst->top--;
}
//判空
bool STEmpty(ST* pst)
{assert(pst);return pst->top == 0;
}
//长度
int STSize(ST* pst)
{assert(pst);return pst->top;
}
//栈顶
STDataType STTop(ST* pst)
{assert(pst);return pst->a[pst->top - 1];
}

Test.c

#include"Stack.h"int main()
{ST st;//初始化STInit(&st);//插入+删除STPush(&st, 1);STPush(&st, 2);STPush(&st, 3);STPush(&st, 4);STPush(&st, 5);STPop(&st);STPop(&st);//长度STSize(&st);//栈顶STTop(&st);//销毁STDestroy(&st);return 0;
}

二、队列

1、队列的结构及概念

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

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

队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。
在这里插入图片描述
下面话不多说，直接开始代码实现

1、队列的链式结构设计

//链式结构 表示队列
typedef int QDataType;
typedef struct QueueNode
{struct QueueNode* next;QDataType val;                                                                          
}QNode;
//队列的结构
typedef struct Queue
{QNode* phead;QNode* ptail;int size;
}Queue;

2、常用的功能接口

//初始化
void QueueInit(Queue* pq);
//销毁队列
void QueueDeatroy(Queue* pq);
//队尾入列
void QueuePush(Queue* pq, QDataType x);
//队头出列
void QueuePop(Queue* pq);
//获取队列头部元素
QDataType QueueFront(Queue* pq);
//获取队列尾部元素
QDataType QueueBack(Queue* pq);
//检测队列是否为空，如果为空返回非零结果，如果非空返回0 
bool QueueEmpty(Queue* pq);
//获取队列中有效元素个数
int QueueSize(Queue* pq);
2.1、初始化队列

只需要将头尾指针都指向空即可，元素个数为零

//初始化
void QueueInit(Queue* pq)
{assert(pq);pq->phead = NULL;pq->ptail = NULL;pq->size = 0;
}
2.2、销毁队列

遍历链表，从头到尾依次删除结点，最后将头尾指针指向空，元素个数为0。

//销毁队列
void QueueDeatroy(Queue* pq)
{assert(pq);QNode* cur = pq->phead;while (cur){QNode* next = cur->next;free(cur);cur = next;}pq->phead = NULL;pq->ptail = NULL;pq->size = 0;}
2.3、入队列

创建新节点，若队列为空，则将头指针和尾指针都指向新创建的节点，若不为空，则尾插，因为是链式存储，所以和单链表的尾插一样，将尾指针的next指向该节点，再把该节点设为新的尾节点

void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail");return;}newnode->val = x;newnode->next = NULL;if (pq->ptail == NULL){pq->ptail = pq->phead = newnode;}else{pq->ptail->next = newnode;pq->ptail = newnode;}pq->size++;
}
2.4、出队列

注意：出列要考虑队列是空还是只有一个结点又或者有多个结点，为空则在代码第一步就报错，若只有一个结点，则直接删除该结点，并将头尾俩指针指向空，若不止一个结点，可以创建一个临时指针来记录当前头指针，然后尾指针往后遍历，再free掉创建的临时指针，并置空

void QueuePop(Queue* pq)
{assert(pq);assert(pq->phead);QNode* del = pq->phead;pq->phead = pq->phead->next;free(del);del = NULL;if (pq->phead == NULL)pq->ptail = NULL;pq->size--;
}
2.5、获取队列头部元素

断言，然后直接返回队头指针指向的节点元素

//获取队列头部元素
QDataType QueueFront(Queue* pq)
{assert(pq);assert(pq->phead);return pq->phead->val;
}
2.6、获取队列尾部元素

也是一样的，直接返回队尾指针指向的节点元素

//获取队列尾部元素
QDataType QueueBack(Queue* pq)
{assert(pq);assert(pq->phead);return pq->ptail->val;
}
2.7、判空

检测队列是否为空，如果为空返回非零结果，如果非空返回0


bool QueueEmpty(Queue* pq)
{assert(pq);return pq->phead == NULL;
}
2.8、获取有效元素个数
//获取队列中有效元素个数
int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}

完整代码

Queue.h

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>//链式结构 表示队列
typedef int QDataType;
typedef struct QueueNode
{struct QueueNode* next;QDataType val;                                                                          
}QNode;
//队列的结构
typedef struct Queue
{QNode* phead;QNode* ptail;int size;
}Queue;
//初始化
void QueueInit(Queue* pq);
//销毁队列
void QueueDeatroy(Queue* pq);
//队尾入列
void QueuePush(Queue* pq, QDataType x);
//队头出列
void QueuePop(Queue* pq);
//获取队列头部元素
QDataType QueueFront(Queue* pq);
//获取队列尾部元素
QDataType QueueBack(Queue* pq);
//检测队列是否为空，如果为空返回非零结果，如果非空返回0 
bool QueueEmpty(Queue* pq);
//获取队列中有效元素个数
int QueueSize(Queue* pq);

Queue.c

#include"Queue.h"//初始化
void QueueInit(Queue* pq)
{assert(pq);pq->phead = NULL;pq->ptail = NULL;pq->size = 0;
}
//销毁队列
void QueueDeatroy(Queue* pq)
{assert(pq);QNode* cur = pq->phead;while (cur){QNode* next = cur->next;free(cur);cur = next;}pq->phead = NULL;pq->ptail = NULL;pq->size = 0;}
//队尾入列
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail");exit(-1);}newnode->next = NULL;newnode->val = x;if (pq->ptail == NULL){pq->phead = pq->ptail = newnode;}else{//现在newnode是新的尾结点pq->ptail->next = newnode;pq->ptail = newnode;}pq->size++;
}
//队头出列
void QueuePop(Queue* pq)
{assert(pq);assert(pq->phead); //保存当前节点QNode* tmp = pq->phead;//phead往下走pq->phead = pq->phead->next;free(tmp);tmp = NULL;if (pq->phead = NULL){pq->ptail = NULL;}pq->size--;
}
//获取队列头部元素
QDataType QueueFront(Queue* pq)
{assert(pq);assert(pq->phead);return pq->phead->val;
}
//获取队列尾部元素
QDataType QueueBack(Queue* pq)
{assert(pq);assert(pq->phead);return pq->ptail;
}
//检测队列是否为空，如果为空返回非零结果，如果非空返回0 
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->phead == NULL;
}
//获取队列中有效元素个数
int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}

Test.c

#include"Queue.h"int main()
{Queue q;QueueInit(&q);QueuePush(&q, 1);QueuePush(&q, 2);QueuePush(&q, 3);while (!QueueEmpty(&q)){printf("%d ", QueueFront(&q));QueuePop(&q);}QueueDeatroy(&q);return 0;}

在这里插入图片描述

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

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

相关文章

【JavaWeb学习专栏 | CSS篇】css简单介绍 css常用选择器集锦

【JavaWeb学习专栏 | CSS篇】css简单介绍 css常用选择器集锦

个人主页&#xff1a;[兜里有颗棉花糖(https://xiaofeizhu.blog.csdn.net/) 欢迎 点赞&#x1f44d; 收藏✨ 留言✉ 加关注&#x1f493;本文由 兜里有颗棉花糖 原创 收录于专栏【JavaWeb学习专栏】【Java系列】 希望本文内容可以帮助到大家&#xff0c;一起加油吧&#xff01;…
阅读更多...
Ubuntu安装向日葵【远程控制】

Ubuntu安装向日葵【远程控制】

文章目录 引言下载向日葵安装向日葵运行向日葵卸载向日葵参考资料 引言 向日葵是一款非常好用的远程控制软件。这一篇博文介绍了如何在 Ubuntu Linux系统 中安装贝瑞向日葵。&#x1f3c3;&#x1f4a5;&#x1f4a5;&#x1f4a5;❗️ 下载向日葵 向日葵官网: https://sunl…
阅读更多...
CAN总线协议编程实例

CAN总线协议编程实例

1. can.h #ifndef __CAN_H #define __CAN_H#include "./SYSTEM/sys/sys.h"/******************************************************************************************/ /* CAN 引脚 定义 */#define CAN_RX_GPIO_PORT GPIOA #define CAN_RX_GPI…
阅读更多...
unity 2d 入门 飞翔小鸟 死亡 显示GameOver（十四)

unity 2d 入门 飞翔小鸟 死亡 显示GameOver（十四)

1、添加Img create->ui->img 把图片拖进去 2、和分数一样、调整位置 3、修改角色脚本 using System.Collections; using System.Collections.Generic; using UnityEngine;public class Fly : MonoBehaviour {//获取小鸟&#xff08;刚体&#xff09;private Rigidbod…
阅读更多...
在springboot中引入参数校验

在springboot中引入参数校验

一、概要 一般我们判断前端传过来的参数&#xff0c;需要对某些值进行判断&#xff0c;是否满足条件。 而springboot相关的参数校验注解&#xff0c;可以解决我们这个问题。 二、快速开始 首先&#xff0c;我用的springboot版本是 3.1.5 引入参数校验相关依赖 <!--1…
阅读更多...
ArkUI Button组件

ArkUI Button组件

Button 1.声明button组件 Button(label?:ResourceStr) label是按钮上面显示的文字 如果不传入label 则需要在内部嵌套其他组件 内部嵌套其他组件 可以放入icon图标来构建自己想要的样式 按钮类型 按钮使用type(ButtonType.xxx)属性来设置&#xff0c;xxx的类型分为三种 1.…
阅读更多...
无人机自动停机坪的多样化选择

无人机自动停机坪的多样化选择

随着巡查无人机的广泛应用&#xff0c;无人机自动停机坪成为一项重要的支持设施&#xff0c;主要用于提供停放、充电/换电、机身保护以及气象监测等功能。尽管许多人认为无人机自动停机坪只是一个简单的箱体结构&#xff0c;但实际上&#xff0c;国内无人机自动停机坪产品在外观…
阅读更多...
ky10 server x86在线安装ffmpeg

ky10 server x86在线安装ffmpeg

命令 yum install -y ffmpeg
阅读更多...
Android View.inflate 和 LayoutInflater.from(this).inflate 的区别

Android View.inflate 和 LayoutInflater.from(this).inflate 的区别

前言 两个都是布局加载器&#xff0c;而View.inflate是对 LayoutInflater.from(context).inflate的封装&#xff0c;功能相同&#xff0c;案例使用了dataBinding。 View.inflate(context, layoutResId, root) LayoutInflater.from(context).inflate(layoutResId, root, fals…
阅读更多...
HarmonyOS开发工具DevEco Studio的下载和安装

HarmonyOS开发工具DevEco Studio的下载和安装

一、DevEco Studio概述 一、下载安装鸿蒙应用开发工具DevEco Studio 开发鸿蒙应用可以从鸿蒙系统上运行第一个程序Hello World开始。 为了得到这个Hello World&#xff0c;你需要得到这个Hello World的源代码&#xff0c;源代码是用人比较容易看得懂的计算机编程语言规范写的…
阅读更多...
总结一篇本地idea配合阿里云服务器使用docker

总结一篇本地idea配合阿里云服务器使用docker

idea打包打镜像发到阿里云服务器 先说一下使用docker desktop软件怎么使用 1.下载docker desktop官网&#xff0c;先注册个账号吧&#xff0c;后面桌面软件登录会用到&#xff08;当然&#xff0c;配合这个软件使用需要科学上网&#xff09; 安装这个要配合wsl使用&#xf…
阅读更多...
Spring Bean基础

Spring Bean基础

写在最前面: 本文运行的示例在我github项目中的spring-bean模块&#xff0c;源码位置: spring-bean 前言 为什么要先掌握 Spring Bean 的基础知识&#xff1f; 我们知道 Spring 框架提供的一个最重要也是最核心的能力就是管理 Bean 实例。以下是其原因&#xff1a; 核心组件…
阅读更多...
静态SOCKS5的未来发展趋势和新兴应用场景

静态SOCKS5的未来发展趋势和新兴应用场景

随着网络技术的不断发展和进步&#xff0c;静态SOCKS5代理也在不断地完善和发展。未来&#xff0c;静态SOCKS5代理将会呈现以下发展趋势和新兴应用场景。 一、发展趋势 安全性更高&#xff1a;随着网络安全问题的日益突出&#xff0c;用户对代理服务器的安全性要求也越来越高…
阅读更多...
SQL语句的执行顺序怎么理解？

SQL语句的执行顺序怎么理解？

SQL语句的执行顺序怎么理解&#xff1f; 我们常常会被SQL其书写顺序和执行顺序之间的差异所迷惑。理解这两者的区别&#xff0c;对于编写高效、可靠的SQL代码至关重要。今天&#xff0c;让我们用一些生动的例子和场景来深入探讨SQL的执行顺序。 一、书写顺序 VS 执行顺序 SQ…
阅读更多...
SVN修改已提交版本的日志方法

SVN修改已提交版本的日志方法

1.在工做中一直是使用svn进行項目的版本控制的&#xff0c;有时候因为提交匆忙&#xff0c;或是忘了添加Log&#xff0c;或是Log内容有错误。遇到此类状况&#xff0c;想要在查看项目的日志时添加log或是修改log内容&#xff0c;遇到以下错误&#xff1a; Repository has not b…
阅读更多...
openEuler 22.03 升级openssh9.5

openEuler 22.03 升级openssh9.5

安装telnet 进行下面操作前&#xff0c;务必确保telnet服务安装成功。 安装xinetd yum install xinetd -y安装telnet服务&#xff0c;下载地址下载地址 rpm -ivh telnet-0.17-86.aarch64.rpm rpm -ivh telnet-server-0.17-86.aarch64.rpm重启 service xinetd restart确保能…
阅读更多...
php实现个性化域名(短网址)和个性化登录模版的解决方案

php实现个性化域名(短网址)和个性化登录模版的解决方案

在PHP中&#xff0c;个性化域名通常指的是根据用户或业务需求动态生成具有特定规律的子域名。实现个性化域名的方法主要依赖于服务器配置和路由规则。下面是一些基本的步骤和考虑因素&#xff0c;以帮助你了解如何个性化域名&#xff0c;并了解这样做的好处。 如何实现个性化域…
阅读更多...
基于java swing 药品销售管理系统

基于java swing 药品销售管理系统

大家好&#xff0c;我是DeBug&#xff0c;很高兴你能来阅读&#xff01;作为一名热爱编程的程序员&#xff0c;我希望通过这些教学笔记与大家分享我的编程经验和知识。在这里&#xff0c;我将会结合实际项目经验&#xff0c;分享编程技巧、最佳实践以及解决问题的方法。无论你是…
阅读更多...
PHP对接企业微信

PHP对接企业微信

前言 最近在做项目中&#xff0c;要求在后台管理中有企业微信管理的相关功能。相关准备工作&#xff0c;需要准备好企业微信账号&#xff0c;添加自建应用&#xff0c;获得相应功能的权限&#xff0c;以及agentid、secre等。 参考文档&#xff1a; 企业微信开发文档 功能实现 因…
阅读更多...
经典目标检测YOLO系列(一)引言_目标检测架构

经典目标检测YOLO系列(一)引言_目标检测架构

经典目标检测YOLO系列(一)引言_目标检测架构 一个常见的目标检测网络&#xff0c;其本身往往可以分为一下三大块&#xff1a; Backbone network&#xff0c;即主干网络&#xff0c;是目标检测网络最为核心的部分&#xff0c;backbone选择的好坏&#xff0c;对检测性能影响是十…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023