TUGAS QUEUE

1)      Jelaskan perbedaan antara queue dengan stack.

2)      Buatlah contoh program dari Queue.

3)      Sebutkan contoh Queue yang Anda terapkan dalam kehidupan sehari – hari.

4)      Jelaskan konsep dari operasi – operasi Queue.

5)      Apa saja kondisi yang harus diperhatikan dalam operasi – operasi Queue

Perbedaan Antara Queue Dengan Stack

Perbedaan antara stack dan queue terdapat pada aturan penambahan dan penghapusan elemen. Pada stack, operasi penambahan dan penghapusan elemen dilakukan di satu ujung. Elemen yang terakhir kali dimasukkan akan berada paling dekat dengan ujung atau dianggap paling atas sehingga pada operasi penghapusan, elemen teratas tersebut akan dihapus paling awal, sifat demikian dikenal dengan LIFO.

Sedangkan Pada queue, operasi tersebut dilakukan di tempat yang berbeda. Penambahan elemen selalu dilakukan melalui salah satu ujung, menempati posisi di belakang elemen-elemen yang sudah masuk sebelumnya atau menjadi elemen paling belakang. Sedangkan penghapusan elemen dilakukan di ujung yang berbeda, yaitu pada posisi elemen yang masuk paling awal atau elemen terdepan. Sifat yang demikian dikenal dengan FIFO.

Contoh Program Dari Queue

PROGRAM QUEUE01;

uses wincrt;

const MAX=50;

type

larik = Array[0..MAX] of char;

RecQueue = RECORD

info : larik;

awal : integer;

akhir : integer;

END;

var

antri : RecQueue;

pilih,elm : char;

procedure init;

begin

antri.awal := 0;

antri.akhir := 0;

end;

function Isfull:boolean;

begin

if antri.akhir = MAX then

Isfull := true

else

Isfull := false;

end;

            function IsEmpty:boolean;

            begin

            if antri.akhir = 0 then

            Isempty := true

            else

            Isempty := false;

            end;

            procedure baca;

            var i:integer;

            begin

            writeln('Isi queue sekarang : ');

            for i := antri.awal to antri.akhir do

            write(antri.info[i], ' ');

            writeln('');

            end;

procedure inQueue(elemen:char);

begin

if Isempty = true then

begin

antri.awal := 1;

antri.akhir:= 1;

antri.info[antri.awal] := elemen;

end

else if Isfull <> true then

begin

antri.akhir := antri.akhir + 1;

antri.info[antri.akhir]:=elemen;

end

else

writeln('Queue overflow...');

end;

function deQueue:char;

var isi:char;

i : integer;

begin

if Isempty <> true then

begin

isi := antri.info[antri.awal];

for i:=antri.awal to antri.akhir - 1 do

antri.info[i] := antri.info[i+1];

antri.akhir := antri.akhir - 1;

deQueue := isi;

end

else

writeln('Queue underflow...');

end;

BEGIN

CLRSCR;

writeln('--- Demo Queue dg Linear Array ---');

init;

repeat

writeln('OPERASI QUEUE dg Linear Array :');

writeln('[1] InQueue (Insert Queue)');

writeln('[2] DeQueue (Delete Queue)');

writeln('[3] Baca');

writeln('[4] Selesai...');

write(' Pilihan : ');

readln(pilih);

case pilih of

'1' : begin

write('Antrian Masuk : ');

readln(elm);

inQueue(elm);

end;

'2' :

 begin

 elm:=deQueue;

writeln(elm,' Keluar dr antrian');

end;

'3' : baca;

'4' : writeln('Wakarimasuta (?_?)');

else writeln('Salah pilih...');

end;

writeln('');

until (pilih = '4');

readln;

END.

Contoh Queue Yang Anda Terapkan Dalam Kehidupan Sehari – Hari

Ø  Antrian Mobil diloket Tol

Ø   Antrian mahasiswa saat melakukan pendaftaran

Ø   Antrian saat membeli tiket film di bioskop

Ø  Antrian reservasi tiket kereta api

Ø  Antrian saat mengisi BBM SPBU

Ø  Antrian saat melakukan pengecekan tiket dan paspor saat chekin pesawat.

