循环队列C++实现

circularQueue.h

#pragma once
#pragma once
#ifndef CIRCULARQUEUE_H
#define CIRCULARQUEUE_H

#include<iostream>
#include<ostream>
using std::cout;
using std::cin;
using std::endl;
using std::ostream;
template<class T>  class cirQueue;

template<typename T>
class cirQueue
{
public:
	cirQueue(int sz);
	~cirQueue();
	void push(const T& elem);//进队
	void pop(T& elem);//出队
	bool empty();//查看队列是否为空
	int getSize();//返回队列中元素的个数
	void clearQueue();//清空队列中的元素
	void print();//打印队列中的元素
	int getfront() { return front; }
	int getrear() { return rear; }
	bool getTop(T& elem);//读取队列首个元素

	template<typename T>
	friend ostream& operator<<(ostream& os, cirQueue<T>& queue);

private:
	bool _full()const;//判断队列是否已满
	int maxsize;//队列最大的空间
	T* element;//存放于队列中的元素数组
	int front;//模拟队头指针
	int rear;//模拟队尾指针
};


template<typename T>
cirQueue<T>::cirQueue(int sz) {
	maxsize = sz;
	element = new T[maxsize];
	if (element == nullptr)
		cout << "内存分配失败" << endl;
	front = 0;
	rear = 0;
}


template<typename T>
cirQueue<T>::~cirQueue() {
	if (element != nullptr)
		delete element;
}

//进队
template<typename T>
void cirQueue<T>::push(const T& elem) {//需要保证队尾指针位置与首个元素相差一个位置
	if (rear > (maxsize - 1))
		rear -= maxsize ;
	if (front > (maxsize - 1))
		front -= maxsize ;
	if (!_full()) {//队列未满的情况		
		element[rear++] = elem;//队尾向后移动一位
		//++rear;
	}
	else {
		cout << "队列已满，不能插入！" << endl;
		return;
	}
}

//出队
template<typename T>
void cirQueue<T>::pop(T& elem) {
	if (rear > (maxsize - 1))
		rear -= (maxsize - 1);
	if (front > (maxsize - 1))
		front -= (maxsize - 1);
	if (!empty()) {//队列未空的情况
		elem = element[front++];//队头向后移动一位
		element[front - 1] = 0;//置零
	}
	else {
		cout << "队列已空！" << endl;
		return;
	}
}

//查看队列是否为空
template<typename T>
bool cirQueue<T>::empty() {
	if (front == rear)//待定
		return true;
	return false;
}

//返回队列中元素的个数
template<typename T>
int cirQueue<T>::getSize() {
	int num = 0;
	if (front <= rear)
		return rear - front;
	else
		return maxsize - front + rear + 1;
}

//清空队列中的元素
template<typename T>
void cirQueue<T>::clearQueue() {
	if (!empty())
	{
		int Index = 0;
		while (front < rear) {//front逼近rear
			element[front++] = 0;
			if (front == rear)
				return;
		}
		if (rear < front) {
			while (front <= maxsize - 1)//删除front至数组尾端的数据
				element[front++] = 0;
			front -= maxsize;
			while (front < rear) {//删除front至rear的数据
				element[front++] = 0;
				if (front == rear)
					return;
			}
		}
	}
}

//打印队列中的元素
template<typename T>
void cirQueue<T>::print() {//与clearQueue函数原理一致，将front替换为Index
	if (!empty())
	{
		int Index = front;
		while (Index < rear) {
			cout << element[Index++] << " ";
			if (Index == rear) {
				cout << endl;
				return;
			}
		}
		if (rear < Index) {
			while (Index <= maxsize - 1)
				cout << element[Index++] << " ";
			Index -= maxsize;
			while (Index < rear) {
				cout << element[Index++] << " ";
				if (Index == rear) {
					cout << endl;
					return;
				}
			}
		}
	}
}

//读取队列首个元素
template<typename T>
bool cirQueue<T>::getTop(T& elem) {
	if (!empty()) {
		elem = element[front];
		return true;
	}
	return false;
}

template<typename T>
ostream& operator<<(ostream& os, cirQueue<T>& queue) {
	os << "队列中的元素数量为：" << queue.getSize() << endl;
	return os;
}

//判断队列是否已满
template<typename T>
bool cirQueue<T>::_full()const {
	if (front - rear == 1 || front - rear == -maxsize + 1)
		return true;
	return false;
}

#endif // !CIRCULARQUEUE_H

main.cpp

#include"CircularQueue.h"


int main()
{
	cirQueue<int> cq(20);
	int a = 0;
	for (int i = 0; i < 19; i++)
	{
		cq.push(i);
	}
	cq.print();
	cout << cq;
	for (int i = 0; i < 20; i++)
	{
		cq.pop(a);
	}
	cout << cq;//此时front=rear=19
	cout << cq.getfront() << "   " << cq.getrear() << endl;
	//for (int i = 19; i < 25; i++)
	//{
	//	cq.push(i);
	//}
	cq.push(19);
	cq.print();
	cout << cq.getfront() << "   " << cq.getrear() << endl;
	cout << endl << endl;
	cq.push(20);	
	cq.getTop(a);
	cout << a << endl;
	cq.print();
	cout << cq.getfront() << "   " << cq.getrear() << endl;
	return 1;
}