C++数据结构之队列详解

此时思考一个问题，当删除元素时（元素出队列时）会出现假饱和的情况，如上图m_data[0]和m_data[1]再进行出队列操作之后，这两个位置可以容纳新的元素，但m_rear没有回到原本的m_data[0]位置，因此需要引入一个新的队列结构，环形队列，m_rear这个位置可以从0到9再到0,周而复始不停的重复，保存的数据像在一个环状空间一样，这种头尾相连的队列结构就叫循环队列。前面的几种队列都可以

dryter

1959人浏览 · 2023-03-23 21:41:12

dryter · 2023-03-23 21:41:12 发布

1.队列的简述

队列也是一种收限制的线性表，其特点是在一端进行插入的时，再另一端进行出队列的操作（删除操作）。把允许插
入操作的一端叫做队尾，允许删除操作的一端叫做队头。队列就像超市排队结账的人群，排在收银台一端的优先结账
离开，后面的依次排队并一直收银台前进，每出队列一个，向前走一步。
向队列插入元素称为入队，从队列中删除元素称为出队。不包含任何数据的队列称为空队列，队列也被称为先进先出
（First In First Out：FIFO）的线性表，换句话说，插入数据只能在队尾进行，删除操作只能在队头进行。
（后面还会有特殊情况：双端队列）

队列的入队
在这里插入图片描述
队头填充进四个元素

2.队列的基本顺序存储代码：

#define MaxSize 10//队列的初始化尺寸

template<typename T>
class SeqQueue 
{
public:
	SeqQueue();
	~SeqQueue();

public:
	bool EnQueue(const T& e);//入队列
	bool DeQueue(T& e);//出队列
	bool GetHead(T& e);//读取头元素
	void ClearQueue();//清空队列
	void DispList();//输出顺序队列中的所有元素
	int ListLength();//获取队列长度（元素个数）
	bool IsEmpty();//判断队列是否为空
	bool IsFull();//判断队列是否已满

private:
	T* m_data;
	int m_front;//队头指针(数组下标)
	int m_rear;//队尾指针（数组下标）,允许出队的那一端
};

template<typename T>
SeqQueue<T>::SeqQueue() 
{
	m_data = new T[MaxSize];
	m_front = 0;
	m_rear = 0;
}

template<typename T>
SeqQueue<T>::~SeqQueue() 
{
	delete[] m_data;
}

template<typename T>
bool SeqQueue<T>::EnQueue(const T& e)
{
	if (IsFull() == true) 
	{
		cout << "队列满了，不能再进行入队列操作了！" << endl;
		return false;
	}
	m_data[m_rear] = e;
	m_rear++;
	return true;
}

template<typename T>
bool SeqQueue<T>::DeQueue(T& e)
{
	if (IsEmpty() == true) 
	{
		cout << "当前队列为空，不能进行出队列操作!" << endl;
		return false;
	}
	e = m_data[m_front];
	m_front++;
	return true;
}

template<typename T>
bool SeqQueue<T>::GetHead(T& e) 
{
	if (IsEmpty() == true) 
	{
		cout << "队列为空，无法进行获取头元素操作!" << endl;
		return false;
	}
	e = m_data[m_front];
	return true;
}

template<typename T>
void SeqQueue<T>::DispList() 
{
	for (int i = 0; i < m_rear;i++) 
	{
		cout << m_data[i] << " ";
	}
	cout << endl;
}

template<typename T>
int SeqQueue<T>::ListLength()
{
	return m_rear - m_front;
}

template<typename T>
bool SeqQueue<T>::IsEmpty() 
{
	if (m_front == m_rear) 
	{
		return true;
	}
	return false;
}

template<typename T>
bool SeqQueue<T>::IsFull() 
{
	if (m_rear >= _Maximum) 
	{
		return true;
	}
	return false;
}

template<typename T>
void SeqQueue<T>::ClearQueue() 
{
	m_rear = m_front = 0;
}

出队列m_data[0]

3.优化普通队列，成为可以循环接受数据的循环队列

循环队列代码如下：

#define MaxSize 10

template<typename T>
class RoundQueue
{
public:
	RoundQueue();
	~RoundQueue();

public:
	bool EnQueue(const T& e);//入队列
	bool DeQueue(T& e);//出队列
	bool GetHead(T& e);//读取头元素
	void ClearQueue();//清空队列
	void DispList();//输出顺序队列中的所有元素
	int ListLength();//获取队列长度（元素个数）
	bool IsEmpty();//判断队列是否为空
	bool IsFull();//判断队列是否已满

private:
	T m_data;
	int m_front;//队头指针(数组下标)
	int m_rear;//队尾指针（数组下标）,允许出队的那一端
	char m_tag;
};

template<typename T>
RoundQueue<T>::RoundQueue()
{
	m_data = new T[MaxSize];
	m_front = 0;
	m_rear = 0;
	m_tag = 0;//加入表示栈是否满的状态
}

template<typename T>
RoundQueue<T>::~RoundQueue()
{
	delete[] m_data;
}

template<typename  T>
bool RoundQueue<T>::EnQueue(const T& e) 
{
	if (IsFull () == true)
	{
		cout << "队列满了，不能再进行入队列操作了！" << endl;
		return false;
	}
	m_tag = 1;
	m_data[m_rear] = e;
	m_rear = (m_rear + 1) % MaxSize;
	return true;
}

template<typename T>
bool RoundQueue<T>::DeQueue(T& e) 
{
	if (IsEmpty() == true)
	{
		cout << "当前队列为空，不能进行出队列操作!" << endl;
		return false;
	}
	m_tag = 0;
	e = m_data[m_front];
	m_front = (m_front + 1) % MaxSize;
	return true;
}

template<typename T>
bool RoundQueue<T>::GetHead(T& e)
{
	if (IsEmpty() == true)
	{
		cout << "队列为空，无法进行获取头元素操作!" << endl;
		return false;
	}
	e = m_data[m_front];
	return true;
}

template<typename T>
void RoundQueue<T>::DispList()
{
	for (int i = m_front;i != m_rear)
	{
		cout << m_data[i] << " ";
		i = (i + 1) % MaxSize;
	}
	cout << endl;
}

template<typename T>
bool RoundQueue<T>::IsFull()
{
	if (m_rear == m_front && tag == 0)
	{
		return true;
	}
	return false;
}

template<typename T>
int RoundQueue<T>::ListLength()
{
	return (m_rear + MaxSize - m_front) % MaxSize;
}

template<typename T>
bool RoundQueue<T>::IsEmpty()
{
	if (m_front == m_rear && tag == 0)
	{
		return true;
	}
	return false;
}

template<typename T>
void RoundQueue<T>::ClearQueue()
{
	m_rear = m_front = m_tag = 0;
}

循环队列队列满的情况，如下图：
在这里插入图片描述

4.队列的链式结构实现

和前面所有的数据结构一样，队列也有链式结构

空队列的情况：
在这里插入图片描述
插入两个元素之后的队列：

实现代码如下图所示：

template<typename T>
struct QueueNode 
{
	T data;//数据域
	QueueNode<T>* next;//指针域，指向下一个节点
};

template<typename T>
class LinkQueue 
{
public:
	LinkQueue();
	~LinkQueue();

public:
	bool EnQueue(const T& e);//入队
	bool DeQueue(T& e);//出队
	bool GetHead(T& e);//读取头元素
	void DispList();//输出链式队列中的所有元素
	int ListLength();//获取链式队列的长度（链式表元素个数）
	bool IsEmpty();//判断链式队列是否为空

private:
	QueueNode<T>* m_front;//头指针，这一端允许出队（删除）
	QueueNode<T>* m_rear;//尾指针记录入队
	int m_length;
};

template<typename T>
LinkQueue<T>::LinkQueue() 
{
	m_front = new QueueNode<T>;
	m_front->next = nullptr;
	m_rear = m_front;
	m_length = 0;
}

template<typename T>
LinkQueue<T>::~LinkQueue() 
{
	QueueNode<T>* pnode = m_front->next;
	QueueNode<T>* ptmp;
	while (pnode != nullptr)
	{
		ptmp = pnode;
		pnode = pnode->next;
		delete ptmp;
	}
	delete m_front;
	m_front = m_rear = nullptr;
	m_length = 0;
}

template<typename T>
bool LinkQueue<T>::EnQueue(const T& e) 
{
	QueueNode<T>* node = new QueueNode<T>;
	node->data = e;
	node->next = nullptr;

	m_rear->next = node;//新节点插入到头指针之后
	m_rear = node;//更新队尾指针的位置
	m_length++;
	return true;
}

template<typename T>
bool LinkQueue<T>::DeQueue(T& e) 
{
	if (IsEmpty() == true) 
	{
		cout << "当前链式队列为空，无法进行出队列操作!" << endl;
		return false;
	}
	QueueNode<T>* p_willdel = m_front->next;
	e = p_willdel->data;
	m_front->next = p_willdel->next;
	if (m_rear == p_willdel) //队列中只有一个元素，删除之后，m_rear和m_front相连
	{
		m_rear = m_front;
	}
	delete p_willdel;
	m_length--;
	return true;
}

template<typename T>
void LinkQueue<T>::DispList() 
{
	QueueNode<T>* p = m_front->next;
	while (p != nullptr) 
	{
		cout << p->data << " ";
		p = p->next;
	}
	cout << endl;
}

