Pengertian Stack : data struktur
penting yang menyimpan elemen-elemennya dengan kaidahnya tersendiri. (tumpukan)
ilustrasi stack :
Konsep Stack:
·
Stack dapat menggunakan array atau linked list.
· Dapat dibilang Last In First Out.
·
Elemen di stack paling atas dapat
ditambah/dihilangkan. Elemen yang berada di stack paling atas dapat disebut
sebagai TOP.
Representasi di stack : stack
mempunyai 2 variabel yaitu TOP & MAX. jika TOP null maka stack itu kosong. Jika
TOP = MAX-1, maka stack full.
Representasi Linked list di stack
: setiap node mempunyai 2 bagian. Satu yang menyimpan data dan satu yang menyimpan
alamat dari node selanjutnya.
Operasi-operasi yang ada di stack
:
·
Push(x) :
menambahkan elemen x ke bagian teratas dari stack. berfungsi untuk memasukkan sebuah nilai atau data ke dalam stack. Sebelum sebuah nilai atau data dimasukkan ke dalamstack, prosedur ini terlebih dahulu akan menaikkan posisi top satu level ke atas.
·
Pop() :
menghilangkan bagian teratas dari stack.berfungsi untuk mengeluarkan atau menghapus nilai terakhir (yang berada pada posisi paling atas) dari stack, dengan cara menurunkan nilai top satu level ke bawah.
·
Top() :
memunculkan atau mengembalikan bagian teratas stack. Top disebut juga peek.
Infix, Postfix, dan prefix notasi:
·
Prefix :
menuliskan operator sebelum operand. Contohnya : + 4 / * 6 – 5 2 3
·
Infix :
menuliskan operator diantara operand. Contohnya : 4 + 6 * (5 – 2) / 3
·
Postfix :
menuliskan operator setelah operand. Contohnya : 4 6 5 2 – * 3 / +
Depth First Search (DFS) :
algoritma untuk melintasi atau mencari didalam grafik atau pohon. Kita mulai
dari akar sebuat pohon meng-explore sebisa mungkin pada setiap cabang sebelum
backtracking.
Pengaplikasian DFS:
·
menemukan artikulasi point dan bridge di grafik
·
menemukan connected component
·
topological sorting
Queue : sama seperti stack tapi
ini berpua barisan. Elemen-elemen di queue di tambahkan pada bagian akhirnya,
dan penghilangan pada bagian depannya saja. Atau dapat disebut First In First
Out.
"An excellent example of a queue is a line of students in the food court of the UC. New additions to a line made to the back of the queue, while removal (or serving) happens in the front. In the queue only two operations are allowed enqueue and dequeue. Enqueue means to insert an item into the back of the queue, dequeue means removing the front item. The picture demonstrates the FIFO access. The difference between stacks and queues is in removing. In a stack we remove the item the most recently added; in a queue, we remove the item the least recently added."
Operasi – operasi yang ada di queue:
·
Push (x) :
menambahkan item x pada queue paling belakang.
·
Pop() :
menghilangkan item pada bagian depan queue.
·
Front() :
memunculkan dan mengembalikan item paling deoan dari queue .dikenal dengan peek.
Circular Queue : kita dapat
wrap-around index L dan R. jika R mencapai MAXN lalu set R sebagai 0, begitu
juga pada L.
Deques : list di dalam setiap elemen yang dapat
dimasukan atau dihilangkan disetiap bagian akhir. Deques dikenal sebagai
head-tail linked list karena elemen-elemen dapat dimasukan atau dihilangkan
dari depan/belakang.
Dua variasi pada double-ended
queue yaitu Input restricted deque dan output restricted deque.
·
· Priority Queue : tipe data yang abstrak di setiap elemen memiliki prioritas sendiri.
Aturan umum saat
memproses elemen priorias queue yaitu:
·
Elemen dengan prioritas tertinggi di proses
sebelum elemen dengan prioritas yang rendah
· Dua elemen yang memiliki prioritas yang sama
akan diproses elemen yang dating duluan
Breadth First
Search (BFS) = seperti DFS.
x
No comments:
Post a Comment