c语言数据结构之队列

前言

        不同于栈，队列是一个先进先出的数据结构，规定数据节点从队列尾插入，从队列头取出，禁止对头尾两端以外的数据进行 *** 作。队列可以分为顺序队列和循环队列。

C语言数据结构之单链表

C语言数据结构之双向链表

c语言数据结构之栈

c语言数据结构之队列

1   顺序队列 1.1  队列结构

顺序队列并不是说内存地址连续的队列，它是通过链表的形式链接而成。Node结构体表示一个节点，包括数据域和指针域；Queue结构体定义front、near指针分别指向节点的头和尾。

typedef struct _NODE {
    int data;
    struct _NODE *next;
}Node,*Nodelist;

typedef struct _QUEUE {
    Node * front;    //队首指针
    Node * near;     //队尾指针
}Queue,*Queuep;

1.2  队列判空

队列需要有个判断是否为空的 *** 作，以便更好的进行入、出队列 *** 作。

front、near指向NULL为空队列。

int queue_empty(Queuep que)
{
    if(que->front == NULL){
        return 0;
    }
    return 1;
}

1.3  队列创建

很简单，将队列front、near指针初始化为NULL，然后函数返回一个创建的队列地址值即可。

Queuep queue_create()
{
    Queuep que = (Queuep )malloc(sizeof(Queue));
    if(que == NULL){
        printf("malloc error.\n");
        exit(-1);
    }
    que->front = NULL;
    que->near = NULL;

    return que;
}

1.4  入队列 *** 作

将新节点加入队列尾部中，需要注意以下几点：

①队列为空：将front和near指向新节点；

②队列非空：将队列尾节点的next指向新节点，然后队列尾指针near指向新节点。

void queue_push(Queuep que)
{
    int data = 0;
    Node *p = NULL;

    printf("please input Node data: ");
    scanf("%d",&data);
    p = add_node(data);

    if(queue_empty(que) == 0){
        que->front = que->near = p;
    }
    else{
        que->near->next = p;
        que->near = p;
    }
}

1.5  出队列 *** 作

从非空队列的头部取出数据，然后将front指向下个节点处，释放掉取消节点的内存空间。出队列时需要对队列进行判空 *** 作，空队列直接返回。

如果取出前只有一个数据节点了，取出后将front、near指向NULL表示队列为空了。

void queue_pop(Queuep que)
{
    Node *p = NULL;
    if(queue_empty(que) == 0){
        printf("queue is empty.\n");
        return ;
    }
    else{
        printf("pop queue data :%d\n",que->front->data);
        if(que->front == que->near){  
            p = que->front;
            free(p);
            que->front = NULL;
            que->near = NULL;
        }
        else{
            p = que->front;
            que->front = que->front->next;
            free(p);
        }
        printf("\n");
    }
}

1.6  示例程序

/****************************************
Fuction:C语言实现顺序队列
Time:9/25/2022
Author:Qurry
****************************************/


#include 
#include 

typedef struct _NODE {
    int data;
    struct _NODE *next;
}Node,*Nodelist;

typedef struct _QUEUE {
    Node * front;    //队首指针
    Node * near;     //队尾指针
}Queue,*Queuep;

/******     创建队列       ******/
Queuep queue_create()
{
    Queuep que = (Queuep)malloc(sizeof(Queue));
    if(que == NULL){
        printf("malloc error.\n");
        exit(-1);
    }
    que->front = NULL;
    que->near = NULL;

    return que;
}

/******     添加新节点      ******/
Nodelist add_node(int data)
{
    Node * p = (Nodelist)malloc(sizeof(Node));
    if(p == NULL){
        printf("malloc error.\n");
        exit(-1);
    }  
    p->data = data;
    p->next = NULL;

    return p;  
}

/*******    判断队列是否为空    ********
 * return :0   空
 *         1   非空
 * **********************************/
int queue_empty(Queuep que)
{
    if(que->front == NULL){
        return 0;
    }
    return 1;
}

/*******    入队列      *********/
void queue_push(Queuep que)
{
    int data = 0;
    Node *p = NULL;

    printf("please input Node data: ");
    scanf("%d",&data);
    p = add_node(data);

    if(queue_empty(que) == 0){
        que->front = que->near = p;
    }
    else{
        que->near->next = p;
        que->near = p;
    }
}

/*******    出队列      **********/
void queue_pop(Queuep que)
{
    Node *p = NULL;
    if(queue_empty(que) == 0){
        printf("queue is empty.\n");
        return ;
    }
    else{
        printf("pop queue data :%d\n",que->front->data);
        if(que->front == que->near){  
            p = que->front;
            free(p);
            que->front = NULL;
            que->near = NULL;
        }
        else{
            p = que->front;
            que->front = que->front->next;
            free(p);
        }
        printf("\n");
    }
}

/********   遍历打印队列    ***********/
void queue_print(Queuep que)
{
    Node *p = NULL;

    if(queue_empty(que) == 0){
        printf("queue is empty.\n");
        return ;
    }
    else{
        p = que->front;
        printf("queue data,front to near: ");
        while(1){
            printf("%d\t",p->data);
            if(p->next == NULL){
                break;
            }
            p = p->next;
        }
        printf("\n");
    }
}

/***********    选择菜单     **************/
int menu_select()
{
    int mode;
    printf("1:入队列    2:出队列    3:打印队列数据    0:退出\n");
    printf("Please input mode : ");
    scanf("%d",&mode);
    return mode;
}

/************    退出释放内存   ************/
void free_node(Queuep que)
{
    Node *p = NULL,*q = NULL;

    if(queue_empty(que) == 0){
        printf("queue is empty.\n");
        return ;
    }
    else{
        p = que->front;
        q = p;
        while(1){
            if(p->next == NULL){
                free(p);
                break;                
            }
            else{
                p = p->next;
                free(q);
                q = p;
            }
        }
    }
    printf("Bye bye.\n");
}

void main()
{
    int mode = 0;
    Queue *que = queue_create();

    while(1){
        mode = menu_select();
        switch (mode)
        {
        case 0:
            free_node(que);
            return ;
        
        case 1:
            queue_push(que);
            break;

        case 2:
            queue_pop(que);
            break;

        case 3:
            queue_print(que);
            break;

        default:
            printf("input num error!\n");
            break;
        }
    }
}

1.7  测试结果

对创建、出、入队列 *** 作的测试。