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

C语言数据结构—队列

article 2024/12/24 11:27:20

队列（Queue）是一种基本的数据结构，遵循“先进先出”（First-In-First-Out, FIFO）的原则。队列在计算机科学中有广泛的应用，如任务调度、缓冲区管理、广度优先搜索等。在C语言中，队列可以通过数组或链表来实现。本文将详细介绍如何使用链表在C语言中实现队列，包括其基本结构、操作、示例代码以及优缺点。

队列的基本概念

  • 先进先出（FIFO）原则：最先进入队列的元素最先被移出。

  • 主要操作：

    • 入队（Enqueue）：将元素添加到队列的尾部。

    • 出队（Dequeue）：移除并返回队列的头部元素。

    • 查看队头（Front 或 Peek）：查看队列头部的元素但不移除。

    • 查看队尾（Rear）：查看队列尾部的元素但不移除。

    • 检查队列是否为空（IsEmpty）。

使用链表实现队列

使用链表实现队列时，通常维护两个指针：front 指向队列的头部（用于出队操作），rear 指向队列的尾部（用于入队操作）。这样可以在常数时间内进行入队和出队操作。

队列节点的结构体定义

首先，定义队列节点的结构体：

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

// 定义队列节点结构体
typedef struct QueueNode {
    int data;                  // 数据域
    struct QueueNode* next;    // 指向下一个节点的指针
} QueueNode;

创建新节点

创建一个新的队列节点：

// 创建一个新节点并返回指针
QueueNode* createNode(int data) {
    QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
    if (!newNode) {
        printf("内存分配失败\n");
        exit(1);
    }
    newNode->data = data;      // 初始化数据
    newNode->next = NULL;      // 初始化指针
    return newNode;
}

队列的基本操作

1. 入队（Enqueue）

将元素添加到队列的尾部：

typedef struct Queue {
    QueueNode* front; // 指向队列头部
    QueueNode* rear;  // 指向队列尾部
} Queue;

// 初始化队列
void initializeQueue(Queue* q) {
    q->front = q->rear = NULL;
}

// 入队操作
void enqueue(Queue* q, int data) {
    QueueNode* newNode = createNode(data);
    if (q->rear == NULL) { // 队列为空
        q->front = q->rear = newNode;
        printf("入队: %d (队列为空，成为头和尾)\n", data);
        return;
    }
    q->rear->next = newNode; // 将新节点链接到队尾
    q->rear = newNode;       // 更新队尾指针
    printf("入队: %d\n", data);
}
2. 出队（Dequeue）

移除并返回队列的头部元素：

int dequeue(Queue* q) {
    if (q->front == NULL) { // 队列为空
        printf("队列为空，无法出队\n");
        exit(1); // 或者返回一个错误码
    }
    QueueNode* temp = q->front;
    int dequeued = temp->data;
    q->front = q->front->next; // 更新队头指针
    if (q->front == NULL) {    // 队列变为空
        q->rear = NULL;
    }
    free(temp); // 释放出队的节点
    printf("出队: %d\n", dequeued);
    return dequeued;
}
3. 查看队头元素（Front）

查看队列头部元素但不移除：

int front(Queue* q) {
    if (q->front == NULL) {
        printf("队列为空\n");
        exit(1); // 或者返回一个错误码
    }
    return q->front->data;
}
4. 查看队尾元素（Rear）

查看队列尾部元素但不移除：

int rear(Queue* q) {
    if (q->rear == NULL) {
        printf("队列为空\n");
        exit(1); // 或者返回一个错误码
    }
    return q->rear->data;
}
5. 检查队列是否为空（IsEmpty）

判断队列是否为空：

int isEmpty(Queue* q) {
    return q->front == NULL;
}
6. 遍历队列

遍历并显示队列中的所有元素：

