C++(数据结构与算法):32---队列的实现（数组形式）

一、数组描述的3种形式

形式①

• 假定采用下面的公式把队列的元素映射到一个数组queue中

location(i)=i

• 这个公式用在数组描述的线性表和栈中很有效，有以下的形式：
  • 队列的第i个元素存储在queue[i]中，i>=0
  • 令arrayLength为队列的长度
  • queueFront、queueBack分别为队首和队尾元素的位置
  • queueFront=0，arrayLength=queueBack+1
  • 队列为空时，queueBack=-1

• 复杂度：
  • 插入元素时，先将queueBack增1，然后把新元素插入到queue[queueBack]，因此插入操作所需的时间为Θ(1)
  • 删除一个元素，先把位置1至位置queueBack的元素左移一个位置。因此时间为Θ(n)。（n为删除之后剩余元素的个数）

形式②

• 假定采用下面的公式把队列的元素映射到一个数组queue中

location(i)=localtion(队首元素)+i

• 这种形式的队列：
  • 每删除一个队列元素，就把queueFront向右移动一位即可。因此删除一个队列元素所需的时间为Θ(1)
  • 插入一个元素时，先将queueBack增1，然后新元素插到queue[queueBack]中，因此插入操作所需的时间为Θ(1)
  • queueFront=location(队首元素)，queueBack=location(队尾元素)，队列为空时，queueBack<queueFront

• 备注：如果queueBack指向数组的最后一个位置，而queueFront>0，此时queueFront前面还有空闲的位置，那么此时就需要把队列所有元素整个移动到队列的最短，这样就可以在队列的右端腾出空间。如果出现这种情况，那么插入操作的复杂度将从Θ(1)增加到Θ(arrayLength)。这样看到，删除操作的效率提高了，但是插入操作的效率降低了

形式③

• 如果把队列的两端连接，那么在数组长度不变的情况下，插入和删除操作的最坏时间复杂度均变成Θ(1)。这是，把数组视为一个环而不是一条直线
• 把数组视为一个环，每一个位置都有其下一个位置和前一个位置：
  • arrayLength-1的下一个位置为0
  • 而0的前一个位置是arrayLength-1
  • 当队列尾元素的位置是arrayLength-1时，下一个元素的插入位置便是0
  • 用环形数组来表示队列的方法通过下面的公式来实现

location(i)=(location(队首元素)+i)%arrayLength

• 注意事项：当且仅当queueFront=queueBack时，队列为空。初始条件queueFront=queueBack=0定义了一个初始为空的队列。如果向队列插入元素，直到数组queue的元素个数等于数组长度（即队列满）为止，那么结果如下图所示，此时queueFront=queueBack，那么队列为空和为满的条件一样了。为了避免这种情况出现，队列不能插满，在向队列插入一个元素之前，先要判断本次操作是否会使队列变满，如果会那么就把数组长度加倍，然后再执行插入操作

二、编码实现

• 下面使用环形的数组来实现队列，queueFront索引处不存放元素，queueFront+1索引处存放队列的第一个元素

头文件定义

#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <numeric>

using std::cout;
using std::cin;
using std::endl;
using std::string;
using std::copy;

异常类定义

class illegalParameterValue
{
	std::string message;
public:
	illegalParameterValue(const char *theMessage = "Illegal Parameter Value") :message(theMessage) {}
	const char *what() {
		return message.c_str();
	}
};

class queueEmpty
{
public:
	queueEmpty(std::string theMessage = "Invalid operation on empty queue") :message(theMessage) {}
	const char *what() {
		return message.c_str();
	}
private:
	std::string message;
};

队列的抽象类定义

template<class T>
class queue
{
public:
	virtual ~queue() = default;
	virtual bool empty()const = 0; //判断队列是否为空
	virtual int size()const = 0; //返回队列中元素个数
	virtual T& front() = 0; //返回头元素的引用
	virtual T& back() = 0; //返回尾元素的引用
	virtual void pop() = 0; //删除首元素
	virtual void push(const T& theElement) = 0; //把元素theElement加入队尾
};

arrayQueue类的定义

• 构造函数的复杂度：T是一个基本数据类型时为O(1)，T为用户定义的类型时为O(initialCapacity)
• empty、size、front、back、pop的复杂度均为Θ(1)
• 插入函数的复杂度：队列容量不加倍时为Θ(1)，加倍时为Θ(queueSize)

template<class T>
class arrayQueue :public queue<T>
{
public:
	arrayQueue(int initialCapacity=10);
	~arrayQueue();
	bool empty()const override;
	int size()const override; 
	T& front() override;
	T& back() override;
	void pop() override;
	void push(const T& theElement) override;