Ø   antrian saat mengambil makanan di pesta

Ø  Antrian saat pergi ke toilet.

Ø   Antrian saat menanti pelayanan teller di bank

Konsep Dari Operasi – Operasi Queue

1. Inisialisasi Queue

Inisialisasi queue adalah proses pemberian nilai 0 untuk field depan dan belakang dari queue dan juga pemberian nilai maks ke maks_queue yang menunjukan banyaknya maksimal data dalam queue. Karena dalam bahasa C elemen sebuah array dimulai dengan 0 maka proses inisialisasi nilai depan dan belakang bukan 0 tetapi -1 sehingga ketika ada proses penambahan elemen (enqueue) akan bernilai 0 sehingga elemen tersebut akan disimpan dalam elemen antrian pada posisi 0.

Implementasi fungsi inisialisasi queue dalam bahasa C adalah :

void inisialisasi (TQueue *Q)
{
Q->maks_queue=maks;
Q->depan=-1;
Q->belakang=-1;
}
Cara pemanggilannya adalah :
Inisialisasi (&Q);

2. Enqueue

Digunakan untuk menambahkan elemen ke dalam Antrian, penambahan elemen selalu ditambahkan di elemen paling belakang. Penambahan elemen selalu menggerakan variabel Tail dengan cara increment counter Tail terlebih dahulu.

Contoh : Seseorang membeli tiket melalui tempat pembayaran tiket yang disediakan.

3. Dequeue

Digunakan untuk menghapus elemen terdepan/pertama (head) dari Antrian. Dengan cara menggeser semua elemen antrian kedepan dan mengurangi Tail dengan 1. Penggeseran dilakukan dengan menggunakan looping.

Contoh : Setelah membeli tiket, langsung menuju tempat penungguan kereta, dengan sebelumnya petugas memeriksa cek tiket tersebut.

4.      IsEmpty()

Untuk memeriksa apakah Antrian sudah penuh atau belum. Dengan cara memeriksa nilai Tail, jika Tail = -1 maka empty. Kita tidak memeriksa Head, karena Head adalah tanda untuk kepala antrian (elemen pertama dalam antrian) yang tidak akan berubah-ubah. Pergerakan pada Antrian terjadi dengan penambahan elemen Antrian kebelakang, yaitu menggunakan nilai Tail.

Contoh : Petugas tiket Kereta melihat tidak ada lagi yang ingin membeli tiket kereta.

5.      IsFull

Untuk mengecek apakah Antrian sudah penuh atau belum. Dengan cara mengecek nilai Tail, jika Tail >= MAX-1 (karena MAX-1 adalah batas elemen array pada C) berarti sudah penuh.

6.      Clear()

Untuk menghapus elemen-elemen Antrian dengan cara membuat Tail dan Head = -1 Penghapusan elemen-elemen Antrian sebenarnya tidak menghapus arraynya, namun hanya mengeset indeks pengaksesan-nya ke nilai -1 sehingga elemen-elemen Antrian tidak lagi terbaca  

7.       Tampil()

Untuk menampilkan nilai-nilai elemen Antrian Menggunakan looping dari head s/d tail

Kondisi Yang Harus Diperhatikan  Dalam Operasi – Operasi Queue

Kondisi antrian yang menjadi perhatian adalah :

1)      Penuh

Bila elemen di antrian  mencapai  kapasitas  maksimum  antrian. Pada kondisi ini, tidak mungkin dilakukan penambahan ke antrian. Penambahan elemen menyebabkan kondisi kesalahan Overflow.

2)      Kosong

Bila tidak ada elemen di antrian. Pada kondisi ini, tidak mungkin dilakukan pengambilan elemen dari antrian. Pengambilan elemen menyebabkan kondisi kesalahan Underflow.

TUGAS STACK

TUGAS

1. Jelaskan konsep dari Stack yang anda ketahui?
2. Berikan masing-masing contoh konsep dari push dan pop?
3. Buatlah program dari Stack !
4. Apa yang anda ketahui tentang ADT
5. Jelaskan konsep Array dalam Stack

KONSEP DARI SATACK

