队列
队列简称队, 也是一种操作受限的线性表, 只允许在表的一端进行插入, 而在表的另一端进行删除.其特点为”先进先出(FIFO)”,故又称为先进先出的线性表,简单队列如图所示:
循环队列
顺序队列有一个先天不足, 那就是空间利用率不高, 会产生”假溢出”现象,即:其实队列中还有空闲的空间以存储元素, 但我们在判断队列是否还有空间时, 队列告诉我们队列已经满了, 因此这种溢出并不是真正的溢出, 在data数组中依然存在可以放置元素的空位置, 所以说这是一种”假溢出”;
于是我们就引入了循环队列的概念, 将顺序队列臆造为一个环状的空间, 即把存储队列元素的表从逻辑上看成一个环, 称为循环队列,其示意图如下:
注意:如图中所示,我们的循环队列为了在实现上的便利, 会有一个位置的空闲, m_front(如图中的front)指针总会指向一个元素值为空的位置,因此(m_front+1)%capacity才真正的指向队首元素, 而m_rear(图中为rear)才指向一个真实存在的队尾元素;
补充说明
当队列已满时的两类扩充操作:
扩充之后的内存布局:
附-测试代码: