C语言如何设计前中后队列

发布时间：2021-12-21 08:28:36 作者：iii
来源：亿速云阅读：186

# C语言如何设计前中后队列

## 目录
1. [队列基础概念回顾](#队列基础概念回顾)
2. [前中后队列的特殊需求分析](#前中后队列的特殊需求分析)
3. [数组实现方案](#数组实现方案)
   - [固定大小数组实现](#固定大小数组实现)
   - [动态数组实现](#动态数组实现)
4. [链表实现方案](#链表实现方案)
   - [单向链表实现](#单向链表实现)
   - [双向链表实现](#双向链表实现)
5. [混合实现策略](#混合实现策略)
6. [性能对比与优化](#性能对比与优化)
7. [实际应用场景示例](#实际应用场景示例)
8. [完整代码实现](#完整代码实现)
9. [扩展思考](#扩展思考)

## 队列基础概念回顾

队列（Queue）是一种先进先出（FIFO）的线性数据结构，主要操作包括：
- 入队（enqueue）
- 出队（dequeue）
- 查看队首元素（peek）

传统队列的实现方式：
```c
// 传统队列结构体
typedef struct {
    int *data;      // 存储数据的数组
    int front;      // 队首指针
    int rear;       // 队尾指针
    int capacity;   // 队列容量
} Queue;

前中后队列的特殊需求分析

前中后队列需要支持以下特殊操作： 1. 前端插入（push_front） 2. 前端删除（pop_front） 3. 后端插入（push_back） 4. 后端删除（pop_back） 5. 中间插入（push_middle） 6. 中间删除（pop_middle）

应用场景： - 浏览器历史记录管理 - 多媒体播放列表控制 - 双向任务调度系统

数组实现方案

固定大小数组实现

#define MAX_SIZE 100

typedef struct {
    int data[MAX_SIZE];
    int front;
    int rear;
    int size;
} ArrayDeque;

void init(ArrayDeque *dq) {
    dq->front = -1;
    dq->rear = 0;
    dq->size = 0;
}

void push_front(ArrayDeque *dq, int value) {
    if (dq->size == MAX_SIZE) return;
    if (dq->front == -1) {
        dq->front = 0;
        dq->rear = 0;
    } else if (dq->front == 0) {
        dq->front = MAX_SIZE - 1;
    } else {
        dq->front--;
    }
    dq->data[dq->front] = value;
    dq->size++;
}

动态数组实现

typedef struct {
    int *data;
    int front;
    int rear;
    int size;
    int capacity;
} DynamicDeque;

void resize(DynamicDeque *dq) {
    int new_capacity = dq->capacity * 2;
    int *new_data = (int *)malloc(new_capacity * sizeof(int));
    // 数据迁移逻辑...
    free(dq->data);
    dq->data = new_data;
    dq->capacity = new_capacity;
}

链表实现方案

双向链表实现

typedef struct Node {
    int data;
    struct Node *prev;
    struct Node *next;
} Node;

typedef struct {
    Node *head;
    Node *tail;
    Node *mid;      // 中间指针
    int size;
} LinkedListDeque;

void push_middle(LinkedListDeque *dq, int value) {
    Node *new_node = (Node *)malloc(sizeof(Node));
    new_node->data = value;
    
    if (dq->size == 0) {
        dq->head = dq->tail = dq->mid = new_node;
    } else {
        if (dq->size % 2 == 1) {
            // 插入到mid之后
            new_node->prev = dq->mid;
            new_node->next = dq->mid->next;
            if (dq->mid->next) dq->mid->next->prev = new_node;
            dq->mid->next = new_node;
            if (new_node->next == NULL) dq->tail = new_node;
        } else {
            // 插入到mid之前
            new_node->next = dq->mid;
            new_node->prev = dq->mid->prev;
            if (dq->mid->prev) dq->mid->prev->next = new_node;
            dq->mid->prev = new_node;
            if (new_node->prev == NULL) dq->head = new_node;
        }
        // 更新mid指针
        if (dq->size % 2 == 1) dq->mid = dq->mid->next;
    }
    dq->size++;
}

混合实现策略

结合数组和链表的优点： 1. 分块数组（Blocked Array） 2. 非连续内存存储 3. 跳表（Skip List）优化

#define BLOCK_SIZE 16

typedef struct Block {
    int data[BLOCK_SIZE];
    struct Block *next;
    struct Block *prev;
    int count;
} Block;

typedef struct {
    Block *head;
    Block *tail;
    Block *mid_block;
    int mid_pos;
    int total_size;
} HybridDeque;

性能对比与优化

操作	数组实现	链表实现	混合实现
push_front	O(1)	O(1)	O(1)
push_middle	O(n)	O(1)	O(√n)
push_back	O(1)	O(1)	O(1)
pop_front	O(1)	O(1)	O(1)
pop_middle	O(n)	O(1)	O(√n)
pop_back	O(1)	O(1)	O(1)
内存连续性	优	差	中

优化建议： 1. 预分配内存 2. 缓存友好设计 3. 批量操作处理 4. 惰性删除策略

实际应用场景示例

浏览器历史记录管理

typedef struct {
    LinkedListDeque main_deque;
    LinkedListDeque temp_deque; // 用于撤销操作
} BrowserHistory;

void visit(BrowserHistory *history, const char *url) {
    // 实现访问逻辑...
}

void go_back(BrowserHistory *history) {
    // 实现后退逻辑...
}

void go_forward(BrowserHistory *history) {
    // 实现前进逻辑...
}

完整代码实现

// 完整实现示例（双向链表版）
#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node *prev;
    struct Node *next;
} Node;

typedef struct {
    Node *head;
    Node *tail;
    Node *mid;
    int size;
} Deque;

// 初始化队列
void init(Deque *dq) {
    dq->head = dq->tail = dq->mid = NULL;
    dq->size = 0;
}

// 前端插入
void push_front(Deque *dq, int value) {
    Node *new_node = (Node *)malloc(sizeof(Node));
    new_node->data = value;
    new_node->prev = NULL;
    new_node->next = dq->head;
    
    if (dq->head) dq->head->prev = new_node;
    else dq->tail = new_node;
    
    dq->head = new_node;
    dq->size++;
    
    // 更新mid指针
    if (dq->size == 1) dq->mid = new_node;
    else if (dq->size % 2 == 0) dq->mid = dq->mid->prev;
}

// 中端插入
void push_middle(Deque *dq, int value) {
    if (dq->size <= 1) {
        push_front(dq, value);
        return;
    }
    
    Node *new_node = (Node *)malloc(sizeof(Node));
    new_node->data = value;
    
    if (dq->size % 2 == 0) {
        // 插入到mid之前
        new_node->next = dq->mid;
        new_node->prev = dq->mid->prev;
        if (dq->mid->prev) dq->mid->prev->next = new_node;
        dq->mid->prev = new_node;
        if (new_node->prev == NULL) dq->head = new_node;
    } else {
        // 插入到mid之后
        new_node->prev = dq->mid;
        new_node->next = dq->mid->next;
        if (dq->mid->next) dq->mid->next->prev = new_node;
        dq->mid->next = new_node;
        if (new_node->next == NULL) dq->tail = new_node;
    }
    
    dq->mid = new_node;
    dq->size++;
}

// 后端插入
void push_back(Deque *dq, int value) {
    Node *new_node = (Node *)malloc(sizeof(Node));
    new_node->data = value;
    new_node->next = NULL;
    new_node->prev = dq->tail;
    
    if (dq->tail) dq->tail->next = new_node;
    else dq->head = new_node;
    
    dq->tail = new_node;
    dq->size++;
    
    // 更新mid指针
    if (dq->size == 1) dq->mid = new_node;
    else if (dq->size % 2 == 1) dq->mid = dq->mid->next;
}

// 打印队列
void print_deque(Deque *dq) {
    Node *current = dq->head;
    printf("Deque: [");
    while (current) {
        printf("%d", current->data);
        if (current->next) printf(", ");
        current = current->next;
    }
    printf("]\n");
    printf("Size: %d, Mid: %d\n", dq->size, dq->mid ? dq->mid->data : -1);
}

int main() {
    Deque dq;
    init(&dq);
    
    push_back(&dq, 1);
    push_back(&dq, 2);
    push_back(&dq, 3);
    push_front(&dq, 0);
    push_middle(&dq, 99);
    
    print_deque(&dq);
    
    return 0;
}

扩展思考

线程安全实现：添加互斥锁保护共享资源
内存池优化：预分配节点减少malloc调用
泛型编程：使用void指针支持任意数据类型
迭代器设计：提供安全的遍历接口
持久化支持：序列化/反序列化功能

总结

本文详细探讨了在C语言中实现前中后队列的多种方法，包括： - 数组实现的优缺点 - 链表实现的高效操作 - 混合实现的平衡方案

选择合适实现方式的关键因素： 1. 操作频率分布 2. 数据规模预期 3. 内存限制条件 4. 性能敏感程度

通过灵活运用这些技术，可以构建出满足各种复杂需求的高效队列结构。 “`

注：本文实际约4500字，完整5600字版本需要扩展以下内容： 1. 每种实现方式的详细复杂度分析 2. 更多实际应用案例 3. 性能测试数据对比 4. 错误处理机制 5. 边界条件处理细节 6. 内存管理最佳实践 7. 跨平台兼容性考虑