循环队列/顺序队列（C++）

队列（queue）是一种限定存取位置的线性变。他允许在表的一端插入，在另一端删除。这个和计算机调度策略中的先来先服务FCFS(First Come/First Served)是一样的。队列中可以插入的一端为队尾（rear），允许删除的一端称为队头（front）。

队列也分为两种，一种是用数组的存储表示，一种是基于链表的存储表示。

基于数组的存储表示的队列被称为顺序队列。其数据成员包括，一维数组elements用来存储数据，指针front和rear用来指示队尾队头的位置，maxSize是数组的最大长度。

从上边的图可以看出来，rear指针到指到数组最后一位时就不能继续往后添加元素，如果之前删除过元素，front指针前还有空闲的空间未被使用，造成空间的浪费。所以，使队列循环起来就可以使其最大限度的利用空间。

变成循环队列，为了避免越界，每次添加新元素时，尾指针需要加一后对堆长取余

即 rear = (rear+1)%maxSize;

删除元素也一样

front = (front+1)%maxSize;

为了区别于空队列，用(rear+1)%maxSize==front来判断是否队满，即队尾走到队头前一个位置即判定队满。再因为队尾所指的空间为最后一个元素的下一个位置，所以循环队列最多能存放maxSize-1个元素。

//queue.h

#ifndef _QUEUE_H

#define _QUEUE_H

#include<iostream>

using namespace std;

const int maxSize = 50;

template<class T>

class Queue

{

public:

	Queue(){};

	~Queue(){};

	virtual bool EnQueue(const T& x) = 0;

	virtual bool DeQueue(T& x) = 0;

	virtual bool getFront(T& x) = 0;

	virtual bool IsEmpty()const = 0;

	virtual bool IsFull()const = 0;

	virtual int getSize()const = 0;

};

#endif

//main.cpp
#include<assert.h>

#include"queue.h"

template<class T>

class SeqQueue;

template<class T>

ostream& operator<< (ostream& out, SeqQueue<T>& Q)//将友元函数声明在前可以避免其警告友元函数未声明

{

	cout<<"front = "<<Q.front<<", rear = "<<Q.rear<<endl;

	if(!Q.IsEmpty())

	{

		int i = Q.front;

		while(i!=Q.rear)

		{

			cout<<Q.elements[i]<<" | ";

			i = (++i)%maxSize;

		}

	}

	return out;

}

template<class T>

class SeqQueue: public Queue<T>

{

private:

	int rear, front;

	T *elements;

	int maxSize;

public:

	SeqQueue(int sz=10);//构造函数

	~SeqQueue(){delete[] elements;}//析构函数

	bool EnQueue(const T& x);//入队列

	bool DeQueue(T& x);//出队列

	bool getFront(T& x);//找队头

	bool IsEmpty()const{return (this->rear==this->front) ? true : false;}//判空

	bool IsFull()const{return ((this->rear+1)%this->maxSize==this->front) ? true : false;}//判满

	int getSize()const{return(this->rear-this->front+this->maxSize)%this->maxSize;}//得队长

	friend ostream& operator<<<>(ostream& out, SeqQueue<T>& Q);

//void print();

};

/*template<class T>

void SeqQueue<T>::print()

{

	if(!this->IsEmpty())

	{

		int i = this->front;

		while(i!=this->rear)

		{

			cout<<this->elements[i]<<" | ";

			i = (++i)/this->maxSize;

		}

	}

}*/

template<class T>

bool SeqQueue<T>::EnQueue(const T& x)

{

	if(!this->IsFull())

	{

		this->elements[this->rear] = x;

		this->rear = (this->rear+1)%this->maxSize;

		return true;

	}

	return false;

}

template<class T>

bool SeqQueue<T>::DeQueue(T& x)

{

	if(!this->IsEmpty())

	{

		x = this->elements[this->front];

		this->front = (this->front+1)%this->maxSize;

		return true;

	}

	return false;

}

template<class T>

bool SeqQueue<T>::getFront(T& x)

{

	if(!this->IsEmpty())

	{

		x = this->elements[this->front];

		return true;

	}

	return false;

}

template<class T>

SeqQueue<T>::SeqQueue(int sz):front(0),rear(0),maxSize(sz)

{

	this->elements = new T[maxSize];

	assert(this->elements!=NULL);

}

int main()

{

	SeqQueue<int> Q(7);

	for(int i=7; i>0; --i)

		Q.EnQueue(i);

	cout<<Q<<endl;//声明友元函数并重载输出运算符<<就可以用cout直接输出对象

	int q = 0;

	for(int i=3; i>=0; --i)

		Q.DeQueue(q);

	cout<<Q<<endl;

        cout<<"Size = "<<Q.getSize()<<endl;

	return 0;

}

运行结果

巴特西

循环队列/顺序队列（C++）

最新文章

热门文章