首页 > 代码库 > 数据结构基础(7) --循环队列的设计与实现
数据结构基础(7) --循环队列的设计与实现
队列
队列简称队, 也是一种操作受限的线性表, 只允许在表的一端进行插入, 而在表的另一端进行删除.其特点为”先进先出(FIFO)”,故又称为先进先出的线性表,简单队列如图所示:
循环队列
顺序队列有一个先天不足, 那就是空间利用率不高, 会产生”假溢出”现象,即:其实队列中还有空闲的空间以存储元素, 但我们在判断队列是否还有空间时, 队列告诉我们队列已经满了, 因此这种溢出并不是真正的溢出, 在data数组中依然存在可以放置元素的空位置, 所以说这是一种”假溢出”;
于是我们就引入了循环队列的概念, 将顺序队列臆造为一个环状的空间, 即把存储队列元素的表从逻辑上看成一个环, 称为循环队列,其示意图如下:
注意:如图中所示,我们的循环队列为了在实现上的便利, 会有一个位置的空闲, m_front(如图中的front)指针总会指向一个元素值为空的位置,因此(m_front+1)%capacity才真正的指向队首元素, 而m_rear(图中为rear)才指向一个真实存在的队尾元素;
//循环队列的实现与解析 template <typename Type> class MyQueue { template <typename T> friend ostream &operator<<(std::ostream &os, const MyQueue<T> &queue); public: MyQueue(int queueSize = 64); ~MyQueue(); void push(const Type &item); void pop() throw (std::range_error); const Type &front() const throw (std::range_error); const Type &rear() const throw (std::range_error); bool isEmpty() const; private: Type *m_queue; int m_front; //队首指针(其实(m_front+1)%capacity才真正的指向队首元素) int m_rear; //队尾指针 int capacity; //队列的内存大小, 但实际可用的大小为capacity-1 };
template <typename Type> MyQueue<Type>::MyQueue(int queueSize): capacity(queueSize) { if (queueSize < 1) throw std::range_error("queueSize must >= 1"); m_queue = new Type[capacity]; if (m_queue == NULL) throw std::bad_alloc(); m_front = m_rear = 0; }
template <typename Type> MyQueue<Type>::~MyQueue() { delete []m_queue; m_queue = NULL; m_front = m_rear = 0; capacity = -1; }
template <typename Type> inline bool MyQueue<Type>::isEmpty() const { return m_front == m_rear; }
template <typename Type> inline void MyQueue<Type>::push(const Type &item) { if ((m_rear+1)%capacity == m_front) //队列已满 { Type *newQueue = new Type[2 * capacity]; //新队列的长度为原队列的2倍 if (newQueue == NULL) throw std::bad_alloc(); int start = (m_front+1)%capacity; //数据序列的起始地址 if (start <= 1) //队列指针尚未回绕 { //只需拷贝一次:从start所指向的元素直到m_rear所指向的元素 //std::copy(m_queue+start, m_queue+start+capacity-1, newQueue); std::copy(m_queue+start, m_queue+m_rear+1, newQueue); } else { //需要拷贝两次 //1:从start所指向的元素直到数组(不是队列)末尾 std::copy(m_queue+start, m_queue+capacity, newQueue); //2:从数组(不是队列)起始直到队列末尾 std::copy(m_queue, m_queue+m_rear+1, newQueue+capacity-start); } //重新设置指针位置:详细信息请看下面图解 m_front = 2*capacity-1; m_rear = capacity-2; capacity *= 2; delete []m_queue; m_queue = newQueue; } //队尾指针后移 //注意:此处m_front+1可能需要回绕 m_rear = (m_rear+1)%capacity; m_queue[m_rear] = item; }
template <typename Type> inline const Type &MyQueue<Type>::front() const throw (std::range_error) { if (isEmpty()) throw range_error("queue is empty"); //注意:此处m_front+1可能需要回绕 return m_queue[(m_front+1)%capacity]; } template <typename Type> inline const Type &MyQueue<Type>::rear() const throw (std::range_error) { if (isEmpty()) throw range_error("queue is empty"); return m_queue[m_rear]; }
template <typename Type> inline void MyQueue<Type>::pop() throw (std::range_error) { if (isEmpty()) throw range_error("queue is empty"); //注意:此处m_front+1可能需要回绕 m_front = (m_front+1)%capacity; m_queue[m_front].~Type(); //显示调用析构函数以销毁(析构)对象 }
//输出队列所有内容以做测试 template <typename Type> ostream &operator<<(ostream &os, const MyQueue<Type> &queue) { for (int i = (queue.m_front+1)%(queue.capacity); i <= queue.m_rear; /**空**/ ) { os << queue.m_queue[i] << ‘ ‘; if (i == queue.m_rear) break; else i = (i+1)%(queue.capacity); } return os; }
补充说明
当队列已满时的两类扩充操作:
扩充之后的内存布局:
附-测试代码:
int main() { MyQueue<char> cQueue(3); cQueue.push(‘A‘); cQueue.push(‘B‘); //因为cQueue实际能够用的大小为2, 所以此处会对数组进行放大 cQueue.push(‘C‘); cout << cQueue << endl; cout << "front = " << cQueue.front() << ", rear = " << cQueue.rear() << endl; cQueue.pop(); cQueue.pop(); cQueue.push(‘D‘); cQueue.push(‘E‘); cQueue.push(‘F‘); //此时queue的m_rear会进行回绕 cQueue.push(‘G‘); cQueue.pop(); cQueue.push(‘H‘); //此时队列已满, 再添加元素则会进行对队列扩张 //此时m_rear已经回绕, 则会触发两次拷贝操作 cQueue.push(‘I‘); //验证是否能够正常工作 cout << cQueue << endl; cout << "front = " << cQueue.front() << ", rear = " << cQueue.rear() << endl; for (char ch = ‘1‘; ch <= ‘9‘; ++ch) cQueue.push(ch); for (int i = 0; i < 4; ++i) cQueue.pop(); cout << cQueue << endl; cout << "front = " << cQueue.front() << ", rear = " << cQueue.rear() << endl; return 0; }
数据结构基础(7) --循环队列的设计与实现
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。