数据结构之环形队列实现 (C++数组)

数据结构之环形队列实现 (C++/数组)

1.概念示意图

   内存中不存在环形数据结构，均由基础结构实现逻辑上的闭环效果

2.环形队列与普通队列的区别

1.front头部指针 一般队列：front头部指针初始值为-1，从队列取数据时，该值依次递增，指向的元素即待取出的数据，而队列的头部数据所在的指针位置为front+1。当front=maxSize-1时，队列最后一个数据取出，此时队列为空。 环形队列：front头部指针初始值为0，指向的元素既是队列的头部数据也是待取出的数据。从队列取数据时，因逻辑上的闭环，指针可能再次回到前面的位置，不能单一递增处理，需通过取模来重新计算指针的值。 2.rear尾部指针 一般队列：rear尾部指针初始值为-1，队列添加数据时，该值依次递增，当rear=maxSize-1时，队列满，无法再添加数据。 环形队列：rear尾部指针初始值为0，指向待添加数据的位置，队列添加数据时，因逻辑上的闭环，指针可能再次回到前面的位置，不能单一递增处理，会出现角标越界异常，需通过取模来重新计算指针的值。 3.队列空的判断逻辑 一般队列：rear == front时，队列空。 环形队列：rear == front时，队列空。 4.队列满的判断逻辑 一般队列：rear = maxSize - 1时，队列满。 环形队列：(rear + 1) % maxSize == front时，队列满。

3.代码实现

  

#include <iostream> #include <cstdlib> #include <memory.h> class Ciclequeue { public: //队列最大容量 int m_maxSize; //队列头指针 int m_frontIdx; //队列尾指针 int m_rearIdx; //队列数组 int *m_queueArr; public: //构造函数 Ciclequeue(int tmpSize) { m_maxSize = tmpSize; m_frontIdx = 0; m_rearIdx = 0; m_queueArr = new int[m_maxSize]; memset(m_queueArr, 0 , sizeof(int)*m_maxSize); } //析构函数 ~Ciclequeue() { delete m_queueArr; m_queueArr = NULL; } //入队 void enqueue(int datavalue) { if(isfull()) { std::cout<<"Queue is full!"<<std::endl; return; } m_queueArr[m_rearIdx] = datavalue; m_rearIdx = (m_rearIdx + 1)%m_maxSize; } //出队 void dequeue() { if(isempty()) { std::cout<<"Queue is empty!"<<std::endl; return; } m_queueArr[m_frontIdx] = -1; //模拟出队列动作 m_frontIdx = (m_frontIdx + 1)%m_maxSize; } //检查队列是否已满 bool isfull() { if(m_maxSize == -1) { std::cout<<"Create queue error!"<<std::endl; return false; } return (m_rearIdx + 1)%m_maxSize == m_frontIdx; } //检查队列是否为空 bool isempty() { if(m_maxSize == -1) { std::cout<<"Create queue error!"<<std::endl; return false; } return m_rearIdx == m_frontIdx; } //当前队列元素各个数 int size() { return (m_rearIdx - m_frontIdx + m_maxSize) % m_maxSize; } //显示队列 void showqueue() { if(isempty()) { return; } for(int i = m_frontIdx; i < m_frontIdx + size(); i++ ) { std::cout<<m_queueArr[i]<<" "<<std::endl; } } //显示队列头 void showqueuefront() { std::cout<<m_queueArr[m_frontIdx]<<std::endl; } }; int main(int argc, char **argv) { int tmpSize = std::atoi(argv[1]); if(tmpSize <= 0) { std::cout<<"Set MaxSize Error!"<<std::endl; return 0; } Ciclequeue *testqueue = new Ciclequeue(tmpSize); testqueue->enqueue(3); testqueue->enqueue(2); testqueue->dequeue(); testqueue->enqueue(4); testqueue->dequeue(); testqueue->enqueue(5); testqueue->enqueue(66); testqueue->enqueue(88); testqueue->enqueue(1204); testqueue->showqueue(); delete testqueue; testqueue = NULL; return 0; }