数据结构队列基本实现

news/2024/10/23 0:38:50/

        队列是一种操作受限的线性表。在这种线性表上，插入操作限定在表的某一端进行，删除限定在表的另一端进行。允许插入的一端为队尾，允许删除的一端为对头。队列按照存储方式分为两种，分别是顺序存储和链式存储。其中顺序存储方式的队列为循环队列。

废话不多说，直接上代码，下面是是我简单实现的队列的两种模式，顺序和链式，采用C++语言,在Qt5.9.0下编译成功。

#include "queue.h"

#ifndef QUEUE_H
#define QUEUE_H#include <iostream>#define MaxSize 100
#define ERROR   0
#define OK      1
typedef int size_type;
typedef unsigned status_type;template <class QElemType>
class Queue
{template<class T>friend std::ostream &operator<<(std::ostream &output, const Queue<T> &Q);
public:Queue();//构造函数Queue(size_type size);Queue(const Queue<QElemType> &Q);//拷贝构造~Queue();status_type EnQueue(QElemType x);//入队status_type Full();//判断队列是否已满status_type Empty();//判空函数size_type Size() const;status_type OutQueue(QElemType *x);//出队status_type GetHeadQueue(QElemType *x);//取队头QElemType Front()const;QElemType& Front();Queue<QElemType>& operator=(const Queue<QElemType> &Q);private:QElemType *m_Data;size_type m_Front;size_type m_Rear;size_type m_size;
};#endif // QUEUE_H

#include "queue.cpp"

#include "queue.h"
#include <cassert>template <class QElemType>
Queue<QElemType>::Queue():m_Front(0),m_Rear(0),m_size(MaxSize + 1)
{m_Data = new QElemType[MaxSize + 1];assert(m_Data != NULL);
}template <class QElemType>
Queue<QElemType>::Queue(size_type size):m_Front(0),m_Rear(0),m_size(size + 1)
{m_Data = new QElemType[size + 1];assert(m_Data != NULL);
}template <class QElemType>
Queue<QElemType>::Queue(const Queue<QElemType> &Q):m_Front(Q.m_Front),m_Rear(Q.m_Rear),m_size(Q.m_size)
{m_Data = new QElemType[m_size];assert(m_Data != NULL);for (int i = 0; i < Q.Size(); i++){m_Data[(m_Front + i + 1) % m_size] = Q.m_Data[(Q.m_Front + i + 1) % Q.m_size];}
}template <class QElemType>
Queue<QElemType>::~Queue()
{delete []m_Data;
}template<class QElemType>
Queue<QElemType>& Queue<QElemType>::operator=(const Queue<QElemType> &Q)
{if (this != &Q){delete []m_Data;m_Front = Q.m_Front;m_Rear  = Q.m_Rear;m_size  = Q.m_size;m_Data = new QElemType[m_size];if (!m_Data){std::cerr << "Error:Malloc faiure!" << std::endl;return *this;}for(int i = 0; i < Q.Size(); i++){m_Data[(m_Front + i + 1) % m_size] = Q.m_Data[(m_Front + i + 1) % m_size];}}return *this;
}template <class QElemType>
status_type Queue<QElemType>::EnQueue(QElemType x)
{if (Full()){QElemType *newData = new QElemType[2*m_size];if (!newData){std::cerr <<"Error:Queue is full,out of memory!" << std::endl;return ERROR;}for (int i = 0; i != 2*m_size && !Empty(); i++){OutQueue(newData + m_Front + 1);}delete []m_Data;m_Data = newData;m_size = 2*m_size;m_Front = 0;m_Rear = (m_Rear + 1) % m_size;m_Data[m_Rear] = x;return OK;}m_Rear = (m_Rear + 1) % m_size;m_Data[m_Rear] = x;return OK;
}template <class QElemType>
status_type Queue<QElemType>::OutQueue(QElemType *x)
{if (Empty()){std::cerr << "Error:Queue is free!" << std::endl;return ERROR;}m_Front = (m_Front + 1) % m_size;*x = m_Data[m_Front];return OK;
}template <class QElemType>
status_type Queue<QElemType>::GetHeadQueue(QElemType *x)
{if (Empty()){std::cerr << "Error:Queue is free!" << std::endl;return ERROR;}*x = m_Data[(m_Front + 1) % m_size];return OK;
}template <class QElemType>
status_type Queue<QElemType>::Empty()
{return m_Rear == m_Front;
}template <class QElemType>
status_type Queue<QElemType>::Full()
{return (m_Rear + 1) % m_size == m_Front;
}template <class QElemType>
size_type Queue<QElemType>::Size()const
{return (m_Rear - m_Front + m_size) % m_size;
}template <class QElemType>
QElemType Queue<QElemType>::Front()const
{if (Empty()){std::cerr << "Error:Queue is empty!" << std::endl;assert(!Empty());}return m_Data[m_Front + 1];
}template <class QElemType>
QElemType& Queue<QElemType>::Front()
{if (Empty()){std::cerr << "Error:Queue is empty!" << std::endl;assert(!Empty());}return m_Data[m_Front + 1];
}template<class T>
std::ostream &operator<<(std::ostream& output, const Queue<T> &Q)
{size_type front = Q.m_Front;output << "Queue element is:" << std::endl;while (front != Q.m_Rear) {output << Q.m_Data[++front % Q.m_size] << " ";}return output;
}

        上面的代码是采用顺序存储方式实现的队列，默认数组第一个元素不存储数据，队列的最大存储容量为MaxSize - 1，所以构造函数中，对成员变量m_size的初始化需要做MaxSize + 1的操作。但是在EnQueue()函数中做了一个扩容的操作，所以实际的存储容量是不固定的。

