C++数据结构：普通队列与循环队列_循环队列和普通队列的区别

什么是队列？

       队列是一种特殊的线性表，它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。队列中的数据元素遵循“先进先出”（First In First Out）的原则，简称FIFO结构。

队列分类

      普通队列与循环队列，普通队列可以看做是一列数据，环形队列可以看做是一个圆，当普通队列的数据索引可以循环设置时，普通队列就成了循环队列。这两种都可以用数组来实现。

循环队列的C++实现

       下面说明用数组实现循环队列的方法

     （1）队头和队尾都是0位置，从队尾插入，队头取数据。

     （2）插入数据：每次插入数据时，先判断队列是否是满的。在队列未满时，从队尾插入数据，队尾移向下一个位置。在队列满了时，如果要再插入数据，此时就得把队头数据弹出，队头指向下一个位置，再从队尾插入。

     （3）取数据，从队头取。

  示例代码：

  头文件

/*
环形队列
用数组模拟环形队列的实现
*/
 
#pragma once
 
class CircularQueue
{
public:
	CircularQueue(int capcity);
	~CircularQueue();
 
	int getQueueLength() const;
	bool isEmpty();
	bool isFull();
	void Clear();
	void Push(int data);  //插入新元素，队尾插
	int Pop();    //弹出首元素
	void Print();
 
private:
	int *m_pCirQueue;  //存放队列数据的数组容器
	int m_iCapacity;   //队列容量
	int m_iLength;     //队列长度
	int m_iHead;       //队列头索引
	int m_iTail;       //队列尾部索引
 
};
 

cpp文件

#include "CircularQueue.h"
#include <iostream>
 
using namespace std;
 
CircularQueue::CircularQueue(int capcity)
{
	m_iCapacity = capcity;
	m_iHead = 0;
	m_iTail = 0;
	m_iLength = 0;
	m_pCirQueue = new int[m_iCapacity];
}
 
CircularQueue::~CircularQueue()
{
	delete[] m_pCirQueue;
}
 
int CircularQueue::getQueueLength() const
{
	return m_iLength;
}
 
bool CircularQueue::isEmpty()
{
	if (m_iLength > 0)
	{
		return false;
	}
 
	return true;
}
 
bool CircularQueue::isFull()
{
	if (m_iLength == m_iCapacity)
	{
		return true;
	}
 
	return false;
}
 
void CircularQueue::Clear()
{
	m_iLength = 0;
	m_iHead = 0;
	m_iTail = 0;
}
 
void CircularQueue::Push(int data)
{
	if (isFull())
	{
		Pop();
	}
 
	m_pCirQueue[m_iTail] = data;
	m_iTail++;  //尾部指向下一个位置
 
	m_iTail = m_iTail % m_iCapacity;
	m_iLength++;
}
 
int CircularQueue::Pop()
{
	if (isEmpty())
	{
		return false;
	}
 
	int pop = m_pCirQueue[m_iHead];
	m_iHead++;
	m_iHead = m_iHead % m_iCapacity;
	m_iLength--;
	return pop;
}
 
//遍历循环队列
void CircularQueue::Print()
{
	for (int i = m_iHead; i < m_iHead + m_iLength; i++)
	{
		cout << m_pCirQueue[i % m_iCapacity] << " ";
	}
 
	cout << endl;
}

main.cpp测试循环队列的功能

#include <iostream>
#include "CircularQueue.h"
 
using namespace std;
 
int main()
{
	CircularQueue *pQueue = new CircularQueue(4);
 
	pQueue->Push(2);
	pQueue->Push(4);
	pQueue->Push(6);
	pQueue->Push(8);
	pQueue->Push(9);
	
	cout << "遍历队列" << endl;
	pQueue->Print();
 
	pQueue->Pop();
	cout << "遍历队列" << endl;
	pQueue->Print();
 
	system("pause");
	return 0;
}
 

运行结果：

模板队列的实现

       上面是用的int数组作为队列容器，我们可以用模板对其改造，代码如下，新建一个模板队列类TCircularQueue， 代码如下：

       TCircularQueue.h

#pragma once
 
template<typename T>
class TCircularQueue
{
public:
	TCircularQueue(int capacity = 10);
	~TCircularQueue();
 
