首页 > 其他分享 >14.队列的顺序存储

14.队列的顺序存储

时间：2023-06-11 14:11:06浏览次数：71  
标签：return 14 队列 SQ int LQ front 顺序存储

1.队列的概念

1.1队列的定义

队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。
队列是一种先进先出（First In First Out）的线性表，简称FIFO。允许插入的一端称为队尾，允许删除的一端称为队头。

队头（Front）：允许删除的一端，又称队首。
队尾（Rear）：允许插入的一端。
空队列：不包含任何元素的空表。

1.2队列的常见基本操作

InitQueue(&Q)：初始化队列，构造一个空队列Q。
QueueIsEmpty(Q)：判队列空，若队列Q为空返回true，否则返回false。
QueueIsFull(Q)：判队列满，若队列Q为满返回true，否则返回false。
PrintQueue(Queue* Q)：打印队列中的各元素
EnQueue(&Q, x)：入队，若队列Q未满，将x加入，使之成为新的队尾。
DeQueue(&Q, &x)：出队，若队列Q非空，删除队头元素，并用x返回。
ClearQueue(Queue* Q)：清空队列
GetHead(Q, &x)：读队头元素，若队列Q非空，则将队头元素赋值给x。

————————————————
版权声明：本文为CSDN博主「UniqueUnit」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/Real_Fool_/article/details/113852222

2.队列的顺序存储

采用数组来保存队列的元素，设立一个队首指针front，一个队尾指针rear，分别指向队首和队尾元素。则
rear-front 即为存储的元素个数！

2.1队列定义

#define MaxSize 5 //队列的最大容量
typedef int DataType; //队列中元素类型
typedef struct Queue
{
    DataType queue[MaxSize];
    int front; //队头指针
    int rear; //队尾指针
}SeqQueue;

2.2队列初始化

//队列初始化，将队列初始化为空队列
void InitQueue(SeqQueue *SQ)
{
    if(!SQ) return;
    SQ->front = SQ->rear = 0;//把对头和队尾指针同时置0
}

2.3队列为空

//判断队列为空
int IsEmpty(SeqQueue *SQ)
{
    if(!SQ) return 0;
    if (SQ->front == SQ->rear)
    {
        return 1;
    }
    return 0;
}

2.4队列为满

//判断队列是否为满
int IsFull(SeqQueue *SQ)
{
    if(!SQ) return 0;
    if (SQ->rear == MaxSize)
    {
        return 1;
    }
    return 0;
}

2.5入队

//入队,将元素data 插入到队列SQ 中
int EnterQueue( SeqQueue *SQ, DataType data)
{
    if(!SQ) return 0;
    if(IsFull(SQ))
    {
        cout<<"无法插入元素"<<data<<", 队列已满!"<<endl;
        return 0;
    }
    SQ->queue[SQ->rear] = data; //在队尾插入元素data
    SQ->rear++; //队尾指针后移一位
    return 1;
}

2.6打印队列中的元素

//打印队列中的各元素
void PrintQueue(SeqQueue* SQ)
{
    if(!SQ) return ;
    int i = SQ->front;
    while(i<SQ->rear)
    {
        cout<<setw(4)<<SQ->queue[i];
        i++;
    }
    cout<<endl;
}

2.7出队

方式 1 - 删除 front 所指的元素, 后面所有元素前移 1 并返回被删除元素

//出队，将队列中队头的元素data 出队，后面的元素向前移动
int DeleteQueue(SeqQueue* SQ, DataType *data)
{
    if(!SQ || IsEmpty(SQ))
    {
        cout<<"队列为空！"<<endl;
        return 0;
    }
    if(!data) return 0;
    *data = SQ->queue[SQ->front];
    for(int i=SQ->front+1; i<SQ->rear; i++)//移动后面的元素
    {
        SQ->queue[i-1]=SQ->queue[i];
    }
    SQ->rear--;//队尾指针前移一位
    return 1;
}

方式 2 - 删除 front 所指的元素，然后加 1 并返回被删元素。8979438401111

//出队，将队列中队头的元素data 出队，出队后队头指针front 后移一位
int DeleteQueue2(SeqQueue* SQ,DataType* data)
{
    if (!SQ || IsEmpty(SQ))
    {
        cout<<"队列为空！"<<endl;
        return 0;
    }
    if(SQ->front>=MaxSize)
    {
        cout<<"队列已到尽头!"<<endl;
        return 0;
    }
    *data = SQ->queue[SQ->front]; //出队元素值
    SQ->front = (SQ->front)+1; //队首指针后移一位
    return 1;
}

2.8取队首元素：返回front 指向的元素值

//获取队首元素
int GetHead(SeqQueue* SQ,DataType* data)
{
    if (!SQ || IsEmpty(SQ))
    {
        cout<<"队列为空!"<<endl;
    }
    return *data = SQ->queue[SQ->front];
}

2.9清空队列

//清空队列
void ClearQueue(SeqQueue* SQ)
{
    SQ->front = SQ->rear = 0;
}

2.10获取队列长度

//获取队列中元素的个数
int getLength(SeqQueue* SQ)
{
    if(!SQ) return 0;
    return SQ->rear-SQ->front;
}

完整代码

#include <stdio.h>
#include <assert.h>
#include <Windows.h>
#include <iostream>
#include <iomanip>

using namespace std;

#define MaxSize 5 //队列的最大容量

typedef int DataType; //队列中元素类型

typedef struct Queue
{
    DataType queue[MaxSize];
    int front; //队头指针
    int rear; //队尾指针
}SeqQueue;

//队列初始化，将队列初始化为空队列
void InitQueue(SeqQueue* SQ)
{
    if (!SQ) return;
    SQ->front = SQ->rear = 0; //把对头和队尾指针同时置0
}

//判断队列为空
int IsEmpty(SeqQueue* SQ)
{
    if (!SQ) return 0;
    if (SQ->front == SQ->rear)
    {
        return 1;
    }
    return 0;
}

//判断队列是否为满
int IsFull(SeqQueue* SQ)
{
    if (!SQ) return 0;
    if (SQ->rear == MaxSize)
    {
        return 1;
    }
    return 0;
}

//入队,将元素data 插入到队列SQ 中
int EnterQueue(SeqQueue* SQ, DataType data) 
{
    if (!SQ) return 0;

    if (IsFull(SQ))
    {
        cout << "无法插入元素" << data << ", 队列已满!" << endl;
        return 0;
    }

    SQ->queue[SQ->rear] = data; //在队尾插入元素data
    SQ->rear++; //队尾指针后移一位

    return 1;
}

//出队，将队列中队头的元素data 出队，后面的元素向前移动
int DeleteQueue(SeqQueue * SQ, DataType * data) 
{
    if (!SQ || IsEmpty(SQ)) 
    {
        cout << "队列为空！" << endl;
        return 0;
    }

    if (!data) return 0;

    *data = SQ->queue[SQ->front];
    for (int i = SQ->front + 1; i < SQ->rear; i++)//移动后面的元素 
    {
        SQ->queue[i - 1] = SQ->queue[i];
    }
    SQ->rear--;//队尾指针前移一位

    return 1;
}

//出队，将队列中队头的元素data 出队，出队后队头指针front 后移一位
int DeleteQueue2(SeqQueue* SQ, DataType* data)
{
    if (!SQ || IsEmpty(SQ))
    {
        cout << "队列为空！" << endl;
        return 0;
    }

    if (SQ->front >= MaxSize) 
    {
        cout << "队列已到尽头!" << endl;
        return 0;
    }

    *data = SQ->queue[SQ->front]; //出队元素值
    SQ->front = (SQ->front) + 1; //队首指针后移一位
    return 1;
}
//打印队列中的各元素
void PrintQueue(SeqQueue* SQ)
{
    if (!SQ) return;

    int i = SQ->front; 
    while (i < SQ->rear)
    {
        cout << setw(4) << SQ->queue[i];
        i++;
    }
    cout << endl;
}

//获取队首元素，不出队
int GetHead(SeqQueue* SQ, DataType* data)
{
    if (!SQ || IsEmpty(SQ))
    {
        cout << "队列为空!" << endl;
    }
    return *data = SQ->queue[SQ->front];
}

//清空队列
void ClearQueue(SeqQueue* SQ)
{
    if (!SQ) return;
    SQ->front = SQ->rear = 0;
}

//获取队列中元素的个数
int getLength(SeqQueue* SQ)
{
    if (!SQ) return 0;
    return SQ->rear - SQ->front;
}

int main()
{
    SeqQueue* SQ = new SeqQueue;
    DataType data = -1;

    //初始化队列
    InitQueue(SQ);

    //入队
    for (int i = 0; i < 7; i++) 
    {
        EnterQueue(SQ, i);
    }
    //打印队列中的元素
    printf("队列中的元素(总共%d 个)：", getLength(SQ));
    PrintQueue(SQ);
    cout << endl;
    //出队
    for(int i=0; i<10; i++)
    {
        if (DeleteQueue2(SQ, &data))
        {
            cout << "出队的元素是：" << data << endl;
        }
        else
        {
        cout << "出队失败！" << endl;
        }
    }

    //打印队列中的元素
    printf("出队一个元素后，队列中剩下的元素：");
    PrintQueue(SQ);
    cout << endl;

    system("pause");
    return 0;
}

3.队列的链式存储

队列的链式存储结构，其实就是线性表的单链表，只不过它只是尾进头出而已，我们把它简称为链队列。为了
操作上的方便，我们将队头指针指向链队列的头结点，而队尾指针指向终端节点

3.1队列的定义

#define MaxSize 5 //队列的最大容量
typedef int DataType;//队列中元素的类型

typedef struct _QNode//结点结构
{
	DataType data;
	struct _QNode* next;
}QNode;

typedef QNode* QueuePtr;

typedef struct Queue
{
	int length;//队列的长度
	QueuePtr front;//队头指针
	QueuePtr rear;//队尾指针
}LinkQueue;

3.2队列初始化

//队列初始化，将队列初始化为空队列
void InitQueue(LinkQueue* LQ)
{
	if (!LQ) return;

	LQ->length = 0;
	LQ->front = LQ->rear = NULL;//把队头指针和队尾指针同时置0
}

3.3判断队列是否为空

//判断队列为空
int IsEmpty(LinkQueue *LQ)
{
	if (!LQ) return 0;

	if (LQ->front == NULL)
	{
		return 1;
	}
	return 0;
}

3.4判断队列是否为满

//判断队列是否为满
int IsFull(LinkQueue* LQ)
{
	if (!LQ) return 0;

	if (LQ->length == MaxSize)
	{
		return 1;
	}
	return 0;
}

3.5入队

空队列时，front 和rear 都指向空。

//入队,将元素data 插入到队列LQ 中
int EnterQueue(LinkQueue* LQ, DataType data)
{
	if (!LQ) return 0;

	if (IsFull(LQ))
	{
		cout << "队列无法插入元素" << data << "，队列已满" << endl;
		return 0;
	}

	//创建结点
	QNode* qNode = new QNode;
	qNode->data = data;
	qNode->next = NULL;

	if (IsEmpty(LQ))//空队列
	{
		LQ->front = LQ->rear = qNode;
	}
	else
	{
		LQ->rear->next = qNode;//在队尾插入结点qNode
		LQ->rear = qNode;//队尾指向新插入的结点
	}
	LQ->length++;

	return 1;
}

3.6删除结点

//出队，将队列中队头的元素data出队，后面的元素向前移动
int DeleteQueue(LinkQueue* LQ, DataType* data)
{
	QNode* tmp = NULL;

	if (!LQ || IsEmpty(LQ))
	{
		cout << "队列为空" << endl;
		return 0;
	}

	if (!data) 
		return 0;

	tmp = LQ->front;

	LQ->front = tmp->next;
	if (!LQ->front) 
		LQ->rear = NULL;//如果队头出列后不存在其他元素，则rear结点也要置空

	*data = tmp->data;
	LQ->length--;

	delete tmp;//配合入队时用了new

	return 1;
}

3.7获取队首元素

//获取队首元素，不出队
int GetHead(LinkQueue* LQ, DataType* data)
{
	if (!LQ || IsEmpty(LQ))
	{
		cout << "队列为空！" << endl;
		return 0;
	}

	if (!data) return 0;

	*data = LQ->front->data;
	return 1;
}

3.8清空队列

//清空队列
void ClearQueue(LinkQueue* LQ)
{
	if (!LQ) return;

	while (LQ->front)
	{
		QueuePtr tmp = LQ->front->next;
		delete LQ->front;
		LQ->front = tmp;
	}
	LQ->front = LQ->rear = NULL;
	LQ->length = 0;
}

3.9获取队列中元素个数

//获取队列中元素的个数
int getLength(LinkQueue* LQ)
{
	if (!LQ) return 0;
	
	return LQ->length;
}

3.10打印队列中的元素

//打印队列中的各元素
void PrintQueue(LinkQueue *LQ)
{ 
    QueuePtr tmp;
    if(!LQ) return ;
    if(LQ->front==NULL)
    {
        cout<<"队列为空！";
        return ;
    }
    tmp = LQ->front;
    while(tmp)
    {
        cout<<setw(4)<<tmp->data;
        tmp = tmp->next;
    }
    cout<<endl;
}

完整代码

#include <stdio.h>
#include <assert.h>
#include <Windows.h>
#include <iostream>
#include <iomanip>

using namespace std;

#define MaxSize 5 //队列的最大容量
typedef int DataType; //队列中元素类型

typedef struct _QNode//结点结构
{ 
	DataType data;
	struct _QNode* next;
}QNode;

typedef QNode* QueuePtr;

typedef struct Queue
{
	int length; //队列的长度
	QueuePtr front; //队头指针
	QueuePtr rear; //队尾指针
}LinkQueue;

//队列初始化，将队列初始化为空队列
void InitQueue(LinkQueue* LQ)
{
	if (!LQ) return;
	LQ->length = 0;
	LQ->front = LQ->rear = NULL; //把对头和队尾指针同时置0
}

//判断队列为空
int IsEmpty(LinkQueue* LQ)
{
	if (!LQ) return 0;
	if (LQ->front == NULL)
	{
		return 1;
	}
	return 0;
}

//判断队列是否为满
int IsFull(LinkQueue* LQ)
{
	if (!LQ) return 0;
	if (LQ->length == MaxSize)
	{
		return 1;
	}
	return 0;
}

//入队,将元素data 插入到队列LQ 中
int EnterQueue(LinkQueue* LQ, DataType data) 
{
	if (!LQ) return 0;
	if (IsFull(LQ)) 
	{
		cout << "无法插入元素" << data << ", 队列已满!" << endl;
		return 0;
	}
	QNode* qNode = new QNode;
	qNode->data = data;
	qNode->next = NULL;
	if (IsEmpty(LQ))//空队列
	{
		LQ->front = LQ->rear = qNode;
	}
	else
	{
		LQ->rear->next = qNode;//在队尾插入节点qNode
		LQ->rear = qNode; //队尾指向新插入的节点
	}
	LQ->length++;
	return 1;
}

//出队，将队列中队头的元素出队，其后的第一个元素成为新的队首
int DeleteQueue(LinkQueue* LQ, DataType* data) {
	QNode* tmp = NULL;
	if (!LQ || IsEmpty(LQ)) 
	{
		cout << "队列为空！" << endl;
		return 0;
	}

	if (!data) return 0;

	tmp = LQ->front;
	LQ->front = tmp->next;
	if (!LQ->front) LQ->rear = NULL;//如果对头出列后不存在其他元素，则rear节点也要置空
		* data = tmp->data;
	LQ->length--;
	delete tmp;

	return 1;
}

//打印队列中的各元素
void PrintQueue(LinkQueue* LQ)
{
	QueuePtr tmp;

	if (!LQ) return;

	if (LQ->front == NULL) 
	{
		cout << "队列为空！";
		return;
	}

	tmp = LQ->front;

	while (tmp)
	{
		cout << setw(4) << tmp->data;
		tmp = tmp->next;
	}
	cout << endl;
}

//获取队首元素，不出队
int GetHead(LinkQueue* LQ, DataType* data)
{
	if (!LQ || IsEmpty(LQ))
	{ 
		cout << "队列为空!" << endl;
		return 0;
	}

	if (!data) return 0;

	*data = LQ->front->data;

	return 1;
}

//清空队列
void ClearQueue(LinkQueue* LQ)
{
	if (!LQ) return;
	while (LQ->front) 
	{
		QueuePtr tmp = LQ->front->next;
		delete LQ->front;
		LQ->front = tmp;
	}

	LQ->front = LQ->rear = NULL;
	LQ->length = 0;
}

//获取队列中元素的个数
int getLength(LinkQueue* LQ) 
{
	if (!LQ) return 0;
	return LQ->length;
}

int main()
{
	LinkQueue* LQ = new LinkQueue;
	DataType data = -1;
	//初始化队列
	InitQueue(LQ);
	//入队
	for (int i = 0; i < 7; i++) {
		EnterQueue(LQ, i);
	}
	//打印队列中的元素
	printf("队列中的元素(总共%d 个)：", getLength(LQ)); 
	PrintQueue(LQ);
	cout << endl;

	//出队
	for(int i=0; i<10; i++)
	{
		if (DeleteQueue(LQ, &data)) 
		{
			cout << "出队的元素是：" << data << endl;
		}
		else 
		{	
			cout << "出队失败！" << endl;
		}
	}

	//打印队列中的元素
	printf("出队一个元素后，队列中剩下的元素[%d]：", getLength(LQ));
	PrintQueue(LQ);
	cout << endl;

	ClearQueue(LQ);
	cout << "清空队列!\n";
	PrintQueue(LQ);

	//清理资源
	delete LQ;
	system("pause");
	return 0;
}

