出入队算法为重点

1. 循环队列

重点就在于4个式子

• 入队：rear = (rear +1)%MAXSIZE;
• 出队：front= (front+1)%MAXSIZE;
• 队满：(rear+1) % MAXSIZE == front;
• 队空：front==rear;

1.1 定义

// 循环队列
#include <stdio.h>
#include <malloc.h>
#define MAXSIZE 20
typedef struct 
{
    int data[MAXSIZE];
    int front;
    int rear;
}cque;

1.2 初始化

cque* initcque(cque* cq){
    cq = (cque*)malloc(sizeof(cque));
    cq->front = -1;
    cq->rear = -1;
    return cq;
}

1.3 入队（重点）

int insert(cque* cq,int x){
    if (cq->rear+1 % MAXSIZE == cq->front){
        printf("queue Full!\n");
        return 0;
    }
    
    cq->rear = (cq->rear+1)%MAXSIZE;
    cq->data[cq->rear] = x;
    return 1;
}

1.4 出队（重点）

int delet(cque* cq){
    if(cq->front == cq->rear){
        printf("queue Null!\n");
        return -1;
    }
    printf("delete %d\n",cq->data[cq->front+1]);
    cq->front= (cq->front+1)%MAXSIZE;
    return 1;
}

1.5 打印队列

void display(cque* cq){
	printf("\n***display***\n");
	while(cq->front!=cq->rear){
		printf("%d ",cq->data[cq->front+1]);
		cq->front= (cq->front+1)%MAXSIZE;
	}
}

2. 链队列

重点理解两个结构体的含义

• 一个结构体用于存放数据，包含数据域和next域；一个结构体专门用于存放头尾节点。
• 其实可以不用两个结构体，改成两个全局的头尾指针也行（参考栈），因为链队列实际上就是具有双端指针的单链表（两个结构体的写法源自课本）

为什么需要单独的结构体存放front和rear？

• 方便传参，毕竟很多地方都需要同时用到front和rear指针，定义一个结构体就省事点

2.1 定义

// 链队列
#include<stdio.h>
#include<stdlib.h> 
typedef int datatype;

typedef struct qnode
{
	datatype data;
	struct qnode *next;
}qnode;

typedef struct
{
	qnode *front;
	qnode *rear;
}linkque;

2.2 初始化

linkque* Initque()
{
    linkque *q;
    qnode *p;
    q = (linkque*)malloc(sizeof(linkque));
    p = (qnode*)malloc(sizeof(qnode));

    p->next = NULL;
    q->front = q->rear = p;
    return q;
}

2.3 入队（重点）

void inque(linkque *q,datatype x){
	qnode *p;
    p = (qnode*)malloc(sizeof(qnode));

	p->data = x;
	p->next = NULL;
	
    q->rear->next=p;
    q->rear = p;
}

2.4 出队（重点）

int deleque(linkque *q){
    //刚开始头尾都指向一个空，所以实际链表在front的下一个
	qnode* t = q->front->next;
	if(q->front==q->rear)
		return 0;
    printf("delete %d\n",t->data);
    q->front->next=t->next;

	//如果是最后一个
    if(q->rear==t)
        q->rear = q->front;
    
    free(t);
	return 1;
}

2.5 打印队列

void display(linkque *q){
    qnode *t=q->front->next;
    while (t!=NULL)
    {
        printf("%d ",t->data);
        t = t->next;
    }
    
}

记忆小结

1. 循环队列初始化头尾都是-1；链队列初始化头尾都是指向一个空节点。
2. 链队列入队尾插法；出队删除头（注意删除点若为最后一个元素则要将头尾同置）。
3. 链队列刚开始时头尾都指向一个空，所以实际链表在front的下一个