-
2021-05-12 14:24:56
顺序队列
前言:
队列是一种特殊的线性表,他的特殊性体现在只能在尾部进行插入,头部进行删除,所以可以将队列看成是一种特殊的线性表。他的鲜明特点就是“先进先出”或者叫“后进后出”。队列这种数据结构的实现一般都是基于线性表的,而线性表又有顺序表和链表两种,所以队列的实现就又分为顺序队列和链队列。这篇文章用以总结使用顺序表来实现的队列–顺序队列。一、实现过程
1.提供队列的接口:IQueue
该接口定义了队列中必须实现的方法,因此在队列实现时只需要继承该接口然后正确实现该接口中的方法即可。无论是顺序队列还是链队列。都可以通过实现该接口来实现,下面是该接口中具体定义的方法。
public interface IQueue { void clear(); boolean isEmpty(); int length(); Object peek();//查看队列头元素 void offer(Object object) throws Exception;//入队 Object poll();//出队 }
2.提供顺序队列的实现:ShunxuQueue
因为队列的特点是只能在尾部插入,头部删除,且是先进先出。所以我们需要定义两个指针(栈只需要一个),分别来指向头部和尾部。这两个指针就叫front和rear(习惯性命名),他们初始状态下为0,也代表了对列为空。注意前面这句话,初始状态下front和rear都为0,所以一旦有数据插入,我们就不能让front和rear相等了。所以当有一个数据元素时,front和rear不能都指向0,我们应该将rear指向尾部元素的后一位。这也就是为什么rear应该指向尾部元素后一位的原因。除了front和rear这两个指针,还需要提供一个数组用以存储数据。front和rear便是指向的数组的下标。然后使用构造函数对数组进行初始化。代码如下:
/** * * 队列可以插入的一端被称为队尾,可以删除的一端被称为队列头, * 所以队列的典型特征就是队尾插入,队头删除 * * @author pcc * @version 1.0.0 * @className ShunxuQueue * @date 2021-04-29 09:32 */ public class ShunxuQueue implements IQueue{ int front = 0; int rear = 0; Object[] objArray; public ShunxuQueue(int n){ objArray = new Object[n]; } }
3.提供清空(clear)、判空(isEmpty)、队列长度(length)等方法
这几个方法的实现都是非常简单,就一起说下就好。清空方法自然就是清空队列了。我们只需要将数组清空,将front和rear置为初始状态就好;判空方法,只需要判断front和rear是否相对即可,相等自然就是空,这也是队列的初始装填;队列的长度方法也很简单,已经知道rear指向的是队尾后一个元素,front指向的是队头的下标,所以队列的长度就是rear-front。三个方法的具体实现如下:
@Override public void clear() { objArray = null; front = rear = 0; } @Override public boolean isEmpty() { return front == rear; } @Override public int length() { return rear - front; }
4.提供入队方法:offer
根据队列的实现思想:尾部插入,头部删除;rear指向尾部元素的下一位。我们可以知道插入时只需要考虑rear即可,删除时才需要考虑fornt。因此代码如下实现:
@Override public void offer(Object object) throws Exception{ rear++; if(rear<=objArray.length) objArray[rear-1] = object; else throw new Exception("队列已满"); }
5.提供出队方法:poll
在出队时我们就需要考虑front的下标位置了。每次出队都应该让front加一位,front的最大值应该是和rear相等,此时队列为空。代码实现如下:
@Override public Object poll() { if(front!=rear){ Object obj = objArray[front]; front++; return obj; } return null; }
6.提供获取队列头部元素的方法:peek
该方法只是获取到队列的头部元素,并不对元素进行出队操作。因此在判定队列有效的情况下可以直接将front下标的位置的元素直接返回。代码如下:
@Override public Object peek() { if(objArray!=null) return objArray[front]; return null; }
7.提供实现的完整代码
到这里IQueue接口中所有的方法就全部都实现了,顺序队列的实现其实很简单,只要是知道思路相信绝大部分实现起来是没有压力的,完整代码如下:
/** * * 队列可以插入的一端被称为队尾,可以删除的一端被称为队列头, * 所以队列的典型特征就是队尾插入,队头删除 * * * @author pcc * @version 1.0.0 * @className ShunxuQueue * @date 2021-04-29 09:32 */ public class ShunxuQueue implements IQueue{ int front = 0; int rear = 0; Object[] objArray; public ShunxuQueue(int n){ objArray = new Object[n]; } @Override public void clear() { objArray = null; front = rear = 0; } @Override public boolean isEmpty() { return front == rear; } @Override public int length() { return rear - front; } @Override public Object peek() { if(objArray!=null) return objArray[front]; return null; } @Override public void offer(Object object) throws Exception{ rear++; if(rear<=objArray.length) objArray[rear-1] = object; else throw new Exception("队列已满"); } @Override public Object poll() { if(front!=rear){ Object obj = objArray[front]; front++; return obj; } return null; } }
二、测试顺序队列的相应方法
1.测试入队和出队
顺序队列的实现代码已经写完,接下来就需要测试下这些实现是否是正确的,先来测试下入队和出队的方法。按照图中的顺序插入若是输出的也是这个顺序,则说明队列的入队和出队没有问题。
从上图可以看到队列长度是5,队列的出队和入队满足“先入先出”的规则,说明也没有问题。2.测试其他方法
其他方法里包括了清空、判空、长度等方法,长度在上面已经测试了显示是没有问题的,这里测试下清空和判空的方法,测试接口如下:
从上面图片可以看出,插入五个元素后队列长度是5,此时队列非空false,然后清空队列,此时队列是空true,获取队列元素时null。可以发现其他方法的实现也是没有问题的。三、总结
这篇文章总结了顺序队列的实现,代码是没有难度的,主要是掌握队列的思想。队列是一种使用很广的数据结构,使用频率也很高,比如finalize队列,线程池的等待队列,以及各种阻塞非阻塞队列等等。所以说掌握队列的思想还是很有必要的,这篇文章只是以一个实现者的角度去写的,可能并不是适合很多人,但也希望可以帮到看到这篇文章的你。
更多相关内容 -
C++数据结构之实现循环顺序队列
2020-12-31 13:27:43数据结构–用C++实现循环顺序队列 队列的操作特性:先进先出 队列中元素具有相同类型 相邻元素具有前驱和后继关系 设置队头、队尾两个指针,以改进出队的时间性能 约定:队头指针front指向队头元素的前一个位置... -
TIA博途SCL语言_顺序队列FIFO算法_FB库文件.rar
2021-11-24 10:54:28TIA博途SCL语言_顺序队列FIFO算法_FB库文件 -
顺序队列基本运算操作
2018-09-03 15:40:21本程序共设计了顺序队列需要的的5个基本操作运算,分别是入队,出队,取对头元素,置空队列,输出队列。附带实验报告。 -
顺序队列的实现(Go)
2021-01-20 13:40:12顺序队列结构定义如下: type ArrayQueue struct { q []interface{} capacity int // 队列容量 head int // 队头指针 tail int // 队尾指针 } 实现如下操作: 新建队列 元素入队 元素出队 队列是否为空/为满 ... -
顺序队列和链式队列的实现
2017-11-08 15:16:21顺序队列和链式队列的实现 -
C语言实现的顺序队列
2017-01-20 11:57:34C语言实现的顺序队列 -
链队列和顺序队列.zip
2019-08-30 19:17:59C语言编写的链队列和顺序队列,内含有良好的交互式界面,可以通过指令测试程序,可用于展示给其他人看。代码格式规范,有大量注释。 -
数据结构(C语言版)——循环顺序队列(代码版)
2020-09-24 11:01:25数据结构(C语言版)——循环顺序队列(代码版)里面...基本操作为:1:初始化循环顺序队列2:销毁循环顺序队列3:清空循环顺序队列4:循环顺序队列是否为空5:返回循环顺序队列头元素6:元素入队7:元素出队8:当前循环顺序队列长度 -
顺序队列的实现
2015-05-30 10:37:08队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队... -
循环顺序队列(+1判满)的基本操作.cpp
2020-10-11 15:36:16循环顺序队列(+1判满)的基本操作,采用牺牲一个存储单元判空,判满。包括出队,入队,队的判空,判满,队的销毁等。是针对初学者的原理展示,实用性较差。 -
顺序队列C实现
2018-02-10 15:23:15这是顺序队列的简单实现,含有如下功能: 1.创建队列; 2.销毁队列; 3.清空队列; 4.进队列; 5.出队列; 6.获取队头元素; 7.获取队列的长度。 -
数据结构教案-顺序队列
2019-02-20 16:44:54数据结构顺序队列详细教案,绝对完整。 -
数据结构-顺序队列
2016-09-12 14:37:091、实现顺序队列相关API函数 2、泛型编程思想,由主调函数提供内存空间 3、实体数据可以是基本类型或者复合类型 4、遍历时,使用回调函数。实现“策略”与“机制”分离 -
C语言实现顺序队列
2020-06-24 12:51:10C语言详解顺序队列
顺序队列常规操作
/********************* 顺序队列的常规操作 *************************/ Queue InitSeQueue(); // 初始化顺序队列 int QueueFull(); // 判断顺序队列满 int QueueEmpty(); // 判断顺序队列空 int QueueLength(); // 求顺序队列长度(元素个数) int EnQueue(); // 入队 int DeQueue(); // 出队 /****************************************************************/
定义顺序队列结构体
#include "stdio.h" #include "malloc.h" #define TRUE 1 #define FALSE 0 #define MAXSIZE 10 // 队列最大的存储量 typedef int ElemType; // 定义顺序队列结构体 typedef struct SeQueue{ ElemType *base; // 队列首地址 int front; // 队列头下标 int rear; // 队列尾下标 }*Queue;
顺序队列和顺序栈相类似,在队列的顺序存储结构中,除了用一组地址连续的存储单元依次存放从队列头到队列尾的元素之外,尚需附设两个 “指针”
front
和rear
分别指示队列头元素及队列尾元素的位置。为了在C语言中描述方便起见,初始化建空队列时,令
front = rear = 0;
每当插入新的队尾元素时 “尾指针增1”;每当删除队头元素时 “头指针增1”。
因此,在非空队列中,头指针始终指向队列头元素,而尾指针始终指向队列尾元素的下一个位置。
初始化顺序队列
/* * 初始化顺序队列 */ Queue InitSeQueue(){ Queue q; // 分配队列空间 q -> base = (ElemType *)malloc(sizeof(ElemType) * MAXSIZE); q -> front = q -> rear = 0; // 开始队列的头尾下标相等 return q; }
顺序队列判满
/* * 顺序队列判满 * q 顺序队列 */ int QueueFull(Queue q){ if(q == NULL){ return FALSE; } // 判断队列尾下标是否超过最大容量 if(q -> rear >= MAXSIZE){ return TRUE; } return FALSE; }
顺序队列判空
/* * 顺序队列判空 * q 顺序队列 */ int QueueEmpty(Queue q){ if(q == NULL){ return FALSE; } return q -> front == q -> rear; }
计算顺序队列的长度
/* * 求顺序队列的长度(元素个数) * q 顺序队列 */ int QueueLength(Queue q){ if(q == NULL){ return FALSE; } return q -> rear - q -> front; }
顺序队列入队(EnQueue)
/* * 入队 * q 顺序队列 * data 入队元素 */ int EnQueue(Queue q, ElemType data){ // 队列判满 if(QueueFull(q)){ return FALSE; } // 把元素插入队尾 q -> base[q -> rear] = data; q -> rear++; return TRUE; }
顺序队列出队(DeQueue)
/* * 出队 * q 顺序队列 * *val 用来存出队元素的数据 */ int DeQueue(Queue q, ElemType *val){ // 队列判空 if(QueueEmpty(q)){ return FALSE; } // 把队头元素取出来并利用指针返回去 *val = q -> base[q -> front]; q -> front ++; return TRUE; }
顺序队列各操作测试
/* * 打印队满、队空、队长状态 * q 顺序队列 */ void QueueStatus(Queue q){ printf("QueueFull():%d\n", QueueFull(q)); printf("QueueEmpty():%d\n", QueueEmpty(q)); printf("QueueLength():%d\n\n", QueueLength(q)); } // 程序主入口 int main(int argc, char const *argv[]) { Queue q = InitSeQueue(); printf("QueueMaxSize: %d\n\n", MAXSIZE); QueueStatus(q); // 打印队满、队空、队长状态 // 入队 printf("EnQueue():"); for(int i = 1; i < MAXSIZE * 2; i+=2){ printf("%d\t", i); EnQueue(q, i); } printf("\n"); QueueStatus(q); // 出队 int val; printf("DeQueue():"); while(!QueueEmpty(q)){ DeQueue(q, &val); printf("%d\t", val); } printf("\n"); QueueStatus(q); // 此时队列元素全出队了,测试假溢出 int num = 20; printf("EnQueue(%d): %d\t(0 Failed, 1 Success)\n", num, EnQueue(q, num)); return 0; }
结果如下:
QueueMaxSize: 10 QueueFull():0 QueueEmpty():1 QueueLength():0 EnQueue():1 3 5 7 9 11 13 15 17 19 QueueFull():1 QueueEmpty():0 QueueLength():10 DeQueue():1 3 5 7 9 11 13 15 17 19 QueueFull():1 QueueEmpty():1 QueueLength():0 EnQueue(20): 0 (0 Failed, 1 Success)
QueueFull():1
、EnQueue(20): 0
可以看出顺序队列存在假溢出(实际可用空间并未占满,却不能进行入队操作)例如:
1️⃣:初始化空队列,
q -> front = q -> rear = 0
2️⃣:入队a1、a2、a3,
q -> front = 0, q -> rear = 3
3️⃣:出队a1、a2,
q -> front = 2, q -> rear = 3
4️⃣:入队a4、a5、a6,
q -> front = 2, q -> rear = 6
执行 4️⃣ 操作后队列的"尾指针"已经超出对队列的最大范围了,之后无法再进行入队操作,而队列实际空间并未占满,就造成了假溢出。
用 循环队列 就可以解决假溢出情况。
源代码
源代码已上传到 GitHub Data-Structure-of-C,欢迎大家下载 C语言实现数据结构
✍ 码字不易,记得点赞 👍 收藏 ⭐️
-
队列之顺序队列详解(C语言版)
2021-02-14 21:46:15本篇文章详细的介绍了数据结构队列中的顺序队列,并用C语言对其常用操作进行了实现。
前言
大家好,越努力,越幸运。本篇文章小猿将跟您分享数据结构队列中的顺序队列,希望对您有所帮助。
一、顺序队列的定义
首先我们来看看什么是队列?队列是一种先进先出(FIFO)的线性表,它只允许在表的一端进行插入,而在另一端删除元素。这和我们日常生活中的排队是一致的,最早进入队列的元素最早离开。队列的结构图如下所示:
明白了队列之后,顺序队列就非常简单了,用顺序存储结构表示的队列就简称为顺序队列。和顺序栈相类似,在队列的顺序存储结构中,除了用一组地址连续的存储单元依次存放从队列头到队列尾的元素之外,尚需附设两个指针front和rear分别指示队列头元素及队列尾元素的位置。为了在C语言中描述方便起见,在此我们约定:初始化建空队列时,令front=rear=0,每当插人新的队列尾元素时,“尾指针增1”;每当删除队列头元素时,“头指针增1”。因此,在非空队列中,头指针始终指向队列头元素,而尾指针始终指向队列尾元素的下一个位置。了解了顺序队列之后,我们可以发现顺序队列有一个很大的缺点,它会出现虚假的满状态,为了解决这个问题我们可以将其改造成循环队列(循环队列将在下次进行介绍)。二、顺序队列的结构
结构图
代码描述
//数据类型 #define ElemType int //队列可容纳的最多元素个数 #define MAXSIZE 8 //队列的管理结构 typedef struct Queue { ElemType *base; //指向队列的存储空间 int front; //指向队头 int rear; //指向队尾 }Queue;
三、顺序队列的常用操作
初始化
//初始化顺序队列 void InitQueue(Queue *Q) { //为顺序队列开辟存储空间 Q->base = (ElemType *)malloc(sizeof(ElemType) * MAXSIZE); assert(Q->base != NULL); //初始化时,队头和队尾都在0位置 Q->front = Q->rear = 0; }
入队
//入队操作 void EnQueue(Queue *Q, ElemType x) { //判断队列是否还有存储空间 if(Q->rear >= MAXSIZE) return; //如果还有存储空间,将数据入队 Q->base[Q->rear++] = x; }
出队
//出队 void DeQueue(Queue *Q) { //判断队列中的元素是否为空 if(Q->front == Q->rear) return; //如果队列中的元素不为空,进行出队操作 Q->front++; }
打印队列数据
//打印顺序队列中的元素 void ShowQueue(Queue *Q) { //遍历队头到队尾中的每个元素,并将其打印输出 for(int i=Q->front; i<Q->rear; ++i) { printf("%d ",Q->base[i]); } printf("\n"); }
获取队头元素
//获取队头元素 void GetHdad(Queue *Q, ElemType *v) { //判断队列中的元素是否为空 if(Q->front == Q->rear) return; //如果队列中的元素不为空,取出队头元素 *v = Q->base[Q->front]; }
求队列长度
//获取队列元素个数 int Length(Queue *Q) { //将尾指针位置减去头指针的位置就是队列中元素的个数 return (Q->rear - Q->front); }
清空队列
//清空队列 void ClearQueue(Queue *Q) { //将队头指针和队尾指针都重置为0 Q->front = Q->rear = 0; }
销毁队列
//销毁队列 void DestroyQueue(Queue *Q) { //释放队列的存储空间 free(Q->base); //将队列空间的位置指针置空 Q->base = NULL; }
结语
对顺序队列的介绍就到这里啦,希望这篇文章能给予你一些帮助,感谢各位人才的:点赞、收藏和评论,我们下次见。
附录
以下提供顺序队列的测试代码
SeqQueue.h
#ifndef __SEQQUEUE_H__ #define __SEQQUEUE_H__ #include<stdio.h> #include<malloc.h> #include<assert.h> //数据类型 #define ElemType int //队列可容纳的最多元素个数 #define MAXSIZE 8 //队列的管理结构 typedef struct Queue { ElemType *base; //指向队列的存储空间 int front; //指向队头 int rear; //指向队尾 }Queue; void InitQueue(Queue *Q); void EnQueue(Queue *Q, ElemType x); void ShowQueue(Queue *Q); void DeQueue(Queue *Q); void GetHdad(Queue *Q, ElemType *v); int Length(Queue *Q); void ClearQueue(Queue *Q); void DestroyQueue(Queue *Q); #endif //__SEQQUEUE_H__
SeqQueue.cpp
#include"SeqQueue.h" //初始化顺序队列 void InitQueue(Queue *Q) { //为顺序队列开辟存储空间 Q->base = (ElemType *)malloc(sizeof(ElemType) * MAXSIZE); assert(Q->base != NULL); //初始化时,队头和队尾都在0位置 Q->front = Q->rear = 0; } //入队操作 void EnQueue(Queue *Q, ElemType x) { //判断队列是否还有存储空间 if(Q->rear >= MAXSIZE) return; //如果还有存储空间,将数据入队 Q->base[Q->rear++] = x; } //打印顺序队列中的元素 void ShowQueue(Queue *Q) { //遍历队头到队尾中的每个元素,并将其打印输出 for(int i=Q->front; i<Q->rear; ++i) { printf("%d ",Q->base[i]); } printf("\n"); } //出队 void DeQueue(Queue *Q) { //判断队列中的元素是否为空 if(Q->front == Q->rear) return; //如果队列中的元素不为空,进行出队操作 Q->front++; } //获取队头元素 void GetHdad(Queue *Q, ElemType *v) { //判断队列中的元素是否为空 if(Q->front == Q->rear) return; //如果队列中的元素不为空,取出队头元素 *v = Q->base[Q->front]; } //获取队列元素个数 int Length(Queue *Q) { //将尾指针位置减去头指针的位置就是队列中元素的个数 return (Q->rear - Q->front); } //清空队列 void ClearQueue(Queue *Q) { //将队头指针和队尾指针都重置为0 Q->front = Q->rear = 0; } //销毁队列 void DestroyQueue(Queue *Q) { //释放队列的存储空间 free(Q->base); //将队列空间的位置指针置空 Q->base = NULL; }
Main.cpp
#include"SeqQueue.h" void main() { Queue Q; InitQueue(&Q); for(int i=1; i<=8; ++i) { EnQueue(&Q, i); } ShowQueue(&Q); DeQueue(&Q); EnQueue(&Q,10); ShowQueue(&Q); }
-
java队列实现方法(顺序队列,链式队列,循环队列)
2020-08-28 12:28:01下面小编就为大家分享一篇java队列实现方法(顺序队列,链式队列,循环队列),具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧 -
C#实现顺序队列和链队列的代码实例
2020-12-31 20:58:18和上篇栈的实现基本是一个思路: 废话不多说,直接写代码吧 //自定义队列接口 namespace 队列 { interface IQueue ...//顺序队列的实现类 namespace 队列 { class SeqQueue<T> : IQueue { private -
顺序队列(循环队列)的常用操作(C语言)
2013-10-19 16:43:51C语言实现顺序队列(循环队列)的常用操作,包括初始化顺序队,创建顺序队,入队,出队,计算队的长度,清空队列等等 -
顺序队列/链式队列
2018-04-09 15:49:55队列是另一种限定性的线性表,他只允许在表的一端插入元素,而在...一,顺序队列 顺序队列使用顺序表来实现的,即队列中的元素均存放在一片连续的内存空间中。通过该片内存的地址对队列中元素进行访问。之前是用数...队列是另一种限定性的线性表,他只允许在表的一端插入元素,而在表的另一端删除元素,具有“先进先出”的特点。在队列中,允许插入的一端称为队尾,允许删除的一端称为队首。
与线性表相似,队列也有两种存储结构:顺序队列和链式队列。
一,顺序队列
顺序队列使用顺序表来实现的,即队列中的元素均存放在一片连续的内存空间中。通过该片内存的地址对队列中元素进行访问。之前是用数组来实现顺序表的。通过数组名访问数组元素。数组的长度必须提前设定,一旦超过设定的大小,则无法再向其中添加元素。
这里采用与顺序栈类似的方法,通过设定初始值来动态申请内存,当内存不够用时,修改初始值来再次申请更大的内存达到扩容的目的。所以可以通过动态申请的内存地址来访问队列中的元素。
因此,以下实现的是可以扩容的顺序队列。
1. 顺序队列的结构
要实现扩容的顺序队列,
(1)首先要动态申请一片连续的内存。该内存需要一个指针data指向,通过该指针来访问该内存。
(2)而该内存的大小需提前设定,用capacity进行表示
(3)另外,还需要知道队列中实际元素的个数size
因为队列具有“先进先出”的特点,只能在一端(队尾)进,另一端(队头)出。所以可能造成下面的情况:
此时,需要时刻知道队列两端所在的位置,但又不能像顺序栈一样用size来表示队尾结点所在位置。所以还需要两个变量:(4)head表示队首结点所在的下标
(5)tail表示队尾结点的下个位置所在的下标(这样入队时直接在tail处设置元素即可)。
所以,队列中所有元素的下标所在范围为:[head,tail),如下图:
代码如下:
typedef char SeqQueueType; //顺序队列的结构 typedef struct SeqQueue { SeqQueueType* data;//指向顺序队列的指针 int size;//顺序队列的实际长度 int capacity;//顺序队列的有效长度 int head;//顺序队列的头节点所在的下标 int tail;//顺序队列尾节点下个元素所在的下标,即[head,tail) }SeqQueue;
2. 顺序队列的初始化
在对队列初始化时,首先要设定队列有效长度的初始值,再根据该初始值来动态申请内存,并由data指向。因为此时队列中并没有元素,所以,实际长度size,head和tail均置为0即可。
代码如下:
//初始化顺序队列 void SeqQueueInit(SeqQueue* queue) { if(queue == NULL) { //非法输入 return; } queue->size = 0;//初始时队列为空 queue->capacity =1000;//设置有效长度为1000 queue->data = (SeqQueueType*)malloc(queue->capacity*sizeof(SeqQueueType));//动态申请内存,由data指向 queue->head = 0;//初始时,队列为空 queue->tail = 0; }
3. 顺序队列入队操作
因为是从队尾进行入队的,所以只需将下标tail处的值设置为指定值,然后tail加1,size加1即可。但是在入队之前要考虑以下几点:
(1)如果队列中的元素个数已经到达动态申请内存的上限值,此时就需要扩容来申请更大的内存。在扩容时:
1)首先要重新设定更大的有效长度,根据新设置的有效长度来动态申请更大的内存空间
2)其次,要将原内存中的数据拷贝到新申请的内存中。在拷贝时,要考虑以下几点:
i)如果head小于tail的值,则从下标为head开始到下标为tail结束,依次将各节点的信息拷贝到新内存中,如图:
ii)如果head大于等于tail的值,则需要先从head开始到原capacity将各节点拷贝到新内存对应的下标处,再将从下标为0开始到tail的各节点拷贝到新内存已有结点之后。拷贝结束后需要修改新内存中的tail值。如下图:
3)拷贝完之后,要释放原来的内存,以免造成内存泄漏。并使队列中的指针data指向新申请的内存
(2)如果原队列中的元素为以下情况:
此时,已经无法从队尾入队,但是队列并没有满。所以需要将tail的值改为0。这样便可以继续入队。
(3)在进行(1)(2)之后或者没有出现(1)(2)的情况,就可以使新元素直接直接放置在下标为tail处,然后tail加1,size加1即可。
根据上述分析,编写代码如下:
//入队,queue为顺序队列的指针 void SeqQueuePush(SeqQueue* queue,SeqQueueType value) { if(queue == NULL) { //非法输入 return; } //原内存已满,需要扩容 if(queue->size >= queue->capacity) { //扩容函数 Expanding(queue); } //如果尾节点为数组最后一个元素,但是数组前面还有空余的地方 if(queue->tail == queue->capacity) { queue->tail = 0; queue->data[queue->tail++] = value; queue->size++; return; } //尾节点不为数组最后一个节点且数组还有空余的地方 queue->data[queue->tail++] = value; queue->size++; return; }
//扩容函数 void Expanding(SeqQueue* queue) { if(queue == NULL) { //非法输入 return; } //重新设置新内存的有效长度 queue->capacity = 2*(queue->capacity) + 1; //重新申请新的内存 SeqQueueType* new_data = (SeqQueueType*)malloc(queue->capacity*sizeof(SeqQueueType)); //将原内存中的数据复制到新内存中 //如果尾节点在头节点之后 int i; if(queue->head < queue->tail) //注意没有"=" { i = queue->head; for(;i < queue->tail;++i)//按对应下标复制即可 { new_data[i] = queue->data[i]; } } else//如果尾节点在头节点之前 { i = queue->head; //先拷贝队首到原capacity的数据 for(;i < queue->size;++i)//此时size等于原capacity { new_data[i] = queue->data[i]; } //在拷贝0到队尾的数据 i = 0; for(;i < queue->tail;++i) { new_data[queue->size + i] = queue->data[i]; } queue->tail = queue->head + queue->size;//修改扩容后的tail值 } //释放原内存 free(queue->data); //将队列结构中的data指针指向新内存 queue->data = new_data; return; }
4. 顺序队列的出队操作
顺序队列是从队头出队的:
(1)首先考虑队列是否为空,为空则出队失败。(为空的条件是队列长度为0)
(2)然后需要考虑以下情形:
此时,出队的元素为capacity-1处的元素,而出队后需要将head设置为0,同时是使size减1。
(3)如果不满足(1)(2)只需将head加1,size减1即可(此时原head处的值为无效元素)。
代码如下:
//出队 void SeqQueuePop(SeqQueue* queue) { if(queue == NULL) { //非法输入 return; } if(queue->size == 0) { //空队列 return; } //如果出队元素为最大数组下标处的元素 if(queue->head == queue->capacity - 1) { queue->head = 0; queue->size--; } else//如果不是最大数组下标处的元素 { queue->head++; queue->size--; } return; }
5. 取队首元素
(1)如果队列为空,则操作失败
(2)不为空,只需将队首下标head处的数据保存下来即可
代码如下:
//取队首元素:-1出错返回,0成功返回 int SeqQueueTop(SeqQueue* queue,SeqQueueType* value) { if(queue == NULL || value == NULL) { //非法输入 return -1; } if(queue->size == 0) { //空队列 return -1; } //取队首元素 *value = queue->data[queue->head]; return 0; }
6. 销毁队列
队列初始化前只有一个队列结构体,而没有动态申请的内存和其中的元素。所以只需释放动态申请的内存,将队列长度置为0即可恢复到初始化前的状态。
//销毁队列 void SeqQueueDestory(SeqQueue* queue) { if(queue == NULL) { //非法输入 return; } free(queue->data); queue->size = 0; queue->capacity = 0; queue->head = 0; queue->tail = 0; return; }
二,链式队列
链式队列采用单链表来实现的。通过在链表的一端(队尾)添加结点来实现入队,在链表的另一端(队头)释放节点来实现出队。
1. 链式队列的结构
链表是由一个个的结点组成,所以链式队列的结点结构与单链表的结点结构相同。包含一个数据域data和指针域next。
typedef char LinkQueueType; //定义链式队列的节点结构 typedef struct LinkQueueNode { LinkQueueType data;//节点的数据域 struct LinkQueueNode* next;//指向下一个节点的指针 }LinkQueueNode;
因为出,入队列需要从两端进行操作,所以在对该链式队列设置两个指针变量,head指向队列的队头结点,tail指向队列的队尾结点,将这两个指针封装在结构体中作为链式队列结构的成员。
//定义链式队列 typedef struct LinkQueue { LinkQueueNode* head;//指向链式队列的头节点 LinkQueueNode* tail;//指向链式队列的尾指针 }LinkQueue;
这里的两个指针其实和单链表中的head指针作用类似,单链表只从一端开始进行操作,所以只需维护一个头指针来表示单链表。而队列出队,入队要从两端操作,所以为方便起见,需维护两个指针来共同表示链式队列。
2. 链式队列的初始化
初始时队列中并没有结点,所以将队首指针和队尾指针均置空即可。
//初始化链式队列 void LinkQueueInit(LinkQueue* queue) { if(queue == NULL) { //非法输入 return; } queue->head = NULL; queue->tail = NULL; }
3. 链式队列入队操作
队列是从队尾进行入队,所以
(1)首先要创建一个新节点
(2)如果原队列为空,则使队头指针和队尾指针均指向新结点即可
(3)如果原队列不为空,则使队尾指针的next域指向新节点,然后队尾指针后移即可。
代码如下:
//尾插入队列 void LinkQueuePush(LinkQueue* queue,LinkQueueType value) { if(queue == NULL) { //非法输入 return; } //创建一个新节点 LinkQueueNode* new_node = CreateNode(value); //对新节点进行尾插 if(queue->head == NULL)//如果原队列为空 { queue->head = queue->tail = new_node; } else//如果原队列不为空 { queue->tail->next = new_node; queue->tail = queue->tail->next; } return; }
4. 链式队列的出队操作
队列是从队头进行出队的,所以
(1)首先要考虑队列是否为空,为空则出队失败
(2)不为空,先使队头指针指向队头结点的下一个节点作为新的队首结点,然后释放原队首节点即可。
代码如下:
//头删出队列 void LinkQueuePop(LinkQueue* queue) { if(queue == NULL) { //非法输入 return; } if(queue->head == NULL) { //空队列 return; } //头删 LinkQueueNode* to_delete = queue->head;//保存要销毁的队首节点 queue->head = to_delete->next;//使队头指针指向要销毁节点的下一个节点 DestoryNode(to_delete);//销毁原队首节点 return; }
5. 取队首元素
(1)如果队列为空,则操作失败
(2)如果不为空,只需将队头指针所指向的结点数据域保存下来即可。
代码如下:
//取队首元素:出错返回-1,成功返回0 int LinkQueueTop(LinkQueue queue,LinkQueueType* value) { if(value == NULL) { //非法输入 return -1; } if(queue.head == NULL) { //空队列 return -1; } *value = queue.head->data;//保存队首元素 return 0; }
6. 销毁链式队列
队列在初始化前只有两个指针,所以销毁后也要恢复到初始化前的状态。
(1)遍历链表将各节点依次销毁
(2)使队首,队尾指针置空,以防变为野指针
代码如下:
//销毁队列 void LinkQueueDestory(LinkQueue* queue) { if(queue == NULL) { //非法输入 return; } //从队头开始遍历队列 LinkQueueNode* to_delete = queue->head; while(to_delete != NULL) { LinkQueueNode* next_node = to_delete->next;//保存要销毁节点的下一个节点 free(to_delete);//销毁节点 to_delete = next_node; } //使队首指针,队尾指针置空 queue->head = NULL; queue->tail = NULL; return; }
-
顺序队列实现源码(C、C++、Java)
2017-01-24 17:32:35顺序队列实现源码,分别用C、C++、JAVA实现。 -
数据结构之循环顺序队列
2014-05-30 09:10:12顺序循环队列,详细介绍见博客链接:http://blog.csdn.net/u013071074/article/details/27583741 -
C语言实现顺序队列的各种操作
2021-04-16 11:45:29C语言-顺序队列的基本操作 一、我们先明确一下什么是队列? 队列(Queue):只允许在表的一端进行插入,另外一端进行删除 入队/进队:插入元素 出队/离队:删除元素 队头:允许删除的一端 队尾:允许插入的一端 二、... -
顺序队列的实现(循环队列)
2019-12-01 16:24:57在顺序队列中,通常让队尾指针rear指向刚进队的元素的位置,让队首指针front指向刚出队的元素的位置。因此,元素进队的时候rear指针要向后移动,元素出队的时候front指针也要向后移动。 #define _CRT_SECURE_NO_... -
顺序队列以及链式队列的操作
2021-02-05 23:41:54队列的基本操作的实现,这个程序中演示了顺序队列和链式队列的初始化、创建、删除、查找以及输出等功能。使用c语言所写。 -
顺序队列的假溢出
2021-01-16 20:48:43顺序队列的假溢出 我们已经明白了队列这种基本数据结构,对于顺序队列而言,其存在已经足够解决大多时候的设计问题了,但是其依旧存在一些缺陷和不足,因为我们的入队和出队操作均是直接在其后面进行结点的链接和... -
数据结构(六)——顺序队列、链队列
2019-11-23 21:34:16队列——顺序队列、链队列 队列概念 队列是一种特殊的、只允许在一端进行数据的输入,在另一端进行数据的删除、具有先进先出(FIFO)特性的线性表,进行插入操作的一端称为队尾,进行删除操作的一端称为队头 ... -
数据结构之顺序队列实现
2019-06-25 20:34:40文章目录数据结构之循环队列实现代码及思想测试截图 数据结构之循环队列实现 代码及思想 #include <iostream> #include <cstdio> #include <cstdlib> using namespace std; #define MAXSIZE 7//... -
顺序队列的基本操作
2019-01-25 12:03:16顺序队列会发生假溢出的情况,具体运行情况请看效果截图,相关代码如下: 一、顺序队列的定义: #include&amp;amp;amp;lt;stdio.h&amp;amp;amp;gt; #include&amp;amp;amp;lt;stdlib.h&...