程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> 關於C語言 >> 靜態循環隊列的相關操作及詳解

靜態循環隊列的相關操作及詳解

編輯:關於C語言

循環隊列

        隊列通常分為兩類:一是動態鏈式隊列(其核心思想為鏈表,只是少了鏈表的一些功能),二是靜態(順序)隊列(其核心是用數組實現,准確一點講是由向量空間來實現,向量空間好比是開辟的一塊內存,由我們的指針來指向其地址)。順序隊列實際上是運算受限的順序表,由於隊列的隊頭和隊尾的位置是變化的,通常設置兩個指針front和rear分別指示隊頭元素和隊尾元素在向量空間中的位置,它們的初值在隊列初始化時均應置為0。由於入隊和出隊操作中,頭尾指針只增加不減小,致使被刪元素的空間永遠無法重新利用。當隊列中實際的元素個數遠遠小於向量空間的規模時,也可能由於尾指針已超越向量空間的上界而不能做入隊操作。這種“假上溢”現象常常造成內存資源的浪費,這時就產生了循環隊列(首尾相接)。循環隊列克服“假上溢”現象的方法是:將向量空間想象成一個首尾相連的圓環,將循環隊列存放在其中。循環隊列中,由於入隊時尾指針向前追趕頭指針;出隊時頭指針向前追趕尾指針,造成隊空和隊滿時頭尾指針均相等。因此,無法通過條件front==rear來判別隊列是"空"還是"滿"。針對這樣情況,有兩種解決方法:一是少用一個元素的空間。約定入隊前,測試尾指針在循環意義下加1後是否等於頭指針,若相等則認為隊滿(注意:rear所指的單元始終為空),;二是使用一個計數器記錄隊列中元素的總數(即隊列長度)。我們通常使用第一種方法,也就是少用一個元素的空間。


循環隊列相關操作思路

      \

       1.初始化:   造數組,設其數組長度為n=5(規定當數組中有n-1個元素時已滿),初始化隊頭隊尾值都為0;

      2.入隊

                先判斷隊列是否已滿:(隊尾+1)%數組長度==隊頭 是否成立?即隊尾和隊頭緊挨著;

                為隊尾的下一個元素賦值;

                讓隊尾加1;

       3.出隊

                 先判斷隊列是否為空:若隊首和隊尾相等,則該隊列一定為空(但隊首和隊尾值不一定為0,這個由初始化、入隊、出隊等相關操作後的數組下標位置決定)

                 保存一份要出隊的值;

                 讓隊頭加1;

 

實例說明

 

?<SPAN style="FONT-SIZE: 14px">#include<stdio.h> 
#include<malloc.h>  
#include<stdlib.h>  
typedef struct Queue 
{ 
    int *pBase;//pBase指向數組名(通常靜態隊列都使用循環隊列)  
    int front;//數組下標,這裡規定從零開始  
    int rear; 
}QUEUE;//QUEUE代表了struct Queue  
void init(QUEUE *);//初始化  
bool en_queue(QUEUE *,int);//入隊  
bool full_queue(QUEUE *);//判斷循環隊列是否已滿  
bool del_queue(QUEUE *,int *);//出隊  
bool empty_queue(QUEUE *);//判斷循環隊列是否為空  
bool traverse_queue(QUEUE *);//遍歷輸出  
int length(QUEUE *);//求循環隊列的長度  
 
int main() 
{ 
    QUEUE Q; 
    int val; 
    init(&Q); 
    en_queue(&Q,1); 
    en_queue(&Q,2); 
    en_queue(&Q,3); 
    en_queue(&Q,4); 
    traverse_queue(&Q);       
    if(del_queue(&Q,&val)) 
        printf("出隊成功,出隊元素的值為:%d\n",val); 
    else 
        printf("出隊失敗!"); 
    traverse_queue(&Q);  
    printf("隊列的長度為:%d\n",length(&Q)); 
     
    return 0; 
} 
void init(QUEUE *pQ) 
{ 
    pQ->pBase=(int *)malloc(sizeof(int)*5);//造數組,設其數組長度為n=5(規定當數組中有n-1個元素時已滿),初始化時使Queue的成員front、rear的值都為0  
    if(NULL==pQ->pBase) 
    { 
        printf("動態內存分配失敗!\n"); 
        exit(-1); 
    } 
    pQ->front=0; 
    pQ->rear=0; 
} 
bool full_queue(QUEUE *pQ) 
{ 
    if((pQ->rear+1)%5==pQ->front) 
        return true; 
    else 
        return false; 
} 
bool en_queue(QUEUE *pQ,int val) 
{ 
    if(full_queue(pQ)) 
    { 
        printf("隊列已滿,入隊失敗!\n"); 
        return false; 
    } 
    pQ->pBase[pQ->rear]=val; 
    pQ->rear=(pQ->rear+1)%5;//隊尾加1  
    return true; 
} 
bool del_queue(QUEUE *pQ,int *pVal) 
{ 
    if(empty_queue(pQ)) 
        return false; 
    *pVal=pQ->pBase[pQ->front]; 
    pQ->front=(pQ->front+1)%5; 
    return true; 
} 
bool empty_queue(QUEUE *pQ) 
{ 
    if(pQ->rear==pQ->front)//因為隊列不為空時,rear和front肯定不相等  
        return true; 
    else 
        return false; 
} 
bool traverse_queue(QUEUE *pQ) 
{ 
    int i=pQ->front; 
    if(empty_queue(pQ)) 
    { 
        printf("隊列為空,遍歷失敗!\n"); 
        return false; 
    } 
    printf("隊列元素有:"); 
    while(i!=pQ->rear) 
    { 
        printf("%d  ",pQ->pBase[i]); 
        i=(i+1)%5;               
    } 
    printf("\n"); 
    return true; 
} 
int length(QUEUE *pQ) 
{ 
    int len=0; 
    int i=pQ->front;; 
    if(empty_queue(pQ)) 
        return 0;//隊列為空,長度為0  
    while(i!=pQ->rear) 
    { 
        i=(i+1)%5; 
        ++len; 
    } 
    return len; 
}</SPAN> 

