C++数据结构环形队列Deque实现

来源:互联网 时间:1970-01-01

队列是一种常见的数据结构,生活中的排队买票,排队等车,都是队列。队列的特点是先进先出FIFO。队列可以基于数组实现,也可以基于链表实现。

这里是基于链表实现的。每次出队操作,头指针后移,每次入队,尾指针也后移。因为数组是固定长度连续空间,首位指针后移,队尾可插入区域会越来越小。当然,可以每次出队,整个队列前移,但是数组移动需要牺牲性能。环形队列可以解决数组移动的缺点,当尾指针超出数组末尾时,尾指针移动数组头部。这就将数组虚拟成了一个环形,只要

队列长度没达到最大值,就可以插入,而不用移动数组。

下面是头文件

#pragma onceclass RingQueue{public: RingQueue(int maxSize); ~RingQueue(); void clearQueue(); int length() const; void traverse(); bool enQueue(int item); bool deQueue(int& item); bool isEmpty() const; bool isFull() const;private: int *m_pQueue; //数组指针 int m_length; //长度 int m_capacity; //最大长度 int m_iHead; //队头 int m_iTail; //队尾 int move(int& head_or_tail);};

头文件里定义了队列的基本操作。注意 int move(int& head_or_tail) 函数的作用是安全的移动 head 和tail 指向的位置。超出界线重新判断。

下面是代码实现

#include <iostream>#include "RingQueue.h"using namespace std;RingQueue::RingQueue(int maxSize){ m_capacity = maxSize; m_iHead = 0; m_iTail = 0; m_length = 0; m_pQueue = new int[maxSize];}RingQueue::~RingQueue(){ delete[] m_pQueue;}void RingQueue::clearQueue(){ m_iHead = 0; m_iTail = 0; m_length = 0;}int RingQueue::length() const{ return m_length;}void RingQueue::traverse(){ if (isEmpty()) return; int f = m_iHead, t = m_iTail; do { cout<<m_pQueue[f]<<" "; } while (move(f)!=t); cout << endl;}bool RingQueue::enQueue(int item){ if (isFull()) return false; m_pQueue[m_iTail] = item; move(m_iTail); m_length++;}bool RingQueue::deQueue(int& item){ if (isEmpty()) return false; item = m_pQueue[m_iHead]; move(m_iHead); m_length--;}bool RingQueue::isEmpty() const{ return m_length==0;}bool RingQueue::isFull() const{ return m_length == m_capacity;}int RingQueue::move(int& head_or_tail){ ++head_or_tail; head_or_tail%=m_capacity; return head_or_tail;}





相关阅读:
Top