欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-07-14 14:19:32
...

一、数组描述的3种形式

形式①

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

location(i)=i

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

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

  • 复杂度:
    • 插入元素时,先将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

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

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

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

形式③

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

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

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

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

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

二、编码实现

  • 下面使用环形的数组来实现队列,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]<<" ";
	}
}

队列满时如何扩充数组

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

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

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

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

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

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

  • 数组加长的过程要复制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开始的位置

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

主函数

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;
}

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

三、代码下载