队列的用法详解

队列是一种常用的数据结构，具有先进先出（FIFO, First-In-First-Out）的特点。通常用来管理需要按顺序处理的任务，例如打印队列、任务调度、资源分配等。下面详细介绍队列的基本概念、常用操作、类型及其在C语言中的实现。

队列的基本概念

在队列中：

• 入队 (enqueue)：将元素添加到队列的尾部。
• 出队 (dequeue)：从队列的头部移除元素。
• 队头 (front)：指向队列第一个元素的指针或索引。
• 队尾 (rear)：指向队列最后一个元素的指针或索引。

队列的常见类型

1. 普通队列

   • 先进先出（FIFO）顺序，元素只能从尾部入队，从头部出队。

2. 循环队列

   • 队列空间循环利用，队尾达到数组末尾时会循环至队列头部。

3. 双端队列 (Deque)

   • 允许在两端进行入队和出队操作。

4. 优先队列

   • 元素带有优先级，出队时优先级高的元素先出队，而不是按入队顺序出队。

队列的常用操作

以下是队列的基本操作及其描述：

• 初始化队列：创建一个空队列。
• 判断队列是否为空：检查队列是否有元素。
• 判断队列是否满（对于数组实现的固定大小队列）。
• 入队：将元素添加到队尾。
• 出队：移除队头的元素。
• 获取队头元素：查看队头元素但不移除它。
• 获取队列长度：返回队列中的元素个数。

队列的实现方法

1. 数组实现普通队列

普通队列可以用固定大小的数组实现，但缺点是数组空间不能重复利用。每次出队，队列头指针向后移动一位，可能导致尾部的空闲空间无法使用。

#include <stdio.h>
#include <stdlib.h>
#define MAX 5

typedef struct Queue {
    int data[MAX];
    int front;  // 队头索引
    int rear;   // 队尾索引
} Queue;

// 初始化队列
Queue* initializeQueue() {
    Queue* queue = (Queue*)malloc(sizeof(Queue));
    queue->front = -1;
    queue->rear = -1;
    return queue;
}

// 判断队列是否为空
int isEmpty(Queue* queue) {
    return queue->front == -1;
}

// 判断队列是否满
int isFull(Queue* queue) {
    return queue->rear == MAX - 1;
}

// 入队
void enqueue(Queue* queue, int value) {
    if (isFull(queue)) {
        printf("队列已满\n");
        return;
    }
    if (isEmpty(queue)) {
        queue->front = 0;
    }
    queue->data[++queue->rear] = value;
    printf("入队：%d\n", value);
}

// 出队
int dequeue(Queue* queue) {
    if (isEmpty(queue)) {
        printf("队列为空\n");
        return -1;
    }
    int value = queue->data[queue->front];
    if (queue->front == queue->rear) {
        // 队列变空
        queue->front = queue->rear = -1;
    } else {
        queue->front++;
    }
    printf("出队：%d\n", value);
    return value;
}

// 获取队头元素
int peekFront(Queue* queue) {
    if (isEmpty(queue)) {
        printf("队列为空\n");
        return -1;
    }
    return queue->data[queue->front];
}

2. 循环队列

循环队列利用“环形”数组解决了普通队列不能重复利用空间的问题。队列的尾部超过数组末尾时，会绕到数组开头继续填充。

• 队满判断条件：(rear + 1) % MAX == front
• 队空判断条件：front == -1

  #define MAX 5
  
  typedef struct CircularQueue {
      int data[MAX];
      int front;
      int rear;
  } CircularQueue;
  
  // 初始化循环队列
  CircularQueue* initializeCircularQueue() {
      CircularQueue* queue = (CircularQueue*)malloc(sizeof(CircularQueue));
      queue->front = -1;
      queue->rear = -1;
      return queue;
  }
  
  // 判断队列是否为空
  int isCircularEmpty(CircularQueue* queue) {
      return queue->front == -1;
  }
  
  // 判断队列是否满
  int isCircularFull(CircularQueue* queue) {
      return (queue->rear + 1) % MAX == queue->front;
  }
  
  // 入队
  void enqueueCircular(CircularQueue* queue, int value) {
      if (isCircularFull(queue)) {
          printf("循环队列已满\n");
          return;
      }
      if (isCircularEmpty(queue)) {
          queue->front = 0;
      }
      queue->rear = (queue->rear + 1) % MAX;
      queue->data[queue->rear] = value;
      printf("循环队列入队：%d\n", value);
  }
  
  // 出队
  int dequeueCircular(CircularQueue* queue) {
      if (isCircularEmpty(queue)) {
          printf("循环队列为空\n");
          return -1;
      }
      int value = queue->data[queue->front];
      if (queue->front == queue->rear) {
          // 队列变空
          queue->front = queue->rear = -1;
      } else {
          queue->front = (queue->front + 1) % MAX;
      }
      printf("循环队列出队：%d\n", value);
      return value;
  }
  
  // 获取队头元素
  int peekCircularFront(CircularQueue* queue) {
      if (isCircularEmpty(queue)) {
          printf("循环队列为空\n");
          return -1;
      }
      return queue->data[queue->front];
  }
  

  3. 链表实现队列

  链表实现的队列不受固定大小限制，动态内存分配适用于队列大小不固定的情况。

  typedef struct Node {
      int data;
      struct Node* next;
  } Node;
  
  typedef struct LinkedQueue {
      Node* front;
      Node* rear;
  } LinkedQueue;
  
  // 初始化链表队列
  LinkedQueue* initializeLinkedQueue() {
      LinkedQueue* queue = (LinkedQueue*)malloc(sizeof(LinkedQueue));
      queue->front = queue->rear = NULL;
      return queue;
  }
  
  // 判断队列是否为空
  int isLinkedQueueEmpty(LinkedQueue* queue) {
      return queue->front == NULL;
  }
  
  // 入队
  void enqueueLinked(LinkedQueue* queue, int value) {
      Node* newNode = (Node*)malloc(sizeof(Node));
      newNode->data = value;
      newNode->next = NULL;
      if (isLinkedQueueEmpty(queue)) {
          queue->front = queue->rear = newNode;
      } else {
          queue->rear->next = newNode;
          queue->rear = newNode;
      }
      printf("链表队列入队：%d\n", value);
  }
  
  // 出队
  int dequeueLinked(LinkedQueue* queue) {
      if (isLinkedQueueEmpty(queue)) {
          printf("链表队列为空\n");
          return -1;
      }
      Node* temp = queue->front;
      int value = temp->data;
      queue->front = queue->front->next;
      if (queue->front == NULL) {
          queue->rear = NULL;
      }
      free(temp);
      printf("链表队列出队：%d\n", value);
      return value;
  }
  
  // 获取队头元素
  int peekLinkedFront(LinkedQueue* queue) {
      if (isLinkedQueueEmpty(queue)) {
          printf("链表队列为空\n");
          return -1;
      }
      return queue->front->data;
  }
  

  队列的应用场景

• 操作系统的任务调度：使用队列管理任务，使其按顺序执行。
• 图的广度优先搜索 (BFS)：用队列记录访问节点顺序。
• 打印队列：将待打印的文件按请求顺序排入队列。
• 网络流量管理：数据包按到达顺序排入队列，依次处理。