C语言设计前中后队列实例代码

C语言设计前中后队列实例代码攻略

在本篇文章中，我们将学习如何在C语言中设计前、中、后队列，并提供相应的示例代码。下面将分别对前、中、后队列进行介绍和说明。

前队列

前队列，也称为顺序队列。它是一种数据结构，它具有先进先出（First in First Out，简称FIFO）的特点，是一种简单但基本的数据结构，常用在队列缓存、消息队列、web服务器等领域。下面是前队列的基本操作：

初始化队列

#define MAXSIZE 50 // 定义队列的最大长度
typedef struct {
    int data[MAXSIZE]; // 存放队列元素
    int front; // 队首指针
    int rear; // 队尾指针
} SqQueue;

void initQueue(SqQueue *q) { // 初始化队列
    q->front = q->rear = 0; // 初始化队首和队尾指针
}

判断队列是否为空

int isEmpty(SqQueue q) { // 判断队列是否为空
    if (q.front == q.rear) { // 如果队首和队尾相等，即为一个空队列
        return 1; // 返回真
    } else {
        return 0; // 返回假
    }
}

入队操作

int enQueue(SqQueue *q, int e) { // 入队操作
    if ((q->rear + 1) % MAXSIZE == q->front) { // 队列已满，无法入队
        return 0;
    }
    q->data[q->rear] = e; // 将元素e插入队尾位置
    q->rear = (q->rear + 1) % MAXSIZE; // 队尾指针向后移动一位，取模运算是为了防止数组越界
    return 1;
}

出队操作

int deQueue(SqQueue *q, int *e) { // 出队操作
    if (isEmpty(*q)) { // 队列为空，无法出队
        return 0;
    }
    *e = q->data[q->front]; // 队首元素出队
    q->front = (q->front + 1) % MAXSIZE; // 队首指针向后移动一位，取模运算是为了防止数组越界
    return 1;
}

示例说明

下面是一个在前队列中入队5个元素，然后依次出队的操作：

int main() {
    int e; // 定义一个中间变量
    SqQueue q; // 定义一个队列
    initQueue(&q); // 初始化队列
    printf("队列是否为空：%d\n", isEmpty(q)); // 队列是否为空：1

    enQueue(&q, 1); // 入队操作
    enQueue(&q, 2);
    enQueue(&q, 3);
    enQueue(&q, 4);
    enQueue(&q, 5);

    printf("队列是否为空：%d\n", isEmpty(q)); // 队列是否为空：0

    while (!isEmpty(q)) { // 循环出队操作
        deQueue(&q, &e);
        printf("%d ", e);
    }

    return 0;
}

中队列

中队列的操作和前队列大部分相同，区别在于中队列在出队操作时，不是将队首元素出队，而是将队列中间位置的元素出队。由于中队列操作和前队列基本一致，这里我们不再赘述前队列中的操作。

出队操作

int deMidQueue(SqQueue *q, int *e) { // 出队操作
    if (isEmpty(*q)) { // 队列为空，无法出队
        return 0;
    }
    int mid = (q->front + q->rear - 1) / 2; // 中间位置的下标
    *e = q->data[mid]; // 中间位置元素出队
    for (int i = mid; i < q->rear - 1; i++) { // 将中间位置后面的元素依次向前移动一位
        q->data[i] = q->data[i+1];
    }
    q->rear--; // 将队尾指针向前移动一位
    return 1;
}

示例说明

下面是一个在中队列中入队5个元素，然后依次出队的操作：

int main() {
    int e; // 定义一个中间变量
    SqQueue q; // 定义一个队列
    initQueue(&q); // 初始化队列
    printf("队列是否为空：%d\n", isEmpty(q)); // 队列是否为空：1

    enQueue(&q, 1); // 入队操作
    enQueue(&q, 2);
    enQueue(&q, 3);
    enQueue(&q, 4);
    enQueue(&q, 5);

    printf("队列是否为空：%d\n", isEmpty(q)); // 队列是否为空：0

    while (!isEmpty(q)) { // 循环出队操作
        deMidQueue(&q, &e);
        printf("%d ", e);
    }

    return 0;
}

后队列

后队列，又称为链队列。在后队列链表中，队列的两端都定义在链表的两个头部，不仅需要维持队头指针，还要维护队尾指针。与前队列和中队列不同，后队列在出队操作时只是将队首元素出队，并且队列为空的判断也不同。下面是后队列的基本操作：

定义一个链表节点

typedef struct node {
    int data; // 存放元素值
    struct node *next; // 指向下一个节点
}QNode;

定义队列

typedef struct {
    QNode *front; // 队首指针
    QNode *rear; // 队尾指针
} LinkQueue;

void initQueue(LinkQueue *q) { // 初始化队列
    QNode *head = (QNode *)malloc(sizeof(QNode));
    head->next = NULL;
    q->front = q->rear = head;
}

判断队列是否为空

int isEmpty(LinkQueue q) { // 判断队列是否为空
    if (q.front == q.rear) { // 如果队首和队尾相等，即为一个空队列
        return 1; // 返回真
    } else {
        return 0; // 返回假
    }
}

入队操作

int enQueue(LinkQueue *q, int e) { // 入队操作
    QNode *p = (QNode *)malloc(sizeof(QNode)); // 创建新节点
    p->data = e; // 将元素插入节点中
    p->next = NULL; // 在链表末尾添加新节点
    q->rear->next = p; // 更新队尾指针
    q->rear = p;
    return 1;
}

出队操作

int deQueue(LinkQueue *q, int *e) { // 出队操作
    if (isEmpty(*q)) { // 队列为空，无法出队
        return 0;
    }
    QNode *p = q->front->next; // 获取队首节点
    *e = p->data; // 队首元素出队
    q->front->next = p->next; // 更新队首指针
    if (q->rear == p) q->rear = q->front; // 如果队首指针指向的是链表中的最后一个节点，则更新队尾指针
    free(p); // 释放空间
    return 1;
}

示例说明

下面是一个在后队列中入队5个元素，然后依次出队的操作：

int main() {
    int e; // 定义一个中间变量
    LinkQueue q; // 定义一个队列
    initQueue(&q); // 初始化队列
    printf("队列是否为空：%d\n", isEmpty(q)); // 队列是否为空：1

    enQueue(&q, 1); // 入队操作
    enQueue(&q, 2);
    enQueue(&q, 3);
    enQueue(&q, 4);
    enQueue(&q, 5);

    printf("队列是否为空：%d\n", isEmpty(q)); // 队列是否为空：0

    while (!isEmpty(q)) { // 循环出队操作
        deQueue(&q, &e);
        printf("%d ", e);
    }

    return 0;
}