队列（数组实现和链表实现）

1.概念：具有一定操作约束的线性表
2.特点：（1）只能在一端插入（入队），另一端删除（出队）。
（2）.先进先出。
3.存储实现方式：数组、链表。
4.基本操作：
1.数组实现（循环数组）：
注意：（1）、普通的顺序存储的数组用来实现队列时，存在一个问题：当rear（记录队尾的变量）到达maxsize-1时，不能确定队列是否满，因为前面可能删除了一些元素（front（记录对头的变量）可能已经增加了），所以用循环数组来实现队列的操作
（2）、对于循环数组，无论是空队列还是满队列，front与rear都相等，所以，引入了一个变量size来记录队列中元素的个数。
基本操作：
（1）、队列结构体定义：

typedef struct Queue
{
    int data[maxsize];
    int front;
    int rear;
    int size;
}Q;

（2）、建立空队列：

Q *makeEmpty(Q *q)//建立空队列 
{
    q->size = 0;
    q->front = -1;
    q->rear = -1;
    return q;
}

（3）、判断队列是否空，是否满：

int Isempty(Q *q)//判断队列是否为空 
{
    return (q->size) == 0;
}
int Isfull(Q *q)//判断队列是否满 
{
    return q->size == maxsize;
} 

（4）、入队列和出队列：

void AddQ(Q *q,int num)//入队列 
{
    if(Isfull(q))//判断队列是否满 
    {
        printf("队列满！\n");
        return ;
    }
    else
    (q->size)++;
    q->data[(++(q->rear)%maxsize)] = num;
    //先将rear+1，再对maxsize取余得到下标 
    return ;
}
int deleteQ(Q *q)//出队列
{
    if(Isempty(q))
    {
        printf("队列空！\n");
        return 0;
    }
    else
    {
        (q->size)--;
        q->front = (++(q->front)%maxsize);
        return q->data[q->front];//front+1为要删除的元素的下标 
    }
}

（5）、数组实现队列的完整代码：

#include <stdio.h>
#define maxsize 10
#include <stdlib.h>
typedef struct Queue
{
    int data[maxsize];
    int front;
    int rear;
    int size;
}Q;
int Isempty(Q *q)//判断队列是否为空 
{
    return (q->size) == 0;
}
int Isfull(Q *q)//判断队列是否满 
{
    return q->size == maxsize;
 } 
Q *makeEmpty(Q *q)//建立空队列 
{
    q->size = 0;
    q->front = -1;
    q->rear = -1;
    return q;
}
void AddQ(Q *q,int num)//入队列 
{
    if(Isfull(q))//判断队列是否满 
    {
        printf("队列满！\n");
        return ;
    }
    else
    (q->size)++;
    q->data[(++(q->rear)%maxsize)] = num;//先将rear+1，再对maxsize取余得到下标 
    return ;
}
int deleteQ(Q *q)
{
    if(Isempty(q))
    {
        printf("队列空！\n");
        return 0;
    }
    else
    {
        (q->size)--;
        q->front = (++(q->front)%maxsize);
        return q->data[q->front];//front+1为要删除的元素的下标 
    }
}
int main()
{
    Q *q;
    q = (Q*)malloc(sizeof(Q));//动态申请内存 
    q = makeEmpty(q);
    int n = Isempty(q);
    printf("x%d\t",n);
    for(int i = 0;i<2;i++)
    {
        AddQ(q,i);
    }
    n = Isempty(q);
    printf("x%d\t",n);  
    for(int i = 0;i < 2;i++)
    {
        int temp = deleteQ(q);
        printf("%d\t",temp);
    }
    free(q);
    return 0;   
 } 

输出结果：

2.链表实现队列：
注意：由于链表的尾不能进行删除操作，所以front指向链表的头，rear指向链表的尾。
（1）、 结构体的定义：

typedef struct Node
{
    int data;
    struct Node *next;
}Qnode;
typedef struct 
{
    Qnode *front;//指向链表头结点 
    Qnode *rear;//指向链表尾结点 
}Q;

（2）、核心代码：增添和删除结点信息

void AddQ(Q *q,int num)
//增添结点 
{
    Qnode *p = (Qnode *)malloc(sizeof(Qnode));
    p->data = num;
    Qnode *temp = q->rear;
    if(temp != NULL)//判断队列是否为空 
    {
        temp->next = p;
        q->rear = p;
        p->next = NULL;
    }
    else
    {
        q->front =  p;//若队列为空，将首尾均指向新增结点 
        q->rear = p;
        p->next = NULL;
    }
} 

int deleteQ(Q *q)
//删除结点并返回删除结点的值 
{
    Qnode *temp;
    int term;
    if(q->front == NULL)
    {
        printf("队列空！\n");
        return 0;
    }

    temp = q->front;//保留头结点 
    if(q->front == q->rear)//若队列只有一个元素 
    q->front = q->rear = NULL;//将头结点尾结点都设为空 
    else
    q->front = q->front->next;//否则改变头结点
    term = temp->data; 
    free(temp);//释放头结点 
    return term;//返回头结点的值 
}

（3）、完整代码：

#include <stdio.h>
#include <stdlib.h>
typedef struct Node
{
    int data;
    struct Node *next;
}Qnode;
typedef struct 
{
    Qnode *front;//指向链表头结点 
    Qnode *rear;//指向链表尾结点 
}Q;

int deleteQ(Q *q)//删除结点并返回删除结点的值 
{
    Qnode *temp;
    int term;
    if(q->front == NULL)
    {
        printf("队列空！\n");
        return 0;
    }

    temp = q->front;//保留头结点 
    if(q->front == q->rear)//若队列只有一个元素 
    q->front = q->rear = NULL;//将头结点尾结点都设为空 
    else
    q->front = q->front->next;//否则改变头结点
    term = temp->data; 
    free(temp);//释放头结点 
    return term;//返回头结点的值 
}

void AddQ(Q *q,int num)//增添结点 
{
    Qnode *p = (Qnode *)malloc(sizeof(Qnode));
    p->data = num;
    Qnode *temp = q->rear;
    if(temp != NULL)//判断队列是否为空 
    {
        temp->next = p;
        q->rear = p;
        p->next = NULL;
    }
    else
    {
        q->front =  p;//若队列为空，将首尾均指向新增结点 
        q->rear = p;
        p->next = NULL;
    }
} 
int main()
{
    Q *q =(Q *) malloc(sizeof(Q));
    q->front = q->rear = NULL; 
    for(int i = 0;i < 2;i++)
    {
        AddQ(q,i);
    }
    for(int i = 0;i<2;i++)
    {
        int n = deleteQ(q);
        printf("%d\t",n);
    }
    free(q);
    return 0;
}

运行结果：