队列-JZTXT

1、定义：先进先出的线性表，就像排队，它只允许在队列一端插入元素，在另一端删除元素（插入一端队尾，删除一端队头）

2、典型例子：作业排队

3、基本功能

　　1、宏定义结构体定义

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

#define ERROR 0;
#define OK 1;

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

typedef struct pointer
{
    QNode *front;//队首指针，不存放队列元素
    QNode *rear;//队尾指针，存放队尾数据元素
}Qpointer;//就只是指针

　　2、初始化

// 队列的初始化
void Init_Q(Qpointer *Q)
{
    QNode * que = (QNode *)malloc(sizeof(QNode));//队首结点队尾结点指向同一个元素，元素就是那个结构体
    que ->next = NULL;
    Q->front = que;
    Q->rear = que;
}

　　3、判空

//判断队列是否为空
int isEmpty(Qpointer *Q)
{
    if(Q->front == Q->rear)//首尾元素相同就为空，不是环形的，不会插满的
    {
        return 1;
    }
    return 0;
}

　　4、插入数据元素

//插入数据元素，插入成功返回1，失败返回0
int PUsh_Q(Qpointer *Q,int e)
{
    QNode * que;
    que = (QNode*)malloc(sizeof(QNode));
    if(!que)
    {
        return 0;
    }
    que->data = e;
    que->next = NULL;
    Q->rear->next = que;//将节点插入队列尾（有头结点）
    Q->rear = que;//调整队尾指针（保持队尾指针在队尾）
    return 0;
}

　　5、删除数据元素

//删除数据元素，删除成功返回1，失败返回0
int Pop_Q(Qpointer *Q,int *e)
{
    QNode *que;
    if(isEmpty(Q))
    {
        return 0;
    }
    que = Q->front->next;//有头结点嘛
    *e = que->data;
    Q->front->next = que->next;

    if(Q->rear == que)//如果当前删除节点是最后一个人，就把队列设为空
    {
        Q->rear = Q->front;
    }
    free(que);
    return 1;
    
}

　　6、主函数

int main()
{
    Qpointer *Q;
    int x;
    Q = (Qpointer *)malloc(sizeof(Qpointer));
    Init_Q(Q);
    printf("please input positive integers:");
    scanf("%d",&x);
    while(x>0)
    {
        PUsh_Q(Q,x);
        scanf("%d",&x);
    }
    //
    QNode *p = Q->front->next;
    if(!p)
    {
        return 0;
    }
    printf("queue element:\n");
    while(p)
    {
        printf("%d ",p->data);
        p = p->next;
    }
    printf("\n");
    //
    printf("delete queue:\n");
    while(Pop_Q(Q,&x))
    {
        printf("%d ",x);
    }
    printf("\n");
    //
    p = Q->front;//指向头结点啊
    free(p);
    free(Q);

    return 0;
    
}