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 

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 Push(6);
	pQueue->Push(8);
	pQueue->Push(9);
	
	cout Pop();
	cout  0)
	{
		return false;
	}

	return true;
}

template
bool TCircularQueue::isFull()
{
	if (m_iLength == m_iCapacity)
	{
		return true;
	}

	return false;
}

template
void TCircularQueue::Clear()
{
	m_iLength = 0;
	m_iHead = 0;
	m_iTail = 0;
}

template
void TCircularQueue::Push(T data)
{
	if (isFull())
	{
		Pop();
	}

	m_pCirQueue[m_iTail] = data;
	m_iTail++;  //尾部指向下一个位置

	m_iTail = m_iTail % m_iCapacity;
	m_iLength++;
}

template
T TCircularQueue::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
T* TCircularQueue::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 getQueueLength();
	cout