Struktur Data dan Algoritma Queue (Antrian)

Baca selengkapnya »

            Queue (Antrian)

            Queue (Antrian) adalah suatu kumpulan data yang mana penambahan data / elemen hanya dapat dilakukan pada sisi belakang sedangkan penghapusan / pengeluaran elemen dilakukan pada sisi depan. Jenis struktur data antrian sering digunakan untuk menstimulasikan keadaan dunia nyata. Antrian banyak dijumpai dalam kehidupan sehari-hari. Misal : antrian registrasi mahasiswa, tiket kereta api dan lain-lain.

            Berbeda dengan stack, prinsip yg digunakan dalam antrian adalah FIFO ( First In First Out ). Dengan kata lain, urutan keluar elemen akan sama dengan urutan masuknya. Dalam antrian tidak semuanya dilakukan secara FIFO murni, contoh yg relevan dalam bidang komputer adalah Time-sharing Computer System, dimana ada sejumlah penakai (user) yg menggunakan sistem tersebut secara serempak. Karena sistem ini biasanya menggunakan processor, dan sebuah memory utama. Jika processor sedang dipakai oleh seorang user, maka user yang lain harus antri sampai gilirannya.

            Antrian ini tidak akan dilayani secara FIFO murni tetapi biasanya didasarkan pada suatu prioritas tertentu. Antrian yang memasukkan unsur prioritas dinamakan dengan Antrian Prioritas (Priority Queue).

            Elemen yang pertama kali masuk ke antrian akan keluar pertama kalinya. Dequeue adalah mengeluarkan satu elemen dari suatu antrian. Terdapat satu buah pintu masuk di suatu ujung dan satu buah pintu keluar di ujung satunya sehingga membutuhkan variabel Head dan Tail.

Deklarasi Queue :

            Operasi dalam Queue

•             Create ( )

1.       Untuk menciptakan dan menginisialisasi Queue
2.       Dengan cara membuat Head dan Tail = -1

 

•             IsEmpty ( )

1.  Untuk memeriksa apakah Antrian sudah penuh atau belum
2.  Dengan cara memeriksa nilai Tail, jika Tail = -1 maka empty
3.  Kita tidak memeriksa Head, karena Head adalah tanda untuk kepala antrian (elemen pertama dalam antrian) yang tidak akan berubah-ubah
4.  Pergerakan pada Antrian terjadi dengan penambahan elemen Antrian kebelakang, yaitu menggunakan nilai Tail. 

•             IsFull

1.                     Untuk mengecek apakah Antrian sudah penuh atau belum
2.        Dengan cara mengecek nilai Tail, jika Tail >= MAX-1 (karena MAX-1 adalah batas elemen array pada C) berarti sudah penuh

•            Enqueue (data)

1.  Untuk menambahkan elemen ke dalam antrian, penambahan elemen selalu ditambahkan di elemen paling belakang.
2.    Penambahan elemen selalu menggerakan variabel Tail dengan cara increment counter Tail

•             Dequeue()

1.    Digunakan untuk menghapus elemen terdepan/pertama dari antrian
2.    Dengan cara mengurangi counter Tail dan menggeser semua elemen antrian kedepan.
3.    Penggeseran dilakukan dengan menggunakan looping

•             Clear()

1.   Untuk menghapus elemen-elemen Antrian dengan cara membuat Tail dan Head = -1
2. Penghapusan elemen-elemen antrian sebenarnya tidak menghapus arraynya, namun hanya mengeset indeks pengaksesannya

•             Tampil

1.       Untuk menampilkan nilai-nilai elemen antrian
2.       Menggunakan looping dari head sampai dengan tail

Struktur Data dan Algoritma Queue (Antrian)

Posted by : Unknown

Date :Kamis, 16 April 2015

With 0komentar

Struktur Data dan Algoritma Stack(Tumpukan)

Baca selengkapnya »

A.    Stack (tumpukan)

Stack adalah suatu urutan yang elemennya dapat diambil dan ditambah hanya pada posisi akhir (top).contoh dalam kebidupan sehari-hari adalah tumpukan piring disebuah restoran yang tumpukanya ditambah pada bagian paling atas dan jika mengambilnya pun dari bagian paling atas pula.

1.      Macam-Macam Stack

Stack ada 2 operasi paling besar yang dapat dilakukan yaitu:

1.  Operasi push yaitu operasi menambahkan elemen pada urutan terakhir (paling atas).

2.  Operasi pop yaitu mengambil sebuah elemen data pada urutan terakhir dan menghapus elemen tersebut dari stack.

2.      Proses Operasi Stack

    Selain operasi dasar stack ada lagi operasi lain dapat terjadi dalam stack yaitu:

1.      Proses Deklarasi yaitu proses pendeklarasian stack.

2.   Proses IsEmpty yaitu proses pemeriksaan apakah stack dalam keadaan kosong.

3.      Proses IsFull yaitu proses pemeriksaan apakah stack telah penuh.

4.      Proses Inisialisasi yaitu proses pembuangan stack kosong, biasanya dengan pemberian nial untuk top.

3.      Operasi-Operasi Stack

a.      Pendeklarasian Stack

Suatu stack memiliki beberapa bagian yaitu:

1.      Top : yang berisi posisi data terakhir.

2.    Elemen : yang berisi data yang ada dalam stack bagian inilah yang berbentuk array.

3.    Maks_elemen yaitu variabel yang menunjuk maksimal banyaknya elemen dalam stack.

b.      Inisialisasi

Inisialisasi Stack adalah proses pembuatan suatu stack kosong. Adapun langkah-langkah proses inisialisasi stack yang menggunakan array. Dengan mengisi nilai field top dengan 0. Jika elemen pertama diawali dengan nomor 1, kalau elemen pertamanya array dimulai dengan 0, maka top diisi dengan -1.

c.      Operasi IsEmpty

            Operasi yang digunakan untuk memeriksa apakah stack dalam keadaan kosong. Operasi ini dilakukan dengan memeriksa field top, jika top bernilai 0 atau top bernilai -1, maka berarti dalam keadaan empty.

d.      Operasi IsFull

     Operasi ini untuk memeriksa keadaan stack apakah sudah penuh/belum. Operasi ini memberikan nilai true(1) jika field top sama dengan field maks_elemen.

e.      Operasi Push

       Operasi push adalah operasi dasar dari stack yang berguna untuk menambahkan suatu elemen data baru pada stack dan di simpan pada posisi top yang akan mengakibatkan posisi top akan berubah.

 Langkah-langkah operasi ini:

1.  Periksa apakah stack penuh(IsFull). Jika berniali false/0(tidak penuh) maka proses push dilakukan dan jika pemeriksaan ini bernilai true/1, maka proses push digagalkan.

2.  Proses Push-nya sendiri adalah dengan menambahkan field top dengan 1, kemudian elemen pada posisi top di isi dengan elemen data baru.

f.       Operasi Pop

      Operasi Pop adalah salah satu operasi paling besar dari stack yang brguna untuk mengambil elemen terakhir(top) dan kemudian menghapus elemen tersebut sehingga posisi top akan berpindah.

Operasi ini biasanya dibuat dalam bentuk function yang me-return-kan nilai sesuai data yang ada di top.

Operasi Pop pada Stack yang menggunakan array adalah terlebih dahulu memeriksa apakah stack sedang keadaan kosong, jika tidak kosong maka data diambil pada posisi yang ditunjuk oleh posisi top. Kemudian disimpan dalam variabel baru dengan nama "data".

Struktur Data dan Algoritma Stack(Tumpukan)

Posted by : Unknown

Date :

With 2komentar

Struktur Data dan Algoritma Linked list

Baca selengkapnya »

A.    Linked list

Linked List adalah suatu struktur data linier. Berbeda dengan array yang juga merupakan struktur data linier dan tipe data komposit, linked list dibentuk secara dinamik. Pada saat awal program dijalankan elemen linked list belum data. Elemen linked list (disebut node) dibentuk sambil jalan sesuai instruksi. Apabila setiap elemen array dapat diakses secara langsung dengan menggunakan indeks, sebuah node linked list diakses dengan menggunakan pointer yang mengacu (menunjuk) ke node tersebut. Dalam struktur data algortima linked list mempunyai beberapa jenis yaitu:

1.      Single Linked List

Tempat yang disediakan pada satu area memori tertentu untuk menyimpan data dikenal dengan sebutan node atau simpul. Setiap node memiliki pointer yang menunjuk ke simpul berikutnya sehingga terbentuk satu untaian, dengan demikian hanya diperlukan sebuah variabel pointer. Susunan berupa untaian semacam ini disebut Single Linked List (NULL memilik nilai khusus yang artinya tidak menunjuk ke mana-mana. Biasanya Linked List pada titik akhirnya akan menunjuk ke NULL). Pembuatan Single Linked List dapat menggunakan 2 metode:

1.      LIFO (Last In First Out), aplikasinya : Stack (Tumpukan)

2.      FIFO (First In First Out), aplikasinya : Queue (Antrian)

Gambar 1.1 Single Linked List

2.      Double Linked List

Salah satu kelemahan single linked list adalah pointer (penunjuk) hanya dapat bergerak satu arah saja, maju/mundur, atau kanan/kiri sehingga pencarian data pada single linked list hanya dapat bergerak dalam satu arah saja. Untuk mengatasi kelemahan tersebut, dapat menggunakan metode double linked list. Linked list ini dikenal dengan nama Linked list berpointer Ganda atau Double Linked List.

Gambar 1.2 Double Linked List

3.      Circular Double Linked List

Merupakan double linked list yang simpul terakhirnya menunjuk ke simpul terakhirnya menunjuk ke simpul awalnya menunjuk ke simpul akhir sehingga membentuk suatu lingkaran. Operasi-Operasi yang ada pada Linked List :

a.       Insert

Istilah Insert berarti menambahkan sebuah simpul baru ke dalam suatu linked list.

b.      IsEmpty

Fungsi ini menentukan apakah linked list kosong atau tidak.

c.       Find First

Fungsi ini mencari elemen pertama dari linked list

d.      Find Next

Fungsi ini mencari elemen sesudah elemen yang ditunjuk now

e.       Retrieve

Fungsi ini mengambil elemen yang ditunjuk oleh now. Elemen tersebut lalu dikembalikan oleh fungsi.

f.       Update

Fungsi ini mengubah elemen yang ditunjuk oleh now dengan isi dari sesuatu. 

g.      Delete Now

Fungsi ini menghapus elemen yang ditunjuk oleh now. Jika yang dihapus adalah elemen pertama dari linked list (head), head akan berpindah ke elemen berikut.

h.      Delete Head

Fungsi ini menghapus elemen yang ditunjuk head. Head berpindah ke elemen sesudahnya.

i.        Clear

Fungsi ini menghapus linked list yang sudah ada. Fungsi ini wajib dilakukan bila anda ingin mengakhiri program yang menggunakan linked list. Jika anda melakukannya, data-data yang dialokasikan ke memori pada program sebelumnya akan tetap tertinggal di dalam memori.

Gambar 1.3 Circular Double Linked List

4.      Pointer

Pointer adalah suatu variabel penunjuk, berisi nilai yang menunjuk alamat suatu lokasi memori tertentu. Jadi pointer tidak berisi nilai data, melainkan berisi suatu alamat memori atau null jika tidak berisi data. Pointer yang tidak diinisialisasi disebut dangling   pointer. Lokasi memori tersebut bisa diwakili sebuah variabel atau dapat juga berupa nilai alamat memori secara langsung.

Operasi pada pointer :

1.      Operasi assignment

Antar variabel pointer dapat dilakukan operasi assignment.

- Contoh 1: Assignment dan sebuah alamat dapat ditunjuk oleh lebih dari satu pointer

- Contoh 2: Mengisi variable dengan nilai yang ditunjuk oleh sebuah variabel pointer

- Contoh 3: Mengoperasikan isi variable dengan menyebut alamatnya dengan pointer

 -  Contoh 4: Mengisi dan mengganti variabel yang ditunjuk oleh pointer

2.      Operasi aritmatika

–    Pada pointer dapat dilakukan operasi aritmatika yang akan menunjuk suatu alamat memori baru.

–       Hanya nilai integer saja yang bias dioperasikan pada variabel pointer.

–    Biasanya hanya operasi penambahan/pengurangan saja.

–    Misal pointer X bertipe int  (2 bytes), maka X+1 akan menunjuk pada alamat memori sekarang (mis. 1000) ditambah sizeof(X), yaitu 2, jadi 1002.

        Pada array, pointer hanya perlu menunjuk pada alamat elemen pertama saja karena letak alamat array sudah berurutan pada memori.Variabel pointer hanya perlu increment.

Struktur Data dan Algoritma Linked list

Posted by : Unknown

Date :

With 0komentar