006——队列

队列：

一种受限的线性表（线性逻辑结构），只允许在一段进行添加操作，在另一端只允许进行删除操作，中间位置不可操作，入队的一端被称为队尾，出队的一端被称为队头，在而我们会用两个指针分别用于标记队首和队尾，分别叫做队首指针和队尾指针

 单端队列：

存储结构：

顺序队列

顺序存储，基于数组来存储

两种思路

思路1：r指针指向尾元素的下一个位置

Ⅰ)初始空的队列：f=0,r=0

typedef struct {int* data;//数组int f, r;//front队首指针  rear队尾指针 
}Squeue;

Squeue InitQueue()
{Squeue q;q.data = (int*)malloc(sizeof(int) * maxsize);if (q.data == NULL){printf("空间分配失败\n");}else {q.f = q.r = 0;}return q;
}

Ⅱ）入队：a[r]=k;r++;//a[r++]=k;

void Enqueue(Squeue* q, int k)
{q->data[q->r] = k;r++;
}

Ⅲ）出队：f++;

void Dequeue(Squeue* q)
{q->f++;
}

Ⅳ）判满：r==maxsize(假溢出)

Ⅴ）判空：f==r

思路2：r指针指向真正的尾元素

Ⅰ)初始空的队列：f=0,r=-1

Squeue InitQueue()
{Squeue q;q.data = (int*)malloc(sizeof(int) * maxsize);if (q.data == NULL){printf("空间分配失败\n");}else {q.f = 0;q.r = 1;}return q;
}

Ⅱ）入队：r++;a[r]=k;//a[++r]=k;

void Enqueue(Squeue* q, int k)
{r++;q->data[q->r] = k;}

Ⅲ）出队：f++;

void Dequeue(Squeue* q)
{q->f++;
}

Ⅳ）判满：r==maxsize-1(假溢出)

Ⅴ）判空：f==r+1

如何解决假溢出的问题？

形成循环队列-->取余（思路1相对来说更加方便取余）

Ⅰ)初始空的队列：f=0,r=0

Ⅱ）入队：a[r]=k;r=（r+1）%maxsize;

Ⅲ）出队：f=（f+1）%maxsize;

Ⅳ）判满：

        方法①：牺牲一个存储空间（r+1）%maxsize==f;

        方法②：队满之前的操作一定是入队flag==0操作

                       队空之前的操作一定是出队flag==1操作

        则用一个变量flag来记录此时是入队操作还是出队操作

                        f==r&&flag==0

Ⅴ）判空：f==r

#include<stdio.h>
#include<stdlib.h>
#define maxsize 10
//循环队列
typedef struct {int* data;//数组int f, r;//front队首指针  rear队尾指针 
}Squeue;
Squeue InitQueue()
{Squeue q;q.data = (int*)malloc(sizeof(int) * maxsize);if (q.data == NULL){printf("空间分配失败\n");}else {q.f = q.r = 0;}return q;
}
void Enqueue(Squeue* q, int k)
{if ((q->r + 1) % maxsize == q->f){printf("队满，不能入队\n");return;}q->data[q->r] = k;q->r = (q->r + 1) % maxsize;}
void Dequeue(Squeue* q)
{if (q->f == q->r){printf("队空，不能出队\n");return;}printf("队首%d出队\n", q->data[q->f]);q->f = (q->f + 1) % maxsize;
}
int main()
{return 0;
}

链式队列

#include<stdio.h>
#include<stdlib.h>
#define maxsize 10
//链式队列
typedef struct Qnode {int data;struct Qnode* next;
}QNode;
typedef struct Queue {QNode* f;QNode* r;
}LinkQ;LinkQ InitLinkQ()
{LinkQ q;q.f = (QNode*)malloc(sizeof(QNode));if (q.f == NULL){printf("空间分配失败\n");}else {q.f->next = NULL;q.r = q.f;}return q;
}
LinkQ Enqueue(LinkQ q, int k)
{QNode* s = (QNode*)malloc(sizeof(QNode));if (s == NULL){printf("空间分配失败,不能入队\n");}else {s->data = k;s->next = NULL;q.r->next = s;q.r = s;}return q;}
LinkQ Dequeue(LinkQ q)
{if (q.r == q.f){printf("空间分配失败,不能出队\n");return q;}QNode* p = q.f->next;q.f->next = p->next;if (q.r == p){q.r = q.f;}printf("队首%d出队\n", p->data);free(p);p = NULL;
}
int main()
{return 0;
}

