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

队列的详细实现与扩展

队列的基本概念

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

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

循环队列的完整实现

结构定义与宏定义

#define MAXQSIZE 100  // 队列最大长度
typedef int ElemType; // 元素类型可根据需要修改

typedef struct {
    ElemType data[MAXQSIZE];
    int front;  // 队头指针，指向队首元素
    int rear;   // 队尾指针，指向队尾元素的下一个位置
} CircularQueue;

基本操作实现

1. ​​初始化队列​​

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

1. ​​入队操作​​

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;
}

1. ​​出队操作​​

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;
}

1. ​​获取队首元素（不删除）​​

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

1. ​​队列判空​​

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

1. ​​队列判满​​

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

1. ​​获取队列长度​​

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

循环队列的变体实现

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

// 添加一个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;

基本操作实现

1. ​​初始化链队​​

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

1. ​​销毁链队​​

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

1. ​​入队操作​​

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;
}

1. ​​出队操作​​

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;
}

1. ​​获取队首元素（不删除）​​

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

1. ​​队列判空​​

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

1. ​​获取队列长度​​

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

队列的应用场景

1. ​​操作系统中的进程调度​​

   • 使用队列管理就绪进程，按照FIFO原则分配CPU时间

2. ​​打印任务管理​​

   • 多个打印任务按提交顺序排队等待打印

3. ​​广度优先搜索（BFS）​​

   • 用于图的遍历和最短路径查找

4. ​​消息队列​​

   • 在分布式系统中用于进程间通信

5. ​​缓冲区管理​​

   • 如键盘缓冲区、网络数据包缓冲区等

性能分析与比较

​​选择建议​​：

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

扩展：双端队列（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;
}

最佳实践与注意事项

1. ​​循环队列的边界条件处理​​

   • 特别注意取模运算的使用
   • 确保判空和判满条件正确

2. ​​内存管理​​

   • 链队要及时释放出队结点的内存
   • 使用完毕后要销毁整个链队

3. ​​线程安全​​

   • 在多线程环境中使用队列时需要添加同步机制

4. ​​错误处理​​

   • 对可能失败的操作（如内存分配）进行适当处理

5. ​​性能优化​​

   • 对于频繁操作的队列，可以考虑批量操作
   • 根据实际场景选择合适的队列实现方式