	void showQueue(std::ostream &s)const;
private:
	int queueFront;
	int queueBack;
	int arrayLength;
	T *element;
};

template<class T>
arrayQueue<T>::arrayQueue(int initialCapacity = 10)
{
	if (initialCapacity <= 0) {
		std::ostringstream s;
		s << "The initialCapacity is " << initialCapacity << ",must bt >0";
		throw illegalParameterValue(s.str().c_str());
	}

	this->element = new T[initialCapacity];
	this->arrayLength = initialCapacity;
	this->queueFront = 0;
	this->queueBack = 0;
}

template<class T>
arrayQueue<T>::~arrayQueue() 
{
	if (element){
		delete[] element;
		element = nullptr;
	}
}

template<class T>
bool arrayQueue<T>::empty()const
{
	return (this->queueBack == this->queueFront);
}

template<class T>
int arrayQueue<T>::size()const
{
	return ((this->queueBack - this->queueFront + this->arrayLength) % this->arrayLength);
}

template<class T>
T& arrayQueue<T>::front()
{
	if (empty())
		throw queueEmpty();
	return this->element[(this->queueFront + 1) % this->arrayLength];
}

template<class T>
T& arrayQueue<T>::back()
{
	if (empty())
		throw queueEmpty();
	return this->element[this->queueBack];
}

template<class T>
void arrayQueue<T>::pop()
{
	if (empty())
		throw queueEmpty();
	this->queueFront = (this->queueFront + 1) % this->arrayLength;
	this->element[this->queueFront].~T();
}

template<class T>
void arrayQueue<T>::push(const T& theElement)
{
	if (((this->queueBack + 1) % this->arrayLength) == this->queueFront) {
		T* newQueue = new T[2 * this->arrayLength];

		int start = (this->queueFront + 1) % this->arrayLength;
		if (start < 2)
			copy(this->element + start, this->element + start + this->arrayLength - 1, newQueue);
		else
		{  
			copy(this->element + start, this->element + this->arrayLength, newQueue);
			copy(this->element, this->element + this->queueBack + 1, newQueue + this->arrayLength - start);
		}

		
		this->queueFront = 2 * this->arrayLength - 1;
		this->queueBack = this->arrayLength - 2;
		this->arrayLength *= 2;
		this->element = newQueue;
	}
	this->queueBack = (this->queueBack + 1) % this->arrayLength;
	this->element[this->queueBack] = theElement;
}

template<class T>
void arrayQueue<T>::showQueue(std::ostream &s)const
{
	if (empty())
		throw queueEmpty();

	int index = (this->queueFront + 1) % this->arrayLength;
	for (; index != this->queueBack; index = ((index+1) % this->arrayLength)) {
		s << this->element[index]<<" ";
	}
}

队列满时如何扩充数组

• 当环形队列的数组空间满时，需要扩充数组的大小，如下图所示，左图为环形表示形式，右图为环形拉直之后的形式

• 当数组加倍之后，就如下图所示

• 为了得到合理的环形队列元素布局，必须把第2端的元素（即A和B移到数组的右侧）移到数组的右端，如下图所示

• 数组加长的过程要复制arrayLength个元素，这是加长之前的队列容量，当第2段的元素移到右端之后，总共有arrayLength-2个额外元素要复制。用已有的代码，要复制的元素个数被限制在arrayLength-1个。下图给出了数组加长之后，队列元素的另外一种布局。这个布局可以按照下面的步骤得到（我们的push代码也是这么得到的）：
  • 创建一个新的数组newQueue，其容量加倍
  • 把第2段的元素（从element[queueFron+1]到element[arrayLength-1]）复制到newQueue从0开始的位置
  • 第1段的元素（从element[0]到element[queueBack+1]）复制到newQueue从arrayLength-queueFront-1开始的位置

主函数

int main()
{
	arrayQueue<int>* myQueue = new arrayQueue<int>(4);

	myQueue->push(1);
	myQueue->push(2);
	myQueue->push(3);
	myQueue->push(4);
	std::cout << "Capacity is " << myQueue->size() << std::endl;
	myQueue->showQueue(std::cout);
	std::cout<<std::endl;

	myQueue->pop();
	std::cout << "Capacity is " << myQueue->size() << std::endl;
	myQueue->showQueue(std::cout);
	std::cout << std::endl;

	myQueue->push(5);
	myQueue->push(6);
	std::cout << "Capacity is " << myQueue->size() << std::endl;
	myQueue->showQueue(std::cout);
	std::cout << std::endl;

	return 0;
}

 

三、代码下载

• https://download.csdn.net/download/qq_41453285/12019393