Data Structure Chapter 3
STRUKTUR DATA QUEUE
Dahlia Widhyaestoeti, S.Kom
Agenda Hari Ini
Pengertian Queue Linear Queue Circular Queue Double Ended Queue
3. Double Ended Queue (Deque) Antrian dengan ujung ganda a. Pendahuluan A deque (Double Ended Queue) is a linear list in which insertion and deletion are made to or from either end of the structure. Jean-Paul Tremblay: “An Introduction To Data Structures with Applications”, McGraw-Hill,1985. Representasi Double Ended Queue dalam array 1 dimensi Insert kiri Q[ ]
0
1
2
3
4
x x x
6
7
8
Insert kanan
Delete kanan
Delete kiri R
L
5
3. Double Ended Queue (Deque) Antrian dengan ujung ganda b. Representasi Insert kiri Q[ ]
0
1
2
3
4
x x x
6
7
8
Insert kanan
Delete kanan
Delete kiri L = left R = right
5
L
R
Bila ada perintah Insert Kiri : maka akan masuk di Q[1]; L=L-1 dan Q[L]=X; Bila ada perintah Insert Kanan : maka akan masuk di Q[5]; R=R+1 dan Q[R]=X; Bila ada perintah Delete Kiri : maka yang diambil adalah isi Q[2]; X=Q[L] kemudian L=L+1; menunjuk Q[4] Bila ada perintah Delete Kanan : maka yang diambil adalah isi Q[4]; X=Q[R] kemudian R=R+1; menunjuk Q[3]
3. Double Ended Queue (Deque) Antrian dengan ujung ganda c. Prinsip dan Proses
Prinsip : Bukan FIFO dan bukan pula LIFO
Proses : ✔ AWAL (Inisialisasi) ✔ INSERT (Sisip, masuk, simpan, Tulis) ✔ DELETE (Hapus, keluar, ambil/dilayani, baca)
3. Double Ended Queue (Deque) Antrian dengan ujung ganda c. Prinsip dan Proses
AWAL
Algoritma dasar untuk proses AWAL (inisialisasi) : Bila L=R+1, maka antrian kososng, dimanapun letak L dan R.
void AWAL(void) { L = 0; R = 1; }
Karena sifat antrian, maka pada saat awal, 'terpaksa' L dan R diletakkan di 0 dan -1.
0 Jumlah antrian cukup ditentukan oleh posisi L dan R, tidak perlu menggunakan Counter seperti pada Circular Queue.
1
2
3
4
5
6
Q[ ]
R
L
0
1
L
R
X
7
8
n-1 9
3. Double Ended Queue (Deque) Antrian dengan ujung ganda c. Prinsip dan Proses Insert kiri void INSERT_KIRI(void) { if ( L > 0 ) {L = L 1; Q[L] = X; } Else printf(“Antrian Kiri Penuh”) }
Insert kanan
void INSERT_KANAN(void) { if (R
Sebelum insert kiri, periksa apakah bisa diisi dari kiri. L mundur dulu 1 langkah. (L–1) Isi ditempat yang ditunjuk oleh L. Sebelum insert kanan, periksa apakah bisa diisi dari kanan. R maju dulu 1 langkah. (R+1) Isi ditempat yang ditunjuk oleh L.
3. Double Ended Queue (Deque) Antrian dengan ujung ganda c. Prinsip dan Proses Delete kiri
Sebelum delete kiri, periksa apakah antrian ada isinya.
void DELETE_KIRI(void) { if (L < R+1) {X = Q[L]; L = L + 1; } Else printf(“Antrian Kosong”) }
Ambil elemen yng ditunjuk oleh L yaitu Q[L]. Setelah itu L maju 1 langkah (L+1).
Delete kanan
void DELETE_KANAN(void) { if (L
Sebelum delete kanan, periksa antrian apakah ada isinya. Ambil ditempat yang ditunjuk oleh R yaitu Q[R].
Setelah itu R mundur 1 langkah ( R – 1 ).
3. Double Ended Queue (Deque) Antrian dengan ujung ganda d. Kondisi antrian
1. Kondisi AWAL. Antrian belum diisi. Kondisi
Keterangan
1.
L=0, R=-1
Kondisi awal
2.
L=R+1
KOSONG
3.
L=0
Penuh kiri
4.
R
Bisa insert kanan 0
1
2
3
4
5
6
7
8
n-1 9
Q[ ] R
L
Pada saat ini hanya bisa Insert Kanan di Q[0], Insert Kiri Tidak Bisa
3. Double Ended Queue (Deque) Antrian dengan ujung ganda d. Kondisi antrian
2. Misal masuk 1 pengantri dari kanan. (Insert Kanan) Kondisi
Keterangan
1.
L
Ada isinya
2.
L=0
Penuh kiri
3.
R
Bisa insert kanan 0
Q[ ]
1
2
3
4
5
6
7
8
n-1 9
x L
R
Pada saat ini hanya bisa Insert Kanan di Q[1], Insert Kiri Tidak Bisa
3. Double Ended Queue (Deque) Antrian dengan ujung ganda d. Kondisi antrian
3. Misal masuk lagi 3 pengantri dari kanan. (Insert Kanan) Kondisi
Keterangan
1.
L
Ada isinya
2.
L=0
Penuh kiri
3.
R
Bisa insert kanan 0
Q[ ]
2
3
4
5
6
7
8
x x x x L
1
n-1 9
R
Insert Kanan di Q[4], Insert Kiri Tidak Bisa
3. Double Ended Queue (Deque) Antrian dengan ujung ganda d. Kondisi antrian
4. Misal keluar 1 pengantri dari kiri. (delete kiri) Kondisi
Keterangan
1.
L
Ada isinya
2.
L>0
Bisa insert kiri
3.
R
Bisa insert kanan 0
Q[ ]
1
3
4
5
6
7
8
x x x L
2
n-1 9
R
Insert Kanan di Q[4], Insert Kiri di Q[0]
3. Double Ended Queue (Deque) Antrian dengan ujung ganda d. Kondisi antrian
5. Misal masuk lagi 3 pengantri dari kanan. (INSERT KANAN) Kondisi
Keterangan
1.
L
Ada isinya
2.
L>0
Bisa insert kiri
3.
R
Bisa insert kanan 0
Q[ ]
1
2
3
4
5
7
8
XXXXXX R
L
6
n-1 9
Insert Kanan di Q[7], Insert Kiri di Q[0]
3. Double Ended Queue (Deque) Antrian dengan ujung ganda d. Kondisi antrian
6. Keluar 5 pengantri dari kiri. (DELETE KIRI) Kondisi
Keterangan
1.
L
Ada isinya
2.
L>0
Bisa insert kiri
3.
R
Bisa insert kanan
4.
L=R
Hanya 1 pengantri
0
1
2
3
4
5
6
7
X
Q[ ]
R
8
n-1 9
L
Insert Kanan di Q[7], Insert Kiri di Q[5]
3. Double Ended Queue (Deque) Antrian dengan ujung ganda d. Kondisi antrian
7. Keluar lagi 1 pengantri dari kiri. (DELETE KIRI) Kondisi
Keterangan
1.
L=R+1
Antrian kosong
2.
L>0
Bisa insert kiri
3.
R
Bisa insert kanan
0
1
2
3
4
5
6
7
R
L
8
n-1 9
Q[ ]
Insert Kanan di Q[7], Insert Kiri di Q[6]
3. Double Ended Queue (Deque) Antrian dengan ujung ganda d. Kondisi antrian
8. Masuk 4 pengantri dari kiri. (INSERT KIRI) Kondisi
Keterangan
1.
L=R+1
Antrian kosong
2.
L>0
Bisa insert kiri
3.
R
Bisa insert kanan
0 Q[ ]
1
2
3
4
5
7
8
x4 x3 x2 x1
R
L
6
n-1 9
Insert Kanan di Q[7], Insert Kiri di Q[2]
3. Double Ended Queue (Deque) Antrian dengan ujung ganda d. Kondisi antrian
9. Masuk 2 pengantri dari kanan. (INSERT KANAN) Kondisi
Keterangan
1.
L
Antrian ada isinya
2.
L>0
Bisa insert kiri
3.
R
Bisa insert kanan
0 Q[ ]
1
2
3
4
5
x4 x3 x2 x1
7
8
X X R
L
6
n-1 9
Insert Kanan di Q[9], Insert Kiri di Q[2]
3. Double Ended Queue (Deque) Antrian dengan ujung ganda d. Kondisi antrian
10. Masuk 1 pengantri dari kanan. (INSERT KANAN) Kondisi
Keterangan
1.
L
Antrian ada isinya
2.
L>0
Bisa insert kiri
3.
R=n-1
Penuh kanan
0 Q[ ]
1
2
3
Artinya tidak bisa diisi dari kanan
4
5
x4 x3 x2 x1
7
8
X X X R
L
6
n-1 9
Insert Kanan tidak bisa Insert Kiri di Q[2]
3. Double Ended Queue (Deque) Antrian dengan ujung ganda d. Kondisi antrian
11. Masuk 3 pengantri dari kiri. (INSERT KIRI) Kondisi
Keterangan
1.
L
Antrian ada isinya
2.
L=0
Penuh kiri
3.
R=n-1
Penuh kanan
0 Q[ ]
1
2
x x x
3
4
5
x4 x3 x2 x1
7
8
X X X R
L
6
n-1 9
Insert Kanan tidak bisa Insert Kiri tidak bisa
3. Double Ended Queue (Deque) Antrian dengan ujung ganda d. Kondisi antrian
12. Seluruh pengantri keluar dari kiri. (DELETE KIRI) Kondisi
Keterangan
1.
L=R+1
Antrian kosong
2.
L>0
Bisa insert kiri
3.
R=n-1
Penuh kanan
0
1
2
3
4
5
6
7
8
n-1 9
Q[ ]
Insert Kanan tidak bisa Insert Kiri di Q[9]
R
L
3. Double Ended Queue (Deque) Antrian dengan ujung ganda d. Kondisi antrian Kondisi antrian
Ciri
a.
KOSONG
L = R + 1 dimana saja
b.
PENUH KIRI
L=0
c.
PENUH KANAN
R=n-1
d.
BISA DIISI dari KIRI
L>0
e.
BISA DIISI dari KANAN
R
f.
ADA ISINYA
L