void traverseQueue(Queue* q) {
    QueueNode* temp = q->front;
    printf("队列内容: ");
    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

完整示例程序

下面是一个完整的示例程序，展示了如何使用链表实现队列，并执行基本操作：

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

// 队列节点结构体定义
typedef struct QueueNode {
    int data;
    struct QueueNode* next;
} QueueNode;

// 队列结构体定义
typedef struct Queue {
    QueueNode* front; // 指向队列头部
    QueueNode* rear;  // 指向队列尾部
} Queue;

// 创建新节点
QueueNode* createNode(int data) {
    QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
    if (!newNode) {
        printf("内存分配失败\n");
        exit(1);
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// 初始化队列
void initializeQueue(Queue* q) {
    q->front = q->rear = NULL;
}

// 入队操作
void enqueue(Queue* q, int data) {
    QueueNode* newNode = createNode(data);
    if (q->rear == NULL) { // 队列为空
        q->front = q->rear = newNode;
        printf("入队: %d (队列为空，成为头和尾)\n", data);
        return;
    }
    q->rear->next = newNode; // 将新节点链接到队尾
    q->rear = newNode;       // 更新队尾指针
    printf("入队: %d\n", data);
}

// 出队操作
int dequeue(Queue* q) {
    if (q->front == NULL) { // 队列为空
        printf("队列为空，无法出队\n");
        exit(1);
    }
    QueueNode* temp = q->front;
    int dequeued = temp->data;
    q->front = q->front->next; // 更新队头指针
    if (q->front == NULL) {    // 队列变为空
        q->rear = NULL;
    }
    free(temp); // 释放出队的节点
    printf("出队: %d\n", dequeued);
    return dequeued;
}

// 查看队头元素
int frontElement(Queue* q) {
    if (q->front == NULL) {
        printf("队列为空\n");
        exit(1);
    }
    return q->front->data;
}

// 查看队尾元素
int rearElement(Queue* q) {
    if (q->rear == NULL) {
        printf("队列为空\n");
        exit(1);
    }
    return q->rear->data;
}

// 检查队列是否为空
int isEmpty(Queue* q) {
    return q->front == NULL;
}

// 遍历队列
void traverseQueue(Queue* q) {
    QueueNode* temp = q->front;
    printf("队列内容: ");
    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

// 主函数示例
int main() {
    Queue q;
    initializeQueue(&q); // 初始化空队列

    // 入队操作
    enqueue(&q, 10);
    enqueue(&q, 20);
    enqueue(&q, 30);
    enqueue(&q, 40);

    // 遍历队列
    traverseQueue(&q); // 输出: 10 -> 20 -> 30 -> 40 -> NULL

    // 查看队头和队尾元素
    printf("队头元素: %d\n", frontElement(&q)); // 输出: 10
    printf("队尾元素: %d\n", rearElement(&q));  // 输出: 40

    // 出队操作
    dequeue(&q); // 弹出10
    traverseQueue(&q); // 输出: 20 -> 30 -> 40 -> NULL

    // 出队操作
    dequeue(&q); // 弹出20
    traverseQueue(&q); // 输出: 30 -> 40 -> NULL

    // 检查队列是否为空
    if (isEmpty(&q)) {
        printf("队列为空\n");
    } else {
        printf("队列不为空\n");
    }

    // 出队操作
    dequeue(&q); // 弹出30
    dequeue(&q); // 弹出40
    traverseQueue(&q); // 输出: NULL

    // 最终检查队列是否为空
    if (isEmpty(&q)) {
        printf("队列为空\n");
    } else {
        printf("队列不为空\n");
    }

    return 0;
}

输出结果

入队: 10 (队列为空，成为头和尾)
入队: 20
入队: 30
入队: 40
队列内容: 10 -> 20 -> 30 -> 40 -> NULL
队头元素: 10
队尾元素: 40
出队: 10
队列内容: 20 -> 30 -> 40 -> NULL
出队: 20
队列内容: 30 -> 40 -> NULL
队列不为空
出队: 30
出队: 40
队列内容: NULL
队列为空

队列的优缺点

优点

  1. 有序性：队列按照先进先出的顺序组织数据，适合需要有序处理的场景。

  2. 动态大小：使用链表实现的队列可以根据需要动态调整大小，不需要预先确定容量。

  3. 高效的插入和删除：在链表实现中，入队和出队操作只需更新指针，具有常数时间复杂度。

缺点

  1. 访问限制：只能访问队头和队尾元素，无法随机访问队列中的其他元素。

  2. 额外的内存开销：每个节点需要额外存储指针，增加了内存消耗。

  3. 缓存局部性差：节点在内存中不连续，可能导致缓存命中率降低，影响性能。

队列的变种与扩展

  1. 循环队列（Circular Queue）：使用数组实现的队列，通过环形结构提高空间利用率，避免“假溢出”问题。
#define SIZE 100

typedef struct CircularQueue {
  int items[SIZE];
  int front, rear;
} CircularQueue;

void initializeCircularQueue(CircularQueue* q) {
  q->front = q->rear = -1;
}

int isCircularQueueFull(CircularQueue* q) {
  if ((q->rear + 1) % SIZE == q->front)
      return 1;
  return 0;
}

int isCircularQueueEmpty(CircularQueue* q) {
  return q->front == -1;
}

void enqueueCircular(CircularQueue* q, int data) {
  if (isCircularQueueFull(q)) {
      printf("循环队列满，无法入队\n");
      return;
  }
  if (isCircularQueueEmpty(q)) {
      q->front = q->rear = 0;
  } else {
      q->rear = (q->rear + 1) % SIZE;
  }
  q->items[q->rear] = data;
  printf("入队: %d\n", data);
}

int dequeueCircular(CircularQueue* q) {
  if (isCircularQueueEmpty(q)) {
      printf("循环队列为空，无法出队\n");
      exit(1);
  }
  int data = q->items[q->front];
  if (q->front == q->rear) { // 队列变为空
      q->front = q->rear = -1;
  } else {
      q->front = (q->front + 1) % SIZE;
  }
  printf("出队: %d\n", data);
  return data;
}
  1. 双端队列（Deque, Double-Ended Queue）：支持在队列的两端插入和删除元素，既可以作为队列也可以作为栈使用。
typedef struct DequeNode {
  int data;
  struct DequeNode* next;
  struct DequeNode* prev;
} DequeNode;

typedef struct Deque {
  DequeNode* front;
  DequeNode* rear;
} Deque;

// 初始化双端队列
void initializeDeque(Deque* dq) {
  dq->front = dq->rear = NULL;
}

// 在前端插入
void insertFront(Deque* dq, int data) {
  DequeNode* newNode = (DequeNode*)malloc(sizeof(DequeNode));
  if (!newNode) {
      printf("内存分配失败\n");
      exit(1);
  }
  newNode->data = data;
  newNode->prev = NULL;
  newNode->next = dq->front;
  if (dq->front != NULL)
      dq->front->prev = newNode;
  dq->front = newNode;
  if (dq->rear == NULL)
      dq->rear = newNode;
  printf("在前端插入: %d\n", data);
}

// 在后端插入
void insertRear(Deque* dq, int data) {
  DequeNode* newNode = (DequeNode*)malloc(sizeof(DequeNode));
  if (!newNode) {
      printf("内存分配失败\n");
      exit(1);
  }
  newNode->data = data;
  newNode->next = NULL;
  newNode->prev = dq->rear;
  if (dq->rear != NULL)
      dq->rear->next = newNode;
  dq->rear = newNode;
  if (dq->front == NULL)
      dq->front = newNode;
  printf("在后端插入: %d\n", data);
}

// 从前端删除
int deleteFront(Deque* dq) {
  if (dq->front == NULL) {
      printf("双端队列为空，无法删除前端元素\n");
      exit(1);
  }
  DequeNode* temp = dq->front;
  int data = temp->data;
  dq->front = dq->front->next;
  if (dq->front != NULL)
      dq->front->prev = NULL;
  else
      dq->rear = NULL;
  free(temp);
  printf("删除前端元素: %d\n", data);
  return data;
}

// 从后端删除
int deleteRear(Deque* dq) {
  if (dq->rear == NULL) {
      printf("双端队列为空，无法删除后端元素\n");
      exit(1);
  }
  DequeNode* temp = dq->rear;
  int data = temp->data;
  dq->rear = dq->rear->prev;
  if (dq->rear != NULL)
      dq->rear->next = NULL;
  else
      dq->front = NULL;
  free(temp);
  printf("删除后端元素: %d\n", data);
  return data;
}
  1. 优先级队列（Priority Queue）：每个元素都有一个优先级，出队时优先级高的元素先被移出，常通过堆实现。

队列的应用场景

  1. 任务调度：操作系统和各种应用程序中使用队列管理待处理的任务或请求。

  2. 缓冲区管理：在生产者-消费者问题中使用队列作为缓冲区，例如打印任务队列、网络数据缓冲等。

  3. 广度优先搜索（BFS）：图或树的广度优先遍历使用队列来管理要访问的节点。

  4. 网络数据包处理：网络路由器和交换机使用队列管理进入的和离开的数据包。

  5. 实时系统：在实时系统中，队列用于管理事件或中断请求，确保按顺序处理。

队列的优缺点

优点

  1. 有序性：按照先进先出的顺序处理元素，适合需要顺序处理的应用场景。

  2. 动态大小：使用链表实现的队列可以根据需要动态调整大小，避免固定大小的限制。

  3. 高效的插入和删除：入队和出队操作在链表实现中具有常数时间复杂度。

缺点

  1. 访问限制：只能访问队头和队尾元素，无法随机访问队列中的其他元素。

  2. 额外的内存开销：每个节点需要额外存储指针，增加了内存消耗。

  3. 缓存局部性差：节点在内存中不连续，可能导致缓存命中率降低，影响性能。


http://www.kler.cn/a/354242.html

相关文章：

  • 网络安全概论——身份认证
  • 【Qt】显示类控件：QLabel、QLCDNumber、QProgressBar、QCalendarWidget
  • 【085】基于51单片机PID直流电机控制系统【Proteus仿真+Keil程序+报告+原理图】
  • Android Studio AI助手---Gemini
  • Chapter 19 Layout and Packaging
  • (OCPP服务器)SteVe编译搭建全过程
  • Springboot中基于 IP 地址的请求速率限制拦截器
  • Java 创建图形用户界面（GUI）组件详解之JFrame、JTextField、JTextArea、JPasswordField、JScrollPane、JLabel
  • docker安装kafka并使用SASL 进行身份验证
  • 无人机组装、维护、飞行技术全能培训详解
  • WebGl 使用缓冲区对象绘制多个点
  • 建造者模式（C++）
  • MySQL日期类型选择建议
  • FPGA学习-将modelsim中的波形数据保存到TXT文件方便MATLAB画图分析
  • 023 elasticsearch查询数据 高亮 分页 中文分词器 field的数据类型
  • 【布隆过滤器】
  • 在生产制造领域，可视化大屏的作用可以说无可替代。
  • 用Java爬虫API，轻松获取taobao商品SKU信息
  • C++_Stack和Queue的使用及其模拟实现
  • vue-vben-admin 首页加载慢优化 升级vite2到vite3
  • Qt-系统处理鼠标相关事件(57)
  • 阿里巴巴系列数据库
  • Halcon 使用二维像素分类对图像进行分割
  • Linux期末考试简答题题库
  • Ajax：原生ajax、使用FormData的细节问题，数据的载体
  • C#Process进程的使用，以及对ProcessInfo中所有的参数详细记录