链式队列的结构设计及基本操作的实现(初始化,入队,出队,获取元素个数,判空,清空,销毁)

本文主要是介绍链式队列的结构设计及基本操作的实现(初始化,入队,出队,获取元素个数,判空,清空,销毁),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

一.链式队列的设计思想

二.链式队列的结构设计

三.链式队列的实现

四.链式队列的总结


一.链式队列的设计思想

首先一定要理解设计的初衷,就是队头队尾的位置要满足怎么快怎么设计.那么分析如下:

最终我们敲定了入队,出队的时间复杂度都为O(1)的一种设计,也就是第四种设计;当然,头节点的数据域不使用,所以我们设计链式队列的头节点的时候删除数据域即可,链式队列的结构设计如下:

二.链式队列的结构设计

typedef struct LPNode//数据节点{int data;//数据struct LPNode* next;//后继指针
}LPNode;typedef struct HNode //链式队列的头节点{struct LPNode* front;//队头指针,指向第一个数据节点struct LPNode* rear;//队尾指针,指向最后一个数据节点
}HNode ,*PLQueue;

三.链式队列的实现

//初始化
void InitQueue(PLQueue pq)
{assert(pq != NULL);if (pq == NULL)return;pq->front = NULL;pq->rear = NULL;}//入队;
bool Push(PLQueue pq, int val)
{assert(pq != NULL);if (pq == NULL)return false;//申请节点LPNode* p = (LPNode*)malloc(sizeof(LPNode));p->data = val;p->next = NULL;//p->next=pq->rear->next;//插入if (IsEmpty(pq))//第一次入队{pq->front = p;pq->rear = p;}else{pq->rear->next = p;//将P插入到队尾pq->rear = p;//更新队尾指针}return true;
}//出队,获取队头的值并且删除
bool Pop(PLQueue pq, int* rtval)
{assert(pq != NULL);if (pq == NULL)return false;if (IsEmpty(pq)){return false;}*rtval = pq->front->data;//删除第一个节点LPNode* p = pq->front;pq->front = p->next;free(p);if (pq->front == NULL)//删除最后一个节点{pq->rear = NULL;}return true;
}//获取队头元素的值但不删除
bool GetTop(PLQueue pq, int* rtval)
{assert(pq != NULL);if (pq == NULL)return false;if (IsEmpty(pq)){return false;}*rtval = pq->front->data;return true;
}//获取长度
int GetLength(PLQueue pq)
{assert(pq != NULL);if (pq == NULL)return -1;int count = 0;for (LPNode* p = pq->front; p != NULL; p = p->next){count++;}return count;}//判空
bool IsEmpty(PLQueue pq)
{assert(pq != NULL);if (pq == NULL)return false;return pq->front == NULL;
}//销毁
void Destroy(PLQueue pq)
{assert(pq != NULL);if (pq == NULL)return;LPNode* p;while (pq->front != NULL)//总是删除第一个数据节点{p = pq->front;pq->front = p->next;free(p);}pq->rear = NULL;
}

四.链式队列的总结

1.带头节点,队头为第一个数据节点,队尾在最后一个数据节点
2.头节点为一个队头指针,一个队尾指针,增加队尾指针可以让入队的时间复杂度为O(1)

这篇关于链式队列的结构设计及基本操作的实现(初始化,入队,出队,获取元素个数,判空,清空,销毁)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/447219

相关文章

Python实现图片分割的多种方法总结

《Python实现图片分割的多种方法总结》图片分割是图像处理中的一个重要任务,它的目标是将图像划分为多个区域或者对象,本文为大家整理了一些常用的分割方法,大家可以根据需求自行选择... 目录1. 基于传统图像处理的分割方法(1) 使用固定阈值分割图片(2) 自适应阈值分割(3) 使用图像边缘检测分割(4)

Android实现在线预览office文档的示例详解

《Android实现在线预览office文档的示例详解》在移动端展示在线Office文档(如Word、Excel、PPT)是一项常见需求,这篇文章为大家重点介绍了两种方案的实现方法,希望对大家有一定的... 目录一、项目概述二、相关技术知识三、实现思路3.1 方案一:WebView + Office Onl

C# foreach 循环中获取索引的实现方式

《C#foreach循环中获取索引的实现方式》:本文主要介绍C#foreach循环中获取索引的实现方式,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录一、手动维护索引变量二、LINQ Select + 元组解构三、扩展方法封装索引四、使用 for 循环替代

Spring Security+JWT如何实现前后端分离权限控制

《SpringSecurity+JWT如何实现前后端分离权限控制》本篇将手把手教你用SpringSecurity+JWT搭建一套完整的登录认证与权限控制体系,具有很好的参考价值,希望对大家... 目录Spring Security+JWT实现前后端分离权限控制实战一、为什么要用 JWT?二、JWT 基本结构

Java实现优雅日期处理的方案详解

《Java实现优雅日期处理的方案详解》在我们的日常工作中,需要经常处理各种格式,各种类似的的日期或者时间,下面我们就来看看如何使用java处理这样的日期问题吧,感兴趣的小伙伴可以跟随小编一起学习一下... 目录前言一、日期的坑1.1 日期格式化陷阱1.2 时区转换二、优雅方案的进阶之路2.1 线程安全重构2

Android实现两台手机屏幕共享和远程控制功能

《Android实现两台手机屏幕共享和远程控制功能》在远程协助、在线教学、技术支持等多种场景下,实时获得另一部移动设备的屏幕画面,并对其进行操作,具有极高的应用价值,本项目旨在实现两台Android手... 目录一、项目概述二、相关知识2.1 MediaProjection API2.2 Socket 网络

使用Python实现图像LBP特征提取的操作方法

《使用Python实现图像LBP特征提取的操作方法》LBP特征叫做局部二值模式,常用于纹理特征提取,并在纹理分类中具有较强的区分能力,本文给大家介绍了如何使用Python实现图像LBP特征提取的操作方... 目录一、LBP特征介绍二、LBP特征描述三、一些改进版本的LBP1.圆形LBP算子2.旋转不变的LB

Redis消息队列实现异步秒杀功能

《Redis消息队列实现异步秒杀功能》在高并发场景下,为了提高秒杀业务的性能,可将部分工作交给Redis处理,并通过异步方式执行,Redis提供了多种数据结构来实现消息队列,总结三种,本文详细介绍Re... 目录1 Redis消息队列1.1 List 结构1.2 Pub/Sub 模式1.3 Stream 结

C# Where 泛型约束的实现

《C#Where泛型约束的实现》本文主要介绍了C#Where泛型约束的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录使用的对象约束分类where T : structwhere T : classwhere T : ne

将Java程序打包成EXE文件的实现方式

《将Java程序打包成EXE文件的实现方式》:本文主要介绍将Java程序打包成EXE文件的实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录如何将Java程序编程打包成EXE文件1.准备Java程序2.生成JAR包3.选择并安装打包工具4.配置Launch4