顺序队列的基本操作（入队出队遍历）及C/C++代码实现

创作时间:

作者:

@小白创作中心

顺序队列的基本操作（入队出队遍历）及C/C++代码实现

引用

来源

https://www.dotcpp.com/course/106

顺序队列是一种常见的数据结构，其基本操作包括入队、出队和遍历。本文将详细介绍这些操作的原理和C/C++代码实现。

1. 入队操作

在进行入队（push）操作时，首先需要判断队列是否为空。如果队列为空，需要将头指针和尾指针一同指向第一个结点；如果队列不为空，则只需要将尾结点向后移动。

代码实现如下：

//入队操作
void push(queue *q, int data){
    node *n = init_node();
    n->data = data;
    n->next = NULL;   //采用尾插入法
    if (empty(q)){
        q->front = n;
        q->rear = n;
    } else {
        q->rear->next = n;    //n成为当前尾结点的下一结点
        q->rear = n;  //让尾指针指向n
    }
}

2. 出队操作

出队（pop）操作需要在队列不为空的情况下进行。如果队列只有一个元素，需要将头尾指针制空并释放该结点；如果队列含有两个以上元素，则将队列的头指针指向下一个元素并释放当前元素。

代码实现如下：

//出队操作
void pop(queue *q){
    node *n = q->front;
    if (empty(q)){
        return;    //此时队列为空，直接返回函数结束
    }
    if (q->front == q->rear){
        q->front = NULL;  //只有一个元素时直接将两端指向制空即可
        q->rear = NULL;
        free(n);        //记得归还内存空间
    } else {
        q->front = q->front->next;
        free(n);
    }
}

3. 打印队列元素（遍历）

遍历队列元素需要在队列不为空的情况下，通过结点的next指针依次遍历并输出元素。

代码实现如下：

//打印队列元素
void print_queue(queue *q){
    node *n = init_node();
    n = q->front;
    if (empty(q)){
        return;    //此时队列为空，直接返回函数结束
    }
    while (n != NULL){
        printf("%d\t", n->data);
        n = n->next;
    }
    printf("\n");   //记得换行
}

此外，遍历操作还可以用于计算队列中元素的数量：

int calac(queue *q){
    node *n = init_node();
    n = q->front;
    int cnt = 0;    //计数器设计
    if (empty(q)){
        return 0;    //此时队列为空，直接返回函数结束
    }
    while (n != NULL){
        n = n->next;
        cnt++;
    }
    return cnt;
}

4. 代码实现

完整的代码实现如下：

#include <stdio.h>
#include <stdlib.h>

//结点定义
typedef struct node{
    int data;
    struct node *next;
}node;

//队列定义，队首指针和队尾指针
typedef struct queue{
    node *front;
    node *rear;
}queue;

//初始化结点
node *init_node(){
    node *n = (node*)malloc(sizeof(node));
    if (n == NULL){    //建立失败，退出
        exit(0);
    }
    return n;
}

//初始化队列
queue *init_queue(){
    queue *q = (queue*)malloc(sizeof(queue));
    if (q == NULL){    //建立失败，退出
        exit(0);
    }
    //头尾结点均赋值NULL
    q->front = NULL;
    q->rear = NULL;
    return q;
}

//队列判空
int empty(queue *q){
    if (q->front == NULL){
        return 1;   //1--表示真，说明队列非空
    } else {
        return 0;   //0--表示假，说明队列为空
    }
}

//入队操作
void push(queue *q, int data){
    node *n = init_node();
    n->data = data;
    n->next = NULL;   //采用尾插入法
    if (empty(q)){
        q->front = n;
        q->rear = n;
    } else {
        q->rear->next = n;    //n成为当前尾结点的下一结点
        q->rear = n;  //让尾指针指向n
    }
}

//出队操作
void pop(queue *q){
    node *n = q->front;
    if (empty(q)){
        return;    //此时队列为空，直接返回函数结束
    }
    if (q->front == q->rear){
        q->front = NULL;  //只有一个元素时直接将两端指向制空即可
        q->rear = NULL;
        free(n);        //记得归还内存空间
    } else {
        q->front = q->front->next;
        free(n);
    }
}

//打印队列元素
void print_queue(queue *q){
    node *n = init_node();
    n = q->front;
    if (empty(q)){
        return;    //此时队列为空，直接返回函数结束
    }
    while (n != NULL){
        printf("%d\t", n->data);
        n = n->next;
    }
    printf("\n");   //记得换行
}

//主函数调用，这里只是简单介绍用法
int main(){
    queue *q = init_queue();
    /////////////入队操作/////////////////
    printf("入队\n");
    for (int i = 1; i <= 5; i++){
        push(q, i);
        print_queue(q);
    }
    /////////////出队操作/////////////////
    printf("出队\n");
    for (int i = 1; i <= 5; i++){
        pop(q);
        print_queue(q);
    }
    return 0;
}