数据结构算法整理-04-循环队列和链队列
出入队算法为重点
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；链队列初始化头尾都是指向一个空节点。
- 链队列入队尾插法；出队删除头（注意删除点若为最后一个元素则要将头尾同置）。
- 链队列刚开始时头尾都指向一个空，所以实际链表在front的下一个
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2019/12/22 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
