队头指针为front,指向队头元素,队尾指针为rear,指向队尾元素的后一位;
为了避免浪费空间,队列通常定义为循环队列的形式;
int queue[n], front = 0, rear = 0;
向队尾推入一个数x:
queue[rear] = x;
rear = (rear+1) % n;
从队头弹出一个数:
front = (front+1) % n;
获取队头的数:
queue[front];
注解:
(1)出队、取队头需判断队不空;
rear != front // 队不空的条件
入队需判断队不满;
(rear+1) % n != front // 队不满的条件
(2)长度为n的数组最多只能容纳长度为n-1的队列,原因如下:
假设队列有m个元素,那么队列共有m+1中状态(多出的一种状态为队列空),如果固定front指针,rear必须要有m+1个位置才能表示这m+1状态,所以数组长度要比队列长度多一。
因此,rear不是指向队尾元素,而是指向队尾元素的下一位,这样队头=队尾表示队列空,队尾=队头+1表示队列只有一个元素,对头=队尾+1表示队列满。
(3)假设队列指针为t,在循环队列中:
t+1 要改成 (t+1) % n
t-1 要改成 (t-1 + n) % n
(4)实际题目中一般会说明数据个数,可以将队列容量n设置成不少于数据个数,这样能避免循环队列的取模操作。