数据结构与算法学习笔记三---队列的表示和实现(C语言)

  • 开发
  • 10

目录

前言

1.定义         

2.队列的表示和实现

1.链队列

1.定义

2.初始化

3.入队

4.出队

5.队列为空

6.队列长度

7.清空队列

8.获取队首元素

9.完整代码

2.顺序队列

1.定义

2.初始化

3.入队

4.出队

5.队列为空

6.队列长度

7.清空队列

8.获取队首元素

9.完整代码

前言

        这篇博客主要讲队列的用法。

1.定义         

        队列是一种常见的数据结构，它按照先进先出（FIFO，First In First Out）的原则管理元素。队列可以被看作是一个有限长度的线性表，它有两个主要的操作：入队和出队。

1. 入队（enqueue）：将新元素添加到队列的末尾。
2. 出队（dequeue）：从队列的头部移除并返回元素。

        队列的特点是只能在队列的一端进行插入（入队），在另一端进行删除（出队）。这种操作方式保证了队列中的元素按照其添加的顺序被处理。除了入队和出队操作，队列通常还包括以下常用操作：

1.队列是否为空（isEmpty）：判断队列中是否有元素。
2.队列的长度（size）：返回队列中元素的数量。
3.获取队首元素（front）：返回队列中的第一个元素，但不从队列中移除它。

         队列的应用十分广泛，例如：

1.在计算机科学中，队列常用于实现广度优先搜索算法（BFS）、任务调度等。
2.在操作系统中，队列可用于实现进程调度、缓存管理等。
3. 在网络通信中，队列用于数据包的传输与接收。
4.在生活中，队列的概念也常见于排队等待购票、排队买东西等场景。

2.队列的表示和实现

        队列可以分别使用顺存和链式两种存储方式实现。

1.链队列

        使用链式存储结构表示队列。

1.定义

        和单链表的定义相同，我们需要定义队列的指针域和值域。

// 节点类型定义
typedef struct QNode{
    int data;//元素
    struct QNode * next;//指向下一个节点的指针
}QNode,*QueuePtr;

typedef struct {
    QueuePtr front; // 队首指针
    QueuePtr rear;  // 队尾指针
}LinkQueue;

2.初始化

        初始化队列的时候，首先给队列分配存储空间，然后设置队首指针和队尾指针

// 初始化队列
int initQueue(LinkQueue *queue) {
    queue->front = queue->rear = (QueuePtr)malloc(sizeof(QNode));
    if (!queue->front) {
        return 0;
    }
    queue->front->next = NULL;
    return 1;
}

3.入队

        入队的时候，首先生成一个新节点，节点的值域指向我们传递的数据元素，然后把新节点插入到队尾。

// 入队
int EnQueue(LinkQueue *queue, int element) {
    QueuePtr newNode = (QueuePtr)malloc(sizeof(QNode)); // 新节点
    if (!newNode) { // 存储分配失败
        return 0;
    }
    newNode->data = element;
    newNode->next = NULL;
    queue->rear->next = newNode; // 新节点插入到队列尾部
    queue->rear = newNode;       // 更新队尾指针
    return 1;
}

4.出队

        出队列的时候，修改队首指针。这里要注意的是如果队列中只有一个数据元素的时候，要更新下尾节点指针。

// 出队
int DeQueue(LinkQueue *queue, int *element) {
    if (queue->front == queue->rear) {
        return 0; // 队列为空，出队失败
    }
    QueuePtr temp = queue->front->next; // 暂存队首节点
    *element = temp->data;              // 获取要出队的元素值
    queue->front->next = temp->next;    // 更新队首指针
    if (queue->rear == temp) {
        queue->rear = queue->front;     // 如果出队后队列为空，更新队尾指针
    }
    free(temp);                         // 释放出队节点的内存
    return 1; // 出队成功
}

5.队列为空

        队首和队尾相同的时候，队列为空。

// 是否为空队列
int QueueEmpty(LinkQueue *queue) {
    return queue->front == queue->rear;
}

6.队列长度

        遍历队列中的数据元素。

// 队列长度
void QueueLength(LinkQueue *queue) {
    int length = 0;
    QueuePtr p = queue->front->next;
    while (p) {
        length++;
        p = p->next;
    }
    printf("队列长度：%d\n", length);
}

7.清空队列

        遍历队列中的数据元素，释放数据元素的存储空间。

// 清空队列
void clearQueue(LinkQueue *queue) {
    QueuePtr p = queue->front->next;
    while (p) {
        QueuePtr temp = p;
        p = p->next;
        free(temp);
    }
    queue->front->next = NULL;
    queue->rear = queue->front;
}

8.获取队首元素

// 获取队首元素
void getQueueHead(LinkQueue *queue) {
    if (QueueEmpty(queue)) {
        printf("队列为空，无法获取队首元素！\n");
    } else {
        printf("队首元素：%d\n", queue->front->next->data);
    }
}

9.完整代码

        

#include <stdlib.h>

// 节点类型定义
typedef struct QNode{
    int data;//元素
    struct QNode * next;//指向下一个节点的指针
}QNode,*QueuePtr;

typedef struct {
    QueuePtr front; // 队首指针
    QueuePtr rear;  // 队尾指针
}LinkQueue;
// 初始化队列
int initQueue(LinkQueue *queue) {
    queue->front = queue->rear = (QueuePtr)malloc(sizeof(QNode));
    if (!queue->front) {
        return 0;
    }
    queue->front->next = NULL;
    return 1;
}

// 入队
int EnQueue(LinkQueue *queue, int element) {
    QueuePtr newNode = (QueuePtr)malloc(sizeof(QNode)); // 新节点
    if (!newNode) { // 存储分配失败
        return 0;
    }
    newNode->data = element;
    newNode->next = NULL;
    queue->rear->next = newNode; // 新节点插入到队列尾部
    queue->rear = newNode;       // 更新队尾指针
    return 1;
}

// 出队
int DeQueue(LinkQueue *queue, int *element) {
    if (queue->front == queue->rear) {
        return 0; // 队列为空，出队失败
    }
    QueuePtr temp = queue->front->next; // 暂存队首节点
    *element = temp->data;              // 获取要出队的元素值
    queue->front->next = temp->next;    // 更新队首指针
    if (queue->rear == temp) {
        queue->rear = queue->front;     // 如果出队后队列为空，更新队尾指针
    }
    free(temp);                         // 释放出队节点的内存
    return 1; // 出队成功
}

// 打印队列中的数据元素
void printQueue(LinkQueue *queue) {
    if (queue->front == queue->rear) {
        printf("队列为空\n");
        return;
    }
    QueuePtr p = queue->front->next;
    printf("队列元素：");
    while (p) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

// 是否为空队列
int QueueEmpty(LinkQueue *queue) {
    return queue->front == queue->rear;
}

// 队列长度
void QueueLength(LinkQueue *queue) {
    int length = 0;
    QueuePtr p = queue->front->next;
    while (p) {
        length++;
        p = p->next;
    }
    printf("队列长度：%d\n", length);
}

// 清空队列
void clearQueue(LinkQueue *queue) {
    QueuePtr p = queue->front->next;
    while (p) {
        QueuePtr temp = p;
        p = p->next;
        free(temp);
    }
    queue->front->next = NULL;
    queue->rear = queue->front;
}


// 获取队首元素
void getQueueHead(LinkQueue *queue) {
    if (QueueEmpty(queue)) {
        printf("队列为空，无法获取队首元素！\n");
    } else {
        printf("队首元素：%d\n", queue->front->next->data);
    }
}


void test_queue(void) {
    LinkQueue queue;
    // 初始化队列
    printf("初始化队列...\n");
    if (initQueue(&queue)) {
        printf("队列初始化成功！\n");
    } else {
        printf("队列初始化失败！\n");
    }
    
    // 入队元素 10
    printf("入队元素 10...\n");
    if (EnQueue(&queue, 10)) {
        printf("入队成功！\n");
    } else {
        printf("入队失败！\n");
    }

    
    // 入队元素 20
    printf("入队元素 20...\n");
    if (EnQueue(&queue, 20)) {
        printf("入队成功！\n");
    } else {
        printf("入队失败！\n");
    }
    
    // 入队元素 30
    printf("入队元素 30...\n");
    if (EnQueue(&queue, 30)) {
        printf("入队成功！\n");
    } else {
        printf("入队失败！\n");
    }
    
    // 打印队列
    printf("当前队列：\n");
    printQueue(&queue);
    
    // 出队
    int element;
    printf("出队元素...\n");
    if (DeQueue(&queue, &element)) {
        printf("出队元素：%d\n", element);
    } else {
        printf("队列为空，出队失败！\n");
    }
    
    // 打印队列
    printf("当前队列：\n");
    printQueue(&queue);
    
    // 获取队首元素
    printf("获取队首元素...\n");
    getQueueHead(&queue);
    
    // 清空队列
    printf("清空队列...\n");
    clearQueue(&queue);
    
    // 打印队列
    printf("当前队列：\n");
    printQueue(&queue);
}

2.顺序队列

1.定义

        队列的顺序类型定义中，base表示队列的基地址，front表示队首指针，rear表示队尾指针。

#define MAXQSIZE 100 //最大队列长度
typedef struct{
    int * base;//队列基址
    int front; //队首指针,若队列不为空 指向队列头元素
    int rear;  //队尾指针 若队尾不为空 指向队尾指针元素的下一个位置
}SeqQueue;

2.初始化

        初始化队列的时候，首先分配存储空间，然后队首和队尾的数据元素都为0；

// 初始化队列
int initSeqQueue(SeqQueue *seqQueue){
    seqQueue->base = (int *)malloc(sizeof(int) * MAXQSIZE);
    if (!seqQueue->base) {
        return 0;
    }
    seqQueue->front = seqQueue->rear = 0;
    return 1;
}

3.入队

        判断是否对满，对满的时候无法入队，入队之后rear++。

// 入队
int EnSeqQueue(SeqQueue *queue,int element){
    if (queue->rear >= MAXQSIZE ) {
        return 0;
    }
    queue->base[queue->rear++] = element;
    return 1;
}

4.出队

        出队的时候判断队列是否为空，不为空的话,front++。

// 出队
int DeSeqQueue(SeqQueue *queue, int *element){
    if (queue->front == queue->rear) {
        return 0; // 队列为空，出队失败
    }
    *element = queue->base[queue->front]; // 获取队首元素
    queue->front++; // 更新队首指针
    return 1; // 出队成功
}

5.队列为空

        队首和队尾相同的时候，队列为空。

// 是否为空队列
int seqQeueEmpty(SeqQueue *seqQueue){
    return seqQueue->front == seqQueue->rear;
}

6.队列长度

        遍历队列中的数据元素。

// 队列长度
int seqQueueLength(SeqQueue * seqQueue){
    return seqQueue->rear - seqQueue->front;
}

7.清空队列

        遍历队列中的数据元素，释放数据元素的存储空间。

// 清空队列
void clearQueue(LinkQueue *queue) {
    QueuePtr p = queue->front->next;
    while (p) {
        QueuePtr temp = p;
        p = p->next;
        free(temp);
    }
    queue->front->next = NULL;
    queue->rear = queue->front;
}

8.获取队首元素

        首先判断队列是否为空，空队列无法获取队首元素。

// 队列首元素
int getSeqQueueHead(SeqQueue * seqQueue,int * element){
    if (!seqQeueEmpty(seqQueue)) {
        * element = seqQueue->base[seqQueue->front];
        return 1;
    }
    return 0;
}

9.完整代码

        

#include <stdlib.h>
#include <stdio.h>

#define MAXQSIZE 5 //最大队列长度
typedef struct{
    int * base;//队列基址
    int front; //队首指针,若队列不为空 指向队列头元素
    int rear;  //队尾指针 若队尾不为空 指向队尾指针元素的下一个位置
}SeqQueue;


// 打印队列中的数据元素
void printSeqQueue(SeqQueue *queue){
    for (int i = 0; i<queue->rear; i++) {
        printf("%d\t",queue->base[i]);
    }
    printf("\n");
}

// 初始化队列
int initSeqQueue(SeqQueue *seqQueue){
    seqQueue->base = (int *)malloc(sizeof(int) * MAXQSIZE);
    if (!seqQueue->base) {
        return 0;
    }
    seqQueue->front = seqQueue->rear = 0;
    return 1;
}
// 出队
int DeSeqQueue(SeqQueue *queue, int *element){
    if (queue->front == queue->rear) {
        return 0; // 队列为空，出队失败
    }
    *element = queue->base[queue->front]; // 获取队首元素
    queue->front++; // 更新队首指针
    return 1; // 出队成功
}
// 入队
int EnSeqQueue(SeqQueue *queue,int element){
    if (queue->rear >= MAXQSIZE ) {
        return 0;
    }
    queue->base[queue->rear++] = element;
    return 1;
}

// 是否为空队列
int seqQeueEmpty(SeqQueue *seqQueue){
    return seqQueue->front == seqQueue->rear;
}

// 队列长度
int seqQueueLength(SeqQueue * seqQueue){
    return seqQueue->rear - seqQueue->front;
}

// 清空队列
void clearSeqQueue(SeqQueue * seqQueue){
    seqQueue->front = seqQueue->rear = 0;
}
// 销毁队列
void destroySeqQueue(SeqQueue * seqQueue){
    if (seqQueue->base) {
        free(seqQueue->base);
        seqQueue->base = NULL;
    }
    seqQueue->front = seqQueue->rear = 0;
}
// 队列首元素
int getSeqQueueHead(SeqQueue * seqQueue,int * element){
    if (!seqQeueEmpty(seqQueue)) {
        * element = seqQueue->base[seqQueue->front];
        return 1;
    }
    return 0;
}
//创建测试队列
SeqQueue createTestSeqQueue(SeqQueue seqQueue){
    int success = 0;
    for (int i = 1; i<= 5; i++) {
        if (EnSeqQueue(&seqQueue, 10 * i)) {//入队成功
            success = 1;
        }else{
            break;
        }
    }
    return seqQueue;
}

void testSeqQueue(void){
    SeqQueue seqQueue;
    printf("队列初始化.......\n");
    if(initSeqQueue(&seqQueue)){
        printf("队列初始化成功\t✅\n");
    }else{
        printf("队列初始化失败\n");
    }
    //测试入队
    for (int i = 1; i<= 5; i++) {
        //入队
        if (EnSeqQueue(&seqQueue, 10 * i)) {
            printf("第%d次入队 数据入队数据元素:%d 成功! 入队之后front = %d\t rear=%d\t\t✅\n",i,10 * i,seqQueue.front,seqQueue.rear);
        }else{
            printf("入队失败!");
        }
    }
    printf("\n********************\t队列长度和队列是否为空测试\t********************\n");
    printf("\n********************\t队列中的数据元素\t********************\n");
    printSeqQueue(&seqQueue);
    if (!seqQeueEmpty(&seqQueue)) {
        printf("\n队列不为空\t队列长度为:%d\t✅\n",seqQueueLength(&seqQueue));
    }
    int queueHeadElement;
    if (getSeqQueueHead(&seqQueue, &queueHeadElement)) {
        printf("队列首元素:%d\n",queueHeadElement);
    }
    
    printf("\n********************\t队列清空测试\t********************\n");
    clearSeqQueue(&seqQueue);
    if (seqQeueEmpty(&seqQueue)) {
        printf("队列为空,清空测试通过\t✅\n");
    }
    
    printf("\n********************\t队列销毁测试\t********************\n");
    seqQueue = createTestSeqQueue(seqQueue);
    printf("销毁之前队列:\n");
    destroySeqQueue(&seqQueue);
    if (seqQueueLength(&seqQueue)==0) {
        printf("队列为空,队列销毁成功\t✅\n");
    }
    printSeqQueue(&seqQueue);
}

int main(int argc, const char *argv[]) {
    testSeqQueue();
    return 0;
}
阅读全部

相关推荐

  1. 数据结构与算法学习笔记三---队列的表示和实现(C语言)

    2024-05-01 08:14:02       11 阅读

  5. 数据结构与算法学习笔记五---栈的表示和实现(C语言)

    2024-05-01 08:14:02       12 阅读

  7. 数据结构与算法学习笔记一---顺序表的静态存储表示和实现(C语言)

    2024-05-01 08:14:02       9 阅读

最近更新

  4. TCP协议是安全的吗?

    2024-05-01 08:14:02       18 阅读

  12. 阿里云服务器执行yum，一直下载docker-ce-stable失败

    2024-05-01 08:14:02       19 阅读

  13. 【Python教程】压缩PDF文件大小

    2024-05-01 08:14:02       18 阅读

  18. 通过文章id递归查询所有评论（xml）

    2024-05-01 08:14:02       20 阅读

热门阅读

  1. 手写数字识别：基于决策树算法，KNN算法，支持向量机（SVM）算法与卷积神经网络（CNN）算法

    2024-05-01 08:14:02       13 阅读

  4. requestbody无法将json字符串转为相应类

    2024-05-01 08:14:02       10 阅读

  5. Nacos 1.4.1核心功能组件及使用入门

    2024-05-01 08:14:02       7 阅读

  7. CentOS常见的命令

    2024-05-01 08:14:02       12 阅读

  20. WPF控件：密码框绑定MVVM

    2024-05-01 08:14:02       10 阅读

  21. wpf 树形结构

    2024-05-01 08:14:02       10 阅读

  25. Jetson Orin NX L4T35.5.0平台相机stop导致系统死机问题调试

    2024-05-01 08:14:02       11 阅读

  27. 等保保护测评试题中

    2024-05-01 08:14:02       12 阅读

  28. 如何看待AIGC技术？宝兰德有话说

    2024-05-01 08:14:02       13 阅读