程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 數據庫知識 >> SyBase數據庫 >> SyBase教程 >> 數據結構-隊列靜態順序存儲結構

數據結構-隊列靜態順序存儲結構

編輯:SyBase教程

數據結構-隊列靜態順序存儲結構


隊列的基本概念

1 隊列的基本概念
隊列(Queue):也是運算受限的線性表。是一種先進先出(First In First Out ,簡稱FIFO)的線性表。只允許在表的一端進行插入,而在另一端進行刪除。
隊首(front) :允許進行刪除的一端稱為隊首。
隊尾(rear) :允許進行插入的一端稱為隊尾。
  例如:排隊購物。操作系統中的作業排隊。先進入隊列的成員總是先離開隊列。
隊列中沒有元素時稱為空隊列。在空隊列中依次加入元素a1, a2, …, an之後,a1是隊首元素,an是隊尾元素。顯然退出隊列的次序也只能是a1, a2, …, an ,即隊列的修改是依先進先出的原則進行的

隊列的抽象數據類型定義

ADT Queue{
數據對象:D ={ ai|ai∈ElemSet,  i=1, 2, …, n, n >= 0} 
數據關系:R = {<ai-1, ai> | ai-1, ai∈D,  i=2,3,…,n } 約定a1端為隊首,an端為隊尾。
基本操作:
Create():創建一個空隊列;
EmptyQue():若隊列為空,則返回true ,否則返回flase ;
   ??
InsertQue(x) :向隊尾插入元素x;
DeleteQue(x) :刪除隊首元素x;
    } ADT Queue

隊列的靜態順序存儲結構

在非空隊列裡,隊首指針始終指向隊頭元素,而隊尾指針始終指向隊尾元素的下一位置。
順序隊列中存在“假溢出”現象。因為在入隊和出隊操作中,頭、尾指針只增加不減小,致使被刪除元素的空間永遠無法重新利用。因此,盡管隊列中實際元素個數可能遠遠小於數組大小,但可能由於尾指針巳超出向量空間的上界而不能做入隊操作。該現象稱為假溢出。

循環隊列

循環隊列:將為隊列分配的向量空間看成為一個首尾相接的圓環,並稱這種隊列為循環隊列(Circular Queue)。
特點:
克服上述“假溢出”現象,充分利用向量空間
出隊、入隊操作,隊首、隊尾指針仍要加1,朝前移動
當隊首、隊尾指針指向向量上界(MAX_QUEUE_SIZE-1)時,其加1操作的結果是指向向量的下界0

2  入隊操作
Status Insert_CirQueue(SqQueue  Q , ElemType  e)
  /*  將數據元素e插入到循環隊列Q的隊尾  */
{  if  ((Q.rear+1)%MAX_QUEUE_SIZE== Q.front)
return  ERROR;      /*  隊滿,返回錯誤標志    */
Q.Queue_array[Q.rear]=e ;   /*  元素e入隊  */
Q.rear=(Q.rear+1)% MAX_QUEUE_SIZE ; 
/*  隊尾指針向前移動  */
return OK;        /*  入隊成功    */
}
2  入隊操作(正確)
Status Insert_CirQueue(SqQueue  *Q , ElemType  e)
  /*  將數據元素e插入到循環隊列Q的隊尾  */
{  if  ((Q->rear+1)%MAX_QUEUE_SIZE== Q-> front)
return  ERROR;      /*  隊滿,返回錯誤標志    */
Q-> Queue_array[Q-> rear]=e ;   /*  元素e入隊  */
Q-> rear=(Q-> rear+1)% MAX_QUEUE_SIZE ; 
/*  隊尾指針向前移動  */
return OK;        /*  入隊成功    */
}
3  出隊操作
Status Delete_CirQueue(SqQueue  Q, ElemType  *x )
   /*  將循環隊列Q的隊首元素出隊  */
{   if  (Q.front== Q.rear)
return ERROR ;       /*  隊空,返回錯誤標志    */
*x=Q.Queue_array[Q.front] ;  /* 取隊首元素 */
Q.front=(Q.front+1)% MAX_QUEUE_SIZE ;
     /*  隊首指針向前移動  */
return OK ;
}
3  出隊操作(正確)
Status Delete_CirQueue(SqQueue  *Q, ElemType  *x )
   /*  將循環隊列Q的隊首元素出隊  */
{   if  (Q-> front== Q-> rear)
return ERROR ;       /*  隊空,返回錯誤標志    */
*x= Q-> Queue_array[Q-> front] ;  /* 取隊首元素 */
Q-> front=(Q-> front+1)% MAX_QUEUE_SIZE ;
     /*  隊首指針向前移動  */
return OK ;
}

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