数据结构之循环队列基本操作(c语言）

骑猪看日落 2023-01-13 08:55 127阅读 0赞

**队列**：  
队列是一种**先进先出**(First In First Out)的线性表。它只允许在表的一端进行插入，在另一端删除元素。

允许插入的一端成为**队尾**，允许删除的一端成为**队头**  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjM2NDcxMA_size_16_color_FFFFFF_t_70][]

**循环队列的顺序表示和实现：**

队列有**顺序**表示和**链式**表示两种方式，我们此处用顺序表示

队列的顺序存储结构：

#define MAXSIZE 10
    typedef struct{
         ElemType *base; //存储空间基地址(数组首地址）
         int  front; //队头
         int  rear; //队尾
    }SqQueue;

在初始化创建空队列时，令front=rear=0（图a)，每当插入新的元素时，队尾指针rear增1，每当删除队列头元素时，头指针front增1

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjM2NDcxMA_size_16_color_FFFFFF_t_70 1][]

当前队列分配的空间为5，当队列处于图（d）状态时不可再继续插入新元素，否则将会出现**溢出**现象，

即因为**数组越界**，可是此时队列**并占未满**，所以这种现象称为**"假溢出"。**

**解决办法：**

将顺序队列变为一个循环队列

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjM2NDcxMA_size_16_color_FFFFFF_t_70 2][]

头尾指针以及队列元素之间的关系不变，只是在队列中头 尾指针“**依环增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");
       }
    }

执行结果：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjM2NDcxMA_size_16_color_FFFFFF_t_70 3][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjM2NDcxMA_size_16_color_FFFFFF_t_70]: /images/20221022/b5346fa8d2b44649a64ec530b09f7600.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjM2NDcxMA_size_16_color_FFFFFF_t_70 1]: /images/20221022/e40bf6a296ae4aaea5064d71a43a75a8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjM2NDcxMA_size_16_color_FFFFFF_t_70 2]: /images/20221022/15f149aba5aa49a3aba635da8cf8e8e7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjM2NDcxMA_size_16_color_FFFFFF_t_70 3]: /images/20221022/a7c3a3f23b674e178ee3ebe4a8e6a975.png