【数据结构】循环队列的认识和基本操作
程序员文章站
2022-05-04 17:24:08
...
队列的基本认识:点击打开链接
一.循环队列
头指针和尾指针连在一起的顺序存储结构就是循环队列。
循环队列初始条件:队头指针(front)=队尾指针(rear)=0
循环队列队满条件:(rear+1)%size == front (size是顺序表的最大储存空间)
循环队列空条件:队头指针(rear)=队尾指针(front)
队头指针向前移动计算:队头指针=(rear+1)%size (size是顺序表的最大储存空间)
队尾指针向后移动计算:队尾指针=(front+1%size (size是顺序表的最大储存空间)
循环队列队满条件:(rear+1)%size == front (size是顺序表的最大储存空间)
循环队列空条件:队头指针(rear)=队尾指针(front)
队头指针向前移动计算:队头指针=(rear+1)%size (size是顺序表的最大储存空间)
队尾指针向后移动计算:队尾指针=(front+1%size (size是顺序表的最大储存空间)
面试题:循环队列中如何判断队列空和满?
-
少用一个储存单元 (size-1)
- 设置一个标记 (front=i , rear ==i )
- 设置一个计数器(flag == size)
- (rear+1)%size == front (size是顺序表的最大储存空间) (本次实现的代码中是用这个判断)
注意:在c语言中不能用动态分配的一维数组来实现循环队列
下边是队列的基本操作的代码
queue.h
#pragma once
#include<stdio.h>
#include<Windows.h>
#include<assert.h>
typedef int DataType;
#define size 10
typedef struct Queue
{
DataType* array;
int front;
int rear;
}Queue;
//初始化队列
void QueueInit(Queue* q);
// 入队列
void QueuePush(Queue* q, DataType data);
// 出队列
void QueuePop(Queue* q);
// 获取队列顶元素
DataType QueueTop(Queue* q);
// 获取队列中元素个数
int QueueSize(Queue* q);
// 检测队列是否为空
int QueueEmpty(Queue* q);
//销毁队列
void DestroyQueue(Queue* q);
//清空队列
void ClearQueue(Queue* q);
//打印队列
void printQueue(Queue* q);
queue.c
#include"queue.h"
//初始化队列
void QueueInit(Queue* q)
{
q->array = (DataType*)malloc(size*sizeof(DataType));
if (NULL == q->array)
{
printf("申请失败!!!");
return;
}
//初始化队列的条件
q->front = q->rear = 0;
}
//入队列
void QueuePush(Queue* q, DataType data)
{
//判断队列满的条件
if ((q->rear + 1) % size == q->front)
{
printf("队列已满!!!");
return;
}
q->array[q->rear] = data;
q->rear = (q->rear + 1) % size; //队尾指针向后移动条件
return;
}
// 出队列
void QueuePop(Queue* q)
{
//判断队列满的条件
if ((q->rear + 1) % size == q->front)
{
printf("队列已满!!!");
return;
}
//队头指针向前移动
q->front = (q->front + 1) % size;
}
// 获取队头元素
DataType QueueTop(Queue* q)
{
//判断队列是否为空
if (q->front == q->rear)
{
printf("队列以空!!!");
return 0;
}
return (q->array[q->front]);
}
// 获取队列中元素个数
int QueueSize(Queue* q)
{
//判断队列是否为空
if (q->front == q->rear)
{
printf("队列以空!!!");
return 0;
}
return ((q->rear - q->front) + size) % size;
}
// 检测队列是否为空
int QueueEmpty(Queue* q)
{
//判断队列是否为空
if (q->front == q->rear)
{
printf("队列以空!!!");
return 0;
}
return 1;
}
//销毁队列
void DestroyQueue(Queue* q)
{
while (q->front != q->rear)
{
free(&q->array[q->front]);
q->front = (q->front + 1) % size;
}
}
//清空队列
void ClearQueue(Queue* q)
{
int i = q->front;
while (i != q->rear)
{
i = 0;
i++;
}
q->front = q->rear = 0;
}
//打印队列
void printQueue(Queue* q)
{
int i = q->front;
while (i != q->rear)
{
printf("%d->", q->array[i]);
i++;
}
printf("\n");
}
test.c
#include"queue.h"
void QueueTest()
{
Queue q;
QueueInit(&q);
QueuePush(&q, 1);
QueuePush(&q, 2);
QueuePush(&q, 3);
QueuePush(&q, 4);
QueuePush(&q, 5);
printQueue(&q);
QueuePop(&q);
printQueue(&q);
printf("size: %d\n",QueueSize(&q));
printf("top: %d\n", QueueTop(&q));
}
int main()
{
QueueTest();
system("pause");
return 0;
}
运行后的结果
上一篇: 十种分布式ID生成方法
下一篇: Java 设计模式之单例模式