数据结构（五）队列
队列（Queue）是一种限定在表的一端（队尾）进行插入，另一端（队首）进行删除的线性表，具有先进先出（First in first out，FIFO）的特点。
图1 队列示意图
1.队列的表示
#define m 100 /* 队列m的最大容量 */
struct Queue
{
QueueType Elem[m];
int front; /* 队首 */
int rear; /* 队尾 */
};循环队列元素下标移动：
front = (front + 1) % m;
rear = (rear + 1) % m;队空的条件：front = rear
队满的条件：front = (rear + 1) % m
2.队列的操作
（1）入队
void EnterQueue(struct Queue Queue_m,QueueType x)
{
if((Queue_m.rear + 1) % m == Queue_m.front)
{
error("队满");
}
else
{
Queue_m.Elem[Queue_m.rear] = x; /* 入列 */
Queue_m.rear = (Queue_m.rear + 1) % m;
}
}算法时间复杂度：T(n) = O(1)
（2）出队
void DelQueue(struct Queue Queue_m,QueueType x)
{
if(Queue_m.rear == Queue_m.front)
{
error("队空");
}
else
{
x = Queue_m.Elem[front];
Queue_m.front = (Queue_m.front + 1) % m;
}
}算法时间复杂度：T(n) = O(1)
3.链式队列的表示（以下示例均使用伪代码表示）
图2 链式队列示意
（1）入队
typedef struct node
{
QueueType Data;
struct node *next; /* 队首 */
}*Node;
p = (Node)malloc(sizeof(Node)); /* 生成新结点p */
p -> Data = x;
p -> next = f;
r -> next = p;
r = p;（2）出队
p = f -> next;
x = p -> Data;
f -> next = p -> next;
free(p);
if(f -> next == r)
{
r = f;
}删除最后一个结点后，队尾指针r指向头结点。
本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2020-03-30，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