参考资料来源：

奇牛学院

标签：return,14,队列,SQ,int,LQ,front,顺序存储
From： https://www.cnblogs.com/codemagiciant/p/17472885.html

相关文章

  • 第四天打卡|24. 两两交换链表中的节点 ● 19.删除链表的倒数第N个节点 面试题 02.07.
    24.两两交换链表中的节点：简单的交换 19.删除链表的倒数第N个节点： ●  面试题 02.07. 链表相交:这题没看过答案真的写不出来。太巧妙了  142.环形链表II：这题写过但是忘记怎么解的了还是看的答案。下次不能忘记  ......
  • 算法学习day53动态规划part14-1143、53、1035
    packageLeetCode.DPpart14;/***1143.最长公共子序列*给定两个字符串text1和text2，返回这两个字符串的最长公共子序列的长度。*如果不存在公共子序列，返回0。*一个字符串的子序列是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些......
  • UVA1401 Remember the Word
    思路首先有一个比较朴素的DP就是记\(f_i\)为\(s\)的从第\(i\)个字符开始到字符串结尾的划分方案数，记模板串的集合为\(T\)，\(s\)从第\(i\)个字符开始到字符串结尾的子串为\(s(i)\)，那么不难写出方程：\[f_i=\sumf_{i+\operatorname{len}(t)}[t\inT\landt是s(......
  • odoo14在tree、kanban视图上添加dashboard
    效果图：  实现代码：js：view的类型原来1个js给拆分成了4个：view,controller,renderer,model​​1、view：AbstractView​​的子类，这是工厂类：类需要解析 ​​arch​​字段并设置其它3个类2、Renderer：渲染器，来自 ​​AbstractRenderer：负责在用户界面中展示数据；​​3、Contr......
  • 9.14 泛型的基本定义
    demo1classPoint<T>{//T属于类型标记,可以设置多个标记privateTx;privateTy;publicvoidsetX(Tx){this.x=x;}publicvoidsetY(Ty){this.y=y;}publicTgetX(){returnthis.x;}publicT......
  • Google Earth Engine（GEE）——全球栖息地异质性(数据集包含14个指标)
    全球栖息地异质性这些数据集包含14个指标，根据中分辨率成像分光仪（MODIS）获取的增强植被指数（EVI）图像的纹理特征，以多种分辨率量化全球生境的空间异质性。关于这些指标的更多信息以及对其在生物多样性建模中的效用的评价。该数据集以1公里、5公里和25公里的分辨率生成，这里只列出了1公里......
  • 4.14学习总结
    androidstdio中button的按下与松开实现图标转换 图片：首先在res目录下的drawable文件夹下创建select功能的.xml文件,然后下载两张图片drawable文件夹(图片名称开头不可以是数字)，第二步，在.xml文件中添加如下两行代码<itemandroid:drawable="@drawable/图片名称"android:stat......
  • Luogu P3167 [CQOI2014]通配符匹配
    [CQOI2014]通配符匹配题目描述几乎所有操作系统的命令行界面(CLI)中都支持文件名的通配符匹配以方便用户。最常见的通配符有两个，一个是星号(”“')，可以匹配0个及以上的任意字符：另一个是问号(”？“)，可以匹配恰好一个任意字符。现在需要你编写一个程序，对于给定的文件名列表和一个包......
  • ObjectARX 2014 项目升级到高版本vs2017出现提示平台集v141未安装
    ARX2014项目升级到vs2017的时候提示平台集未安装。解决方式：在vcproj文件中，添加相应的平台集。v141类似截图......
  • 《数据结构与算法》之队列与链表复习
    导言：我们在上一次学习了堆栈的数据结构以后，可以了解到它是受限制的操作，比如我们操作只能在栈顶，现在我们要学习的东西叫做队列，它也是受限制的一种数据结构，它的特点是队头只出数据，而队尾只入数据，它的结构就和它的名字，像我们平时排队一样先来的人肯定要先服务啊，所以它的英文叫做Fri......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99