大家好,又见面了,我是你们的朋友全栈君。
队列的一些说明
队列的定义
队列,一种特殊的线性表
特点:只允许在一端输入,在另一端输出。输入端称为队尾,输出端称为队头
因此,队列,又称为先进先出表(FIFO),类似于生活中的排队,先来的排在前头,后来的排在后头,一个一个办理业务。
队列有两种,一种叫做循环队列(顺序队列),另一种叫做链式队列。
这一篇讲的是循环队列,链式队列在另外一篇文章中
链式队列讲解与C++实现
循环数组
循环队列使用的是数组,但是这个数组比较特别,为循环数组。为什么要使用循环数组呢?
可以想象一下,假如我们使用通常的数组。
那么在使用过程中,我们是从后面加入数据,从前面移除数据。那么随着出队和入队的进行,数组会整体向右平移,因为数组前面的元素因为出队变成了空白,变得不可使用。造成空间的浪费。
如果每出队一次,都将数组向左平移一次,又会很麻烦,造成时间上的浪费。综上,我们使用循环队列,就是将队首和队尾黏在一起。类似于一个⚪;
那么知道了循环数组后,我们应该考虑下,队首和队尾怎么放置,才能使我们循环队列能够使用。
不同的队首和队尾的初始化,将导致我们判断队列是否已满以及队列是否为空的方法的不同。
(1)front(队首)和rear(队尾)初始化均为0。那么,在这种情况下,front会永远指向队首元素,而rear会指向队尾元素的下一格。
(2)front(队首)和rear(队尾)错开。比如 front 初始为0,rear初始为5。在这种情况下front会永远指向队首元素,rear会永远指向队尾元素。
因此,在判断队列是否已满与非空时,初始化不同,判断方式不同。或者干脆就不用front与rear的位置来判断队列是否已满与非空。多加一个参数Size,表示队列的现有容积也行。
另外,如何在代码实现过程中将正常数组变成循环数组呢?
很简单,取余即可
C语言实现循环队列
定义结构体
struct Queue{
//结构体
int *data;
int capacity; //最大容积
int front; //表头
int rear; //表尾
//int size; //size表示队列的现有容量,
};
队列的初始化
void init(struct Queue *pq,int capacity){
//队列的初始化
pq->capacity=capacity;
pq->data=(int*)malloc(sizeof(int)*(capacity+1));
pq->front = 0; //初始化的不同,会导致后面判断队列是否为空以及是否已满的不同
pq->rear = 0;
}
判断队列是否已满
int isFull(const struct Queue *pq){
//判断队列是否已满
if((pq->rear + 1)%(pq->capacity+1) == pq->front) return 1;
else return 0;
}
判断队列是否为空
int isEmpty(const struct Queue *pq){
//判断是否为空
return pq->front == pq->rear;
}
入队操作,x表示插入的元素
int enQueue(struct Queue *pq,int x){
//入队操作
if(isFull(pq)) return 0;
else{
pq->data[pq->rear] = x;
pq->rear = (pq->rear+1) % (pq->capacity+1);
return 1; //成功返回1,失败返回0
}
}
出队操作,同时返回出队的值给px
int deQueue(struct Queue *pq,int *px){
//出队操作
if(isEmpty(pq)) return 0;
else {
*px = pq->data[pq->front];
pq->front = (pq->front+1) % (pq->capacity+1);
return 1; //成功返回1,失败返回0
}
}
完整代码
#include<stdio.h>
#include<stdlib.h>
using namespace std;
//循环队列
struct Queue{
//结构体
int *data;
int capacity; //最大容积
int front; //表头
int rear; //表尾
//int size; //size表示队列的现有容量,
};
void init(struct Queue *pq,int capacity){
//队列的初始化
pq->capacity=capacity;
pq->data=(int*)malloc(sizeof(int)*(capacity+1));
pq->front = 0; //初始化的不同,会导致后面判断队列是否为空以及是否已满的不同
pq->rear = 0;
}
int isFull(const struct Queue *pq){
//判断队列是否已满
if((pq->rear + 1)%(pq->capacity+1) == pq->front) return 1;
else return 0;
}
int isEmpty(const struct Queue *pq){
//判断是否为空
return pq->front == pq->rear;
}
int enQueue(struct Queue *pq,int x){
//入队操作
if(isFull(pq)) return 0;
else{
pq->data[pq->rear] = x;
pq->rear = (pq->rear+1) % (pq->capacity+1);
return 1; //成功返回1,失败返回0
}
}
int deQueue(struct Queue *pq,int *px){
//出队操作
if(isEmpty(pq)) return 0;
else {
*px = pq->data[pq->front];
pq->front = (pq->front+1) % (pq->capacity+1);
return 1; //成功返回1,失败返回0
}
}
int main()
{
struct Queue q;
init(&q,4);
enQueue(&q,11);
enQueue(&q,22);
enQueue(&q,33);
enQueue(&q,44);
enQueue(&q,55);
int x;
deQueue(&q,&x);
printf("%d\n",x);
deQueue(&q,&x);
printf("%d\n",x);
deQueue(&q,&x);
printf("%d\n",x);
deQueue(&q,&x);
printf("%d\n",x);
deQueue(&q,&x);
printf("%d\n",x);
}
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/140889.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...