Stack atau Tumpukan adalah suatu struktur data yang terbentuk dari barisan hingga yang terurut dari satuan data. Pada Stack, penambahan dan penghapusan elemennya hanya dapat dilakukan pada satu posisi, yaitu posisi akhir stack. Posisi ini disebut Puncak atau Top dari stack.

Elemen Stack S yang berada pada posisi Top / Puncak dinyatakan dengan : TOP(S).

Jika stack S = [S1 ,S2 , . . . ,ST ] maka : TOP(S) = S T

Sedang banyaknya elemen stack S dinyatakan dengan :

NOEL(S) = T.

Stack pada Struktur Data dapat diilustrasikan dengan dua buah kotak yang ditumpuk, kotak yang satu akan ditumpuk diatas kotak yang lainnya. Jika kemudian stack 2 kotak tadi, ditambah kotak ketiga, keempat, kelima, dan seterusnya, maka akan diperoleh sebuah stack kotak yang terdiri dari N kotak. 

Stack bersifat LIFO (Last In First Out) artinya Benda yang terakhir masuk ke dalam stack akan menjadi yang pertama keluar dari stack 

Operasi-operasi yang biasanya tredapat pada Stack yaitu:

1. Push : digunakan untuk menambah item pada stack pada tumpukan paling atas

2. Pop : digunakan untuk mengambil item pada stack pada tumpukan paling atas

3. Clear : digunakan untuk mengosongkan stack

4. IsEmpty : fungsi yang digunakan untuk mengecek apakah stack sudah kosong

5. IsFull : fungsi yang digunakan untuk mengecek apakah stack sudah penuh

Cara mendefenisikan Stack dengan Array of Struct yaitu:

1. Definisikan Stack dengan menggunakan struct

2. Definisikan konstanta MAX_STACK untuk menyimpan maksimum isi stack

3. Buatlah variabel array data sebagai implementasi stack

4. Deklarasikan operasi-operasi/function di atas dan buat implemetasinya.

contoh :

//Deklarasi MAX_STACK

                #define MAX_STACK 10   

            

//Deklarasi STACK dengan struct dan array data

                typedef struct STACK{

                                int top;

                                char data[10][10];                                                           

                }; 

//Deklarasi/buat variabel dari struct

                STACK tumpuk;

Inisialisasi Stack

Pada mulanya isi top dengan -1, karena array dalam C dimulai dari 0, yang berarti stack adalah kosong.

v   Top adalah suatu variabel penanda dalam STACK yang menunjukkan elemen teratas Stack sekarang.  Top Of Stack akan selalu bergerak hingga mencapai MAX of STACK sehingga menyebabkan stack penuh.

v   IsFull berfungsi untuk memeriksa apakah stack sudah penuh atau tidak. Dengan cara, memeriksa top of stack, jika sudah sama dengan MAX_STACK-1 maka full, jika belum (masih lebih kecil dari MAX_STACK-1)  maka belum full.

v     IsEmpty berfungsi untuk memeriksa apakah stack masih kosong atau tidak. Dengan cara memeriksa top of stack, jika masih -1 maka berarti stack masih kosong.

v  Push berfungsi untuk memasukkan elemen ke stack, selalu menjadi elemen teratas stack (yang ditunjuk oleh TOS).

Tambah satu (increment)  nilai top of stack lebih dahulu setiap kali ada penambahan elemen stack.

Asalkan stack masih belum penuh, isikan data baru ke stack berdasarkan indeks top of stack setelah diincrement sebelumnya.

v  Pop berfungsi untuk mengambil elemen teratas (data yang ditunjuk oleh TOS) dari stack. Ambil dahulu nilai elemen teratas stack dengan mengakses top of stack, tampilkan nilai yang akan dipop, baru dilakukan decrement nilai top of stack sehingga jumlah elemen stack berkurang.

v   Print berfungsi untuk menampilkan semua elemen-elemen stack dengan cara looping semua nilai array secara terbalik, karena kita harus mengakses dari indeks array tertinggi terlebih dahulu baru ke indeks yang kecil.

v   create berfungsi untuk membuat sebuah stack baru yang masih kosong.

Contoh Konsep Dari Push Dan Pop

Ø    Konsep Push

