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