1.队列概念和特点
队列是⼀种特殊的线性表，特殊之处就在于它只允许在表的前端进⾏删除操作，在表的后端进⾏ 插⼊操作。和栈⼀样，队列也是⼀种操作受到限制的线性表。进⾏插⼊操作的端称之为队尾，进⾏删除 操作的端称之为队头。队列中没有队列的时候，称之为空队列。队列的数据元素，⼜叫做队列元素。在 队列中插⼊⼀个队列元素称之为⼊队，在队列中删除⼀个队列元素，称之为出队。因为队列只允许在⼀ 端插⼊，在另⼀端删除，所以只有最早进⼊的队列元素才可以从队列中删除，故队列⼜称为先进先出线性表。
队列的表示和实现（存储结构）
链队列 ：采用链式存储结构的队列
顺序队列 ：采用顺序存储结构的队列
队列的操作包括初始化、销毁、入队、出队、获取队首元素、获取队尾元素以及检查队列是否为空等。
2.顺序队列
当我⽤⼀⽚连续的存储空间来存储队列中的数据元素的时候，这样的队列就称之为顺序队列。类似于顺序栈。⽤⼀维数组来存放顺序队列中的数据元素。队头设置在最近⼀个离开队列元素所占的位置。队尾设置在最近⼀个进⾏⼊队列的元素位置。那么队头和队尾随着插⼊和删除的变化⽽变化。当队列为空时，front = rear；队列中的元素个数可以由队头 - 队尾求得。
假溢出
但是，这个时候，会有⼀个问题。当我们的队尾指针指向size - 1 时，代表⻓度已满。但是根据队 列的规则，就实际情况来说，他还有空闲的空间。那么这个时候，我们就将其称之为假溢出。
为了解决假溢出的问题，就是将我们的顺序队列看成是⾸位相接的循环结构。⾸尾指示器不变， 这种队列就叫做，循环顺序队列。
也就是说，当我们的队尾元素达到数组的上限时，如果还有数据元素⼊队并且数组的第0个空间是 空闲时，队尾指示器就指向数组的0端，所以。整个队尾指示器+1的操作就可以修改为：rear = （rear + 1）%maxSize；队头指示器同样是如此。当队头的操作达到数组的上限的时候，如果还有数组元素出 队，这个时候，队头指示器就要指向数组的0端。所以，队头指示器+1的操作就是 front = （front + 1）%maxSize。
这样的话，就⼜有⼀个问题，队满和队空的时候，都有rear = front。为了解决这个问题，⼀般的 ⽅法就是，少使⽤⼀个空间。所以，我们判断队空的条件就变成了 rear = front。判断队满的条件是 （rear + 1）%maxSize = front。与此同时，循环队列中数据元素的个数是（rear - front + maxSize）% maxSize。
所以普通队列的实现我们用链式存储结构。
3.链队列的代码实现
1.结点结构
///链式队列//
typedef struct qnode{//链式队列结点
int data;//队列元素
struct qnode *next;//指向下一个结点的指针
}qnode,*lqueue;
typedef struct linkqueue{//链式队列---可选，不写结构体，直接定义对头队尾指针也可
lqueue front,rear;//队头队尾指针,队首指针是链表头结点
}linkqueue;2.初始化
//初始化
void initqueue(linkqueue *q)
{
q->front=q->rear=(lqueue)malloc(sizeof(qnode));
if(q->front==NULL)
{
printf("分配失败\n");
}
else{
q->front->next=NULL;
}
} 3.入队
//入队
void enqueue(linkqueue* q,int x)
{
lqueue s=(lqueue )malloc(sizeof(qnode));
s->data =x;
s->next =NULL;//新节点插入到链尾
q->rear->next=s;
q->rear =s;
} 4.出队
//出队，队首指针是链表头结点 ，删除的是队首指针的下一个，即front->next
void dequeue(linkqueue* q)
{
int x;//保存出队元素
//先判空，不空才能出
if(q->front->next==NULL)
{
printf("空\n");//队空，报错
}
else{
lqueue p=q->front->next;
x=p->data;
q->front ->next=p->next ;
printf("%d\n",x);
//若原队列只有一个结点了，则删除边空，需要处理尾指针
if(q->rear==p)
q->rear =q->front;
free(p);
p=NULL;
}
}4.顺序实现循环队列
1.结点结构
//循环队列
typedef struct
{
int* data;//指针模拟开数组
int f,r;//本质是下标
}squeue;
2.初始化
//初始化
squeue initqueue()
{
squeue q;
q.data=(int*)malloc(sizeof(int)*maxx);
q.f=q.r=0;
return q;
} 3.入队
//入队---->前提先判满
void enqueue(squeue* q,int k)
{
//判满
if(q->f==((q->r+1)%maxx))
{
printf("队满\n");
return;
}
q->data[q->r]=k;
q->r=(q->r+1)%maxx;
} 4.出队
//出队 --->前提 判空
void dequeue(squeue* q)
{
//判空
if(q->r==q->f)
{
printf("队空\n");
return ;
}
q->f=(q->f+1)%maxx;
}5.双端队列
1.特点
对于双端队列来说，就是两端都是结尾的队列。队列的每⼀端都可以插⼊数据项和移除 数据项。相对于普通队列。双端队列的⼊队和出队操作在两端都可以进进⾏。
这种数据结构的特性，使得他更加的实⽤和⽅便。当你只允许使⽤⼀端出队、⼊队操作的时候， 他等价于⼀个栈。当限制⼀端只能出队，另⼀端只能⼊队，他就等价于⼀个普通队列。
2.双端队列链式存储全操作展示
#define maxx 10
typedef struct Node{
int data;
struct Node* pre;
struct Node* next;
}node;
//中间节点存储右端第一次插入的数据
node* l;
node* r;
void initqueue()
{
node* s=(node*)malloc(sizeof(node));
s->pre=s->next=NULL;
l=r=s;
}
//左边插入
void left_insert(int k)
{//l 指向真实的左端数据
node* s=(node*)malloc(sizeof(node));
s->data=k;
s->pre=NULL;
l->pre=s;
s->next=l;
l=s;
}
//右插入
void right_insert(int k)
{
//r 指向真实的右端数据的下一个节点
node* s=(node*)malloc(sizeof(node));
r->data=k;
r->next=s;
s->next=NULL;
s->pre=r;
r=s;
}
//左删除
void left_del()
{
if(l==r)
{
printf("空\n");
return;
}
node* p=l;
l=l->next;
l->pre=NULL;
printf("删除了%d\n",p->data);
free(p);
p=NULL;
}
//右删除
void right_del()
{
if(l==r)
{
printf("空\n");
return;
}
node* p=r;
r=r->pre;
r->next=NULL;
printf("删除了%d\n",r->data);
free(p);
p=NULL;
} 3.双端队列顺序存储全操作展示
#define maxx 10
typedef struct {
int *data;
int l,r;
int sum;//元素个数
}douqueue;
douqueue initqueue()
{
douqueue q;
q.data=(int *)malloc(sizeof(int)*maxx);
q.l=q.r=0;
q.sum=0;
return q;
}
//左端插入
void left_insert(douqueue *q,int k)
{
if(q->sum==maxx)
{
printf("满\n");
return;
}
q->data[q->l]=k;
q->l=(q->l+maxx-1)%maxx;//
q->sum++;
}
//左端删除
void left_delet(douqueue *q)
{
int x;//保存删除的元素
if(q->sum==0)
{
printf("空\n");
return;
}
x=q->data[(q->l+1)%maxx];
printf("删除了%d\n",x);
q->l=(q->l+1)%maxx;
q->sum--;
}
//右端插入
void right_insert(douqueue *q,int k)
{
if(q->sum==maxx)
{
printf("满\n");
return;
}
q->r=(q->r+1)%maxx;
q->data[q->r]=k;
q->sum++;
}
//右端删除
void right_delet(douqueue *q)
{
int x;//保存删除的元素
if(q->sum==0)
{
printf("空\n");
return;
}
x=q->data[q->r];
printf("删除了%d\n",x);
q->r=(q->r-1+maxx)%maxx;//
q->sum--;
}