数据结构之环形队列实现 (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;
}