Skip to main content

Stack & Queue


Stack
Stack adalah kumpulan elemen data yang disimpan dalam satu laju linear. Kumpulan elemen-elemen data hanya boleh diatas pada posisi atas (top) tumpukan. Tumpukan digunakan dalam parsing, evaluation, dan backtrack. Elemen-elemen di dalam tumpukan dapat bertipe integer, real, record dalam bentuk sederhana ataupun terstruktur.
Konsep utama dari stack yaitu LIFO (Last in First Out), benda yang terakhir masuk ke dalam stack akan menjadi benda pertama yang dikeluarkan dari stack. Tumpukan atau stack mempunyai istilah pop dan push. Pop adalah penambahan elemen baru ke dalam tumpukan, sedangkan Push adalah penarikan atau penghapusan elemen yang paling atas dari tumpukan. Baik penambahan elemen maupun penghapusan elemen akan selalu dilakukan pada bagian akhir data yang selalu disebut top of stack ( karena data terakhir selalu terletak di bagian atas tumpukan ).

Terdapat beberapa operasi yang sering digunakan dalam struktur data stack. Operasi yang paling umum digunakan adalah push dan pop. Beberapa operasi yang sering digunakan yaitu :
1.     Push digunakan untuk menambah item pada tumpukan paling atas
2.     Pop digunakan untuk mengambil item pada tumpukan paling atas
3.     Clear digunakan untuk mengosongkan stack
4.     Create stack digunakan untuk membuat tumpukan baru dengan jumlah elemen kosong
5.     MakeNull digunakan untuk mengosongkan tumpukan dan menghapus semua elemen ( jika terdapat elemen)
6.     IsEmpty untuk mengecek apakah stack sudah kosong
7.     IsFull untuk mengecek apakah stack sudah penuh
Terdapat juga istilah overflow dan underflow, dimana overflow adalah keadaan dimana stack tidak bisa menampung elemen baru karena jumlah elemen sudah mencapai maksimum, sedangkan underflow adalah keadaan dimana terdapat stack kosong dan tidak ada elemen yang bisa diambil lagi.


Macam – Macam Stack
1)     Stack dengan Array
Sesuai dengan sifat stack, pengambilan ataupun penghapusan elemen dalam stack harus dimulai dari elemen teratas

2)     Double Stack dengan Array
Teknik khusus untuk menghemat pemakaian memori dalam pembuatan dua stack dengan array. Intinya adalah penggunaan hanya sebuah array untuk menampung dua stack


Queue
Queue merupan struktur data linear. Konsepnya hamper sama dengan stack, perbedaannya adalah operasi penambahan dan penghapusan pada ujung yang berbeda. Penghapusan dilakukan pada bagian depan (front), sedangkan penambahan dilakukan pada bagian belakang (rear). Elemen-elemen di dalam antrian dapat bertipe integer, real, record dalam bentuk sederhana atau terstruktur.
Queue juga disebut waiting line yaitu penambahan elemen baru dilakukan pada bagian belakang dan penghapusan elemn dilakukan pada bagian depan. Sistem pengaksesan queue menggunakan sistem FIFO (First in First Out), artinya elemen pertama yang masuk itu yang akan pertama dikeluarkan dari queue . Queue juga merupakan salah satu contoh dari double linked list.
Istilah yang dipakai apabila seseorang masuk ke dalam antrian disebut enqueue, sedangkan apabiala sesorang keluar dari antrian disebut dequeue
Beberapa operasi dalam queue :

§  Create Queue : membuat antrian baru Q, dengan jumlah elemen kosong
§  Make Null : mengosongkan antrian Q, dengan jumlah elemen kosong
§  Enqueue : berfungsi untuk memasukkan data baru ke belakang antrian
§  Dequeue : berfungsi untuk mengeluarkan data terdepan dari antrian
§  Clear : menghapus semua antrian
§  IsEmpty : memeriksa apakah barisan kosong
§  IsFull : memeriksa apakah barisan penuh

Comments

Post a Comment

Popular posts from this blog

Summary of Data Structures ( 1st Semester )

Single Linked List Circular Single Linked List Circular adalah Single Linked List yang pointer selanjutnya menunjuk ke dirinya sendiri. Jika terdiri dari beberapa node, maka pointer next pada node terakhir akan menunjuk ke pointer terdepan.            Single :  artinya field pointer-nya hanya satu buah saja dan satu arah. Circular :  artinya pointer next-nya akan menunjuk ke dirinya sendiri sehingga akan membuat sebuah sirkuit atau sirkular Ilustrasi -           Setiap node pada linked list mempunyai field yang berisi pointer ke node berikutnya yang juga memiliki field yang berisi data -           Pada akhir linked list, node terakhir akan menunjuk ke node terdepan sehingga linked list tersebut berputar. Node terakhir akan menunjuk lagi ke head. Rangkaian Single Linked List tersebut diawali dengan sebuah head un...
Post a Comment
Read more

AVL Tree

AVL Tree adalah Binary Tree yang sudah dapat melakukan self-balancing terhadap node di dalam tree-nya Dalam AVL Tree, terdapat 3 komponen utama yaitu: Key / Data yang bersifat unik Level ( perhitungan dari root sampai node / leaf terjauh ) Balance Factor ( perbedaan level dari anak kiri dan anak kanan ) Dalam Gambar, yang diberi warna biru muda memiliki: Key = 75 Level = 3 ( dihitung dari key 100, key 50, dan key 75 ) Balance Factor = 0, yang dilihat dari level anak kiri 75 yaitu, 65 dan anak kanan 75 yaitu, 85, maka 1-1 = 0 Balance Factor dapat dilihat sebagai berikut :  Leaves selalu memiliki balance factor 0 dan level 1 karena leaves adalah node terujung dan tidak memiliki anak  Dari leaves ke induknya, maka balance factor dan level dihitung dengan ketentuan:  Level Induk = [Level tertinggi anak] + 1 Balance Factor = [Level anak kiri] - [Level anak kanan] Sebuah node tidak boleh memiliki Balance Factor lebih dari 1. Jika terdapat node y...
Post a Comment
Read more

Heap & Tries

Heap Heap adalah struktur data yang berbentuk pohon yang merupakan jenis dari binary tree. Heap juga mempunyai karakter dimana masing-masing node mempunyai maksimum dua children sebagaimana terdapat di dalam binary tree. Heap juga merupakan complete binary tree yang memenuhi sifat - sifat heap. Heap Property Min Heap dimana setiap key dalam node bernilai lebih kecil dari children-nya Max Heap dimana setiap key dalam node bernilai lebih besar dari children-nya Min Heap Setiap key dalam node bernilai lebih kecil dari key children-nya. Key yang bernilai paling kecil berada di root. Key yang bernilai paling besar berada di salah satu dari node leaves. Heap bisa diimplementasikan menggunakan linked list, namun lebih mudah diimplementasikan dengan menggunakan array Applications of Heaps Heap Sort Selection Algorithm Graph Algorithm Selection Algorithm menemukan key minimum atau maksimum, mencari median, dan menentukan elemen k ter...
Post a Comment
Read more