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首必須要在前面的位置上，所導致的。


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

(front,rear，front則是指下一次可讀(刪)的位置;rear指下一次可寫的位置)
以此來避免每刪一次,則需花O(n)來搬移資料。



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;

}

queue link list

queue link list,與一般的link list之間.差在於 queue link list中,只會記錄其front,rear.及在新增'刪除時的操作的不同.

一般link list

  1: typedef int Status; 
  2: 
  3: typedef int QElemType; /* QElemType類型根據實際情形而定，這裡假設為int */
  4: 
  5: typedef struct QNode /* 節點結構 */
  6: {
  7:    QElemType data;
  8:    struct QNode *next;
  9: }QNode,*QueuePtr

而為了以link list來構成queue

則需記錄link list 的front,rear

  1: typedef struct   /* 佇列的鏈結串列結構 */
  2: {
  3:    QueuePtr front,rear; /* 隊首、隊尾指標 */
  4: }LinkQueue;
  5: 

1.空queue



2.新增element(rear)



3.刪除element(front)

  1: #include "stdio.h"
  2: #include "stdlib.h"
  3: #include "io.h"
  4: #include "math.h"
  5: #include "time.h"
  6: 
  7: #define OK 1
  8: #define ERROR 0
  9: #define TRUE 1
 10: #define FALSE 0
 11: #define MAXSIZE 20 /* 儲存空間初始分配量 */
 12: 
 13: typedef int Status;
 14: 
 15: typedef int QElemType; /* QElemType類型根據實際情形而定，這裡假設為int */
 16: 
 17: typedef struct QNode  /* 節點結構 */
 18: {
 19:    QElemType data;
 20:    struct QNode *next;
 21: }QNode,*QueuePtr;
 22: 
 23: typedef struct      /* 佇列的鏈結串列結構 */
 24: {
 25:    QueuePtr front,rear; /* 隊首、隊尾指標 */
 26: }LinkQueue;
 27: 
 28: Status visit(QElemType c)
 29: {
 30:   printf("%d ",c);
 31:   return OK;
 32: }
 33: /* 初始化一個空佇列Q */
 34: Status InitQueue(LinkQueue *Q)
 35: {
 36:   Q->front=Q->rear=(QueuePtr)malloc(sizeof(QNode));
 37:   if(!Q->front)
 38:     exit(OVERFLOW);
 39:   Q->front->next=NULL;
 40:   return OK;
 41: }
 42: 
 43: /* 銷毀佇列Q */
 44: Status DestroyQueue(LinkQueue *Q)
 45: {
 46:   QueuePtr p;
 47:   //已為空Q
 48:   if(Q->front==Q->rear)
 49:     return OK;
 50:   else
 51:   {
 52: 
 53:   }
 54: }
 55: /* 將佇列Q清空 */
 56: Status ClearQueue(LinkQueue *Q)
 57:   {
 58:   if(Q->front==Q->rear)
 59:     return OK;
 60:   QueuePtr p=Q->front->next;
 61:   QueuePtr q;
 62:   Q->rear=Q->front;
 63:   //**
 64:   Q->front->next=NULL;
 65:   while(p)
 66:   {
 67:     q=p->next;
 68:     free(p);
 69:     p=q;
 70:   }
 71:   return OK;
 72:   }
 73: /* 若佇列Q為空佇列，回傳TRUE，否則回傳FALSE */
 74: Status QueueEmpty(LinkQueue Q)
 75:   {
 76:     if(Q.front==Q.rear)
 77:       return TRUE;
 78:     else
 79:       return FALSE;
 80:   }
 81: /* 求佇列長度 */
 82: int QueueLength(LinkQueue Q)
 83:   {
 84:     int iCo=0;
 85:     QueuePtr p=(Q.front)->next;
 86:     for(iCo=0;p!=NULL;p=p->next,iCo++)
 87:       ;
 88:     return iCo;
 89:     //  p=Q.front;
 90:     //  while(Q.rear!=p)
 91:   }
 92: /* 若佇列Q非為空，用e返回佇列Q的隊首元素,回傳TRUE，否則回傳FALSE */
 93: Status GetHead(LinkQueue Q,QElemType *e)
 94:   {
 95:   if(Q.rear==Q.front)
 96:     return ERROR; //emty
 97:   QueuePtr p;
 98:   p=(Q.front)->next;
 99:   *e=p->data;
100:   return OK;
101:   }
102: /* 插入元素e為Q的新的隊尾元素 */
103: Status EnQueue(LinkQueue *Q,QElemType e)
104: {
105:   QueuePtr p=(QueuePtr)malloc(sizeof(QNode));
106:   if(p==NULL)
107:     return ERROR;
108:   p->data=e;
109:   p->next=Q->rear->next;
110:   Q->rear->next=p;
111:   Q->rear=p;
112:   return OK;
113: }
114: /* 若佇列不空，刪除Q的隊首元素，用e回傳其值，並回傳OK，否則回傳ERROR */
115: Status DeQueue(LinkQueue *Q,QElemType *e)
116: {
117:   if(Q->rear==Q->front)
118:     return ERROR; //emty
119:   QueuePtr p;
120:   p=Q->front->next;
121:   *e=p->data;
122:   Q->front->next=p->next;
123:   //**
124:   if(Q->rear==p)
125:     Q->rear=Q->front;
126:   free(p);
127:   return OK;
128: }
129: /* 從隊首到隊尾依次對佇列Q中每個元素輸出 */
130: Status QueueTraverse(LinkQueue Q)
131:   {
132:     QueuePtr p=(Q.front)->next;
133:     while(p!=NULL)
134:     {
135:       visit(p->data);
136:       p=p->next;
137:     }
138:     printf("\n");
139:     return OK;
140:   }
141: int main()
142: {
143:   int i;
144:   QElemType d;
145:   LinkQueue q;
146:   i=InitQueue(&q);
147:   if(i)
148:     printf("成功建立了一個空佇列!\n");
149:   printf("是否為空佇列？%d(1:空 0:否)  ",QueueEmpty(q));
150:   printf("佇列的長度為%d\n",QueueLength(q));
151:   EnQueue(&q,-5);
152:   EnQueue(&q,5);
153:   EnQueue(&q,10);
154:   printf("插入3個元素(-5,5,10)後,佇列的長度為%d\n",QueueLength(q));
155:   printf("是否為空佇列？%d(1:空 0:否)  ",QueueEmpty(q));
156:   printf("佇列的元素依次為：");
157:   QueueTraverse(q);
158:   i=GetHead(q,&d);
159:   if(i==OK)
160:    printf("隊首元素是：%d\n",d);
161:   DeQueue(&q,&d);
162:   printf("刪除了隊首元素%d\n",d);
163:   i=GetHead(q,&d);
164:   if(i==OK)
165:     printf("新的隊首元素是：%d\n",d);
166:   ClearQueue(&q);
167:   printf("清空佇列後,q.front=%u q.rear=%u q.front->next=%u\n",q.front,q.rear,q.front->next);
168:   DestroyQueue(&q);
169:   printf("銷毀佇列後,q.front=%u q.rear=%u\n",q.front, q.rear);
170: 
171:   return 0;
172: }
173: 

stack是只限定在list的尾進行新增、刪除動作的線性表。

queue則是只可在線性表一端做新增；而在另一端做刪除動作。