Push berfungsi untuk memasukkan elemen ke stack, selalu menjadi elemen teratas stack. Tambah satu (increment)  nilai top of stack lebih dahulu setiap kali ada penambahan elemen stack. Asalkan stack masih belum penuh, isikan data baru ke stack berdasarkan indeks top of stack setelah diincrement sebelumnya. Contoh : misalkan dalam sebuah lemari ingin disusun beberapa baju. Sedangkan dalam lemari tersebut sudah terisi dengan beberapa baju,maka terlebih dahulu dilakukan pengecekan kapasitasnya apa masing ada tempat kosong atau tidak, apabila masih tersisa ruang maka boleh diisi lagi dengan baju- baju di atasnya.

Ø  Konsep Pop

Pop berfungsi untuk mengambil elemen teratas (data yang ditunjuk oleh TOS) dari stack. Ambil dahulu nilai elemen teratas stack dengan mengakses top of stack, tampilkan nilai yang akan dipop, baru dilakukan decrement nilai top of stack sehingga jumlah elemen stack berkurang. Contohnya : misalkan ada sebuah tumpukan kotak dan kita ingin mengambil kotak yang berada di tengah – tengah, hal yang pertama yang harus kita lakukan adalah memindahkan kotak – kotak yang ada diatasnya, hingga kotak yang dibutuhkan dapat terambil.

Contoh program dari Stack

program stack;

uses wincrt;

const max = 10;

var

L : array [1..max] of char;

sisa, i, j, top : integer;

jawab : char;

kondisi : string;

procedure inisiasi;

begin

top :=0;

end;

procedure CEK;

begin

sisa := max - top;

if top = max then

kondisi := 'penuh'

else

if ((top < max) and (top > 0)) then

kondisi := 'belum penuh'

else

kondisi := 'kosong'

end;

procedure PUSH;

begin

write('Masukan data : ');

readln(L[top+1]);

top := top + 1;

end;

procedure TAMPIL;

begin

writeln('Stack Yang Dihasilkan : ');

for i := top downto 1 do

begin

writeln(L[i]);

end;

procedure POP;

begin

top := top - 1

end;

BEGIN

clrscr;

inisiasi;

jawab := 'Y';

while ((jawab = 'Y') or (jawab = 'y')) do

begin

writeln('PROGRAM STACK');

writeln('1. PUSH');

writeln('2. POP');

write('PILIH 1 ATAu 2 ?  ');

readln(j);

case j of

1 : begin

CEK;

if kondisi = 'penuh' then

writeln('STACK PENUH, ANDA TIDAK BISA MENAMBAH TUMPUKAN')

else

begin

if kondisi <> 'penuh' then

begin

CEK;

writeln ('Stack ', kondisi, ', Masih Bisa Menampung : ', sisa, ' data');

write ('Apakah Anda mau Menambah Data ? (Y/T)  ');

readln (jawab);

while (((jawab = 'Y') or (jawab = 'y')) and (kondisi <> 'penuh')) do

begin

PUSH;

writeln;

writeln;

CEK;

writeln;

writeln;

TAMPIL;

writeln;

writeln;

writeln ('Stack ', kondisi, 'Masih Bisa Menampung : ', sisa, ' data');

write ('Apakah Anda mau Menambah Data ? (Y/T)  ');

readln (jawab);

end;

end

else

writeln ('STACK PENUH');

end;

end;

2 : begin

write ('Apakah Anda Yakin Mau Menghapus Data ? (Y/T)  ');

readln (jawab);

while (((jawab = 'Y') or (jawab = 'y')) and (kondisi <> 'kosong')) do

begin

POP;

writeln;

writeln;

CEK;

writeln;

writeln;

TAMPIL;

writeln;

writeln;

writeln ('Stack Masih Bisa Dihapus : ', top, ' data');

write ('Apakah Anda Mau Menghapus Data ? (Y/T)  ');

readln (jawab);

end;

if kondisi = 'kosong' then

writeln ('STACK KOSONG')

end;

write ('Apakah Mau Kembali Ke Menu Utama ? (Y/T)  ');

readln (jawab);

end;

END.

ADT (ABSTRACT DATA TYPE)

Abstract  Data  Type  (ADT)  adalah  definisi  TYPE  dan  sekumpulan  PRIMITIF  (operasi  dasar) terhadap TYPE tersebut. Definisi TYPE dari sebuah ADT dapat mengandung sebuah definisi ADT lain. 

Misalnya:

•          ADT Waktu terdiri dari ADT JAM dan ADT DATE

•          GARIS yang terdiri dari dua buah POINT

•          SEGI4 yang terdiri dari pasangan dua buah POINT (Top, Left) dan (Bottom,  Right)

TYPE diterjemahkan menjadi type terdefinisi dalam bahasa yang bersangkutan, misalnya menjadi struct  dalam  bahasa  C.  Primitif,  dalam  konteks  prosedural,  diterjemahkan menjadi  fungsi  atau prosedural.

ADT biasanya diimplementasi menjadi dua buah modul, yaitu:

1.Definisi/Spesifikasi Type dan Primitif

•          Spesifikasi type sesuai dengan bahasa yang bersangkutan

•          Spsesifikasi dari primitif sesuai dengan kaidah dalam konteks prosedural, yaitu:

•          Fungsi : nama, domain, range, dan prekondisi jika ada

•          Prosedur : Initial State, Final State, dan Proses yang dilakukan

2. Body/realisasi dari primitif, berupa kode program dalam bahasa yang bersangkutan.

Konsep Array Dalam Stack

Sebuah array dapat kita manfaatkan untuk mengimplementasikan stack jika jumlah elemen maksimum diketahui. Ketika kita hendak meng- implementasikan stack menggunakan array, kita harus memastikan bahwa array yang dideklarasikan cukup untuk menyimpan data atau elemen maksimum pada stack.Untuk menerapkan stack menggunakan array, tentunya kita harus mendeklarasikan array terlebih dahulu. Misalkan :

int stack[10];Pendeklarasian diatas berarti kita membuat sebuah array dengan ukuran/size sebesar 10, dan hanya dapat menampung maksimal 10 nilai integer.

Setelah mendeklarasikan array, kita perlu mendeklarasikan variabel untuk menyimpan index terakhir (top position), misalnya kita deklarasikan seperti ini :

int top;

Untuk kondisi stack yang masih kosong, mari kita set top = -1

Kemudian baru setelah ini kita akan mengimplementasikan operasi PUSH dan POP.

v   PUSH

Dengan menjalankan operasi PUSH, berarti kita menyimpan data pada posisi top didalam stack. Langkah selanjutnya yang dapat kita tempuh adalah :

1. Melakukan increment terhadap top sebesar 1

2. Menyimpan nilai/value pada index top didalam array

(Sekarang top mengandung index dari elemen yang paling atas)

Ketika stack di implementasikan didalam sebuahh array, size/ukuran dari stack adalah fixed. Hal ini berarti terdapat batas atas pada jumlah maksimum elemen yang dapat ditampung dalam stack. Ketika stack sudah menampung data secara maksimum, maka dapat kita berikan status stack telah penuh/full. Ketika kita mencoba melakukan operasi push pada stack yang sudah penuh, maka akan terjadi overflow. Maka dari itu sebelum  kita melakukan operasi push, kita harus melakukan pengecekan apakah stack sudah full atau belum.

Jika stack sudah penuh, maka kondisi stack tsb adalah :

top = MAX -1

Jika kondisi tersebut true, maka operasi push seharusnya tidak dapat dilaksanakan.

Sehingga kita dapat membuat kondisi seperti berikut :

If top = MAX-1:

a. Display “Stack Full”

b. Exit

v   POP

Operasi POP berarti memindahkan atau menghapus item pada posisi top didalam stack. Untuk mengimplementasikannya kita dapat menggunakan langkah berikut ini :

1. Memungut kembali nilai dari index top

2. Melakukan decrement terhadap top sebesar 1

Bagaimanapun juga, sebelum melakukan operasi pop, kita harus melakukan pengecekan apakah stack itu kosong atau tidak. Jika kosong, tentu tidak ada elemen yang harus kita pop. Masih ingat dengan pendeklarasian diatas? Ya, sebelumnya kita telah mendeklarasikan bahwa jika kondisi stack kosong, maka top = -1

Sehingga kita dapat menerapkan kondisi berikut ini :

if top = -1

a. Display “Stack empty”

b. Exit