1. 队列定义
//顺序存储队列
typedef struct
{
elemType data[maxSize];
int front, rear;
}queue;
//链表存储队列
typedef struct Node
{
elemType data;
Node *next;
};
typedef struct queue
{
Node *front;
Node *rear;
};
通过队列的定义可以看出，队列除了按先后顺序都数据进行存储外，还需要两个指针，分别代表队头和队尾。
2. 进队出队操作
出队操作将队头指针往后移动一位，进队操作则将队尾指针向后移动一位
顺序存储队列
进队
bool enterQueue(queue &q, elemType data)
{
if(q.rear == maxSize)
return false;
//队尾往后移一位，添加数据
q.rear++;
q.data[q.rear] = data;
return true;
}
出队
elemType outQueue(queue &q)
{
//判断队列是否为空
if(q.front == q.rear)
return -9999;
//返回队头元素，队头指针往后移动一位
return q.data[q.front++];
}
链表存储队列
进队
bool enterQueue(queue &q,elemType e)
{
Node *p;
p = (Node *)malloc(sizeof(Node));
p->data = e;
p->next = NULL;
//队列最后一个元素指针域指向新添加的元素
q.rear->next = p;
//队尾指针指向新的队尾
q.rear = p;
return true;
}
出队
elemType outQueue(queue &q)
{
//判断队伍是否为空
if(q.front == q.rear)
return -999;
elemType e;
e = q.front->next->data;
//使队头指针指向新的队头
Node *p = q.front->next;
q.front->next = p->next;
//释放已经出队的结点的空间
free(p);
return e;
}
3. 特殊队列——循环队列与双端队列
此处仅讨论循环队列。循环队列是基于顺序表，与普通队列不同的是
- 指针移动到数组最后的时候需要进行处理使之指向数组最前
- 如何计算队伍长度
- 如何判断队列空队，满队
问题1
//当指针指向最后一个位置时，再进一位时候，就会指向0
front = (front + 1) % maxSize;
问题2
//普通队列
length = q.rear - q.front;
//循环队列
length = (q.rear - q.front + maxSize) % maxSize;
与普通队列区别在于，循环队列存在 q.rear < q.front 的情况。
- 当 q.rear < q.front 时，q.rear - q.front就等于队列中为空的位置个数的相反数，(q.rear - q.front + maxSize)就等于队伍长度，再%maxSize还是等于长度本身
- 当 q.rear > q.front 时，(q.rear - q.front + maxSize) % maxSize等于q.rear - q.front 即队伍长度
问题3
一般情况下循环队列空的时候q.rear = q.front，队满的时候q.rear = q.front。所以无法区分队空，队满。
- 添加tag，队空为0，队满为1.
- 添加size属性，每次 出队/进队 后，修改队列长度
- rear指向最后一个元素的后一个位置，队列中空出一个空位。
(1) 队空的条件仍为：q.front == q.rear
(2) 队满的条件为：(q.rear + 1) % maxSize == q.front
此时队满只存在两种情况：
(1) rear == maxSize && front == 0
(2) rear > front
都能通过(rear + 1) % maxSize 求得front。
