Queue Dan Stack

Queue ( Antrian )

Queue [antrian]  adalah kumpulanan data  yg penambahan elemennya dilakukan dengan penyisipan di suatu ujung, dan  penghapusan elemen di ujung lainnya. Ujung penyisipan biasa disebut tail (ekor/belakang), sedangkan ujung penghapusan disebut head(kepala/depan).  Aturan yang digunakan pada operasi Queue  adalah elemen yang lebih dulu masuk akan keluar lebih dulu. Queue mempunyai prinsip FIFO (First In, First Out).

Ilustrasi yang dapat digambarkan dalam operasi Queue itu seperti dalam memasuki sebuah pintu loket suatu tempat, orang yang pertama masuk lalu tiketnya dicek oleh penjaga akan pertama kali dibolehkan masuk ke tempat tujuan ( keluar pertama dari antrian ).

  Karakteristik dalam Queue atau antrian yaitu :

•      Elemen antrian yaitu item-item data yang terdapat di elemen antrian.
•      Head/front (elemen terdepan dari antrian ).
•      Tail/rear (elemen terakhir dari antrian ).
•      Jumlah elemen pada antrian (count).
•      Status/kondisi antrian.

  Kondisi pada pengoperasian Queue :

•       Penambahan elemen (penambahan data pada sisi belakang antrian)
•       Penghapusan elemen (menghapus data pada sisi depan antrian)
•       Penuh ( jumlah antrian telah mencapai batas max, dan tidak bisa menambahkan elemen baru lagi karna penambahan diatas max menyebabkan  terjadinya kondisi Overflow ).
•       Kosong (jika tidak ada elemen dalam antrian, maka tidak dapat melakukan pengambilan elemen dari antrian. Pengambilan elemen dapat menyebabkan terjanya kondisi Underflow ).

   A.    Operasi yang terdapat dalam Queue :

•      createQueue (Q),constructor menciptakan antrian kosong Q.
•      addQueue (Q, X) memasukkan elemen X sebagai elemen akhir di Q.
•      removeQueue (Q, X) mengambil elemen depan di antrian Q ke elemenX.
•      headQueue (Q), atau Front (Q, X) mengirim elemen terdepan tanpa menghapus.
•      tailQueue (Q), mengirim elemen tanpa menghapusnya.

  B. Operasi-0perasi yang dapat ditambahkan  :

1.isEmptyQueue (Q)  ( mengirim apakah antrian Q adalah kosong. )

2.isFullQueue (Q)   ( mengirim apakah antrian Q adalah penuh bila kapasitas antrian Q didefinisikan.)

3.isOverflowQueue (Q),   (  mengirim apakah antrian Q telah mengalami overflow. )

4.isUnderflowQueue (Q), ( mengirim apakah antrian Q mengalami underflow.)

  C. Operasi umum terhadap seluruh antrian Queue  :

•     sizeQueue (Q), mengetahui jumlah elemen di antrian Q.
•     isEqualQueue (Q1, Q2), mengirim apakah antrian Q1 dan Q2 sama isinya.

Manfaat penggunaan operasi antrian Queue : 

•      Antrian pembelian tiket di depan loket kereta api, bis, bioskop.
•      Antrian kendaraan roda empat di gerbang jalan tol
•      Antrian kendaraan dijalanan umum.

Stack ( Tumpukan )

Kumpulan items yang teratur dimana items baru akan dimasukkan ke dan sebuah items akan dikeluarkan dari satu ujung yang sama, yaitu dari TOP sebuah stack.Struktur data linier dimana hanya bagian TOP-nya saja yang bisa diakses.Bersifat LIFO = Last In First Out. Bisa diimplementasikan menggunakan array atau Linked List.

Ilustrasi Stack

Terdapat 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

OPERASI PADA STACK

2 operasi dasar yang bisa dilaksanakan

pada sebuah stack, yaitu:

Operasi Push (menyisipkan data)‏

memasukkan data ke dalam stack

Operasi Pop (menghapus data)‏

menghapus elemen yang terletak pada posisi paling atas dari sebuah stack

langkah-lngkah :

1. buat stack (stack) – create

membuat sebuah stack baru yang masih kosong

spesifikasi:

• tujuan : mendefinisikan stack yang kosong
• input : stack
• syarat awal : tidak ada
• output stack : – (kosong)‏
• syarat akhir : stack dalam keadaan kosong

2. stack kosong (stack) – empty

fungsi untuk menentukan apakah stack dalam keadaan kosong atau tidak

spesifikasi:

• tujuan : mengecek apakah stack dalam keadaan kosong
• input : stack
• syarat awal : tidak ada
• output : boolean
• syarat akhir : stack kosong bernilai true jika stack dalam keadaan kosong

3. stack penuh (stack) – full

fungsi untuk memeriksa apakah stack yang ada sudah penuh

spesifikasi:

• tujuan : mengecek apakah stack dalam keadaan penuh
• input : stack
• syarat awal : tidak ada
• output : boolean
• syarat akhir : stack penuh bernilai true jika stack dalam keadaan penuh

4. push (stack, info baru)‏

menambahkan sebuah elemen kedalam stack.

spesifikasi:

• tujuan : menambahkan elemen, info baru pada stack pada posisi paling atas
• input : stack dan Info baru
• syarat awal : stack tidak penuh
• output : stack
• syarat akhir : stack bertambah satu elemen

5. pop (stack, info pop)‏

mengambil elemen teratas dari stack

spesifikasi:

• tujuan : mengeluarkan elemen dari stack yang berada pada posisi paling atas
• input : stack
• syarat awal : stack tidak kosong
• output : stack dalam info pop

syarat akhir : stack berkurang satu elemen

contoh source code tentang programan yang mampu melakukan pengecekan terhadap sebuah string yang di dalamnya mengandung satu atau beberapa pasang tanda delimeter yaitu tanda kurung biasa buka dan tutup ‘( )’, tanda kurung kurawal buaka dan tutup ‘{ }’,serta tanda kurung siku buka dan tutup ‘[ ]’. Program mengeluarkan pernyataan ‘benar’, jika struktur string sudah benar dan sebaliknya menguarkan pernyataan ‘salah’ jika struktur string salah. (ada tanda delimeter yang tidak mempunyai pasangan). Program harus mengimplementasikan struktur data stack dengan menggunakan array.