#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
typedef struct Queue
{
 int *pBase;//pBase指向數組名(通常靜態隊列都使用循環隊列)
 int front;//數組下標,這裡規定從零開始
 int rear;
}QUEUE;//QUEUE代表了struct Queue
void init(QUEUE *);//初始化
bool en_queue(QUEUE *,int);//入隊
bool full_queue(QUEUE *);//判斷循環隊列是否已滿
bool del_queue(QUEUE *,int *);//出隊
bool empty_queue(QUEUE *);//判斷循環隊列是否為空
bool traverse_queue(QUEUE *);//遍歷輸出
int length(QUEUE *);//求循環隊列的長度

int main()
{
 QUEUE Q;
 int val;
 init(&Q);
 en_queue(&Q,1);
 en_queue(&Q,2);
 en_queue(&Q,3);
 en_queue(&Q,4);
    traverse_queue(&Q);     
    if(del_queue(&Q,&val))
  printf("出隊成功,出隊元素的值為:%d\n",val);
 else
  printf("出隊失敗!");
 traverse_queue(&Q);
    printf("隊列的長度為:%d\n",length(&Q));
 
 return 0;
}
void init(QUEUE *pQ)
{
 pQ->pBase=(int *)malloc(sizeof(int)*5);//造數組,設其數組長度為n=5(規定當數組中有n-1個元素時已滿),初始化時使Queue的成員front、rear的值都為0
 if(NULL==pQ->pBase)
 {
  printf("動態內存分配失敗!\n");
  exit(-1);
 }
 pQ->front=0;
 pQ->rear=0;
}
bool full_queue(QUEUE *pQ)
{
 if((pQ->rear+1)%5==pQ->front)
  return true;
 else
  return false;
}
bool en_queue(QUEUE *pQ,int val)
{
 if(full_queue(pQ))
 {
  printf("隊列已滿,入隊失敗!\n");
  return false;
 }
    pQ->pBase[pQ->rear]=val;
 pQ->rear=(pQ->rear+1)%5;//隊尾加1
 return true;
}
bool del_queue(QUEUE *pQ,int *pVal)
{
 if(empty_queue(pQ))
  return false;
    *pVal=pQ->pBase[pQ->front];
 pQ->front=(pQ->front+1)%5;
 return true;
}
bool empty_queue(QUEUE *pQ)
{
 if(pQ->rear==pQ->front)//因為隊列不為空時,rear和front肯定不相等
  return true;
 else
  return false;
}
bool traverse_queue(QUEUE *pQ)
{
 int i=pQ->front;
 if(empty_queue(pQ))
 {
  printf("隊列為空,遍歷失敗!\n");
  return false;
 }
 printf("隊列元素有:");
 while(i!=pQ->rear)
 {
  printf("%d  ",pQ->pBase[i]);
  i=(i+1)%5;    
 }
 printf("\n");
 return true;
}
int length(QUEUE *pQ)
{
 int len=0;
 int i=pQ->front;;
 if(empty_queue(pQ))
        return 0;//隊列為空,長度為0
 while(i!=pQ->rear)
 {
  i=(i+1)%5;
  ++len;
 }
 return len;
}

注意

       1.指針只在入隊和出隊時移動,其它情況下不能移動。

       2.隊列初始化:front和rear的值都是零;

       3.隊列非空:front代表的是隊列的第一個元素,rear代表的是隊列的最後一個有效元素的下一個元素。

       4.順序隊列和循環隊列最直觀的區別就是:循環隊列首尾相連形成一個圓環,而順序隊列不成環狀(通常會造成內存資源的浪費)。

       5.隊列的應用非常廣泛,所有與時間有關的操作都可以用到隊列。

 

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved