当前位置：首页 > news >正文

【数据结构】线性表----队列详解

news 来源：原创 2024/9/20 3:33:21

1. 队列的基本概念

话不多说，直接开始！

队列是一种线性数据结构，同栈类似但又不同，遵循先进先出（FIFO, First In First Out）的原则。换句话说，最先进入队列的元素会最先被移除。这样的特点使得队列非常适合用于需要按顺序处理任务的场景。
在这里插入图片描述

特点：

先进先出：第一个进入队列的元素最先被处理。
操作受限：元素只能从队尾插入，从队头移除。

2. 队列的实现

在这里插入图片描述

队列可以通过多种方式实现，常见的有数组和链表两种。

使用数组实现队列：
使用数组实现队列需要维护两个指针，分别指向队头和队尾，并且需要处理数组的溢出问题。所以数组不是很适合用来实现队列。

使用链表实现队列：
链表不会受到同数组一样的困扰，并且链表实现的队列没有数组的大小限制；但需要额外的指针来管理链表的节点。

4. 队列的基本操作

队列的基本操作包括入队（Enqueue）、出队（Dequeue）、查看队头（Peek）和检查队列是否为空（IsEmpty）。

入队（Enqueue）：
将元素添加到队尾。

出队（Dequeue）：
移除队头的元素。

查看队头（Peek）：
查看队头的元素，但不移除。

检查队列是否为空（IsEmpty）：
检查队列中是否有元素。

5. 队列的高级用法

循环队列：
循环队列是一种优化的队列实现，避免了数组实现中由于出队操作造成的空间浪费。

优先队列：
优先队列中的元素具有优先级，出队时优先级高的元素会被优先移除。

6.两种形式的队列实现

在这里插入图片描述

入队（Enqueue）

将元素添加到队尾。如果使用数组实现，需要检查队列是否已满。如果使用链表实现，只需将新节点添加到链表的末尾。

数组实现的入队操作：

void enqueue(Queue* q, int value) {if (isFull(q)) {printf("Queue is full!\n");return;}if (isEmpty(q)) {q->front = 0;}q->rear++;q->items[q->rear] = value;
}

链表实现的入队操作：

void enqueue(Queue* q, int value) {Node* newNode = (Node*)malloc(sizeof(Node));newNode->data = value;newNode->next = NULL;if (isEmpty(q)) {q->front = newNode;} else {q->rear->next = newNode;}q->rear = newNode;
}

出队（Dequeue）

移除队头的元素。如果使用数组实现，需要检查队列是否为空，并调整队头指针。如果使用链表实现，需要移除链表的第一个节点。

数组实现的出队操作：

int dequeue(Queue* q) {if (isEmpty(q)) {printf("Queue is empty!\n");return -1;}int item = q->items[q->front];q->front++;if (q->front > q->rear) {initQueue(q);}return item;
}

链表实现的出队操作：

int dequeue(Queue* q) {if (isEmpty(q)) {printf("Queue is empty!\n");return -1;}int item = q->front->data;Node* temp = q->front;q->front = q->front->next;if (q->front == NULL) {q->rear = NULL;}free(temp);return item;
}

查看队头（Peek）

查看队头的元素，但不移除。如果队列为空，应返回特定的错误值或抛出异常。

数组实现的查看队头操作：

int peek(Queue* q) {if (isEmpty(q)) {printf("Queue is empty!\n");return -1;}return q->items[q->front];
}

链表实现的查看队头操作：

int peek(Queue* q) {if (isEmpty(q)) {printf("Queue is empty!\n");return -1;}return q->front->data;
}

检查队列是否为空（IsEmpty）

检查队列中是否有元素。这是一个常用的辅助操作，用于确保其他操作的前提条件。

数组实现的检查是否为空操作：

int isEmpty(Queue* q) {return q->front == -1;
}

链表实现的检查是否为空操作：

int isEmpty(Queue* q) {return q->front == NULL;
}

队列的高级玩法

除了基本操作外，队列还有一些高级用法，如循环队列和优先队列。

循环队列

在这里插入图片描述

循环队列是一种优化的队列实现，避免了数组实现中由于出队操作造成的空间浪费。循环队列通过将队尾连接到队头，使得数组能够循环使用。

循环队列的实现：

#define MAX 100typedef struct {int items[MAX];int front, rear;
} CircularQueue;void initQueue(CircularQueue* q) {q->front = -1;q->rear = -1;
}int isEmpty(CircularQueue* q) {return q->front == -1;
}int isFull(CircularQueue* q) {return (q->rear + 1) % MAX == q->front;
}void enqueue(CircularQueue* q, int value) {if (isFull(q)) {printf("Queue is full!\n");return;}if (isEmpty(q)) {q->front = 0;}q->rear = (q->rear + 1) % MAX;q->items[q->rear] = value;
}int dequeue(CircularQueue* q) {if (isEmpty(q)) {printf("Queue is empty!\n");return -1;}int item = q->items[q->front];if (q->front == q->rear) {initQueue(q);} else {q->front = (q->front + 1) % MAX;}return item;
}