快捷導(dǎo)航

詳解數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言實(shí)現(xiàn)之循環(huán)隊(duì)列

更新時(shí)間：2016年07月27日 17:03:27 投稿：daisy

在我們生活中有很多隊(duì)列的影子，可以說(shuō)與時(shí)間相關(guān)的問(wèn)題，一般都會(huì)涉及到隊(duì)列問(wèn)題；本文詳細(xì)介紹了如何使用C語(yǔ)言實(shí)現(xiàn)循環(huán)隊(duì)列，下面一起來(lái)看看。

本文講的是循環(huán)隊(duì)列，首先我們必須明白下面幾個(gè)問(wèn)題

循環(huán)隊(duì)列的基礎(chǔ)知識(shí)

1.循環(huán)隊(duì)列需要幾個(gè)參數(shù)來(lái)確定

循環(huán)隊(duì)列需要2個(gè)參數(shù)，front和rear

2.循環(huán)隊(duì)列各個(gè)參數(shù)的含義

（1）隊(duì)列初始化時(shí)，front和rear值都為零；

（2）當(dāng)隊(duì)列不為空時(shí)，front指向隊(duì)列的第一個(gè)元素，rear指向隊(duì)列最后一個(gè)元素的下一個(gè)位置；

（3）當(dāng)隊(duì)列為空時(shí)，front與rear的值相等，但不一定為零；

3.循環(huán)隊(duì)列入隊(duì)的偽算法

（1）把值存在rear所在的位置；

（2）rear=（rear+1）%maxsize ，其中maxsize代表數(shù)組的長(zhǎng)度；

程序代碼：

bool Enqueue(PQUEUE Q, int val) 
{ 
  if(FullQueue(Q)) 
    return false; 
  else 
  { 
    Q->pBase[Q->rear]=val; 
    Q->rear=(Q->rear+1)%Q->maxsize; 
    return true; 
  } 
}

4.循環(huán)隊(duì)列出隊(duì)的偽算法

（1）先保存出隊(duì)的值；

（2）front=（front+1）%maxsize ，其中maxsize代表數(shù)組的長(zhǎng)度；

程序代碼：

bool Dequeue(PQUEUE Q, int *val) 
{ 
  if(EmptyQueue(Q)) 
  { 
    return false; 
  } 
  else 
  { 
    *val=Q->pBase[Q->front]; 
    Q->front=(Q->front+1)%Q->maxsize; 
    return true; 
  } 
}

5.如何判斷循環(huán)隊(duì)列是否為空

if（front==rear）

隊(duì)列空；

else

隊(duì)列不空；

bool EmptyQueue(PQUEUE Q) 
{ 
  if(Q->front==Q->rear)  //判斷是否為空 
    return true; 
  else 
    return false; 
}

6.如何判斷循環(huán)隊(duì)列是否為滿

這個(gè)問(wèn)題比較復(fù)雜，假設(shè)數(shù)組的存數(shù)空間為7，此時(shí)已經(jīng)存放1，a，5,7,22,90六個(gè)元素了，如果在往數(shù)組中添加一個(gè)元素，則rear=front；此時(shí)，隊(duì)列滿與隊(duì)列空的判斷條件front=rear相同，這樣的話我們就不能判斷隊(duì)列到底是空還是滿了；

解決這個(gè)問(wèn)題有兩個(gè)辦法：

一是增加一個(gè)參數(shù)，用來(lái)記錄數(shù)組中當(dāng)前元素的個(gè)數(shù)；

第二個(gè)辦法是，少用一個(gè)存儲(chǔ)空間，也就是數(shù)組的最后一個(gè)存數(shù)空間不用，當(dāng)（rear+1）%maxsiz=front時(shí)，隊(duì)列滿；

bool FullQueue(PQUEUE Q) 
{ 
  if(Q->front==(Q->rear+1)%Q->maxsize)  //判斷循環(huán)鏈表是否滿，留一個(gè)預(yù)留空間不用 
    return true; 
  else 
    return false; 
}

附錄：

queue.h文件代碼：

#ifndef __QUEUE_H_ 
#define __QUEUE_H_ 
typedef struct queue  
{ 
  int *pBase; 
  int front;  //指向隊(duì)列第一個(gè)元素 
  int rear;  //指向隊(duì)列最后一個(gè)元素的下一個(gè)元素 
  int maxsize; //循環(huán)隊(duì)列的最大存儲(chǔ)空間 
}QUEUE,*PQUEUE; 
 
void CreateQueue(PQUEUE Q,int maxsize); 
void TraverseQueue(PQUEUE Q); 
bool FullQueue(PQUEUE Q); 
bool EmptyQueue(PQUEUE Q); 
bool Enqueue(PQUEUE Q, int val); 
bool Dequeue(PQUEUE Q, int *val); 
#endif

queue.c文件代碼：

#include<stdio.h> 
#include<stdlib.h> 
#include"malloc.h" 
#include"queue.h" 
/*********************************************** 
Function: Create a empty stack; 
************************************************/ 
void CreateQueue(PQUEUE Q,int maxsize) 
{ 
  Q->pBase=(int *)malloc(sizeof(int)*maxsize); 
  if(NULL==Q->pBase) 
  { 
    printf("Memory allocation failure"); 
    exit(-1);    //退出程序 
  } 
  Q->front=0;     //初始化參數(shù) 
  Q->rear=0; 
  Q->maxsize=maxsize; 
} 
/*********************************************** 
Function: Print the stack element; 
************************************************/ 
void TraverseQueue(PQUEUE Q) 
{ 
  int i=Q->front; 
  printf("隊(duì)中的元素是:\n"); 
  while(i%Q->maxsize!=Q->rear) 
  { 
    printf("%d ",Q->pBase[i]); 
    i++; 
  } 
  printf("\n"); 
} 
bool FullQueue(PQUEUE Q) 
{ 
  if(Q->front==(Q->rear+1)%Q->maxsize)  //判斷循環(huán)鏈表是否滿，留一個(gè)預(yù)留空間不用 
    return true; 
  else 
    return false; 
} 
bool EmptyQueue(PQUEUE Q) 
{ 
  if(Q->front==Q->rear)  //判斷是否為空 
    return true; 
  else 
    return false; 
} 
bool Enqueue(PQUEUE Q, int val) 
{ 
  if(FullQueue(Q)) 
    return false; 
  else 
  { 
    Q->pBase[Q->rear]=val; 
    Q->rear=(Q->rear+1)%Q->maxsize; 
    return true; 
  } 
} 
 
bool Dequeue(PQUEUE Q, int *val) 
{ 
  if(EmptyQueue(Q)) 
  { 
    return false; 
  } 
  else 
  { 
    *val=Q->pBase[Q->front]; 
    Q->front=(Q->front+1)%Q->maxsize; 
    return true; 
  } 
}

以上就是C語(yǔ)言實(shí)現(xiàn)循環(huán)隊(duì)列的全部?jī)?nèi)容，對(duì)于學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法的研究有所幫助,有需要的朋友可以參考下。

您可能感興趣的文章: