Struktur Data & Algoritme (Data Structures & Algorithms)

Struktur Data & Algoritme (Data Structures & Algorithms) Stacks & Queues

Denny ([email protected]) Suryana Setiawan ([email protected]) Fakultas Ilmu Komputer Universitas Indonesia Semester Genap - 2004/2005 Version 2.0 - Internal Use Only

Review „

Abstract data type (ADT) „

Kumpulan obyek dan metoda operasi yang mempresentasikan sifat-sifat abstrak bagi "user" dengan menyembunyikan bagaimana semua itu direpresentasikan dalam representasi data level yang lebih rendah

SDA/ST-Q/V2.0/2

1

Objectives „ „

Memahami cara kerja dan kegunaan Stack & Queue Dapat mengimplementasi stack dan queue

SDA/ST-Q/V2.0/3

Outline „

ADT Stacks „ Basic operations „ Examples of use „ Implementations

„

ADT Queues „ Basic operations „ Examples of use „ Implementations

• Array-based and linked list-based

• Array-based and linked list-based

SDA/ST-Q/V2.0/4

2

Struktur data linear „

kumpulan komponen-komponen yang tersusun membentuk satu garis linear

„

Stack: struktur data linear dimana penambahan atau pengurangan komponen dilakukan di satu ujung saja.

„

Queue: struktur data linear dimana penambahan komponen dilakukan di satu ujung, sementara pengurangan dilakukan di ujung lain (yang satu lagi).

„

Kedua struktur tersebut merupakan struktur data abstrak dimana implementasi pada tingkat lebih rendah dapat menggunakan struktur sequential (array) atau struktur berkait (linear linked-list).

SDA/ST-Q/V2.0/5

Stack „ „ „

Semua akses dibatasi pada elemen yang paling akhir disisipkan Operasi-operasi dasar: push, pop, top. Operasi-operasi dasar memiliki waktu yang konstan

pop, top

push

Stack SDA/ST-Q/V2.0/6

3

Contoh-contoh di dunia luar komputer Stack of papers „ Stack of bills „ Stack of plates Waktu O ( 1 ) per operasi stack. (Dengan kata lain, waktu konstan per operasi, tidak bergantung berapa banyak item yang tersimpan dalam stack). „

„

SDA/ST-Q/V2.0/7

Aplikasi-aplikasi „

„

„

Stack dapat digunakan untuk memeriksa pasangan tanda kurung (Balanced Symbol), pasanganpasangan seperti {}, (), []. Misalnya: {()} boleh, dan {(}) tidak boleh (tidak dapat dilakukan dengan penghitungan simbol secara sederhana). Saat mendapatkan tanda kurung tutup, ia harus merupakan pasangan kurung buka yang paling terakhir ditemukan. Jadi, stack akan membantu pemeriksaan ini.

SDA/ST-Q/V2.0/8

4

Balanced Symbol Algorithm „ „

Buat stack baru yang kosong. Secara berulang baca token-token; jika token mrpk „ Kurung buka, push token ke dalam stack „ Kurung tutup, maka • If stack kosong, then beri pesan error; • otherwise pop stack dan periksa apakah simbol yang dipop dari stack merupakan pasangannya (jika tidak beri pesan error)

„

Di akhir file, jika stack tidak kosong, beri pesan salah.

SDA/ST-Q/V2.0/9

Contoh „

Input: {()} „ Push ‘{’ „ Push ‘(’; lalu stack berisikan ‘{’, ‘(’ „ Pop; popped item adalah ‘(’ yang adalah pasangan dari ‘)’. Stack sekarang berisikan ‘{’. „ Pop; popped item adalah ‘{’ yang adalah pasangan dari ‘}’. „ End of file; stack kosong, jadi input benar.

SDA/ST-Q/V2.0/10

5

Performance „ „

Running time adalah O (N), yang mana N adalah jumlah data (jumlah token). Algoritma memproses input secara sikuensial, tidak perlu backtrack (mundur).

SDA/ST-Q/V2.0/11

Pemanggilan Stack „

„ „

Matching symbol serupa dengan method call dan method return, karena saat terjadi suatu method return, ia kembali ke method aktif yang paling akhir. Call stack dapat digunakan untuk menangani hal ini. Abstract idea: ketika suatu method call terjadi, simpan current state dalam stack. Saat return, kembalikan state dengan melakukan pop stack.

SDA/ST-Q/V2.0/12

6

Activation Records „ „ „ „

Actual implementation is slightly different (note that text describes the abstract implementation). The top of stack can store the current method environment. When method is called, the new environment is pushed onto stack. On return, old environment is restored by pop

SDA/ST-Q/V2.0/13

Applikasi Lainnya „ „ „

Penghapusan Recursion dapat dilakukan memanfaatkan stack Operator precedence parsing (di kuliah berikutnya: TBA) Pembalikan urutan (Reversing) dapat dengan mudah dilakukan dengan bantuan stack

SDA/ST-Q/V2.0/14

7

Implementasi Array „

„ „ „

Stack dapat diimplementasi dengan suatu array dan suatu integer top yang mencatat indeks dalam array dari top of the stack. Untuk stack kosong maka top berharga -1. Saat terjadi push, lakukan dengan increment counter top, dan tulis ke dalam posisi top tsb dalam array. Saat terjadi pop, lakukan dengan decrement counter top.

SDA/ST-Q/V2.0/15

Stages

Push A

Push B

B A

top(0)

top(1)

A

top(-1)

SDA/ST-Q/V2.0/16

8

Array Doubling „

„

„

Jika stack full (karena semua posisi dalam array sudah terisi), kita dapat memperbesar array, menggunakan array doubling. Kita mengalokasi yang array baru dengan ukuran dua kali lipat semula, dan menyalin isi array yang lama ke yang baru: Object [] oldArray = array; array = new Object [oldArray.length * 2 ]; for (int j = 0; j < oldArray.length; j++) array[j] = oldArray[j]; Amortization technique

SDA/ST-Q/V2.0/17

Running Time „

„

Tanpa adanya array doubling, setiap operasi memiliki waktu konstan, dan tidak bergantung pada jumlah item di dalam stack. Dengan adanya array doubling, satu operasi push dapat (namun jarang) menjadi O(N). Namun, pada dasarnya adalah O(1) karena setiap array doubling yang memerlukan N assignments didahului oleh N/2 kali push yang non-doubling.

SDA/ST-Q/V2.0/18

9

Implementasi Linked-List „ „

„

item pertama dalam list = top of stack push: „ create suatu node baru „ Sisipkan sebagai elemen pertamadalam list pop: „ Memajukan top ke item kedua dalam list

d

c

b

a

topOfStack SDA/ST-Q/V2.0/19

Queue „ „ „

Setiap akses dibatasi ke elemen yang paling terdahulu disisipkan Operasi-operasi dasar: enqueue, dequeue, getFront. Operasi-operasi dengan waktu konstan

enqueue

Queue

dequeue getFront

SDA/ST-Q/V2.0/20

10

Examples Line for 21 tickets „ Line printer queue Queue is a British word for line. Waktu operasi yang O(1) karena mirip dengan stack. „

„ „

SDA/ST-Q/V2.0/21

Applikasi-aplikasi „ „

Queues berguna untuk menyimpan pekerjaan yang tertunda. Kita kelak akan melihat beberapa contoh penggunaannya dalam kuliah-kuliah selanjutnya: „ Shortest paths problem (minimize the number of connecting flights between two arbitrary airports) „ Topological ordering: given a sequence of events, and pairs (a,b) indicating that event a MUST occur prior to b, provide a schedule.

SDA/ST-Q/V2.0/22

11

Queues: Simple Idea „

„ „ „

Simpan item-iten dalam suatu array dengan item terdepan pada index nol and item terbelakang pada index Back. Enqueue dengan mudah: increment Back. Dequeue tidak efisien: setiap elemen harus digeserkan ke depan. Akibatnya: waktu Dequeue akan menjadi O( N ).

SDA/ST-Q/V2.0/23

Better Idea „ „

Menggunakan Front untuk mencatat index terdepan. Dequeue dilakukan dengan increment Front.

a

b

c

Front a

d Back

b Front

c

d Back SDA/ST-Q/V2.0/24

12

Circular Implementation „ „

„

Implementasi sebelumnya adalah O(1) per operasi. Tapi, setelah elemen di-enqueue pada posisi Array.length-1, array sekarang penuh, sekalipun queue secara lojik hampir kosong. Solusi: gunakan wraparound untuk menggunakan kembali sel-sel di awal array yang sudah kosong akibat dequeue. Jadi setelah increment, jika index keluar darI array maka kembali ke 0.

SDA/ST-Q/V2.0/25

Circular Example „

Kedua index Front dan Back melakukan wraparound jika melalui akhir array.

b

c

d

e

Front g

b

Back

Front

f Back

c

d

e

f

SDA/ST-Q/V2.0/26

13

Implementasi Java „

„

Mostly straightforward; maintain „ Front „ Rear „ Current number of items in queue Bagian yang masih tricky adalah array doubling jika jumlah item dalam queue melebihi ukuran array.

SDA/ST-Q/V2.0/27

Linked-List Application „ „

„

front → … → … → back enqueue: „ create a new node „ if empty, front = back „ else attach it as the new back dequeue: „ get node at the front

a

b front

c

d back SDA/ST-Q/V2.0/28

14

Summary „ „ „ „

Kedua versi, baik array maupun linked-list berjalan dengan O(1) Linked-list memiliki overhead akibat diperlukannya reference pada setiap node Khususnya untuk Queues, implementasi array lebih sulit dilakukan Doubling space dalam implementasi array memerlukan space sekurangnya 3 kali jumlah item data.

SDA/ST-Q/V2.0/29

Further Reading „

Chapter 6, 15

SDA/ST-Q/V2.0/30

15

What’s Next „ „

Application of stack & queue, or Tree

SDA/ST-Q/V2.0/31

16