	int getQueueLength() const;
	bool isEmpty();
	bool isFull();
	void Clear();
	void Push(T data);  //插入新元素，队尾插
	T Pop();    //弹出首元素
	T* Print();
 
private:
	T *m_pCirQueue;  //存放队列数据的数组容器
	int m_iCapacity;   //队列容量
	int m_iLength;     //队列长度
	int m_iHead;       //队列头索引
	int m_iTail;       //队列尾部索引
};
 
template<typename T>
TCircularQueue<T>::TCircularQueue(int capacity)
{
	m_iCapacity = capacity;
	m_iHead = 0;
	m_iTail = 0;
	m_iLength = 0;
	m_pCirQueue = new T[m_iCapacity];
}
 
template<typename T>
TCircularQueue<T>::~TCircularQueue()
{
	delete[] m_pCirQueue;
}
 
template<typename T>
int TCircularQueue<T>::getQueueLength() const
{
	return m_iLength;
}
 
template<typename T>
bool TCircularQueue<T>::isEmpty()
{
	if (m_iLength > 0)
	{
		return false;
	}
 
	return true;
}
 
template<typename T>
bool TCircularQueue<T>::isFull()
{
	if (m_iLength == m_iCapacity)
	{
		return true;
	}
 
	return false;
}
 
template<typename T>
void TCircularQueue<T>::Clear()
{
	m_iLength = 0;
	m_iHead = 0;
	m_iTail = 0;
}
 
template<typename T>
void TCircularQueue<T>::Push(T data)
{
	if (isFull())
	{
		Pop();
	}
 
	m_pCirQueue[m_iTail] = data;
	m_iTail++;  //尾部指向下一个位置
 
	m_iTail = m_iTail % m_iCapacity;
	m_iLength++;
}
 
template<typename T>
T TCircularQueue<T>::Pop()
{
	T pop;
 
	if (isEmpty())
	{
		return pop;
	}
 
	pop = m_pCirQueue[m_iHead];
	m_iHead++;
	m_iHead = m_iHead % m_iCapacity;
	m_iLength--;
	return pop;
}
 
//遍历循环队列
template<typename T>
T* TCircularQueue<T>::Print()
{
	T *p = NULL;
	if (m_iLength > 0)
	{
		p = new T[m_iLength];
 
		for (int i = m_iHead, j = 0; i < m_iHead + m_iLength, j < m_iLength; i++, j++)
		{
			//cout << m_pCirQueue[i % m_iCapacity] << " ";
			p[j] = m_pCirQueue[i % m_iCapacity];
		}
	}
 
	return p;
}
 
 

     在新建一个Student类作为模板数据

     .h

#pragma once
 
#include<iostream>
#include<string>
 
using namespace std;
 
class Student
{
public:
	Student(string name = "", int age = 10);
	
	void Print();
 
private:
	string m_name;
	int    m_iAge;
};
 

    .cpp

#include "Student.h"
 
Student::Student(string name, int age)
{
	m_name = name;
	m_iAge = age;
}
 
void Student::Print()
{
	cout << "name = " << m_name << " age = " << m_iAge << endl;
}

    测试代码：

#include <iostream>
#include "TCircularQueue.h"
#include "Student.h"
 
using namespace std;
 
int main()
{
	TCircularQueue<Student> *pQueue = new TCircularQueue<Student>(4);
 
	Student st1("鲁班", 13);
	Student st2("后裔", 400);
	Student st3("安其拉", 14);
	Student st4("甄姬", 25);
	Student st5("妲己", 19);
	Student st6("亚瑟", 78);
 
	pQueue->Push(st1);
	pQueue->Push(st2);
	pQueue->Push(st3);
	pQueue->Push(st4);
	pQueue->Push(st5);
	pQueue->Push(st6);
	
	int leng = pQueue->getQueueLength();
	cout << "leng = " << leng << endl;
 
	Student *p = new Student[leng];
	cout << "遍历队列" << endl;
	p = pQueue->Print();
	for (int i = 0; i < leng; i++)
	{
		p[i].Print();
	}
 
	delete pQueue;
 
	system("pause");
	return 0;
}
 

      运行结果

      队列在开发中应用的很多，比如线程池，音视频同步等。