当前位置 博文首页 > ice_elephant的博客：数据结构算法之循环队列
这里是引用
4.2 循环队列 在队列的顺序存储中，采用出队方式 2, 删除 front 所指的元素，然后加 1 并返回被删元素。这样可以避免元素 移动，但是也带来了一个新的问题“假溢出”。 能否利用前面的空间继续存储入队呢？采用循环队列
循环队列入队, 队尾循环后移： SQ->rear =（SQ->rear+1）%Maxsize; 循环队列出队, 队首循环后移： SQ->front =（SQ->front+1）%Maxsize; 队空：SQ.front=SQ.rear; // SQ.rear 和 SQ.front 指向同一个位置 队满： (SQ.rear+1) %Maxsize=SQ.front; // SQ.rear 向后移一位正好是 SQ.front 计算元素个数: 可以分两种情况判断： ? 如果 SQ.rear>= SQ.front：元素个数为 SQ.rear-SQ.front； ? 如果 SQ.rear<SQ.front：元素个数为 SQ.rear-SQ.front+ Maxsize； 采用取模的方法把两种情况统一为：(SQ.rear-SQ.front+Maxsize)% Maxsize
/*
循环队列，就是避免假溢出，出队的方式中，移动front结点的方式简单粗暴直接+1，而rear结点的方式同样简单粗暴直接+1
实现方法
1、循环队列初始化
2、判断是否为空
3、判断是否已满
4、入队
5、出队
6、遍历
7、获取头节点
8、清空队列
*/
#include<stdio.h>
#include<Windows.h>
typedef int dateType;
#define MAX_SIZE 5
typedef struct _Queue{
dateType date[MAX_SIZE];
int front;
int rear;
}Queue;
//1、初始化
bool initQueue(Queue *SQ){
if(!SQ) return false;
SQ->front = 0;
SQ->rear = 0;
return true;
}
//2、判断队列是否为空
bool isEmpty(Queue *SQ){
if(SQ->front==SQ->rear) return true;
return false;
}
//3、判断队列是否已满
bool isFully(Queue *SQ){
//这里的意思头节点何尾部结点的距离的绝对值是MAX_SIZE的话，那么就是队列满了，
if(((SQ->rear+1)%MAX_SIZE==SQ->front)) return true;
return false;
}
//4、入队
bool insertdate(Queue *&SQ,int date){
if(!SQ||isFully(SQ)) {
printf("当前队列无法插入元素!\n");
return false;
}else{
printf("成功插入元素:%d\n",date);
}
SQ->date[SQ->rear] = date;
SQ->rear = (SQ->rear+1)%MAX_SIZE;
return true;
}
//5、出队
bool popdate(Queue *&SQ){
if(!SQ||isEmpty(SQ)){
printf("无元素出队!\n");
return false;
}
printf("元素出队:%d\t\n",SQ->date[SQ->front]);
SQ->front=(SQ->front+1)%MAX_SIZE;
return true;
}
//6、获取头节点元素
bool getHeadDate(Queue *SQ,dateType &date){
if(!SQ||isEmpty(SQ)) {
printf("头节点元素获取失败!\n");
}
date = SQ->date[SQ->front];
return true;
}
//7、遍历元素
void printDate(Queue *SQ){
if(!SQ||isEmpty(SQ)) return ;
int i = SQ->front;
while(i!=SQ->rear){
printf("遍历元素:%d\t",SQ->date[i]);
i=(i+1)%MAX_SIZE;
}
printf("\n");
}
//8、清空队列
void clearQueue(Queue *SQ){
if(!SQ) return ;
SQ->front = 0;
SQ->rear = 0;
}
//获取队列元素的个数
int getCount(Queue *SQ){
if(!SQ||isEmpty(SQ))return 0;
int count = (SQ->rear-SQ->front+MAX_SIZE)%MAX_SIZE;
return count;
}
int main(void){
Queue *SQ = new Queue;
//1、循环队列初始化
if(initQueue(SQ)){
printf("队列初始化成功！\n");
}else{
printf("队列初始化失败！\n");
}
;
//2、判断是否为空
//3、判断是否已满
for(int i=0;i<4;i++){
insertdate(SQ,i);
}
//
printDate(SQ);
//4、入队
//5、出队
popdate(SQ);
printDate(SQ);
//6、遍历
//7、获取头节点
//8、清空队列
system("pause");
return 0;
}