/*

这部分代码是对队列的一个扩容的操作

*/

QElemType *newData = new QElemType[2*m_size]; if (!newData) { std::cerr <<"Error:Queue is full,out of memory!" << std::endl; return ERROR; }

for (int i = 0; i != 2*m_size && !Empty(); i++) { OutQueue(newData + m_Front + 1); } delete []m_Data; m_Data = newData; m_size = 2*m_size; m_Front = 0; m_Rear = (m_Rear + 1) % m_size; m_Data[m_Rear] = x;

下面是链式存储队列：

#include "linkqueue.h

#ifndef LINKQUEUE_H
#define LINKQUEUE_H#include <iostream>#define ERROR   0
#define OK      1
typedef int status_t;
typedef unsigned size_t;template<class LQElemType>
class LinkQueue
{
private:typedef struct QNode{LQElemType data;struct QNode *next;QNode():next(NULL){}QNode(const LQElemType& newData, QNode* newNext = NULL):data(newData),next(newNext){}}QNode, *QueuePtr;public:LinkQueue();//构造函数LinkQueue(const LinkQueue<LQElemType>& LQ);//拷贝构造~LinkQueue();status_t EnQueue(LQElemType e);//入队status_t OutQueue(LQElemType *e);//出队status_t GetHeadQueue(LQElemType *e);//取队头status_t Empty()const;//判空函数size_t Size()const;void Clear();//清除队列LQElemType Front()const;LQElemType& Front();LinkQueue<LQElemType>& operator = (const LinkQueue<LQElemType>& LQ);template<class T>friend std::ostream& operator << (std::ostream& output, const LinkQueue<T>& LQ);private:QueuePtr m_Front;QueuePtr m_Rear;size_t count;
};#endif // LINKQUEUE_H

#include "linkqueue.cpp"
"

#include "linkqueue.h"
#include <cassert>template<class LQElemType>
LinkQueue<LQElemType>::LinkQueue():count(0)
{QueuePtr pQ = new QNode();assert(pQ != NULL);m_Front = m_Rear = pQ;
}template<class LQElemType>
LinkQueue<LQElemType>::LinkQueue(const LinkQueue<LQElemType> &LQ):count(LQ.count)
{QueuePtr pQ = new QNode();assert(pQ != NULL);m_Front = m_Rear = pQ;QueuePtr p = LQ.m_Front->next;while (p) {if (EnQueue(p->data))p = p->next;}
}template<class LQElemType>
LinkQueue<LQElemType>::~LinkQueue()
{delete m_Front;delete m_Rear;
}template<class LQElemType>
status_t LinkQueue<LQElemType>::EnQueue(LQElemType e)
{QueuePtr pQ = new QNode(e);if (!pQ){std::cerr << "Error:Malloc faiure!" << std::endl;return ERROR;}count++;m_Rear->next = pQ;m_Rear = pQ;return OK;
}template<class LQElemType>
status_t LinkQueue<LQElemType>::OutQueue(LQElemType *e)
{QueuePtr pQ;if (Empty()){std::cerr << "Error:Queue is empty!" << std::endl;return ERROR;}count--;*e = m_Front->next->data;pQ = m_Front->next;m_Front->next = pQ->next;if (m_Front->next == NULL){m_Rear = m_Front;}delete pQ;return OK;
}template<class LQElemType>
status_t LinkQueue<LQElemType>::GetHeadQueue(LQElemType *e)
{if (Empty()){std::cerr << "Error:Queue is empty!" << std::endl;return ERROR;}*e = m_Front->next->data;return OK;
}template<class LQElemType>
status_t LinkQueue<LQElemType>::Empty() const
{return m_Front->next == NULL;
}template<class LQElemType>
size_t LinkQueue<LQElemType>::Size() const
{return count;
}template<class LQElemType>
void LinkQueue<LQElemType>::Clear()
{while (m_Front->next) {QueuePtr p = m_Front->next;m_Front->next = p->next;delete p;}m_Rear = m_Front;count = 0;
}template<class LQElemType>
LQElemType LinkQueue<LQElemType>::Front()const
{if (Empty()){std::cerr << "Error:Queue is empty!" << std::endl;assert(!Empty());}return m_Front->next->data;
}template<class LQElemType>
LQElemType& LinkQueue<LQElemType>::Front()
{if (Empty()){std::cerr << "Error:Queue is empty!" << std::endl;assert(!Empty());}return m_Front->next->data;
}template<class LQElemType>
LinkQueue<LQElemType>& LinkQueue<LQElemType>::operator = (const LinkQueue<LQElemType>& LQ)
{if (this != &LQ){Clear();QueuePtr p = LQ.m_Front->next;while (p) {if (EnQueue(p->data))p = p->next;}count = LQ.count;}return *this;
}template<class T>
std::ostream& operator << (std::ostream& output, const LinkQueue<T>& LQ)
{auto p = LQ.m_Front->next;output << "Link queue element is:" << std::endl;while (p) {output << p->data << " ";p = p->next;}return output;
}

        在链式队列中，对头指针m_Front指向第一个结点，通俗讲就是对头指针m_Front就是第一个结点，而且默认第一个结点是不存储数据的；队尾指针m_Rear指向最后一个结点，当m_Front和m_Rear指向同一个结点时，队列为空。next指针存放下一个结点的地址，当m_Front->next != NULL时，队列一定不为空，而且任何时候m_Rear->next == NULL都成立。

测试代码：

#include <iostream>
#include "queue.cpp"
#include "linkqueue.cpp"using namespace std;int main()
{//C++实现循环队列cout << "C++实现循环队列" << endl;Queue<int> q(20);LinkQueue<int> lq;for (int i = 0; i < 30; i++){q.EnQueue(i + 1);lq.EnQueue(i * 10);}cout << q << endl;Queue<int> q2;q2 = q;cout << q2 << endl;Queue<int> q3 = q2;cout << q3 << endl;cout << lq << endl;LinkQueue<int> lq2;LinkQueue<int> lq3 = lq;lq2 = lq;cout << lq2 << endl;cout << lq3 << endl;LinkQueue<int> lq4;return 0;
}



上面是是我花了一点时间实现的队列，有错的地方或者不完善的地方，欢迎吐槽并指正


http://www.ppmy.cn/news/470564.html

相关文章

二、LINQ

二、LINQ

文章目录 一、LINQ概述与查询语法二、LINQ方法语法基础三、LINQ聚合操作与元素操作四、数据类型转换 LINQ&#xff08;Language Integrated Query&#xff0c;语言集成查询&#xff09;&#xff0c;可为C#语法提供强大的查询功能。 一、LINQ概述与查询语法 LINQ提供了一种跨数…
阅读更多...
L2-2 列车调度

L2-2 列车调度

火车站的列车调度铁轨的结构如下图所示。 两端分别是一条入口&#xff08;Entrance&#xff09;轨道和一条出口&#xff08;Exit&#xff09;轨道&#xff0c;它们之间有N条平行的轨道。每趟列车从入口可以选择任意一条轨道进入&#xff0c;最后从出口离开。在图中有9趟列车&am…
阅读更多...
RLx2~~

RLx2~~

大模型时代&#xff0c;模型压缩和加速显得尤为重要。传统监督学习可通过稀疏神经网络实现模型压缩和加速&#xff0c;那么同样需要大量计算开销的强化学习任务可以基于稀疏网络进行训练吗&#xff1f;本文提出了一种强化学习专用稀疏训练框架&#xff0c;可以节省至多 95% 的训…
阅读更多...
DQL2

DQL2

/* DQL标准语法结构:编写DQL一定要严格按照此语法的顺序来实现&#xff01; SELECT [ALL | DISTINCT] ALL表示查询出所有的内容 DISTINCT 去重 {* | 表名.* | 表名.字段名[ AS 别名][,…]} 指定查询出的字段的 FROM 表名[AS 别名][,表1… AS 别名] [INNER | [LEFT | RIGHT] [OU…
阅读更多...
Hql(01)

Hql(01)

一&#xff1a;什么是Hql HQL是Hibernate Query Language的缩写&#xff0c;提供更加丰富灵活、更为强大的查询能力&#xff1b;HQL更接近SQL语句查询语法。 二&#xff1a;hql和sql区别/异同&#xff08;面试题&#xff09; HQL S…
阅读更多...
HQL(二)

HQL(二)

一、写BaseDao 需求&#xff1a; 按名字分页查询对应书籍信息 我们用hql是想我们的需求&#xff0c;是这样的&#xff1a; public List<Book> list1(Book book,PageBean pageBean){Session session SessionFactoryUtils.getSession();Transaction transaction sess…
阅读更多...
蓝桥杯Java知识准备

蓝桥杯Java知识准备

1.输入输出 提到了几个IO类&#xff0c;这里推荐使用BufferedReader输入&#xff0c;BufferedWriter输出&#xff0c;当输入输出的数据量大于一百万左右就必须使用快速IO不能直接使用Scanne和System.out.print。 1.1 正常输入输出 输入 首先定义一个Scanner对象&#xff0c…
阅读更多...
lq到底是什么意思_LQ是什么意思..?!谁知道..!?

lq到底是什么意思_LQ是什么意思..?!谁知道..!?

导航：网站首页 > LQ是什么意思..?!谁知道..!? LQ是什么意思..?!谁知道..!? 匿名网友: 导商Leading Quotient——LQ。 导商即为领导商，是指一个人领导、指导、引导、带领他人或团队组织的智慧和能力的商数。 导商既取决于领导理论与方式，又取决于领导环境与气氛；既取…
阅读更多...
最新文章

Copyright @ 2022~2023