双端队列

双端队列，可以简单理解成将两个队列合在一起，而双端队列的两端分为前端和后端，而在着两端均可以进行出入队操作

存储方式：

顺式存储

前面可以了解到，顺序存储我们是用数组来实现，那这里就会存在一个问题：前端的位置和后端的位置是不固定的，-因为我们不知道前端的位置具体插入多少元素，后端的位置插入多少元素，所以我们采用循环数组来实现存储

这里还有一个需要考虑的问题：到底是先动指针还是先放数据？

①前后端先动指针后放数据

这个时候我们会发现中间会存放一个空数据，所以是不行的

①前后端先放数据后动指针

这个时候我们会发现有的元素数据会被覆盖掉

所以我们需要一端是先移动指针，一段是先放入数据

不过这样的话，其中一个指针指向的是该元素，另一个指针指向的是该元素的下一个位置

代码案例：

#include<stdio.h>
#include<stdlib.h>
#define maxsize 10
int* q=NULL;//指针模拟开数组
int l, r;//左端 右端
int size;//记录双端队列中实际的元素个数void InitQueue() {q = (int*)malloc(sizeof(int) * maxsize);if (q == NULL) {printf("空间访问失败\n");return;}size = 0;l = r = 0;
}//左端入队
void insert_left(int k) {if (size == maxsize) {printf("队满，不能入队\n");return;}q[l] = k;l = (l - 1 + maxsize) % maxsize;size++;
}//左端出队
void delete_left() {if (size == 0) {printf("队空，不能出队\n");return;}printf("出队元素为%d", q[(l + 1) % maxsize]);l = (l + 1) % maxsize;size--;
}//右端入队
void insert_right(int k) {if (size == maxsize) {printf("队满，不能入队\n");return;}r = (r + 1 ) % maxsize;q[r] = k;size++;
}//右端出队
void delete_right() {if (size == 0) {printf("队空，不能出队\n");return;}printf("出队元素为%d", q[(r - 1 + maxsize) % maxsize]);r = (r - 1 + maxsize) % maxsize;size--;
}//打印
void show() {int i = (l + 1)%maxsize;while (i != r) {printf("%d\t", q[i]);i = (i + 1) % maxsize;}printf("%d\n", q[r]);}int main() {InitQueue();insert_left(10);insert_left(5);insert_right(13);insert_right(56);show();
}

链式存储

因为双端队列需要往两端去延长，所以如果用链表来实现的话，我们需要用双向链表来去实现。

代码示例

#include<stdio.h>
#include<stdlib.h>
#define maxsize 10 
typedef struct linkQ{int data;struct linkQ* pre;struct linkQ* next;
}Node; 
Node* l=NULL;
Node* r=NULL; 
void initqueue()
{l=(Node*)malloc(sizeof(Node));if(l==NULL){printf("空间分配失败\n");return;}l->next=NULL;l->pre=NULL;r=l;
}
//左边
void insert_left(int k)
{Node* s=(Node*)malloc(sizeof(Node));if(s==NULL){printf("空间分配失败,不能入队\n");return;}l->data=k;s->pre=l->pre;l->pre=s;s->next=l;l=s; } 
void delet_left()
{if(l==r){printf("队空，不能出队\n");return; 	}int x=l->next->data;printf("%d出队\n",x); Node* p=l;l=p->next;l->pre=p->pre;free(p);p=NULL;
}
//右边
void insert_right(int k)
{Node* s=(Node*)malloc(sizeof(Node));if(s==NULL){printf("空间分配失败,不能入队\n");return;}s->data=k;s->next=r->next;s->pre=r;r->next=s;r=s;} void delet_right(){if(l==r){printf("队空，不能出队\n");return; 	}int x=r->data;printf("%d出队\n",x); Node* p=r;r=p->pre;r->next=p->next;free(p);p=NULL;
}
void show()
{Node* p=l->next;while(p!=NULL){printf("%d ",p->data);p=p->next;}printf("\n");
}
int main()
{initqueue();insert_left(1);insert_left(2);insert_left(3);insert_right(4);insert_right(8);printff();delet_left();delet_right(); delet_right();delet_right();show();return 0;
}