【数据结构】队列知识点总结--定义；基本操作；队列的顺序实现；链式存储；双端队列；循环队列

 欢迎各位看官^_^

目录

1.队列的定义

2.队列的基本操作

2.1初始化队列

2.2判断队列是否为空

2.3判断队列是否已满

2.4入队

2.5出队

2.6完整代码 

3.队列的顺序实现

4.队列的链式存储

5.双端队列

6.循环队列

---

1.队列的定义

        队列（Queue）是一种先进先出（First In First Out，FIFO）的线性数据结构，它只允许在队尾添加元素，在队头删除元素，不支持随机访问。队列常用的操作有入队（enqueue）、出队（dequeue）、队列长度（size）、队列是否为空（empty）等。队列可以用来实现很多算法，如广度优先搜索算法（BFS）和消息传递等。

2.队列的基本操作

2.1初始化队列

        可以使用数组或链表来实现队列。对于数组，我们可以定义一个数组和两个指针（front和rear）来表示队列。对于链表，我们可以创建一个链表，并定义头节点指针和尾节点指针。队列是一种线性数据结构，可以用数组或链表来实现。

以下是用数组实现队列的C语言代码示例：

#include <stdio.h>
 
#define MAX_SIZE 100
 
int queue[MAX_SIZE];
int front = 0, rear = -1;
 
void enqueue(int data) {
    if (rear == MAX_SIZE - 1) {
        printf("Queue overflow\n");
    } else {
        rear++;
        queue[rear] = data;
    }
}
 
int dequeue() {
    if (front > rear) {
        printf("Queue underflow\n");
        return -1;
    } else {
        int data = queue[front];
        front++;
        return data;
    }
}
 
int main() {
    enqueue(10);
    enqueue(20);
    enqueue(30);
    printf("%d ", dequeue());
    printf("%d ", dequeue());
    printf("%d ", dequeue());
    printf("%d ", dequeue());
    return 0;
}

        上述代码中，`queue`为数组，`front`和`rear`分别表示队列的前后指针，初始化为`0`和`-1`。`enqueue`函数用于向队列中添加元素，先判断队列是否已满，若未满则将数据存入队列尾部。`dequeue`函数用于弹出队列头部元素，先判断队列是否为空，若非空则返回队列头部元素并将`front`指针后移一位。在`main`函数中，先将元素10、20、30添加到队列中，然后依次弹出队列头部元素并输出。

2.2判断队列是否为空

如果队列为空，则front和rear指向同一个位置。

// 判断队列是否为空
int is_empty() {
    return front == rear;
}

2.3判断队列是否已满

如果队列已满，则rear指向的下一个位置就是front（因为它是循环队列）。

// 判断队列是否已满
int is_full() {
    return (rear + 1) % MAX_SIZE == front;
}

2.4入队

当队列不满时，我们将元素插入队列的rear位置，并将rear指针后移。

// 入队
void enqueue(int data) {
    if (is_full()) {
        printf("Queue is full.\n");
        return;
    }
    queue[rear] = data;
    rear = (rear + 1) % MAX_SIZE;
}

2.5出队

当队列不为空时，我们将front指向的元素从队列中删除，并将front指针后移。

// 出队
int dequeue() {
    if (is_empty()) {
        printf("Queue is empty.\n");
        return -1;
    }
    int data = queue[front];
    front = (front + 1) % MAX_SIZE;
    return data;
}

2.6完整代码 

#include <stdio.h>
#define MAX_SIZE 10      // 定义队列的最大容量为10
 
int queue[MAX_SIZE];     // 定义数组队列
int front = 0, rear = 0; // front指向队首，rear指向队尾的下一个位置
 
// 判断队列是否为空
int is_empty() {
    return front == rear;
}
 
// 判断队列是否已满
int is_full() {
    return (rear + 1) % MAX_SIZE == front;
}
 
// 入队
void enqueue(int data) {
    if (is_full()) {
        printf("Queue is full.\n");
        return;
    }
    queue[rear] = data;
    rear = (rear + 1) % MAX_SIZE;
}
 
// 出队
int dequeue() {
    if (is_empty()) {
        printf("Queue is empty.\n");
        return -1;
    }
    int data = queue[front];
    front = (front + 1) % MAX_SIZE;
    return data;
}
 
int main() {
    enqueue(1);
    enqueue(2);
    enqueue(3);
    printf("%d\n", dequeue());
    printf("%d\n", dequeue());
    enqueue(4);
    printf("%d\n", dequeue());
    printf("%d\n", dequeue());
    return 0;
}

        注意：这是一个循环队列，在计算rear的位置时需要使用取模运算。这是因为数组的最后一个位置后面没有下一个位置，我们需要将rear回到数组的开头位置。 

3.队列的顺序实现

C语言队列的顺序实现可以使用数组来实现。实现思路如下：

1. 定义一个数组和队列头尾指针。
2. 队列头指针指向队列的第一个元素，队列尾指针指向队列的最后一个元素。
3. 入队操作时，先判断队列是否已满，如果已满则提示队列已满，否则将元素加入到队列尾部，并更新队列尾指针。
4. 出队操作时，先判断队列是否为空，如果为空则提示队列为空，否则将队列头部的元素出队，并更新队列头指针。
5. 获取队列头元素时，先判断队列是否为空，如果为空则提示队列为空，否则返回队列头的元素。

以下是C语言队列的顺序实现示例代码：

#include <stdio.h>
#define MAX_SIZE 100
 
// 定义队列结构体
typedef struct {
    int data[MAX_SIZE];  // 存储队列的数组
    int front;  // 队列头指针
    int rear;   // 队列尾指针
} Queue;
 
// 初始化队列
void initQueue(Queue *q) {
    q->front = q->rear = 0;
}
 
// 入队
void enqueue(Queue *q, int x) {
    if ((q->rear + 1) % MAX_SIZE == q->front) {
        printf("Queue is full.\n");
    } else {
        q->data[q->rear] = x;
        q->rear = (q->rear + 1) % MAX_SIZE;
    }
}
 
// 出队
void dequeue(Queue *q) {
    if (q->front == q->rear) {
        printf("Queue is empty.\n");
    } else {
        q->front = (q->front + 1) % MAX_SIZE;
    }
}
 
// 获取队列头元素
int front(Queue *q) {
    if (q->front == q->rear) {
        printf("Queue is empty.\n");
        return -1;
    } else {
        return q->data[q->front];
    }
}
 
// 判断队列是否为空
int isEmpty(Queue *q) {
    return q->front == q->rear;
}
 
int main() {
    Queue q;
    initQueue(&q);
 
    // 入队
    enqueue(&q, 1);
    enqueue(&q, 2);
    enqueue(&q, 3);
 
    // 获取队列头元素
    printf("Front of queue: %d\n", front(&q));
 
    // 出队
    dequeue(&q);
 
    // 获取队列头元素
    printf("Front of queue: %d\n", front(&q));
 
    return 0;
}

 

4.队列的链式存储

        队列和链表的关系：队列和链表是两种不同的数据结构，但是在实现队列时可以使用链表来表示。队列是一种先进先出（First In First Out，FIFO）的数据结构，可以理解为是一条通道，从一端（队尾）加入数据，从另一端（队头）取出数据。而链表是一种动态数据结构，由节点之间的指针连接而成。每个节点包含一个数据元素和一个指向下一个节点的指针。在使用链表实现队列时，可以将链表的头作为队列的队头，将链表的尾作为队列的队尾，使用链表的头插法或尾插法对队列进行入队操作，使用链表的尾删除或头删除对队列进行出队操作。因此，可以说队列和链表有一定的关系，但二者仍然是不同的数据结构。 

        队列的链式存储是使用链表来实现队列的存储结构。队列的链式存储结构可以分为单向链表和双向链表两种。

        单向链表的存储结构是每个节点包含一个数据元素和一个指向下一个节点的指针。队列的头指针指向链表的头节点，队列的尾指针指向链表的尾节点。入队操作将元素添加到尾节点之后，出队操作则删除头节点。

        双向链表的存储结构是每个节点包含一个数据元素、一个指向前一个节点的指针和一个指向下一个节点的指针。队列的头指针指向链表头部，队列的尾指针指向链表尾部。入队操作将元素添加到尾节点之后，出队操作则删除头节点。

        链式存储相比于顺序存储的优势在于可以更灵活地插入和删除元素，但是在访问元素时需要通过指针遍历链表，效率较低。

        链式存储结构的队列通常包含一个头结点和一个尾结点，其中头结点指向队列的头部，尾结点指向队列的尾部。每个结点都包含一个数据域和一个指针域，指针域指向下一个结点。

以下是C语言实现队列的链式存储的示例代码：

#include <stdio.h>
#include <stdlib.h>
 
// 队列结点定义
typedef struct queue_node{
    int data;                   // 数据域
    struct queue_node *next;    // 指针域
} queue_node;
 
// 队列定义
typedef struct {
    queue_node *front;          // 队列头指针
    queue_node *rear;           // 队列尾指针
} queue;
 
// 初始化队列
void init_queue(queue *q)
{
    // 分配头结点
    q->front = q->rear = (queue_node *)malloc(sizeof(queue_node));
    if (!q->front) {
        printf("Memory allocation failed.\n");
        exit(-1);
    }
    q->front->next = NULL;
}
 
// 判断队列是否为空
int is_empty(queue *q)
{
    return q->front == q->rear;
}
 
// 入队
void enqueue(queue *q, int data)
{
    queue_node *new_node = (queue_node *)malloc(sizeof(queue_node));
    if (!new_node) {
        printf("Memory allocation failed.\n");
        exit(-1);
    }
    new_node->data = data;
    new_node->next = NULL;
    q->rear->next = new_node;
    q->rear = new_node;
}
 
// 出队
int dequeue(queue *q)
{
    if (is_empty(q)) {
        printf("Queue is empty.\n");
        exit(-1);
    }
    queue_node *p = q->front->next;
    int data = p->data;
    q->front->next = p->next;
    if (q->rear == p) {
        q->rear = q->front;
    }
    free(p);
    return data;
}
 
// 输出队列中元素
void print_queue(queue *q)
{
    queue_node *p = q->front->next;
    while (p) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}
 
int main()
{
    queue q;
    init_queue(&q);
    for (int i = 1; i <= 5; i++) {
        enqueue(&q, i);
    }
    print_queue(&q);
    dequeue(&q);
    print_queue(&q);
    return 0;
}

5.双端队列

        双端队列（deque，全名double-ended queue）是一种具有队列和栈的性质的数据结构，即两端都可以进行插入和删除操作。

        双端队列有两个端点：一个是“前端”（front），可以进行“出队”操作；另一个是“后端”（rear），可以进行“入队”操作。因此，双端队列支持的操作包括入队、出队、队头入队、队尾入队、队头出队、队尾出队等。

        与单端队列相比，双端队列的优势在于可以自由地从两端添加或删除元素，更加灵活、方便地实现某些算法和数据结构。例如，在实现图遍历算法中，使用双端队列可以使得遍历的顺序更加合理，减少搜索的时间和空间复杂度。

        另外，双端队列支持一些其他的操作，如获取队列长度、获取队头/尾元素等。

以下是C语言实现双端队列的代码：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
 
// 双端队列节点结构体
typedef struct DequeNode {
    int val;
    struct DequeNode* next;
    struct DequeNode* prev;
} DequeNode;
 
// 双端队列结构体
typedef struct Deque {
    DequeNode* front; // 队头指针
    DequeNode* rear; // 队尾指针
    int size; // 队列元素个数
} Deque;
 
// 初始化双端队列
void initDeque(Deque* deque) {
    deque->front = NULL;
    deque->rear = NULL;
    deque->size = 0;
}
 
// 判断双端队列是否为空
bool isEmptyDeque(Deque* deque) {
    return deque->size == 0;
}
 
// 获取双端队列的长度
int sizeDeque(Deque* deque) {
    return deque->size;
}
 
// 获取双端队列队头元素
int frontDeque(Deque* deque) {
    return deque->front->val;
}
 
// 获取双端队列队尾元素
int rearDeque(Deque* deque) {
    return deque->rear->val;
}
 
// 在双端队列前端插入元素
void addFrontDeque(Deque* deque, int val) {
    DequeNode* new_node = (DequeNode*)malloc(sizeof(DequeNode));
    new_node->val = val;
    new_node->next = deque->front;
    new_node->prev = NULL;
    if (deque->front != NULL) {
        deque->front->prev = new_node;
    }
    deque->front = new_node;
    if (deque->rear == NULL) {
        deque->rear = new_node;
    }
    deque->size++;
}
 
// 在双端队列后端插入元素
void addRearDeque(Deque* deque, int val) {
    DequeNode* new_node = (DequeNode*)malloc(sizeof(DequeNode));
    new_node->val = val;
    new_node->next = NULL;
    new_node->prev = deque->rear;
    if (deque->rear != NULL) {
        deque->rear->next = new_node;
    }
    deque->rear = new_node;
    if (deque->front == NULL) {
        deque->front = new_node;
    }
    deque->size++;
}
 
// 在双端队列前端删除元素
void removeFrontDeque(Deque* deque) {
    if (deque->front == NULL) {
        return;
    }
    DequeNode* temp = deque->front;
    deque->front = deque->front->next;
    if (deque->front != NULL) {
        deque->front->prev = NULL;
    } else {
        deque->rear = NULL;
    }
    free(temp);
    deque->size--;
}
 
// 在双端队列后端删除元素
void removeRearDeque(Deque* deque) {
    if (deque->rear == NULL) {
        return;
    }
    DequeNode* temp = deque->rear;
    deque->rear = deque->rear->prev;
    if (deque->rear != NULL) {
        deque->rear->next = NULL;
    } else {
        deque->front = NULL;
    }
    free(temp);
    deque->size--;
}
 
// 测试
int main() {
    Deque deque;
    initDeque(&deque);
    addFrontDeque(&deque, 1);
    addRearDeque(&deque, 2);
    addFrontDeque(&deque, 3);
    addRearDeque(&deque, 4);
    while (!isEmptyDeque(&deque)) {
        printf("%d ", frontDeque(&deque));
        removeFrontDeque(&deque);
    }
    printf("\n");
    return 0;
}

6.循环队列

        循环队列是一种环形数据结构，它允许在一端添加数据元素，同时在另一端删除数据元素。与线性队列不同的是，在循环队列中，队头和队尾是可以相互穿越的。这意味着队列的末尾可以连接到队列的开始，形成一个环。这样，可以使用有限的空间，存储无限数量的数据元素。

        循环队列通常使用数组来实现。它有一个前后指针，称为队头和队尾。入队操作时，将新元素加入队尾，并将队尾指针向后移动。出队操作时，将队头元素删除，并将队头指针向后移动。当队列满时，新元素无法插入，即使队列前面有空位置。当队列为空时，无法删除元素。

        循环队列的主要优点是可以避免队列的前面空出大量空间，同时保证队列的顺序性和完整性。缺点是在实现时需要注意控制队列满和空的情况，以及指针的计算。

        循环队列是一种特殊的队列，其队尾指针指向数组的末尾后会回到数组的开头，实现队列的循环利用。下面是C语言实现循环队列的示例代码：

#include <stdio.h>
#include <stdlib.h>
 
#define QUEUE_MAX_SIZE 5  // 队列的最大容量
 
typedef struct {
    int* data;  // 队列数据存储的位置
    int front;  // 队首指针
    int rear;   // 队尾指针
} Queue;
 
// 初始化队列
void InitQueue(Queue* q) {
    q->data = (int*)malloc(QUEUE_MAX_SIZE * sizeof(int));  // 分配队列空间
    q->front = q->rear = 0;  // 初始化队首和队尾指针
}
 
// 判断队列是否为空
int IsEmpty(Queue* q) {
    return q->front == q->rear;
}
 
// 判断队列是否已满
int IsFull(Queue* q) {
    return (q->rear + 1) % QUEUE_MAX_SIZE == q->front;
}
 
// 入队操作
int EnQueue(Queue* q, int value) {
    if (IsFull(q)) {
        return 0;  // 队列已满，无法入队
    }
    q->data[q->rear] = value;  // 将数据存入队列
    q->rear = (q->rear + 1) % QUEUE_MAX_SIZE;  // 队尾指针后移
    return 1;  // 入队成功
}
 
// 出队操作
int DeQueue(Queue* q, int* value) {
    if (IsEmpty(q)) {
        return 0;  // 队列为空，无法出队
    }
    *value = q->data[q->front];  // 取出队首数据
    q->front = (q->front + 1) % QUEUE_MAX_SIZE;  // 队首指针后移
    return 1;  // 出队成功
}
 
// 获取队首元素
int GetFront(Queue* q, int* value) {
    if (IsEmpty(q)) {
        return 0;  // 队列为空，无法获取队首元素
    }
    *value = q->data[q->front];  // 获取队首元素
    return 1;  // 获取成功
}
 
// 获取队列长度
int GetLength(Queue* q) {
    return (q->rear - q->front + QUEUE_MAX_SIZE) % QUEUE_MAX_SIZE;
}
 
// 输出队列中的所有元素
void PrintQueue(Queue* q) {
    int i, len = GetLength(q);
    for (i = 0; i < len; i++) {
        int value;
        DeQueue(q, &value);
        printf("%d ", value);
        EnQueue(q, value);
    }
    printf("\n");
}
 
// 测试代码
int main() {
    Queue q;
    InitQueue(&q);
    EnQueue(&q, 1);
    EnQueue(&q, 2);
    EnQueue(&q, 3);
    EnQueue(&q, 4);
    EnQueue(&q, 5);
    printf("Queue length: %d\n", GetLength(&q));  // 5
    printf("Queue content: ");
    PrintQueue(&q);  // 1 2 3 4 5
    int value;
    DeQueue(&q, &value);
    printf("DeQueue value: %d\n", value);  // 1
    printf("Queue content: ");
    PrintQueue(&q);  // 2 3 4 5
    EnQueue(&q 

        在上面的代码中，我们实现了循环队列的初始化、判断是否为空或已满、入队、出队、获取队首元素、获取队列长度和输出队列中的所有元素等操作。我们可以通过这些操作对循环队列进行基本的操作。 

 

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/爱喝兽奶帝天荒/article/detail/884842?site