Antrian dalam Struktur data

Queue (Antrian) adalah list linier yang :
1. Elemen yang pertama kali masuk antrian akan keluar pertama kalinya
2. Dikenali elemen pertama (Front) dan elemen terakhirnya (Tail)
3. Aturan penyisipan dan penghapusan elemennya disefinisikan sebagai berikut :
a) Penyisipan selalu dilakukan setelah elemen terakhir
b) Penghapusan selalu dilakukan pada elemen pertama
4. Satu elemen dengan elemen lain dapat diakses melalui informasi Next
5. Antrian dapat dibuat dengan menggunakan: Linier Array dan Circular Array

Front dan tail selalu bergerak maju/naik sehingga
1. Bila tail telah mencapai elemen terakhir array, antrian dianggap penuh walau sebenarnya mungkin elemen-elemen awal antrian telah dihapus (dikosongkan).
2. Bila front dan tail mencapai nilai yang sama berarti antrian dalam keadaan kosong maka front dan tail dapat diinisialisasi kembali ke kondisi semula.

Deklarasi queue menggunakan singly linked list:

Type
TData=…;
TKey= …;
PNode=^Node;
Node=record
Key:TKey;
Data:TData;
Next:PNode;
End;
Queue=record
Count:integer;
Front,tail:PNode;
End;
Opersi-operasi di QUEUE
1. InitQ(Q)menciptakan Qdengan queue kosong

Procedure InitQ(var Q:Queue);
Begin
Q.count:=0;
Q.front:=nil;
Q.tail:=nilai;
End;

2. AddQ(Q,x) menambah elemen x ke rear queue

Procedure AddQ(var Q:Queue; p:PNode);
{sama dengan insert last, yang elemen last-nya disimpan}
Begin
Q.tail^.next:=p;
Q.tail:=p;
If Q,front=nil then q.front:=Q.tail; {elemen pertama dan satu-satunya dari queue}
Q.count:=Q.count+1;
End;

3. RemoveQ(Q,x) menghilangkan elemen pada front dari queue Q

Procedure removeQ(var Q:Queue; var k:TKey; d:TData);
{sama dengan delete first}
Var p:PNode;
Begin
If (Q.frontNil) then
Begin
P:=Q.Front;
Q.front:=Q.front^.Next;
If Q.front=nil then Q.tail:=nil; {elemen satu2nya dihapus}
K:=p^.key;
D:=p^.data;
Q.Count:=Q.count-1;
Dispose(p);
End;
End;

4. Front(Q) mengirim elemen front dari queue

Function frontQ (Q:queue):listPtr;
Begin
FrontQ:=Q.front;
End;

5. IsEmptyQ(Q) yang mengembalikan true if Q kosong else false

Function isEmpityQ(Q:queue):Boolean;
Begin
isEmptyQ:=(S.front=nil);
end;

6. HowManyIn(Q) mengirimkan jumlah elemen di Queue

Function howManyInQ(Q:queue):integer;
Begin
howManyInQ:=Q.count;
End;