C++数据结构——队列「建议收藏」

C++数据结构——队列「建议收藏」C++数据结构——队列参考博客:http://www.cnblogs.com/QG-whz/p/5171123.htmlhttp://www.169it.com/article/2718050585107790752.html1、队列(Queue)与栈一样,是一种线性存储结构,它具有如下特点:(1)队列中的数据元素遵循“先进先出”(FirstInFirstOut)的原则,简称FIFO结构;(…

大家好,又见面了,我是你们的朋友全栈君。

                                                  C++数据结构——队列

 

参考博客:

 

1、队列(Queue)与栈一样,是一种线性存储结构,它具有如下特点:

(1)队列中的数据元素遵循“先进先出”(First In First Out)的原则,简称FIFO结构;

(2)在队尾添加元素,在队头删除元素。

2、队列的相关概念:

(1)队头与队尾: 允许元素插入的一端称为队尾,允许元素删除的一端称为队头;

(2)入队:队列的插入操作;

(3)出队:队列的删除操作。

3、队列的操作:

(1)入队: 通常命名为push()

(2)出队: 通常命名为pop()

(3)求队列中元素个数

(4)判断队列是否为空

(5)获取队首元素

4、队列的分类:

(1)基于数组的循环队列(循环队列)

(2)基于链表的队列(链队列)

5、实例分析

       C++队列queue模板类的定义在<queue>头文件中,queue 模板类需要两个模板参数,一个是元素类型,一个容器类型,元素类型是必要的,容器类型是可选的,默认为deque 类型。C++队列Queue是一种容器适配器,它给予程序员一种先进先出(FIFO)的数据结构。

       那么我们如何判断队列是空队列还是已满呢?

      a、栈空: 队首标志=队尾标志时,表示栈空。

      b、栈满 : 队尾+1 = 队首时,表示栈满。

       使用标准库的队列时, 应包含相关头文件,在栈中应包含头文件: #include< queue> 。定义:queue< int > q;

q.empty()               如果队列为空返回true,否则返回false
q.size()                返回队列中元素的个数
q.pop()                 删除队列首元素但不返回其值
q.front()               返回队首元素的值,但不删除该元素
q.push()                在队尾压入新元素
q.back()                返回队列尾元素的值,但不删除该元素

(1)基于数组的循环队列(循环队列)

       以数组作为底层数据结构时,一般讲队列实现为循环队列。这是因为队列在顺序存储上的不足:每次从数组头部删除元素(出队)后,需要将头部以后的所有元素往前移动一个位置,这是一个时间复杂度为O(n)的操作。具体的示例图参考:http://www.cnblogs.com/QG-whz/p/5171123.html

       循环队列,可以把数组看出一个首尾相连的圆环,删除元素时将队首标志往后移动,添加元素时若数组尾部已经没有空间,则考虑数组头部的空间是否空闲,如果是,则在数组头部进行插入。参考博客:【c++版数据结构】之循环队列的实现,判断循环队列是“空”还是“ 满”,有两种处理方法:

  • A. 设置状态标志位以区别空还是满
  • B. 少用一个元素,约定“队头front在队尾rear的下一个位置(指的是环的下一个位置)”作为“满”的标志

        C语言中,不能用动态分配的一维数组来实现循环队列,如果用户的应用程序中设有循环队列,则必须为它设定一个最大队列长度;如果用户无法预估所用队列的最大长度,则宜采用链队列。

       定义front为队列头元素的位置,rear为队列尾元素的位置,MAXSIZE为循环队列的最大长度。注意以下几点,循环队列迎刃而解:

  • A.  求元素的个数:(rear – front + MAXSIZE) % MAXSIZE
  • B.  front/rear指向逻辑的下一个空间  front =(front+1)%MAXSIZE,rear = (rear+1)%MAXSIZE
  • C.  判空:front == rear
  • D.  判满:(rear+1+MAXSZIE) == front

 

例子1、简单的队列操作

#include <queue>
#include <iostream>
using namespace std;

int main(){
	queue<int> q;
	for (int i = 0; i < 10; i++){
		q.push(i);
	}
	if (!q.empty()){
		cout << "队列q非空!" << endl;
		cout << "q中有" << q.size() << "个元素" << endl;
	}
	cout << "队头元素为:" << q.front() << endl;
	cout << "队尾元素为:" << q.back() << endl;
	for (int j = 0; j < 10; j++){
		int tmp = q.front();
		cout << tmp << " ";
		q.pop();
	}
	cout << endl;
	if (!q.empty()){
		cout << "队列非空!" << endl;
	}
	system("pause");
	return 0;
}
运行结果:
C++数据结构——队列「建议收藏」
 
 
例子2、循环队列的C++实现
#include <iostream>
#include <queue>
#include <string>
using namespace std;

template <typename T>
class LoopQueue
{
public:
	LoopQueue(int c = 10);
	~LoopQueue();
	bool isEmpty();        //队列的判空
	int size();            //队列的大小
	bool push(T t);        //入队列
	bool pop();            //出队列
	T front();            //队首元素

private:
	int capacity;
	int begin;
	int end;
	T*  queue;
};


template<typename T>
LoopQueue<T>::LoopQueue(int c = 10)
	:capacity(c), begin(0), end(0), queue(nullptr)
{
	queue = new T[capacity];
};

template<typename T>
LoopQueue<T>::~LoopQueue()
{
	delete[]queue;
}

template <typename T>
bool LoopQueue<T>::isEmpty()                   //判断循环队列是否为空
{
	if (begin == end)
		return true;
	return false;
};

template<typename T>
int LoopQueue<T>::size()
{
	return (end - begin + capacity) % capacity; //计算循环队列的长度
};

template<typename T>
bool LoopQueue<T>::push(T t)
{
	if (end + 1 % capacity == begin)            //判断队列是否已满
	{
		return false;
	}
	queue[end] = t;
	end = (end + 1) % capacity;
	return true;
};

template <typename T>
bool LoopQueue<T>::pop()                        //判断队列是否为空
{
	if (end == begin) 
	{
		return false;
	}
	begin = (begin + 1) % capacity;
	return true;
};

template <typename T>
T LoopQueue<T>::front()
{
	if (end == begin)
	{
		return false;
	}
	return queue[begin];
};

int main()
{
	LoopQueue<string> queue(6);
	queue.push("one");
	queue.push("two");
	queue.push("three");
	queue.push("four");
	queue.push("five");
	cout << "队列长度" << queue.size() << endl;
	while (!queue.isEmpty())
	{
		cout << queue.front() << endl;
		queue.pop();
	}
	getchar();
	//system("pause");
	return 0;
}

运行结果:

C++数据结构——队列「建议收藏」

 

(2)基于链表的队列(链队列)

       链队列是基于链表实现的队列,它不存在数组的O(n)的元素移动问题或空间浪费问题。我们所要确定的就是链表哪头做队首,哪头做队尾显然我们应该以链表头部为队首,链表尾部为队尾。存储一个指向队尾的指针,方便从链表尾插入元素;使用带头节点的链表,方便从链表头删除元素

代码参考:链式队列的C++实现

#include <iostream>
#include <cstdlib>
using namespace std;

struct QNode    //定义队列结点的数据结构
{
	QNode *next; //指针域,指向下一个结点
	double data;    //数据域,存储队列信息
};

struct LinkQueue    //定义队列的数据结构
{
	QNode *front;      //队首指针,指向QNode类型的指针
	QNode *rear;       //队尾指针
};

void InitQueue(LinkQueue &Q)     //构造一个空的队列
{
	QNode *q;
	q = new QNode;    //申请一个结点的空间
	q->next = NULL;   //当作头结点
	//队首与队尾指针都指向这个结点,指针域为NULL
	Q.front = q;
	Q.rear = q;
}

int IsEmpty(LinkQueue &Q)    //判断队列是否为空
{
	if (Q.rear == Q.front)
		return 0;
	else
		return 1;
}

void EnQueue(LinkQueue &Q, double e)     //从队列尾部插入元素
{
	QNode *p;    //新创建一个结点
	p = new QNode;
	p->next = NULL;
	p->data = e;  //输入数据信息
	//将新结点插入队列尾部
	Q.rear->next = p;
	Q.rear = p;       //设置新的尾结点
}

void DeQueue(LinkQueue &Q, double &e)   //从队列首部删除一个结点
{
	QNode *p;
	p = Q.front->next;
	e = p->data;    //保存要出队列的数据
	Q.front->next = p->next;       //将下一个结点当作头结点后面链接的第一个结点
	if (Q.rear == p)    //如果要删除的元素即为尾结点,则将头指针赋予尾指针,一同指向头结点,表示队列为空
		Q.rear = Q.front;
	delete p;
}

