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

來源：本站原創(chuàng)|時間：2020-01-10|欄目：C語言|點擊：次

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

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

1.循環(huán)隊列需要幾個參數(shù)來確定

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

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

（1）隊列初始化時，front和rear值都為零；

（2）當隊列不為空時，front指向隊列的第一個元素，rear指向隊列最后一個元素的下一個位置；

（3）當隊列為空時，front與rear的值相等，但不一定為零；

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

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

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

程序代碼：

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)隊列出隊的偽算法

（1）先保存出隊的值；

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

程序代碼：

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)隊列是否為空

if（front==rear）

隊列空；

else

隊列不空；

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

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

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

解決這個問題有兩個辦法：

一是增加一個參數(shù)，用來記錄數(shù)組中當前元素的個數(shù)；

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

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

附錄：

queue.h文件代碼：

#ifndef __QUEUE_H_ 
#define __QUEUE_H_ 
typedef struct queue  
{ 
  int *pBase; 
  int front;  //指向隊列第一個元素 
  int rear;  //指向隊列最后一個元素的下一個元素 
  int maxsize; //循環(huán)隊列的最大存儲空間 
}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("隊中的元素是:\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)鏈表是否滿，留一個預(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語言實現(xiàn)循環(huán)隊列的全部內(nèi)容，對于學習數(shù)據(jù)結(jié)構(gòu)與算法的研究有所幫助,有需要的朋友可以參考下。

上一篇：C++11新特性之智能指針(shared_ptr/unique_ptr/weak_ptr)

欄目：C語言

下一篇：分析C語言一個簡單程序

本文標題：詳解數(shù)據(jù)結(jié)構(gòu)C語言實現(xiàn)之循環(huán)隊列

本文地址：http://mengdiqiu.com.cn/a1/Cyuyan/2131.html

更多C語言