List, Stack, Queue

List, Stack, Queue

Tujuan :

Setelah  mengikuti  perkuliahan  ini,  mahasiswa

diharapkan mampu :

1. Memahami algoritma list, stack dan queue

•LIST

•STACK

•QUEUE

List

•Struktur data yang dibangun dari satu atau lebih node yang menempati alokasi memori secara dinamis.

•Linked list salah satu bentuk struktur data, berisi kumpulan data (node) yang tersusun secara sekuensial, saling sambung-menyambung, dinamis dan terbatas

List

•Node (simpul) :

- Data value

 - Reference to the next node

•Head

•Tail

Daftar Kegiatan di pagi hari

•Menggosok Gigi

•Mandi

•Membersikan tempat tidur

•Sarapan

•Menyisir rambut

•Berangkat Kuliah

Daftar Kegiatan di pagi hari

2 Menggosok Gigi

1 Mandi

4 Membersikan tempat tidur

5 Sarapan

3 Menyisir rambut

6 Berangkat Kuliah

Daftar Kegiatan di pagi hari

Menggosok Gigi  Mandi

Membersihkan

tempat tidur

Sarapan 

Menyisir Rambut

Sarapan

BerangkatKuliah

Konsep List

Daftar Kegiatan di pagi hari

Menggosok Gigi  Mandi

Struktur Data– Yeni Dwi Rahayu, S.ST

Membersihkan

tempat tidur

Sarapan  Menyisir Rambut

SarapanBerangkat

Kuliah

Konsep List

Daftar Kegiatan di pagi hari

(dirapikan)

Mandi  Menggosok Gigi  Menyisir Rambut

Sarapan

Berangkat Kuliah

TAIL

Membersihkan

tempat tidur

NODE  Data Value

Reference to the next node

Operasi List

1. Inisialisasi

2. isEmpty

3. size

4. Penambahan

5. Penghapusan

6. Penyisipan

7. Pencarian

8. Pengaksesan

Ilustrasi : addFirst(x)

Kondisi awal pada linked list :

  a    b    c    d

head

Menambahkan X pada lokasi paling depan.  

Node input

x

Setelah penambahan node x didepan:

  x    b    c    d  a

head New

Struktur Data– Yeni Dwi Rahayu, S.ST Ilustrasi : addLast(x) 

Kondisi awal pada linked list :

  a    b    c    d

Menambahkan X pada lokasi paling belakang.  

Node input

x

Setelah penambahan node x dibelakang :

Struktur Data– Yeni Dwi Rahayu, S.ST

tail

  x

  b    c    d  a

tail  New Ilustrasi : Insert After(a)

  a    b    c    d

temp

Menyisipkan X  pada lokasi setelah temp.  

  a    b

  c    d  x

 x

temp

Struktur Data– Yeni Dwi Rahayu, S.ST  Linked Lists: menghapus elemen X

• Proses menghapus dilakukan dengan mengabaikan elemen

yang hendak dihapus dengan cara melewati pointer

(reference) dari elemen tersebut langsung pada elemen

selanjutnya.

• Elemen x dihapus dengan meng-assign  field next pada

elemen a dengan alamat b.

  a

temp

Hapus

 x    b    c    d

•LIST

•STACK

•QUEUE

Struktur Data– Yeni Dwi Rahayu, S.ST Stack

•Stack adalah sekelompok item sejenis

dari sebuah elemen.

•Elemen ditambahkan dan dihapus dari

tumpukan yang paling atas (item paling

baru ditambahkan pada tumpukan

yang paling atas).

•Elemen yang ditambahkan paling akhir

akan dihapus pertamakali (LIFO: Last

In, First Out).

Struktur Data– Yeni Dwi Rahayu, S.ST Tumpukan

Buku

Stack

Tumpukan Koin  Tumpukan Ban

Tumpukan

Baju

Struktur Data– Yeni Dwi Rahayu, S.ST

Tumpukan

Piring PUSH(20)

Ilustrasi

20

Struktur Data– Yeni Dwi Rahayu, S.ST PUSH(35)

Ilustrasi

35

20

Struktur Data– Yeni Dwi Rahayu, S.ST PUSH(70)

Ilustrasi

70

35

20

Struktur Data– Yeni Dwi Rahayu, S.ST Pop()

Ilustrasi

35

20

Struktur Data– Yeni Dwi Rahayu, S.ST Pop()

Ilustrasi

20

Struktur Data– Yeni Dwi Rahayu, S.ST PUSH(90)

Ilustrasi

90

20

Struktur Data– Yeni Dwi Rahayu, S.ST Operasi Stack

Operasi Dasar :

1. PUSH

2. POP

Operasi Pendukung

1. MakeEmpty      

2. Boolean IsEmpty

3. Boolean IsFull

Struktur Data– Yeni Dwi Rahayu, S.ST •LIST

•STACK

•QUEUE

Struktur Data– Yeni Dwi Rahayu, S.ST Queue

•Queue (antrian) adalah struktur data

dimana proses pengambilan dan

penambahan element dilakukan pada

ujung yang berbeda.

•Queue mengikuti konsep FIFO.

•FIFO (First In First Out) : elemen yang

pertama masuk akan menjadi elemen

yang pertama kali keluar.

Struktur Data– Yeni Dwi Rahayu, S.ST Ilustrasi

Struktur Data– Yeni Dwi Rahayu, S.ST Operasi Queue

1. Deklarasi

2. Inisialisasi

3. Cek kosong

4. Cek penuh

5. Penambahan

6. Pengambilan

7. Pengaksesan

Struktur Data– Yeni Dwi Rahayu, S.ST Tugas Kelompok

1. Buat 4 Kelompok

2. Pembahasan Masing-masing Kelompok :

a) Stack dengan Array (Kelompok 1)

b) Stack dengan List (Kelompok 2)

c) Queue dengan Array (Kelompok 3)

d) Queue dengan List (Kelompok 4)

3. Kelompok 1 & 2 Presentasi Tgl 9 April

4. Kelompok 3 & 4 Presentasi Tgl 16April

Struktur Data– Yeni Dwi Rahayu, S.ST