void DestoryQueue(LinkQueue &Q)       //销毁一个队列
{
	while (Q.front)
	{
		Q.rear = Q.front;    //从头节点开始,一个一个删除队列结点,释放空间
		delete Q.front;
		Q.front = Q.rear;
	}
}
int main()
{
	LinkQueue *Q;  //定义一个队列Q
	Q = new LinkQueue;
	InitQueue(*Q);
	cout << "开始往队列里输入数据,以-1作为结束符" << endl;
	cout << "请输入一个数:" << endl;
	double a, x;
	cin >> a;
	while (a != -1)
	{
		EnQueue(*Q, a);
		cout << "请输入一个数:" << endl;
		cin >> a;
	}
	//输出队列元素,队首->队尾
	QNode *p;
	p = Q->front->next;
	if (p == NULL)     //如果为空表,直接退出
	{
		cout << "队列为空!" << endl;
		return 0;
	}
	cout << "队列数据依次为:" << endl;
	while (p != NULL)
	{
		cout << p->data << " ";
		p = p->next;
	}
	cout << endl;
	//删除队列元素
	while (!IsEmpty(*Q))
	{
		DeQueue(*Q, x);
		cout << x << " ";
	}
	//释放内存空间
	delete Q->front;
	delete Q;
	system("pause");
	return 0;
}

运行结果:

C++数据结构——队列「建议收藏」

还可以参考代码:C++ 链队列和循环队列基本操作

 

总结:

       1、循环队列中判断队空的方法是判断front==rear,队满的方法是判断front=(rear+1)%MAXSIZE。(为什么不用一个length表示队长,当length==maxSize时表示队满,原因就是,在频繁的队列操作中,多出一个变量会大量的增加执行时间,所以不如浪费一个数组空间来得划算。)

       2、用单链表表示的链式队列特别适合于数据元素变动较大的情形,而且不存在溢出的情况

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/137023.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • 什么是前端开发工程师?

    什么是前端开发工程师?前端工程师是web前端开发工程师的简称,它是随着web(WorldWideWeb)发展,细分出来的行业,可以说,它是时代的产物。Web前端开发技术(因为技术的更新,又称为H5开发工程师)主要包括

  • Eclipse汉化教程2021新版

    Eclipse汉化教程2021新版Eclipse汉化教程Eclipse汉化教程确定Eclipse的版本方法一:打开eclipse,在启动画面中可以看到eclipse的版本名称(我的版本是2021-6),记住这个版本的名称;方法二:在Eclipse启动后,点击菜单栏中的Help(帮助)>>AboutEclipse(关于EclipseIDE)会弹出的AboutEclipse窗口,在这里也可以找到当前Eclipse的版本名称和版本号(Photon4.8.0);下载汉化包1.到Eclipse的官网上下

  • 页面可见性改变事件:visibilitychange

    页面可见性改变事件:visibilitychange1、PC浏览器上(以谷歌浏览器为例)刷新H5页面,会触发该事件,由于刷新导致该页面消失时,会检测到document.visibilityState===‘hidden’切换页面(包括切换离开和切换回来),导致页面暂时不处于激活状态时,会触发该事件。切换离开时document.visibilityState===‘hidden’,切换回该页面时,document.visibilityS…

  • Linux的redis启动过程详解「建议收藏」

    Linux的redis启动过程详解「建议收藏」目录redis的启动设置redis密码redis-server后台启动redis的启动在我的linux启动redis首先进入到安装redis的目录下cd/usr/local/redis/redis/redis-4.0.2/src启动redis-server服务./redis-server这种启动为前台启动,所以一般直接再VM中启动然后在Xshell中远程控制,启动redis客户端./redis-cli可以看到会有默认端口6379这时就

  • python读取图片属性信息

    python读取图片属性信息从照片里面获取GPS信息。可交换图像文件常被简称为EXIF(Exchangeableimagefileformat),是专门为数码相机的照片设定的,可以记录数码照片的属性信息和拍摄数据,EXIF信息不支持png,webp等图片格式。Python中使用ExifRead包读取图片的属性信息,安装方式为:pipinstallexifread使用exifread.process_file获取图像的信息:img_path=r”b…

  • 404页面制作

    404页面制作router/index.js//引用模板importErrorfrom’../components/Error.vue’//配置路由exportdefault[{ path:’*’, component:Error} ]Error.vue<template> <div> {{msg}} 页面不存在 </div…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号