|
队列的顺序表示和实现
一、循环队列概述
循环队列 是把顺序队列首尾相连，把存储队列元素的表从逻辑上看成一个环，成为循环队列。 队头指针(front) 指向队列的队头元素。 队尾指针(rear) 指向队列的最后一个元素的下一个元素。 pBase 指向块内存的首地址 
二、循环队列存储结构
在顺序实现是 队尾指针和队头指针指的就是下标 
typedef struct CircularQueue//队列参数
{
int * pBase;//指向数组首地址的指针
int front;//出队下标指向队列的要出队的第一个元素
int rear;//入队下标，指向队列元入队元素的下一个空间
}CircularQueue, *pCircularQueue;
三、循环队列的操作定义
//1、初始化循环队列
void InitCircularQueue(pCircularQueue Q);
// 2、返回队列中已有元素个数
int CircularQueueLength(pCircularQueue Q);
// 3、判断循环队列是否为满
bool CircularQueueIsFull(pCircularQueue Q);
// 4、将元素e进行入队
bool CircularQueueEn(pCircularQueue Q, ElemType e);
//5、判断循环队列是否为空
bool CircularQueueIsEmpty(pCircularQueue Q);
// 6、遍历队内所有元素
void CircularQueueTraverse(pCircularQueue Q);
//7、出队,出队元素由e返回
bool CircularQueueOut(pCircularQueue Q, ElemType &e);
//8、清空队列
void CircularQueueClear(pCircularQueue Q);
//9、销毁队列
void circularQueueDestory(pCircularQueue Q);
1、初始化循环队列
2、返回队列中已有元素个数
int CircularQueueLength(pCircularQueue Q)
{
return (Q->rear - Q->front + MAX_SIZE) % MAX_SIZE;
}
3、判断循环队列是否为满
4、将元素e进行入队
bool CircularQueueEn(pCircularQueue Q,ElemType e)
{
if (CircularQueueIsFull(Q))
{
printf("队列已满，入队失败！\n");
return false;
}
Q->pBase[Q->rear] = e;
Q->rear = (Q->rear + 1) % MAX_SIZE;
return true;
}
5、判断循环队列是否为空
bool CircularQueueIsEmpty(pCircularQueue Q)
{
if (Q->front == Q->rear)
return true;
else
return false;
}
6、遍历队内所有元素
void CircularQueueTraverse(pCircularQueue Q)
{
int i = Q->front;
while (i!=Q->rear)
{
printf(" %d\n", Q->pBase[i]);
i = (i+1)%MAX_SIZE;
}
}
7、出队,出队元素由e返回
bool CircularQueueOut(pCircularQueue Q, ElemType &e)
{
if (CircularQueueIsEmpty(Q))
{
printf("队列为空，出队失败！\n");
return false;
}
e = Q->pBase[Q->front];
Q->front = (Q->front + 1) % MAX_SIZE;
return true;
}
8、清空队列
void CircularQueueClear(pCircularQueue Q)
{
Q->front = Q->rear = 0;
}
9、销毁队列
void CircularQueueDestory(pCircularQueue Q)
{
if (Q->pBase)//如果队列存在
{
free(Q->pBase);//释放队列所占内存
}
Q->pBase = NULL;//不指向任何存储空间
Q->front = Q->rear = 0;
}
最后给出完整代码
// 循环队列.cpp
# include
# include
# include
# define MAX_SIZE 6//队列最大长度 + 1
typedef int ElemType;
typedef struct CircularQueue//队列参数
{
int * pBase;//指向数组首地址的指针
int front;//出队下标指向队列的要出队的第一个元素
int rear;//入队下标，指向队列元入队元素的下一个空间
}CircularQueue, *pCircularQueue;
//1、初始化循环队列
void InitCircularQueue(pCircularQueue Q);
// 2、返回队列中已有元素个数
int CircularQueueLength(pCircularQueue Q);
// 3、判断循环队列是否为满
bool CircularQueueIsFull(pCircularQueue Q);
// 4、将元素e进行入队
bool CircularQueueEn(pCircularQueue Q, ElemType e);
//5、判断循环队列是否为空
bool CircularQueueIsEmpty(pCircularQueue Q);
// 6、遍历队内所有元素
void CircularQueueTraverse(pCircularQueue Q);
//7、出队,出队元素由e返回
bool CircularQueueOut(pCircularQueue Q, ElemType &e);
//8、清空队列
void CircularQueueClear(pCircularQueue Q);
//9、销毁队列
void CircularQueueDestory(pCircularQueue Q);
int main()
{
CircularQueue Q;
InitCircularQueue(&Q);
if (CircularQueueIsEmpty(&Q))
{
printf("队列为空\n");
}
else
{
printf("队列不为空\n");
}
for (int i = 0; i
if (CircularQueueOut(&Q,e1))
{
printf(" %d\n", e1);
}
}
printf("\n");
CircularQueueTraverse(&Q);
return 0;
}
//1、初始化循环队列
void InitCircularQueue(pCircularQueue Q)
{
Q->pBase = (ElemType *)malloc(sizeof(ElemType)*MAX_SIZE);
if (Q->pBase==NULL)
{
printf("内存分配失败，程序退出！\n");
exit(-1);
}
Q->front = Q->rear = 0;
}
// 2、返回队列中已有元素个数
int CircularQueueLength(pCircularQueue Q)
{
return (Q->rear - Q->front + MAX_SIZE) % MAX_SIZE;
}
// 3、判断循环队列是否为满
bool CircularQueueIsFull(pCircularQueue Q)
{
if ((Q->rear+1)%MAX_SIZE == Q->front)
{
return true;
}
return false;
}
// 4、将元素e进行入队
bool CircularQueueEn(pCircularQueue Q,ElemType e)
{
if (CircularQueueIsFull(Q))
{
printf("队列已满，入队失败！\n");
return false;
}
Q->pBase[Q->rear] = e;
Q->rear = (Q->rear + 1) % MAX_SIZE;
return true;
}
//5、判断循环队列是否为空
bool CircularQueueIsEmpty(pCircularQueue Q)
{
if (Q->front == Q->rear)
return true;
else
return false;
}
// 6、遍历队内所有元素
void CircularQueueTraverse(pCircularQueue Q)
{
int i = Q->front;
while (i!=Q->rear)
{
printf(" %d", Q->pBase[i]);
i = (i+1)%MAX_SIZE;
}
printf("\n");
}
//7、出队,出队元素由e返回
bool CircularQueueOut(pCircularQueue Q, ElemType &e)
{
if (CircularQueueIsEmpty(Q))
{
printf("队列为空，出队失败！\n");
return false;
}
e = Q->pBase[Q->front];
Q->front = (Q->front + 1) % MAX_SIZE;
return true;
}
//8、清空队列
void CircularQueueClear(pCircularQueue Q)
{
Q->front = Q->rear = 0;
}
//9、销毁队列
void CircularQueueDestory(pCircularQueue Q)
{
if (Q->pBase)//如果队列存在
{
free(Q->pBase);//释放队列所占内存
}
Q->pBase = NULL;//不指向任何存储空间
Q->front = Q->rear = 0;
}
|