佇列；
定義
，只允許在一端進行插入操作，而在另一端中進行刪除操作的線性表(有限、有序)
其為一種先進先出(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則是只可在線性表一端做新增；而在另一端做刪除動作。
