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

数据结构与算法：队列的表示和操作的实现

news 2025/8/1 5:20:09

队列的详细实现与扩展

队列的基本概念

队列是一种先进先出（FIFO）的线性数据结构，具有以下特点：

只允许在表的一端（队尾/rear）进行插入操作（入队/Enqueue）
只允许在另一端（队首/front）进行删除操作（出队/Dequeue）
基本操作包括初始化、入队、出队、判空、判满、获取队首元素等

循环队列的完整实现

结构定义与宏定义

#define MAXQSIZE 100  // 队列最大长度
typedef int ElemType; // 元素类型可根据需要修改typedef struct {ElemType data[MAXQSIZE];int front;  // 队头指针，指向队首元素int rear;   // 队尾指针，指向队尾元素的下一个位置
} CircularQueue;

基本操作实现

初始化队列

void InitQueue(CircularQueue *Q) {Q->front = Q->rear = 0;
}

入队操作

bool EnQueue(CircularQueue *Q, ElemType e) {if ((Q->rear + 1) % MAXQSIZE == Q->front) // 队列满return false;Q->data[Q->rear] = e;Q->rear = (Q->rear + 1) % MAXQSIZE;return true;
}

出队操作

bool DeQueue(CircularQueue *Q, ElemType *e) {if (Q->front == Q->rear) // 队列空return false;*e = Q->data[Q->front];Q->front = (Q->front + 1) % MAXQSIZE;return true;
}

获取队首元素（不删除）

bool GetHead(CircularQueue Q, ElemType *e) {if (Q.front == Q.rear) // 队列空return false;*e = Q.data[Q.front];return true;
}

队列判空

bool QueueEmpty(CircularQueue Q) {return Q.front == Q.rear;
}

队列判满

bool QueueFull(CircularQueue Q) {return (Q.rear + 1) % MAXQSIZE == Q.front;
}

获取队列长度

int QueueLength(CircularQueue Q) {return (Q.rear - Q.front + MAXQSIZE) % MAXQSIZE;
}

循环队列的变体实现

不牺牲存储空间的实现方法

// 添加一个size成员记录当前队列长度
typedef struct {ElemType data[MAXQSIZE];int front;int rear;int size; // 当前队列元素个数
} CircularQueueEx;bool EnQueueEx(CircularQueueEx *Q, ElemType e) {if (Q->size == MAXQSIZE) // 队列满return false;Q->data[Q->rear] = e;Q->rear = (Q->rear + 1) % MAXQSIZE;Q->size++;return true;
}bool DeQueueEx(CircularQueueEx *Q, ElemType *e) {if (Q->size == 0) // 队列空return false;*e = Q->data[Q->front];Q->front = (Q->front + 1) % MAXQSIZE;Q->size--;return true;
}

链式队列的完整实现

结构定义

typedef struct QNode {ElemType data;struct QNode *next;
} QNode;typedef struct {QNode *front;  // 队头指针，指向头结点QNode *rear;   // 队尾指针，指向最后一个结点
} LinkQueue;

基本操作实现

初始化链队

void InitQueue(LinkQueue *Q) {Q->front = Q->rear = (QNode *)malloc(sizeof(QNode));if (!Q->front) exit(OVERFLOW); // 内存分配失败Q->front->next = NULL;
}

销毁链队

void DestroyQueue(LinkQueue *Q) {while (Q->front) {Q->rear = Q->front->next;free(Q->front);Q->front = Q->rear;}
}

入队操作

bool EnQueue(LinkQueue *Q, ElemType e) {QNode *p = (QNode *)malloc(sizeof(QNode));if (!p) return false; // 内存分配失败p->data = e;p->next = NULL;Q->rear->next = p;Q->rear = p;return true;
}

出队操作

bool DeQueue(LinkQueue *Q, ElemType *e) {if (Q->front == Q->rear) // 队列空return false;QNode *p = Q->front->next;*e = p->data;Q->front->next = p->next;if (Q->rear == p) // 若删除的是最后一个结点Q->rear = Q->front;free(p);return true;
}

获取队首元素（不删除）

bool GetHead(LinkQueue Q, ElemType *e) {if (Q.front == Q.rear) // 队列空return false;*e = Q.front->next->data;return true;
}

队列判空

bool QueueEmpty(LinkQueue Q) {return Q.front == Q.rear;
}

获取队列长度

int QueueLength(LinkQueue Q) {int length = 0;QNode *p = Q.front;while (p != Q.rear) {length++;p = p->next;}return length;
}

队列的应用场景

操作系统中的进程调度
- 使用队列管理就绪进程，按照FIFO原则分配CPU时间
打印任务管理
- 多个打印任务按提交顺序排队等待打印
广度优先搜索（BFS）
- 用于图的遍历和最短路径查找
消息队列
- 在分布式系统中用于进程间通信
缓冲区管理
- 如键盘缓冲区、网络数据包缓冲区等

性能分析与比较

操作	循环队列时间复杂度	链队时间复杂度
初始化	O(1)	O(1)
入队	O(1)	O(1)
出队	O(1)	O(1)
获取队首元素	O(1)	O(1)
判空	O(1)	O(1)
判满	O(1)	不需要
空间利用率	固定大小	动态分配

选择建议：

当元素数量可预估且固定时，使用循环队列更高效
当元素数量不可预知或变化较大时，使用链队更灵活
循环队列更适合嵌入式系统等内存受限环境
链队更适合需要频繁动态增长和收缩的场景

扩展：双端队列（Deque）

双端队列是一种允许在两端进行插入和删除操作的队列，结合了队列和栈的特性。

typedef struct {ElemType data[MAXQSIZE];int front;  // 指向队首元素int rear;   // 指向队尾元素的下一个位置
} Deque;// 前端插入
bool PushFront(Deque *D, ElemType e) {if ((D->front - 1 + MAXQSIZE) % MAXQSIZE == D->rear)return false; // 队列满D->front = (D->front - 1 + MAXQSIZE) % MAXQSIZE;D->data[D->front] = e;return true;
}// 后端插入
bool PushRear(Deque *D, ElemType e) {return EnQueue(D, e); // 同普通队列的入队
}// 前端删除
bool PopFront(Deque *D, ElemType *e) {return DeQueue(D, e); // 同普通队列的出队
}// 后端删除
bool PopRear(Deque *D, ElemType *e) {if (D->front == D->rear)return false; // 队列空D->rear = (D->rear - 1 + MAXQSIZE) % MAXQSIZE;*e = D->data[D->rear];return true;
}