queue

佇列；

定義

，只允許在一端進行插入操作，而在另一端中進行刪除操作的線性表(有限、有序)

其為一種先進先出(FIFO，first in first out)的線性表。

q=(a1,a2,...,an-1,an);則可設定a1為首，而an為尾。

queue的ADT(抽象資料類型)

ADT queue

Data

    元素為相同的類型，相鄰元素具有前後關係.

Operater

    InitQueue(*Q);//初始化,建立一個空queue

    DestoryQueue(*Q);//若queue存在,則刪除

    ClearQueue(*Q);//清除queue.

    QueueEmpty(Q);//若Q存在且為空,則回傳true

    GetHead(Q,*e);//若queue且非空,則e傳回Q首

    EndQueue(*Q,e);//若queue存在,插入新元素e到queue中.其e成為queue尾

    DeQueue(*Q,*e);//刪除queue首元素,並用e傳回

    QueueLenght(Q);//反回queue中的元素個數.

endADT

因為是線性表，故相同地有

順序儲存

其順序存儲時，有下列問題

其加入元素時，其時間O(1)

刪除時，則時間變為O(n)。這是因為使其queue首必須要在前面的位置上，所導致的。

而其可以改為下列，用二個變數指標來指定其首'尾.

 

1.空

2.滿

3.非空非滿

在此時，會出現"虛溢出"，指還有空間(0)。但無法存放。

而為了改進此我們把rear放在0來形成循環，稱為循環queue

但其該如何來判斷其是是滿或空

方法1:

加一個flag

在初始時front==rear,flag=0.為空

若下次出現front==rear且flag==0.則改flag=1(滿)

方2:

保留一個空間。如下圖的情況即代表為滿。

而其

判斷是否為滿

(rear+1)%QueueSize==front

EX:

rear=0,front=1

((0+1)%5==1)?滿:非滿

rear=4,front=0

(4+1)%5==0? 滿

rear=4,front=1

(4+1)%5==1?非滿

其

長度

(rear-front+QueueSize)%QueueSize

typedef int QElemType;

typedef struct

{

QElemType data[MAXSIZE];

int front;

int rear;

}SqQueue;

Status InitQueue(SqQueue *Q)

{

Q->front=0;

Q->rear=0;

return OK;

}

int QueueLength(Q)

{

return (Q.rear-Q.front+MAXSIZE)%MAXSIZE);

Status EnQueue(SqQueue *q,QElemType e)

{

if((q->rear+1)%MAXSIZE==q->front))

  return ERROR;

q->data[q->rear]=e;

q->rear=q->rear+1%MAXSIZE;

}

Status DeQueue(SqQueue *q, QElemType *e)

{

if(q->rear==q->front)

    return ERROR;

*e=q->data[q->front];

q->front=q->front+1%MAXSIZE;

return OK;

}

 

 

link list