Tuesday, October 2, 2012

Struktur Data List Linear

Definisi

Struktur data linear adalah kumpulan komponen-komponen yang tersusun membentuk satu garis linear. Bila komponen-komponen ditambahkan (atau dikurangi), maka struktur-struktur tersebut berkembang (atau menyusut).
  • 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 ADT dimana implementasi pada tingkat rendah dapat sebagai list, baik  menggunakan struktur sequential (array) atau struktur berkait (linear lenked-list)


Karakteristik Stack

  • Semua akses dibatasi pasa elemen yang paling akhir disisipkan
  • Operasi-operasi dasar : push, pop, top.
Contoh nyata
  • Tumpukan kertas 
  • Tumpukan piring 
Waktu O (1) per operasi stack.
Jadi waktu konstan per operasi, tidak bergantung berapa banyak item yang tersimpan didalam stack

Contoh penggunaan Stack :
Memeriksa pasangan tanda kurung (Balanced Symbol). Misal { [ ( ) ] } (Contoh benar), { ( [ ) ]} (contoh salah)

Karakteristik Queue

  • Setiap akses dibatasi ke elemen yang paling terdahulu disisipkan
  • Operasi-operasi dasar : enqueue, dequeue,getFront
  • Opeasi-operasi dengan waktu konstan. Waktu operasi O(1) karena mirip dengan stack
Contoh nyata
  • Antrian printer
  • Antrian tiket bioskop

Sumber :
  • http://www.scribd.com/doc/56820705/34/Struktur-data-linear
  •  http://aren.cs.ui.ac.id/sda/archive/1998/handout/handout09.html

No comments:

Post a Comment