循環隊列的基本操作-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;
}

           

運作結果