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

Skrrapper

发布于 2024-08-05 09:50:34

780

发布于 2024-08-05 09:50:34

文章被收录于专栏：技术分享

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 100

typedef 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;
}