| C++实现循环队列（数组模拟）【保姆级讲解】 | 您所在的位置：网站首页 › 队列用数组实现 › C++实现循环队列（数组模拟）【保姆级讲解】 |
C++实现循环队列（数组模拟）【保姆级讲解】
|
文章目录
一、循环队列的实现（数组模拟）1、队列的特点2、数组模拟队列3、编写队列结构4、入队操作5、出队操作6、判空和判满7、构造和析构8、完整代码
一、循环队列的实现（数组模拟）
1、队列的特点
队列是一种先进先出的线性表 
例如：上图是一个数组，我们怎样才能让数组的行为和队列一致呢？ 例如上面数组中的1和2，如何让他们写入呢？ 直接利用数组和索引 array[0] = 1; array[1] = 2;这样看起来可以，但是有一个问题，我们需要时刻记得我们入队了几次，否则就无法根据索引入队了。 那么其实我们可以把这个索引用一个变量表示，每次入队只需递增它就可以了。 array[tail] = 1; ++tail; array[tail] = 2; ++tail;出队的话，可以利用和入队类似的办法，但数组无法删除元素，但我们可以用一个数组索引的变量表示队头的位置，每次出队只需把这个索引向递增即可。 例如让上面的1和2出队 ++head; ++head;解决了入队出队问题，我们就来试一下。 队空队满出队到队空  
看起来还不错，但仔细观察出队到队空时，队列里面没有数了，也就是队空了，可以继续加数据，但是，表示队列头尾的变量已经到了数组的最右边的下一个索引，已经没办法再往右了，同时数组还是空的。 怎么办呢，如果队尾指针变量在到数组最后一个之后自动移动到数组第一个位置就可以解决了，如何才能做到呢？ 可以利用模运算！ // 将递加操作用用模运算替代 tail = (tail+1) % 6; // 6是数组的大小 // 对于对头也是一样 head = (head+1) % 6;当tail没有到达数组末尾的时候，tail+1都小于6，因此，模6所得值还是本身，如果tail到达数组末尾，tail+1 = 6模值将会变成0，完美地将tail移动到了数组开头！ 再来试一下 队空入队到队满队满  
发现，当tail到数组末尾之后自动移动到开头了！ 但问题就来了，要怎么判断队列满了呢？很显可以通过head = tail，可是，队空的时候它们也是相等的，这怎么办？可以改变队空或者队满的条件来解决冲突。这里可以将数组的一个格子空出来，当数组还有一个格子的时候，就当作队列已经满了。 第一种情况第二种情况 
第一种情况，很明显，可以用head == tail + 1 判断队满；但第二种情况好像不行，回想之前的模运算，很快可以得到head == (tail+1) % 6，而且这个式子也适用于第一种情况！ 3、编写队列结构很明显，这个队列包含一个数组，还需要队头、队尾两个索引变量和队列大小这四个数据，同时包含入队、出队、判空、判满这四个成员函数。 // 队列结构 class Queue { private: int* data; std::size_t head; std::size_t tail; std::size_t size; public: inline Queue(std::size_t sz); inline ~Queue(); void push(); int pop(); // 为了方便测试，出队时返回出队的数据 inline bool isEmpty(); inline bool isFull(); } 4、入队操作入队时，先将队尾所指位置放入需要入队的值，再将队尾后移。 代码逻辑： 判断是否队满没满则执行入队操作满了就输出错误信息 void Queue::push(int val) { if (!isFull()) { data[tail] = val; tail = (tail+1) % (size+1); } else { std::cerr auto temp = data[head]; head = (head+1) % (size+1); return temp; } else { std::cout return head == (tail+1) % (size+1); } 7、构造和析构 // 由于使用时才传入队列大小，因此需要动态数组，sz+1是为了空一格 inline Queue::Queue(std::size_t sz) : data(new int[sz+1]), head(0), tail(0), size(sz) { } inline ~Queue::Queue() { delete data[]; } 8、完整代码 // Queue.h 队列类头文件 #include // 队列结构 class Queue { private: int* data; std::size_t head; std::size_t tail; std::size_t size; public: inline Queue(std::size_t sz); inline ~Queue(); void push(int val); int pop(); // 为了方便测试，出队时返回出队的数据 inline bool isEmpty(); inline bool isFull(); }; /*inline成员函数都定义到类的头文件中*/ // 由于使用时才传入队列大小，因此需要动态数组，sz+1是为了空一格 inline Queue::Queue(std::size_t sz) : data(new int[sz + 1]), head(0), tail(0), size(sz) { } inline Queue::~Queue() { delete[] data; } inline bool Queue::isEmpty() { return head == tail; } inline bool Queue::isFull() { return head == (tail + 1) % (size + 1); } // Queue.cpp 队列类函数的实现 #include #include "Queue.h" #include void Queue::push(int val) { if (!isFull()) { data[tail] = val; tail = (tail + 1) % (size + 1); } else { std::cerr auto temp = data[head]; head = (head + 1) % (size + 1); return temp; } else { std::cout |
上面的队列中，1最先进入队列，7最后进入，因此1最先出队而7最后出队
【本文地址】