队列:
队列是一种先进先出(First In First Out)的线性表。它只允许在表的一端进行插入,在另一端删除元素。
允许插入的一端成为队尾,允许删除的一端成为队头
循环队列的顺序表示和实现:
队列有顺序表示和链式表示两种方式,我们此处用顺序表示
队列的顺序存储结构:
#define MAXSIZE 10
typedef struct{
ElemType *base; //存储空间基地址(数组首地址)
int front; //队头
int rear; //队尾
}SqQueue;
在初始化创建空队列时,令front=rear=0(图a),每当插入新的元素时,队尾指针rear增1,每当删除队列头元素时,头指针front增1
当前队列分配的空间为5,当队列处于图(d)状态时不可再继续插入新元素,否则将会出现溢出现象,
即因为数组越界,可是此时队列并占未满,所以这种现象称为"假溢出"。
解决办法:
将顺序队列变为一个循环队列
头尾指针以及队列元素之间的关系不变,只是在队列中头 尾指针“依环增1”的操作可用“模”运算来实现,通过取模,头指针和尾指针就可以在顺序表以头尾衔接的方式“循环”移动
但循环队列不能以头指针,尾指针的值是否相等来判断队列空间是 "满" 还是 "空".
解决办法:
少用一个元素空间,及队列空间大小为m时,有m-1个元素就认为是满队。这样判断队空的条件不变,即当头尾指针的值相同时,则认为队空。
而当尾指针在循环意义上加1后等于头指针,则认为队满。
因此在循环队列中队空队满的条件是:
队空:Q.front==Q.rear
队满:(Q.rear+1)%MAXSIZE==Q.front
操作完整代码:
/*循环队列 基本操作:初始化、取队头元素、取队尾元素、判断队空、判断队满、入队、出队、求队列长度*/
#include <stdio.h>
#include <stdlib.h>
#define OK 1
#define ERROR 0
#define LENGTH 10
typedef int ElemType;
typedef int Status;
typedef struct SqQueue{
ElemType *base; //初始化时动态分配存储空间
int front;
int rear;
}SqQueue;
/*Function:循环队列初始化*/
Status Init_SqQueue(SqQueue *q){
q->base=(ElemType *)malloc(LENGTH*sizeof(ElemType));//分配空间
if(!q->base){
return ERROR;
}
q->front=q->rear;
printf("对初始化成功!\n");
return OK;
}
/*Function:求循环队列长度*/
int QueueLength(SqQueue q){
return (q.rear-q.front+LENGTH)%LENGTH;
}
/*FUnction:入队*/
Status EnQueue(SqQueue *q){
ElemType e;
if((q->rear+1)%LENGTH==q->front){
return ERROR;
}
printf("请输入入队元素:\n");
scanf("%d",&e);
q->base[q->rear]=e;
q->rear=(q->rear + 1) % LENGTH; //队尾指针加1
printf("入队成功 \n");
return OK;
}
/*function:出队*/
Status OutQueue(SqQueue *q){
if(q->front==q->rear){
return ERROR;
}
printf("%d出队\n",q->base[q->front]);
q->front++;
return OK;
}
/*Function:取队头元素*/
ElemType getQueueFront(SqQueue q){
if(q.front!=q.rear){ //非空
return q.base[q.front];
}
}
/*Function:取队尾元素*/
ElemType getQueueRear(SqQueue q){
if(q.front!=q.rear){
q.rear--;
return q.base[q.rear];
}
}
/*Function:判断队是否为空 */
Status isEmpty(SqQueue q){
if(q.front==q.rear){//为空
return OK;
}else{
return ERROR;
}
}
/*Function:判断队是否已满 */
Status isFull(SqQueue q){
if((q.rear+1)%LENGTH==q.front){//已满
return OK;
}else{
return ERROR;
}
}
void main(){
SqQueue s;
ElemType e;
Init_SqQueue(&s);
EnQueue(&s);
EnQueue(&s);
EnQueue(&s);
OutQueue(&s);
e=getQueueFront(s);
printf("队头元素为:%d\n",e);
e=getQueueRear(s);
printf("队尾元素为:%d\n",e);
if(isEmpty(s)){
printf("队为空!\n");
}else{
printf("队非空!\n");
}
}
执行结果:
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)