template<typename T>
int LinkQueue<T>::ListLength() 
{
	return m_length;
}

template<typename T>
bool LinkQueue<T>::IsEmpty() 
{
	if (m_front == m_rear) 
	{
		return true;
	}
	return false;
}

5.双端队列

前面的几种队列都可以看成普通的队列，还有一种变形的队列-双端队列。双端队列就是允许两端插入和删除数据。STL中提供的名字叫做deque的容器，就是一个典型的双端队列。双端队列的存取如图所示：

在这里插入图片描述
也可以对双端队列进行一系列的限制，可以有输入受限的的双端队列和输出受限的双端队列，如图为输入受限的双端队列，只能一端输入，两端输出：

也可也一端输出，两端输入的双端队列，如图：

代码实现如下：

// 节点
template<class T>
class Node
{
public:
	T data;
	Node<T> *left;
	Node<T> *right;
	Node() {
		data= 0;
		left = right = nullptr;
	}
	Node(T n) {
		data= n;
		left = right = nullptr;
	}
};
// 双端队列
template<class T>
class double_ended_queue {
public:
	Node<T>*queue_left, *queue_right;
	int num;
	int size;
	
	double_ended_queue() {
		queue_left=queue_right = nullptr;
		num = 0;
		size = 10;
	}
	
	void IsEmpty();
	void IsFull();
	void AddLeft(T);
	void AddRight(T);
	void DeleteLeft();
	void DeleteRight();
	void Print();
};

template<class T>
void double_ended_queue<T>::IsEmpty() {
	num == 0 ? cout << "YES" << endl : cout << "NO" << endl;
}

template<class T>
void double_ended_queue<T>::IsFull() {
	num == size ? cout << "YES" << endl : cout << "NO" << endl;
}

template<class T>
void double_ended_queue<T>::Print() {
	if (num == 0)
	{
		cout << "EMPTY" << endl;
		return;
	}
	Node<T>*p = queue_left;
	for (int i = 0; i < num-1; i++) {
		cout << p->data << " ";
			p = p->right;
	}
	cout << p->data << endl;
}

template<class T>
void double_ended_queue<T>::AddLeft(T n) {
	Node<T>*p = new Node<T>(n);
	if (num == 0)
	{
		queue_left =queue_right=p;
		queue_left->left =queue_left->right=nullptr;
		num++;
	}
	else{
		if (num == size)
		{
			cout << "FULL  ";
			Print();
			return;
		}
		queue_left->left = p;
		p->right = queue_left;
		queue_left = queue_left->left;
		num++;
	}
	Print();
}

template<class T>
void double_ended_queue<T>::AddRight(T n) {
	Node<T>*p = new Node<T>(n);
	if (num == 0)
	{
		queue_left = queue_right = p;
		queue_right->left = queue_right->right = nullptr;
		num++;
	}
	else {
		if (num == size)
		{
			cout << "FULL  " ;
			Print();
			return;
		}
		queue_right->right = p;
		p->left = queue_right;
		queue_right = queue_right->right;
		num++;
	}
	Print();
}

template<class T>
void double_ended_queue<T>::DeleteLeft() {
	if (num == 0) {
		cout << "EMPTY" << endl;
		return;
	}
	Node<T>*p = queue_left->right;
	delete queue_left;
	queue_left = p;
	num--;
	Print();
}

向您推荐>>Eolink开发者社区

权威｜前沿｜技术｜干货｜国内首个API全生命周期开发者社区

更多推荐

ELK实现containerd的容器日志采集展示【基于logging的全栈监测】

企业级ELK Stack构建介绍

云原生

深入理解 Mocha 测试框架：从零实现一个 Mocha

前言什么是自动化测试自动化测试在很多团队中都是Devops环节中很难执行起来的一个环节，主要原因在于测试代码的编写工作很难抽象，99%的场景都需要和业务强绑定，而且写测试代码的编写工作量往往比编写实际业务代码的工作量更多。在一些很多业务场景中投入产出比很低，适合写自动化测试的应该是那些中长期业务以及一些诸如组件一样的基础库。自动化测试是个比较大的概念，其中分类也比较多，比如单元测试，端对端测试，集

云原生

(20200916 Solved)docker-compose up创建容器自动退出

问题描述如题，创建容器后自动退出了。并且docker start container无效解决方案原因是缺失了控制终端的配置，需要在docker-compose.yml中增加tty:true ，有时候这样也不行，需要再增加一个command:/bin/bash，命令不一定是这个，需要是一个不会退出的命令，然后用-d后台启动容器。Referencesdocker-compose启动容器后自动退出...

云原生

所有评论(0)

查看更多评论

dryter

@dryter

已为社区贡献1条内容