循环队列的基本操作-C语言

循环队列的基本操作

• 一、循环队列
• 二、循环队列的理解
• 二、循环队列的算法
• • ①、循环队列--队列的顺序存储结构
  • ②、构造空循环队列
  • ③、入队
  • ④、出队
  • ⑤、返回Q元素的个数,即队列的长度
  • ⑥、遍历
• 应用
• • Queue.h
  • Queue.c
  • 运行结果

一、循环队列

为充分利用向量空间，克服上述“假溢出”现象的方法是：将为队列分配的向量空间看成为一个首尾相接的圆环，并称这种队列为循环队列(Circular Queue)。

二、循环队列的理解

例：设有循环队列QU[0，5]，其初始状态是front=rear=0，各种操作后队列的头、尾指针的状态变化情况如下图所示。

入队时尾指针向前追赶头指针，出队时头指针向前追赶尾指针，故队空和队满时头尾指针均相等。因此，无法通过front=rear来判断队列“空”还是“满”。

☞☞解决此问题的方法是：约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等则认为队满。即：

◆ rear所指的单元始终为空。

◆ 循环队列为空：front=rear 。

◆ 循环队列满：(rear+1)%MAX_QUEUE_SIZE =front。

二、循环队列的算法

①、循环队列–队列的顺序存储结构

/******循环队列--队列的顺序存储结构******/
#define MAXQSIZE 10 /*最大队列长度*/
#define  OK   1
#define  ERROR   -1
typedef  int  Status ;
typedef  int  ElemType ;
typedef struct {
    ElemType *base;  /*初始化的动态分配存储空间*/
    int front;       /*头指针,若队列不为空,指向队列头元素*/
    int rear;        /*尾指针,若队列不为空,指向队列尾元素的下一个位置*/
}SqQueue;
           

②、构造空循环队列

/*构造一个空队列*/
Status InitQueue(SqQueue Q){
    Q.base = (ElemType *) malloc (MAXQSIZE *sizeof (ElemType));
    if(!Q.base) exit (0);           /*存储分配失败退出*/
    Q.front = Q.rear = 0;
    return OK;
}
           

③、入队

/*  将数据元素e插入到循环队列Q的队尾  */
Status EnQueue(SqQueue Q, ElemType *e) {
    if ( ( Q.rear + 1 ) % MAXSIZE == Q.front ) /*判断队列是否满*/
    return ERROR;  /*队列满*/
    Q.base[Q.rear] = e;   /*  元素e入队  */
    Q.rear = ( Q.rear + 1 ) % MAXSIZE; /*  队尾指针向前移动  */
    return OK;      /*  入队成功,返回OK  */
}
           

④、出队

Status OutQueue(SqQueue Q, ElemType *e){
    if (Q.rear == Q.front )  
    return ERROR;                      /*队列为空,返回错误*/
    e = Q.base[Q.front];               /* 取队首元素 */
    Q.front = ( Q.front + 1 ) % MAXSIZE;/* 队首指针向前移动 */
    return OK;
}
           

⑤、返回Q元素的个数,即队列的长度

/*返回Q元素的个数,即队列的长度*/
int QueueLength(SqQueue Q){
    int i;
    i=(Q.rear - Q.front + MAXQSIZE) % MAXQSIZE; /*计算队中元素个数*/
    return(i);
}
           

⑥、遍历

void PrintQuence(SeQuence Q) {
    int i;
    i = (Q->Front + 1) % MAXQSIZE; /*队头加一开始遍历*/
    while (i != Q->rear) {
        printf("%c", Q->base[i]);
        i = (i + 1) % MAXQSIZE;
    }
    printf("%c",Q->base[i]);       /*队尾*/
    printf("\n");
}
           

应用

1、桌上有一叠牌，从第一张牌（即位于顶面的牌）开始从上往下依次编号为1~n。当至少还剩三张牌时进行以下操作：把第一、二张牌扔掉，然后把当前状态下新的第一张放到整叠牌的最后。 输入n,输出每次扔掉的牌，以及最后剩下的牌。 输入输出样例如下：

输入4

第一次：扔掉1,2

从顶向底最后剩下：4,3

Queue.h

#include<stdio.h>
#include<stdlib.h>
#define OK 1
#define ERROR -1
#define MAX 100
typedef int QElemType;
typedef struct
{
    QElemType *data;
    int front;//队头
    int rear;//队尾
}SqQueue;
 /*初始化*/
int InitiQueue(SqQueue &Q)
{
       Q.data=(QElemType*)malloc(MAX*sizeof(QElemType));
    if(!(Q.data))
       {
              exit(0);
       }
    Q.front=Q.rear=0;
    return OK;
}
 /*尾插法入队*/
int EnQueue(SqQueue &Q,QElemType e)
{
    if((Q.rear+1)%MAX== Q.front) //队列满
       {
              return ERROR;
       }
    Q.data[Q.rear]=e;
    Q.rear=(Q.rear+1)%MAX;
    return  OK;
}
 /*出队*/
int DeQueue(SqQueue &Q,QElemType &e){
    if(Q.front == Q.rear)
       {
              return ERROR;
       }
    e=Q.data[Q.front];
    Q.front=(Q.front+1)%MAX;
    return OK;
}
/*纸牌*/
int Playing_Cards(SqQueue &Q,QElemType &e)
{
    int n,i=1;
       int number=1;//计数
    printf("请输入的数量:  ");
    scanf("%d",&n);
       printf("牌的编号为: ");
    for(i=1;i<=n;i++)
       {
        EnQueue(Q,i);
              printf(" %d ",i);
    }
       printf("\n");
    while(1)
       {
 
              DeQueue(Q,e);  
              printf("第 %d 次删除掉：%d ",number++,e);
              if(Q.front==Q.rear)
                     break;
              DeQueue(Q,e);
              printf("%2d \n",e);
        if(Q.front==Q.rear)
                     break;
        DeQueue(Q,e);     //新的第一张出队
        if(Q.front==Q.rear)
                     break;
        if(Q.front+1==Q.rear&&n%2==0)//保留偶数编号牌
                     break;
        EnQueue(Q,e);//把牌放到整叠牌的最后
       }
 
    printf("从顶向底最后剩下:");
       if(Q.front+1== Q.rear)
       {
              printf("%2d ",Q.data[Q.rear-1]);
        printf("%2d ",Q.data[Q.front-1]);
       }
       else
              printf("%2d ",Q.data[Q.rear-1]);
       printf("\n");
       return OK;
}
 
           

Queue.c

#include"Queue.h"
int main()
{
	int e=1;
	SqQueue Q;
	InitiQueue(Q);
	int choice;
	Playing_Cards(Q,e);	
	while(true){
		InitiQueue(Q);
	printf("请问是否继续？1/是，2/否 :\n");
	scanf("%d",&choice);
	if(choice == 1)
	{
		Playing_Cards(Q,e);	
	}
	else return 0;
	}
	return 0;
}

           

运行结果