BAB I

STRUKTUR DATA

Dalam istilah ilmu komputer, sebuah struktur data adalah cara penyimpanan,

penyusunan dan pengaturan data di dalam media penyimpanan komputer sehingga

data tersebut dapat digunakan secara efisien.

Dalam teknik pemrograman, struktur data berarti tata letak data yang berisi

kolom-kolom data, baik itu kolom yang tampak oleh pengguna (user) atau pun

kolom yang hanya digunakan untuk keperluan pemrograman yang tidak tampak

oleh pengguna. Setiap baris dari kumpulan kolom-kolom tersebut dinamakan

catatan (record). Lebar kolom untuk data dapat berubah dan bervariasi. Ada

kolom yang lebarnya berubah secara dinamis sesuai masukan dari pengguna, dan

juga ada kolom yang lebarnya tetap. Dengan sifatnya ini, sebuah struktur data

dapat diterapkan untuk pengolahan database (misalnya untuk keperluan data

keuangan) atau untuk pengolah kata (word processor) yang kolomnya berubah

secara dinamis. Contoh struktur data dapat dilihat pada berkas-berkas lembar-

sebar (spreadsheet), pangkal-data (database), pengolahan kata, citra yang

dipampat (dikompres), juga pemampatan berkas dengan teknik tertentu yang

memanfaatkan struktur data.

A. TAHAPAN PEMBUATAN STRUKTUR DATA

1. Tahap

Spesifikasi atau pendeskripsian struktur data menyatakan apa yang dapat

dilakukan struktur data, bukan cara penempatannya. Pendeskripsian ini

melibatkan level logic sehingga dapat digunakan konvensi matematika untuk

menyatakan sifat-sifat struktur data yang dikehendaki.

2. Tahap Kedua

Implementasi menyatakan cara penerapan struktur data dengan struktur data

yang telah ada. Implementasi struktur dataadalah proses pendefinisian tipe data

abstark sehingga semua operasi dapat dieksekusi computer. Implementasi

berisi dekklarasi struktur penyimpanan item data serta algoritma untuk

implementasi operasi, sehingga menjamin terpenuhinya karakteristik struktur

data, relasi item data tau invariant pada struktur data tersebut.

3. Tahap Ketiga

Pemrograman struktur data adalah penterjemahan menjadi pernyataan dalam

bahasa pemrograman tertentu.struktur data dibangun menggunakan fasilitas

pembentukkan atau pembuatan struktur data yang disediakan bahasa seperti

array, record dan lain-lain.

Dasar Pengetahuan Struktur Data

Dalam mempelajari struktur data hal-hal awal yang perlu kita ketahui adalah

tentang konstanta, variable, dan tipe data.

a. Konstanta

Dalam membuat suatu program, kita perlu menggunakan konstanta agar

program kita bisa lebih mudah diperbaiki jika ada suatu kesalahan yang kita

buat. Dengan menggunakan konstanta kita bisa memberikan nama yang

mudah dimengerti dan dipahami untuk bilangan numerik yang sangat

kompleks. Konstanta dideklarasikan pada awal program dan dideklarasikan

dengan kata baku const. Sesuai dengan namanya “konstanta”, maka nilai

dalam konstanta selalu konstan atau tetap dan kita tidak dapat merubah nilai

dari konstanta pada saat program sedang dijalankan.

b. Variabel

Variabel adalah lokasi di memori yang kita siapkan dan kita beri nama khas

untuk menampung suatu nilai dan atau mengambil nilai kembali tersebut.

Bentuk umum dari variable adalah:

Var

NamaVariabel1,

NamaVariabel2,

……………….

NamaVariabel1N : TipeData1;

NamaVariabel1,

NamaVariabel2,

NamaVariabelNN : TipeDataN;

B. TIPE DATA

Atribut penting yang digunakan untuk suatu tipe data terstruktur adalah sebagai

berikut :

1. Jumlah Komponen

Berdasarkan jumlah komponen selama eksekusi program, maka dapat

dikelompokkan menjadi :

- Struktur Data Statis (Jumlah komponennya tidak berubah)

- Struktur Data Dinamis (Jumlah komponennya dapat berubah)

2. Tipe untuk setiap komponennya

Apabila tipe data untuk seluruh komponennya harus sama, maka disebut

Struktur Data Homogen, dan bila dimungkinkan komponennya mempunyai

tipe data yang berbeda-beda, maka disebut Struktur Data Heterogen.

3. Nama-nama untuk memilih komponen

Hampir semua struktur data menyediakan operasi untuk mengakses komponen

secara individu. Pada suatu array (kumpulan data yang mempunyai tipe sama),

hal ini dilakukan dengan sebuah indeks berupa angka.

4. Jumlah maksimum komponen

Tidak semua jenis struktur data harus ditentukan jumlah maksimum komponen,

namun untuk sebuah tipe data dinamis mungkin perlu ditentukan dengan jelas.

5. Pengorganisasian semua komponennya

Susunan yang paling umum adalah berupa barisan linier seperti pada array

berdimensi 1, record, list, stack dan file. Selanjutnya ada yang dapat

dikembangkan menjadi struktur non linier seperti array multi dimensi dan juga

pohon/tree.

Jenis tipe data yang biasanya digunakan dalam data terstruktur adalah sebagai

berikut :

a. Integer

Integer adalah tipe data nilainya merupakan bilangan bulat dan teerbagi atas

beberapa macam. Berikut ini adalah tabelnya:

Type Range Ukuran Format

ShortIn -128…127 1 Signed 8-bit

Integer -32768..32767 2 Signed 16-bit

LongInt -2147483648..2147483647 4 Signed 32-bit

Byte 0..255 1 Unsigned 8-bit

Word 0..65535 2 Unsigned 16-bit

C. JENIS STRUKTUR DATA

1. Struktur Data Sederhana

a. Array(Larik)

Larik adalah struktur data statik yang menyimpan sekumpulan elemen yang

bertipe sama. Setiap elemen diakses langsung melalui indeksnya. Indeks larik

harus tipe data yang menyatakan keterurutan misalnya integer atau karakter.

Banyaknya elemen larik harus sudah diketahui sebelum program dieksekusi.

Tipe elemen larik dapat berupa tipe sederhana, tipe terstruktur, atau tipe larik

lain. Nama lain array adalah Larik, tabel, atau vektor

b. Record(Catatan)

ADT adalah definisi tipe dan sekumpulan primitif (operasi dasar) terhadap tipe

tersebut. Tipe diterjemahkan menjadi tipe terdefinisi dalam bahasa

pemrograman yang bersangkutan.

2. Struktur Data Majemuk

a. Linier

- Stack(Tumpukan)

Stack (tumpukan) adalah list linier yang dikenali elemen puncaknya (top),

aturan penyisipan dan penghapusan elemennya tertentu (penyisipan selalu

dilakukan “di atas” (top), penghapusan selalu dilakukan pada top). Karena

aturan penyisipan dan penghapusan semacam itu, top adalah satu-satunya

alamat tempat terjadi operasi. Elemen yang ditambahkan paling akhir akan

menjadi elemen yang akan dihapus. Dikatakan bahwa elemen stack akan

tersusun secara LIFO (Last In First Out).

- Queue(Antrian)

Queue (antrian) adalah list linier yang dikenali elemen pertama (head) dan

elemen terakhirnya (tail); Aturan penyisipan dan penghapusan elemennya

disefinisikan sebagai penyisipan selalu dilakukan setelah elemen terakhir,

penghapusan selalu dilakukan pada elemen pertama; Satu elemen dengan

elemen lain dapat diakses melalui informasi next.

- List dan Multi-List (Daftar)

List linier adalah sekumpulan elemen bertipe sama, yang mempunyai

keterurutan tertentu, yang setiap elemennya terdiri dari 2 bagian. sebuah list

linier dikenali dengan (1) elemen pertamanya, biasanya melalui alamat

elemen pertama yang disebut (first); (2) Alamat elemen berikutnya

(suksesor), jika kita mengetahui alamat sebuah elemen, yang dapat diakses

melalui field next; (3) Setiap elemen mempunyai alamat, yaitu tempat

elemen disimpan dapat diacu. Untuk mengacu sebuah elemen, alamat harus

terdefinisi. Dengan alamat tersebut informasi yang tersimpan pada elemen

list dapat diakses; (4) Elemen terakhirnya.

b. Non-Linier

- Binary Tree (Pohon Biner)

Sebuah pohon biner (binary tree) adalah himpunan terbatas yang mungkin

kosong atau terdiri dari sebuah simpul yang disebut sebagai akar dan dua

buah himpunan lain yang disjoint yang merupakan pohon biner yang disebut

sebagai sub pohon kiri (left) dan sub pohon kanan (right) dari pohon biner

tersebut. Pohon biner merupakan tipe yang sangat penting dari struktur data

dan banyak dijumpai dalam berbagai terapan. Karakteristik yang dimiliki

oleh pohon biner adalah bahwa setiap simpul paling banyak hanya memiliki

dua buah anak, dan mungkin tidak punya anak. Istilah-istilah yang

digunakan sama dengan istilah pada pohon secara umum.

- Graph (Graf)

Graph merupakan struktur data yang paling umum. Jika struktur linier

memungkinkan pendefinisian keterhubungan sekuensial antara entitas data,

struktur data tree memungkinkan pendefinisian keterhubungan hirarkis,

maka struktur graph memungkinkan pendefinisian keterhubungan tak

terbatas antara entitas data. Banyak entitas-entitas data dalam masalah-

masalah nyata secara alamiah memiliki keterhubungan langsung (adjacency)

secara tak terbatas demikian. Contoh: informasi topologi dan jarak antar

kota-kota di pulau Jawa. Dalam masalah ini kota X bisa berhubungan

langsung dengan hanya satu atau lima kota lainnya. Untuk memeriksa

keterhubungan dan jarak tidak langsung antara dua kota dapat diperoleh

berdasarkan data keterhubungan-keterhubungan langsung dari kota-kota

lainnya yang memperantarainya. Representasi data dengan struktur data

linier ataupun hirarkis pada masalah ini masih bisa digunakan namun akan

membutuhkan pencarian-pencarian yang kurang efisien. Struktur data graph

secara eksplisit menyatakan keterhubungan ini sehingga pencariannya

langsung (straightforward) dilakukan pada strukturnya sendiri.

Istilah penting dalam struktur data :

1. Data

Data adalah deskripsi dari sesuatu dan kejadian yang kita hadapi(data is the

description of things and events that we face). Data adalah kenyataan yang

menggambarkan suatu kejadian-kejadian dan kesatuan nyata. Kejadian (event)

adalah sesuatu yang terjadi pada saat tertentu. Sebagai contoh, dalam dunia

bisnis kejadian-kejadian nyata yang sering terjadi adalah perubahan dari suatu

nilai yang disebut dengan transaksi. Misalnya penjualan adalah transaksi

perubahan nilai barang menjadi nilai uang atau nilai piutang dagang. Kesatuan

nyata(fact and entity) adalah berupa suatu obyek nyata seperti tempat, benda

dan orang yang betul-betul ada dan terjadi.Sumber dari informasi adalah data.

Data merupakan bentuk jamak dari bentuk tunggal data-item. Data merupakan

bentuk yang belum dapat memberikan manfaat yang besar bagi penerimanya,

sehingga perlu suatu model yang nantinya akan dikelompokkan dan diproses

untuk menghasilkan informasi.

2. Database

Database bisa dikatakan sebagai suatu kumpulan dari data yang tersimpan dan

diatur atau diorganisasikan sehingga data tersebut bisa diambil atau dicari

dengan mudah dan efisien. Sebagai contoh sederhana dari database adalah

buku telepon yang mungkin sering Anda lihat.Bagaimana halnya dengan

database dengan sistem database dengan menggunakan komputer? Hal tersebut

sama saja seperti database yang sifatnya manual (seperti contoh buku telepon

di atas) hanya saja dengan adanya komputer maka informasi yang ada di dalam

database akan sangat mudah untuk di-update dan sangat cepat untuk dicari.

Software atau aplikasi yang bertugas untuk mengatur, menyimpan,

memodifikasi data disebut dengan software database engine dan lebih resminya

disebut dengan DBMS (Database Management System). Ada banyak sekali

aplikasi DBMS ini mulai yang berjalan di komputer personal (PC) sampai ke

komputer skala mainframe. Contoh-contoh dari aplikasi database engine

misalnya seperti:

SQL Server, dibuat oleh Microsoft.

MS Access, dibuat oleh Microsoft.

Oracle Database, dibuat oleh Oracle.

MySQL, dibuat oleh MySQL AB.

Firebird, dibuat oleh komunitas open source berdasarkan dari kode Interbase.

PostgreSQL, dibuat oleh komunitas open source.

DB2, dibuat oleh IBM.

3. Data Set

Istilah untuk sekelompok record data yang sama dan saling terhubung dalam

memori computer.

4. Data bit

Sekelompok bit yang digunakan untuk menggambarkan satu karakter:character

data untuk transmisi:trans...

- Enkapsulasi (Pembungkusan)

Variabel dan method yang dipunyai suatu obyek, bisa ditentukan hak

aksesnya. Definisi enkapsulasi: Pembungkusan variabel dan method dalam

sebuah obyek yang terlindungi. Definisi enkapsulasi: menyembunyikan

cara kerja dan sistem. Dalam OOP, konsep enkapsulasi sebenarnya

merupakan perluasan dari struktur dalam bahasa C.

BAB II

ARRAY

Array adalah suatu struktur yang terdiri dari sejumlah elemen yang memiliki tipe data

yang sama. Elemen-elemen array tersusun secara sekuensial dalam memori komputer.

Array dapat berupa satu dimensi, dua dimensi, tiga dimensi ataupun banyak dimensi

(multi dimensi).

A. ARRAY SATU DIMENSI

Array Satu dimensi tidak lain adalah kumpulan elemen-elemen identik yang tersusun

dalam satu baris. Elemen-elemen tersebut memiliki tipe data yang sama, tetapi isi dari

elemen tersebut boleh berbeda.

Elemen Ke- 0 1 2 3 4 5 6 7 8 9

Nilai 23 34 32 12 25 14 23 12 11 10

Bentuk umum:

<tipe data> NamaArray[n] = {elemen0, elemen1, elemen2,.....,n};

n = jumlah elemen

1. Inisialisasi Array 1 Dimensi

Inisialisasi dapat dilakukan bersama dengan deklarasi atau tersendiri.

Inisialisasi suatu array adalah dengan meletakkan elemen array di antara tanda

kurung kurawal {}, antara elemen yang satu dengan lainnya dipisahkan koma.

int bil [2] = {4,1,8}

bil [0] = 4

bil [1] = 1

bil [2] = 8

AUTOMATIC ARRAY adalah Inisialisasi array dilakukan di dalam fungsi

tertentu. Hanya compiler C yang berstandar ANSI C yang dapat

menginisialisasikan automatic array.

Cara menginisialisasikan array dari compiler yg tidak mengikuti standar

ANSI C:

a. Diinisialisasikan di luar fungsi sebagai variabel GLOBAL/EXTERNAL

ARRAY. int bil[2]={0,0,0}; main()

b. Diinisialisasikan didlm fungsi sebagai variabel LOKAL/STATIC ARRAY.

main()

{

static int bil[2]={0,0,0}; .........

Pada automatic array yang tidak diinisialisasikan , elemen array akan

memiliki nilai yang tidak beraturan. Bila global & static array tidak

diinisialisasi maka semua elemen array secara otomatis akan diberi nilai

nol(0).

Contoh :

main()

{

int y;

int hitung=0;

int x[0];

for(y=0;y<5;y++)

{

hitung+=y;

x[y]=hitung;

printf("%3d - %3d\n",y,x[y]);

}

}

OUTPUT:

0- 0

1- 1

2- 3

3- 6

4- 10

2. Array Dua Dimensi

Array dua dimensi sering digambarkan sebagai sebuah matriks, merupakan

perluasan dari array satu dimensi. Jika array satu dimensi hanya terdiri dari

sebuah baris dan beberapa kolom elemen, maka array dua dimensi terdiri dari

beberapa baris dan beberapa kolom elemen yang bertipe sama.

Bentuk umum:

<tipe data> NamaArray [m][n];

Atau

<tipe data> NamaArray [m][n] = { {a,b,..z},{1,2,...,n-1} };

Contoh:

double matrix[4][4];

bool papan[2][2] = { {true,false},{true,false} };

Pendeklarasian array dua dimensi hampir sama dengan pendeklarasian array

satu dimensi, kecuali bahwa array dua dimensi terdapat dua jumlah elemen

yang terdapat didalam kurung siku dan keduanya boleh tidak sama. Elemen

array dua dimensi diakses dengan menuliskan kedua indeks elemennya dalam

kurung siku seperti pada contoh berikut:

//papan nama memiliki 2 baris dan 5 kolom

bool papan[2][5];

papan[0][0] = true;

papan[0][4] = false;

papan[1][2] = true;

papan[1][4] = false;

B. MENDEFINISIKAN JUMLAH ELEMEN ARRAY DALAM VARIABEL

Besarnya variabel indeks dapat ditentukan dengan menggunakan

preprocessor directives #define

#define N 40

main()

{

int no[N],gaji[N],gol[N],status[N],juman[N];

Bila besari indeks akan diubah menjadi 50, cukup diganti dengan

#define N 50

1. Pada string terdapat karakter null(\0) di akhir string

2. String sudah pasti array, array belum tentu string

Contoh - contoh :

1. array dengan pengisian input melalui keyboard

baca_input()

{

float nilai[10];

for(i=0;i<10;i++)

scanf("%d",&nilai[i]);

}

2. Fungsi yang mencetak isi array dari akhir ke awal

cetak_array()

{

float nilai[10];

for(i=9;i>=0;i--)

scanf("%3f",nilai[i]);

}

3. Menghitung rata - rata isi array nilai

rata_rata()

{

float nilai[10],jum*rata;

for(i=0,jum=0;i<=9;i++)

jum+=nilai[i];

rata=jum/i;

}

4. Mencari nilai terbesar

besar()

float temp,nilai[10];

{

for(temp=nilai[0],i=1;i<=9;i++)

if(nilai[i] > temp)

temp=nilai[i];

}

return(temp)

C. ARRAY DINAMIS

Posted Sab, 03/21/2009 - 01:39 by belajarprogram

1. Versi Ramah Cetak

Panjang suatu array tidak bisa diubah setelah dibuat. Akan tetapi, sering kali

jumlah data yang disimpan dalam array bisa berubah setiap saat. Misalnya

dalam contoh berikut : Suatu array menyimpan baris teks dalam program

pengolah kata. Atau suatu array yang menyimpan daftar komputer yang sedang

mengakses halaman suatu website. Atau array yang berisi gambar yang

ditambahkan user oleh program gambar. Di sini jelas, bahwa kita butuh sesuatu

yang bisa menyimpan data di mana jumlahnya tidak tetap.

2. Array Setengah Penuh

Bayangkan suatu aplikasi di mana sejumlah item yang ingin kita simpan di

dalam array akan berubah-ubah sepanjang program tersebut berjalan. Karena

ukuran array tidak bisa diubah, maka variabel terpisah digunakan untuk

menyimpan berapa banyak sisa tempat kosong yang masih bisa diisi di dalam

array.

Bayangkan misalnya, suatu program yang membaca bilangan bulat positif dari

user, kemudian menyimpannya untuk diproses kemudian. Program akan

berhenti membaca input apabila input yang diterima bernilai 0 atau kurang dari

nol. Bilangan input n tersebut kita simpa di dalam array bilangan dengan tipe

int[]. Katakan banyaknya bilangan yang bisa disimpan tidak lebih dari 100

buah. Maka ukuran array bisa dibuat 100.

Akan tetapi program tersebut harus melacak berapa banyak bilangan yang

sudah diambil dari user. Kita gunakan variabel terpisah bernama jmlBilangan.

Setiap kali suatu bilangan disimpan di dalam array, nilai jmlBilangan akan

bertambah satu.

Sebagai contoh sederhana, masi kita buat program yang mengambil bilangan

yang diinput dari user, kemudian mencetak bilangan-bilangan tersebut dalam

urutan terbalik. (Ini adalah contoh pengolahan yang membutuhkan array,

karena semua bilangan harus disimpan pada suatu tempat. Banyak lagi contoh

program misalnya, mencari jumlah atau rata-rata atau nilai maksimum

beberapa bilangan, bisa dilakukan tanpa menyimpan bilangan tersebut satu per

satu)

public class BalikBilanganInput {

public static void main(String[] args) {

int[] bilangan; // Array untuk menyimpan nilai input dari user

int jmlBilangan; // Banyaknya bilangan yang sudah disimpan dalam array

int bil; // Bilangan yang diambil dari user

bilangan = new int[100]; // Buat array dengan 100 bilangan int

jmlBilangan = 0; // Belum ada bilangan yang disimpan

System.out.println("Masukkan bilangan bulat positif (paling banyak 100

bilangan)" +

", masukkan nol untuk mengakhiri.");

while (true) {

System.out.print("? ");

bil = KonsolIO.ambilInt();

if (bil <= 0)

break;

bilangan[jmlBilangan] = bil;

jmlBilangan++;

}

System.out.println("\nBilangan yang Anda masukkan dalam urutan terbalik

adalah :\n");

for (int i = jmlBilangan - 1; i >= 0; i--) {

System.out.println( bilangan[i] );

}

} // akhir main();

} // akhir kelas BalikBilanganInput

Penting untuk diingat bahwa jml Bilangan memiliki dua peran. Yang pertama,

adalah melacak banyaknya bilangan yang sudah dimasukkan di dalam array. Yang

kedua adalah menentukan di mana indeks kosong berikutnya di dalam array.

Misalnya, jika 4 bilangan sudah dimasukkan ke dalam array, maka bilangan-

bilangan tersebut diisi pada array di posisi 0, 1, 2, dan 3. Maka posisi kosong

berikutnya adalah posisi 4.

Ketika kita akan mencetak angka di dalam array, maka poisisi penuh berikutnya

adalah di lokasi jmlBilangan - 1, sehingga perulangan for mencetak bilangan dari

jmlBilangan - 1 hingga 0.

Mari kita lihat contoh lain yang lebih realistis. Misalkan kita ingin menulis

program game, di mana pemain bisa masuk ke dalam game dan keluar dari game

setiap saat. Sebagai programmer berorientasi objek yang baik, mungkin kita

memiliki kelas bernama Pemain sebagai lambang pemain di dalam game. Daftar

pemain yang sedang ada di dalam game, bisa disimpan di dalam array

ArrayPemain dengan tipe Pemain[].

Karena jumlah pemain bisa berubah-ubah maka kita bisa menggunakan variabel

bantu, misalnya jumlahPemainAktif untuk mencatat banyaknya pemain yang

sedang aktif berada di dalam game. Misalnya jumlah maksimum pemain di dalam

game adalah 10 orang, maka kita bisa mendeklarasikan variabelnya sebagai :

Pemain[] ArrayPemain = new Pemain[10]; // Hingga 10 pemain.

int jumlahPemainAktif = 0; // Di awal game, tidak ada pemain yang aktif

Setelah beberapa pemain masuk ke dalam game, variabel jumlahPemainAktif

akan lebih dari 0, dan objek pemailn akan disimpan dalam array, misalnya

ArrayPemain[0], ArrayPemain[1], ArrayPemain[2], dan seterusnya. Ingat bahwa

pemain ArrayPemain[jumlahPemainAktif] tidak ada. Prosedur untuk menambah

pemain baru, secara sederhana :

// Tambah pemain di tempat kosong

ArrayPemain[jumlahPemainAktif] = pemainBaru;

// And increment playerCt to count the new player.

jumlahPemainAktif++;

Untuk menghapus seorang pemain mungkin sedikit lebih sulit karena kita tidak

ingin meninggalkan lubang di tengah-tengah array. Misalnya kita ingin

menghapus pemain pada indeks k pada ArrayPemain. Jika kita tidak peduli urutan

pemainnya, maka salah satu caranya adalah memindahkan posisi pemain terakhir

ke posisi pemain yang meninggalkan game, misalnya :

ArrayPemain[k] = ArrayPemain[jumlahPemainAktif - 1];

jumlahPemainAktif--;

Pemain yang sebelumnya ada di posisi k, tidak lagi ada di dalam array. Pemain

yang sebelumnya ada di posisi jumlahPemainAktif -1 sekarang ada di array

sebanyak 2 kali. Akan tetapi sekarang ia berada di bagian yang valid, karena nilai

jumlahPemainAktif kita kurangi dengan satu. Ingat bahwa setiap elemen di dalam

array harus menyimpan satu nilai, akan tetapi satu-satunya nilai dari posisi 0

hingga jumlahPemainAktif - 1 akan tetap diproses seperti biasa.

Misalnya kita ingin menghapus pemain di posisi k, akan tetapi kita ingin agar

urutan pemain tetap sama. Untuk melakukannya, semua pemain di posisi k+1 ke

atas harus dipindahkan satu posisi ke bawah. Pemain k+ mengganti pemain k

yang keluar dari game. Pemain k+2 mengganti pemain yang pindah sebelumnya,

dan berikutnya. Kodenya bisa dibuat seperti

for (int i = k+1; i < jumlahPemainAktif; i++) {

ArrayPemain[i-1] = ArrayPemain[i];

}

jumlahPemainAktif--;

Perlu ditekankan bahwa contoh Pemain di atas memiliki tipe dasar suatu kelas.

Elemennya bisa bernilai null atau referensi ke suatu objek yang bertipe Pemain,

Objek Pemain sendiri tidak disimpan di dalam array, hanya referensinya saja yang

disimpan di sana. Karena aturan pemberian nilai pada Java, objek tersebut bisa

saja berupa kelas turunan dari Pemain, sehingga mungkin juga array tersebut

menyimpan beberapa jenis Pemain misalnya pemain komputer, pemain manusia,

atau pemain lainnya, yang semuanya adalah kelas turunan dari Pemain.

Contoh lainnya, misalnya kelas BentukGeometri menggambarkan suatu bentuk

geometri yang bisa digambar pada layar, dan ia memiliki kelas-kelas turunan yang

merupakan bentuk-bentuk khusus, seperti garis, kotak, kotak bertepi bulat, oval,

atau oval berisi warna, dan sebagainya. (BentukGeometri sendiri bisa berbentuk

kelas abstrak, seperti didiskusikan sebelumnya). Kemudian array bertipe

BentukGeometri[] bisa menyimpan referensi objek yang bertipe kelas turunan dari

BentukGeometri. Misalnya, perhatikan contoh pernyataan berikut

BentukGeometri[] gambar = new BentukGeometri[100]; // Array untuk

menyimpan 100 gambar.

gambar[0] = new Kotak(); // Letakkan beberapa objek di dalam array.

gambar[1] = new Garis(); // (Program betulan akan menggunakan beberapa

gambar[2] = new OvalBerwarna(); // parameter di sini

int jmlGambar = 3; // Lacak jumlah objek di dalam array

bisa diilustrasikan sebagai berikut.

Array tersebut bisa digunakan dalam program gambar. Array bisa digunakan

untuk menampung gambar-gambar yang akan ditampilkan. Jika BentukGeometri

memiliki metode "void gambarUlang(Graphics g)" untuk menggambar pada

grafik g, maka semua grafik dalam array bisa digambar dengan perulangan

sederhana

for (int i = 0; i < jmlGambar; i++)

gambar[i].gambarUlang(g);

Pernyataan "gambar[i].gambarUlang(g);" memanggil metode gambarUlang()

yang dimiliki oleh masing-masing gambar pada indeks i di array tersebut. Setiap

objek tahu bagaimana menggambar dirinya sendiri, sehingga perintah dalam

perulangan tersebut sebetulnya melakukan tugas yang berbeda-beda tergantung

pada objeknya. Ini adalah contoh dari polimorfisme dan pengolahan array.

3. Array Dinamis

Dalam contoh-contoh di atas, ada batas tententu dalam jumlah elemennya,

yaitu 100 int, 100 Pemain, dan 100 BentukGeometris. Karena ukuran array

tidak bisa berubah, array tersebut hanya bisa menampung maksimum sebanyak

elemen yang didefinisikan pada pembuatan array. Dalam banyak kasus, adanya

batas maksimum tersebut tidak diinginkan. Kenapa harus bekerja dengan hanya

100 bilangan bulat saja, bukan 101?

Alternatif yang umum adalah membuat array yang sangat besar sehingga bisa

digunakan untuk dalam kehidupan sehari-hari. Akan tetapi cara ini tidak baik,

karena akan sangat banyak memori komputer yang terbuang karena tidak

digunakan. Memori itu mungkin lebih baik digunakan untuk yang lain. Apalagi

jika komputer yang akan digunakan tidak memiliki memori yang cukup untuk

menjalankan program tersebut.

Tentu saja, cara yang lebih baik adalah apabila kita bisa mengubah ukuran

array sesuka kita kapan saja. Ingat bahwa sebenarnya variabel array tidak

menyimpan array yang sesungguhnya. Variabel ini hanya menyimpan referensi

ke objek tersebut. Kita tidak bisa membuat array tersebut lebih besar, akan

tetapi kita bisa membuat array baru yang lebih besar, kemudian mengubah isi

variabel array tersebut ke array baru itu.

Tentunya kita harus mengkopi semua isi di array yang lama ke array baru.

Array lama akan diambil oleh pemulung memori, karena ia tidak lagi

digunakan.

Mari kita lihat kembali contoh game di atas, di mana ArrayPemain adalah array

dengan tipe Pemain[] dan jumlahPemainAktif[/code] adalah jumlah pemain

yang sudah digunakan array tersebut. Misalnya kita tidak ingin membuat limit

banyaknya pemainnya yang bisa ikut main. Jika pemain baru masuk dan array

tersebut sudah penuh, kita akan membuat array baru yang lebih besar.

Variabel ArrayPemain akan merujuk pada array baru. Ingat bahwa setelah ini

dilakukan, ArrayPemain[0] akan menunjuk pada lokasi memori yang berbeda,

akan tetapi nilai ArrayPemain[0] sama dengan sebelumnya. Berikut ini adalah

kode untuk melakukan hal di atas:

// Tambah pemain baru, meskipun array sudah penuh

if (jumlahPemainAktif == ArrayPemain.length) {

// Array sudah penuh. Buat array baru yang lebih besar,

// kemudian kopi isi array lama ke array baru lalu ubah

// ArrayPemain ke array baru.

int ukuranBaru = 2 * ArrayPemain.length; // Ukuran array baru

Pemain[] temp = new Pemain[ukuranBaru]; // Array baru

System.arraycopy(ArrayPemain, 0, temp, 0, ArrayPemain.length);

ArrayPemain = temp; // Ubah referensi ArrayPemain ke array baru.

}

// Di sini kita sudah tahu bahwa pasti ada tempat di array baru.

ArrayPemain[jumlahPemainAktif] = pemainBaru; // Tambah pemain baru...

jumlahPemainAktif++; // ... dan tambah satu jumlahPemainAktif nya

Jika kita akan melakukan hal ini terus menerus, akan lebih indah jika kita

membuat kelas untuk menangani hal ini. Objek mirip array yang bisa berubah

ukuran untuk mengakomodasi jumlah data yang bisa ia tampung disebut array

dinamis. Array dinamis memiliki jenis operasi yang sama dengan array : mengisi

nilai pada posisi tertentu dan mengambil nilai di posisi tertentu. Akan tetapi tidak

ada batas maksimum dari jumlah array (hanya tergantung pada jumlah memori

komputer yang tersedia). Dalam kelas array dinamis, metode put dan get akan

diimplementasikan sebagai metode instansi.

Di sini misalnya, adalah kelas yang mengimplementasikan array dinamis int :

public class ArrayDinamisInt {

private int[] data; // Array untuk menyimpan data

public DynamicArrayOfInt() {

// Konstruktor.

data = new int[1]; // Array akan bertambah besar jika diperlukan

}

public int get(int posisi) {

// Ambil nilai dari posisi tertentu di dalam array.

// Karena semua posisi di dalam array adalah nol, maka

// jika posisi tertentu di luar data array, nilai 0 akan dikembalikan

if (posisi >= data.length)

return 0;

else

return data[posisi];

}

public void put(int posisi, int nilai) {

// Simpan nilai ke posisi yang ditentukan di dalam array

// Data array tersebut akan bertambah besar jika diperlukan

if (posisi >= data.length) {

// Posisi yang ditentukan berada di luar array data

// Besarkan ukuran array 2x lipat. Atau jika ukurannya masih

// terlalu kecil, buat ukurannya sebesar 2*posisi

int ukuranBaru = 2 * data.length;

if (posisi >= ukuranBaru)

ukuranBaru = 2 * posisi;

int[] dataBaru = new int[ukuranBaru];

System.arraycopy(data, 0, dataBaru, 0, data.length);

data = dataBaru;

// Perintah berikut hanya untuk demonstrasi

System.out.println("Ukuran array dinamis diperbesar menjadi "

+ ukuranBaru);

}

data[posisi] = nilai;

}

} // akhir kelas ArrayDinamisInt

Data pada objek ArrayDinamisInt disimpan dalam array biasa, akan tetapi

arraynya akan dibuang dan diganti dengan array baru yang lebih besar apabila

diperlukan. Jika bilangan adalah variable bertipe ArrayDinamisInt, maka perintah

bilangan.put(pos,nilai) akan menyimpan bilangan pada posisi pos di array dinamis

tersebut. Fungsi bilangan.get(pos) mengambil nilai yang disimpan pada posisi

pos.

Pada contoh pertama, kita menggunakan array untuk menyimpan bilangan bulat

positif yang dimasukkan oleh user. Kita bisa menulis ulang program tersebut

dengan menggunakan ArrayDinamisInt. Referensi ke bilangan[i] diganti dengan

bilangan.get[i]. Perintah "bilangan[jmlBilangan] = bil;" kita ganti dengan

"bilangan.put(jmlBilangan,bil);". Berikut ini adalah programnya:

public class BalikBilanganInput {

public static void main(String[] args) {

ArrayDinamisInt bilangan; // Array untuk menyimpan nilai input dari user

int jmlBilangan; // Banyaknya bilangan yang sudah disimpan dalam array

int bil; // Bilangan yang diambil dari user

bilangan = new ArrayDinamisInt();

jmlBilangan = 0; // Belum ada bilangan yang disimpan

System.out.println("Masukkan bilangan bulat positif, masukkan nol untuk

mengakhiri.");

while (true) {

System.out.print("? ");

bil = KonsolIO.ambilInt();

if (bil <= 0)

break;

bilangan.put(jmlBilangan,bil);

jmlBilangan++;

}

System.out.println("\nBilangan yang Anda masukkan dalam urutan terbalik

adalah :\n");

for (int i = jmlBilangan - 1; i >= 0; i--) {

System.out.println( bilangan.get(i) );

}

} // akhir main();

} // akhir kelas BalikBilanganInput

4. Array Multi Dimensi

Posted Sab, 03/21/2009 - 01:45 by belajarprogram

a. Versi ramah cetak

Tipe apapun bisa digunakan sebagai tipe dasar suatu array. Kita bisa membuat

array int, array String, array Object dan seterusnya. Terutama, karena array

adalah tipe Java kelas satu, kita bisa membuat array yang bertipe array.

Misalnya suatu array bertipe int[], juga otomatis memiliki array bertipe int[][],

yaitu "array bertipe array int". Array tersebut disebut array 2 dimensi.

Tentunya, dengan tipe int[][], kita juag bisa membuat arraynya dengan tipe

int[][][], yang merupakan array 3 dimensi, dan seterusnya. Tidak ada batasan

berapa dimensi array yang kita buat, akan tetapi bukan sesuatu yang biasa

dilakukan untuk membuat array lebih dari 3 dimensi. Pembahasan kita akan

lebih dikhususkan pada array 2 dimensi. Tipe TipeDasar[][] biasanya dibaca

"array 2 dimensi bertipe TipeDasar" atau "array dari array TipeDasar".

Deklarasi pernyataan "int[][] A;" adalah membuat variabel bernama A dengan

tipe int[][]. Variabel ini berisi objek yang bertipe int[][]. Pernyataan pemberian

nilai "A = new int[3][4];" akan membuat objek array 2 dimensi dan mengisi A

ke objek yang baru dibuat tersebut.

Seperti biasa, deklarasi dan pemberian nilai bisa digabung menjadi satu

pernyataan, seperti "int[][] A = new int[3][4];". Objek yang baru dibuat adalah

objek yang merupakan array dari array int. Bagian int[3][4] menyatakan bahwa

ada 3 array int di dalam array A, dan di setiap array int tersebut terdapat 4 int.

Cara seperti itu mungkin sedikit membingungkan, akan tetapi akan lebih

mudah apabila kita bayangkan array tersebut seperti matriks. Istilah "int[3][4]"

bisa disebut sebagai matriks dengan 3 baris dan 4 kolom, seperti pada ilustrasi

berikut ini :

Untuk banyak hal, kita bisa mengabaikan kenyataan di atas, dan membayangkan

bentuk matriks seperti di atas. Kadang-kadang kita juga harus ingat bahwa setiap

baris sebenarnya juga merupakan suatu array. Array-array ini bisa dirujuk dengan

A[0], A[1], dan A[2]. Setiap baris bertipe int[].

Pernyataan A[1] merujuk pada salah satu baris pada array A. Karena A[1] itu

sendiri sebenarnya adalah array int, kita bisa menambah indeks lain untuk

merujuk pada posisi pada baris tersebut. Misalnya A[1][3] adalah elemen nomor 3

pada baris 1. Seperti biasa, ingat bahwa posisi baris dan kolom dimulai dari 0.

Jadi pada contoh di atas, A[1][3] bernilai 5. Lebih umum lagi, A[i][j] adalah

posisi pada baris i dan kolom j. Seluruh elemen pada A bisa dinamakan seperti

berikut :

A[0][0] A[0][1] A[0][2] A[0][3]

A[1][0] A[1][1] A[1][2] A[1][3]

A[2][0] A[2][1] A[2][2] A[2][3]

A[i][j] adalah variabel bertipe int. Kita bisa mengisi nilainya atau

menggunakannya seperti variabel bertipe int biasa.

Perlu juga diketahui bahwa A.length akan memberikan jumlah baris pada A.

Untuk mendapatkan jumlah kolom pada A, kita harus mencari jumlah int dalam

setiap baris, yaitu yang disimpan pada A[0]. Jumlah kolom ini bisa didapatkan

dengan menggunakan A[0].length, atau A[1].length atau A[2].length. (Tidak ada

aturan baku yang menyatakan bahwa pada setiap baris suatu array harus memiliki

panjang yang sama, dan sebenarnya pada beberapa aplikasi, juga digunakan array

dengan panjang yang berbeda-beda pada setiap barisnya. Akan tetapi apabila kita

membuat array dengan perintah seperti di atas, maka kita akan selalu

mendapatkan array dengan panjang array yang sama.)

Array 3 dimensi juga dibuat dan diolah dengan cara yang sama. Misalnya, array 3

dimensi bertipe int bisa dibuat dengan pernyataan "int[][][] B = new int

[7][5][11];". Kita juga bisa mengilustrasikannya sebagai kubus 3-dimensi.

Masing-masing bloknya bertipe int yang bisa dipanggil dalam bentuk B[i][j][k].

Array dimensi lain yang lebih tinggi juga mengikuti pola yang sama, akan tetapi

akan sangat sulit untuk membuat visualisasi struktur arraynya.

Kita bisa mengisi array multi dimensi sekaligus pada saat dideklarasikan. Ingat

sebelumnya bagaimana array 1 dimensi biasa dideklarasikan, dan bagaimana

isinya diinisialisasikan, yaitu seperti daftar nilai-nilainya yang dipisahkan dengan

koma, dan diletakkan di dalam tanda kurung kurawal { dan }.

Inisialisasi array bisa juga digunakan untuk array multi dimensi, yang terdiri dari

beberapa inisialisasi array 1 dimensi, masing-masing untuk setiap barisnya.

Misalnya, array A pada gambar di atas dapat dibuat dengan perintah :

int[][] A = { { 1, 0, 12, -1 },

{ 7, -3, 2, 5 },

{ -5, -2, 2, 9 }

};

Jika tidak ada inisialisasi yang diberikan untuk suatu array, maka nilainya akan

diisi dengan nilai awal tergantung pada tipenya : nol untuk bilangan, false untuk

boolean dan null untuk objek.

Seperti halnya array 1 dimensi, array 2 dimensi juga sering diolah dengan

menggunakan perulangan for. UNtuk mengolah semua elemen pada array 2

dimensi, kita bisa menggunakan pernyataan for bertingkat. Jika array A

dideklarasikan seperti

int[][] A = new int[3][4];

maka kita bisa mengisi 0 untuk semua elemen pada A dengan menggunakan

for (int baris = 0; baris < 3; baris++) {

for (int kolom = 0; kolom < 4; kolom++) {

A[baris][kolom] = 0;

}

}

Pertama kali perulangan for bagian luar akan memproses dengan baris = 0. Bagian

dalamnya akan mengisi keempat kolom pada baris pertama, yaitu A[0][0] = 0,

A[0][1] = 0, A[0][2] = 0, dan A[0][3] = 0. Kemudian perulangan for bagian luar

akan mengisi baris kedua, dan seterusnya.

Dan juga, kita bisa menjumlah semua elemen pada A dengan

int jml = 0;

for (int i = 0; i < 3; i++)

for (int j = 0; j < 4; i++)

jml = jml + A[i][j];

Untuk mengolah array 3 dimensi, tentunya kita harus menggunakan perulangan

for bertingkat 3.

Suatu array 2 dimensi bisa digunakan untuk menyimpan data yang secara alami

memang tersusun sebagai baris dan kolom. Misalnya papan catur terdiri dari 8

baris dan 8 kolom. Jika suatu kelas dinamakan PapanCatur untuk

merepresentasikan papan catur, maka kita bisa deklarasikan dengan perintah

PapanCatur[][] papan = new PapanCatur[8][8];

Kadang-kadang array 2 dimensi juga digunakan untuk masalah yang tidak terlalu

jelas matriksnya. Misalnya perusahaan yang memiliki 25 toko. Anggap masing-

masing toko memiliki keuntungan yang didapat pada masing-masing toko tersebut

setiap bulan pada tahun 2009. Jika toko-toko tersebut memiliki nomor 0 hingga

24, dan 12 bulan dari Januari 09 hingga Desember 09 dinomori 0 hingga 11, maka

data keuntungan dapat disimpan dalam array untung yang dideklarasikan seperti :

double[][] untung = new double[25][12];

untung[3][2] adalah keuntungan yang dibuat oleh toko nomor 3 di bulan Maret.

Atau secara umum, untung[noToko][noBulan] adalah keuntungan toko noToko

pada bulan noBulan. Dalam contoh ini array 1 dimensi untung[noToko] memiliki

arti : Data keuntungan satu toko selama satu tahun.

Anggap array untung telah diisi dengan data. Data ini bisa diolah lebih lanjut.

Misalnya, total keuntungan seluruh perusahaan -- sepanjang tahun dari seluruh

toko -- dapat dihitung dengan menjumlahkan semua elemen pada array :

double totalUntung; // Total keuntungan perusahaan tahun 2009

total Untung = 0;

for (int toko = 0; toko < 25; toko++) {

for (int bulan = 0; bulan < 12; bulan++)

totalUntung += untung[toko][bulan];

}

Kadang-kadang kita juga perlu menghitung hanya satu baris atau satu kolom saja,

bukan keseluruhan array. Misalnya, kita ingin menghitung keuntungan total

perusahaan pada bulan Desember, yaitu bulan nomor 11, maka kita bisa gunakan

perulangan :

double untungDesember = 0.0;

for (noToko = 0; noToko < 25; noToko++)

untungDesember += untung[noToko][11];

Sekarang mari kita buat array 1 dimensi yang berisi total keuntungan seluruh toko

setiap bulan :

double[] untungBulanan; // Keuntungan setiap bulan

untungBulanan = new double[12];

for (int bulan = 0; bulan < 12; bulan++) {

// hitung total keuntungan semua toko bulan ini

untungBulanan[bulan] = 0.0;

for (int toko = 0; toko < 25; toko++) {

untungBulanan[bulan] += profit[toko][bulan];

}

}

Sebagai contoh terakhir untuk mengolah array keuntungan, misalnya kita ingin

tahu toko mana yang menghasilkan keuntungan terbesar sepanjang tahun. Untuk

menghitungnya, kita harus menjumlahkan keuntungan setiap toko sepanjang

tahun. Dalam istilah array, ini berarti kita ingin mengetahui jumlah setiap baris

pada array. Kita perlu mencatat hasil perhitungannya untuk mencari mana toko

dengan keuntungan terbesar.

double untungMaks; // Keuntungan terbesar suatu toko

int tokoTerbaik; // Nomor toko yang memiliki keuntungan terbesar

double total = 0.0; // Total keuntungan suatu toko

// Pertama-tama hitung keuntungan dari toko nomo 0

for (int bulan = 0; bulan < 12; bulan++)

total += untung[0][bulan];

tokoTerbaik = 0; // Mulai dengan anggapan toko nomor 0

untungMaks = total; // adalah toko paling menguntungkan

// Sekarang kita lihat seluruh toko, dan setiap kali

// kita melihat toko dengan keuntungan lebih besar dari

// untungMaks, kita ganti untungMaks dan tokoTerbaik

// dengan toko tersebut

for (toko = 1; toko < 25; toko++) {

// Hitung keuntungan toko tersebut sepanjang tahun

total = 0.0;

for (bulan = 0; bulan < 12; bulan++)

total += untung[toko][bulan];

// Bandingkan keuntungan toko ini dengan untungMaks

if (total > untungMaks) {

untungMaks = total; // keuntungan terbesar saat ini

tokoTerbaik = toko; // datang dari toko ini

}

} // akhir for

// Di sini, untungMaks adalah keuntungan terbesar dari 25 toko

// dan tokoTerbaik adalah toko dengan keuntung tersebut

// (Mungkin juga ada toko yang menghasilkan keuntungan

// yang persis sama.)

BAB III

STACK

A. DEFINISI STACK

Stack adalah suatu tumpukan dari benda. Konsep utamanya adalah LIFO (Last In

First Out), benda yang terakhir masuk dalam stack akan menjadi benda pertama

yang dikeluarkan dari stack.

COMPO

TV

VCD

COMPO

TV

VCD

TV

TV

COMPO

Pada gambar di atas, jika kita ingin mengambil sesuatu dari tumpukan maka kita

harus mengambil benda paling atas dahulu, yakni compo. Misalnya jika VCD

langsung

diambil, compo akan jatuh. Prinsip stack ini bisa diterapkan dalam pemrograman.

Di C++, ada dua cara penerapan prinsip stack, yakni dengan array dan linked

list. Setidaknya stack haruslah memiliki operasi-operasi sebagai berikut:

Push = Untuk menambahkan item pada tumpukan paling atas

Pop = Untuk mengambil item teratas

Clear = Untuk mengosongkan stack

IsEmpty = Untuk memeriksa apakah stack kosong

IsFull = Untuk memeriksa apakah stack sudah penuh

Retreive = Untuk mendapatkan nilai dari item teratas

1. Stack dengan Array

Sesuai dengan sifat stack, pengambilan / penghapusan di elemen dalam stack

harus dimulai dari elemen teratas.

2. Operasi-operasi pada Stack dengan Array

- IsFull

Fungsi ini memeriksa apakah stack yang ada sudah penuh. Stack penuh jika

puncak stack terdapat tepat di bawah jumlah maksimum yang dapat

ditampung stack atau dengan kata lain Top =MAX_STACK -1.

- Push

TV TV

Fungsi ini menambahkan sebuah elemen ke dalam stack dan tidak bisa

dilakukan lagi jika stack sudah penuh.

- Is Empty

Fungsi menentukan apakah stack kosong atau tidak. Tanda bahwa stack

kosong adalah Top bernilai kurang dari nol.

- Pop

Fungsi ini mengambil elemen teratas dari stack dengan syarat stack tidak

boleh kosong.

- Clear

Fungsi ini mengosongkan stack dengan cara mengeset Top dengan -1. Jika

Top bernilai kurang dari nol maka stack dianggap kosong.

- Retreive

Fungsi ini untuk melihat nilai yang berada pada posisi tumpukan teratas.

3. Double Stack dengan Array

Metode ini adalah teknik khusus yang dikembangkan untuk menghemat

pemakaian memori dalam pembuatan dua stack dengan array. Intinya adalah

penggunaan hanya sebuah array untuk menampung dua stack. Tampak jelas

bahwa sebuah array dapat dibagi untuk dua stack, stack 1 bergerak ke atas dan

stack 2 bergerak ke bawah. Jika Top1 (elemen teratas dari Stack 1) bertemu

dengan Top 2 (elemen teratas dari Stack 2) maka double stack telah penuh.

Implementasi double stack dengan array adalah dengan memanfaatkan operasi-

operasi yang tidak berbeda jauh dengan operasi single stack dengan array.

4. Operasi-operasi Double Stack Array

- IsFull

Fungsi ini memeriksa apakah double stack sudah penuh. Stack dianggap

penuh jika Top[0] dan Top[1] bersentuhan sehingga stack tida memiliki

ruang kosong. Dengan kata lain, (Top[0] + 1) > Top[1].

- Push

Fungsi ini memasukkan sebuah elemen ke salah satu stack.

- Is Empty

Fungsi memeriksa apakah stack pertama atau stack kedua kosong. Stack

pertama dianggap kosong jika puncak stack bernilai kurang dari nol,

sedangkan stack kedua dianggap kosong jika puncak stack sama atau

melebihiMAX_STACK.

- Pop

Fungsi ini mengeluarkan elemen teratas dari salah satu stack

- Clear

Fungsi ini mengosongkan salah satu stack.

5. Stack Dengan Single Linked List

Selain implementasi stack dengan array seperti telah dijelasnkan sebelumnya,

ada cara lain untuk mengimplementasi stack dalam C++, yakni dengan single

linked list. Keunggulannya dibandingkan array tebtu saja adalah penggunaan

alokasi memori yang dinamis sehingga menghindari pemborosan memori.

Misalnya saja pada stack dengan array disediakan tempat untuk stack berisi

150 elemen, sementara ketika dipakai oleh user stack hanya diisi 50 elemen,

maka telah terjadi pemborosan memori untuk sisa 100 elemen, yang tak

terpakai. Dengan penggunaan linked list maka tempat yang disediakan akan

sesuai dengan banyaknya elemen yang mengisi stack. Oleh karena itu pula

dalam stack dengan linked list tidak ada istilah full, sebab biasanya program

tidak menentukan jumlah elemen stack yang mungkin ada (kecuali jika sudah

dibatasi oleh pembuatnya). Namun demikian sebenarnya stack ini pun

memiliki batas kapasitas, yakni dibatasi oleh jumlah memori yang tersedia.

6. Operasi-operasi untuk Stack dengan Linked List

- IsEmpty

Fungsi memeriksa apakah stack yang adamasih kosong.

- Push

Fungsi memasukkan elemen baru ke dalam stack. Push di sini mirip dengan

insert dalam single linked list biasa.

- Pop

Fungsi ini mengeluarkan elemen teratas dari stack.

- Clear

Fungsi ini akan menghapus stack yang ada.

List berantai adalah salah satu jenis struktur data, yang tersusun dari objek yang

terkait satu sama lain oleh pointer. Pada bagian sebelumnya, kita menggunakan

list berantai untuk menyimpan String terurut, dan kita juga mengimplementasikan

operasi sisip, hapus dan cari pada list tersebut.

Akan tetapi kita juga bisa menyimpan list String pada array atau ArrayList. Kita

bisa juga mengimplementasikan operasi sisip, hapus, dan cari. Implementasi

operasi tersebut akan berbeda, akan tetapi antar muka dan perilakunya akan tetap

sama.

Istilah tipe data abstrak (abstract data type, atau ADT) adalah kumpulan nilai dan

operasi yang bisa dilakukan pada nilai tersebut, tanpa perlu mengetahui

bagaimana nilai tersebut disimpan dan bagaimana operasi tersebut

diimplementasikan.

Suatu "list terurut yang berisi string" adalah contoh tipe data abstrak. Ada banyak

cara untuk mengimplementasikan tipe data abstrak yang sama, misalnya seperti

disebut di atas, list terurut berisi string bisa diimplementasikan dalam bentuk list

berantai atau array.

Program yang menggunakan tipe data ini bisa menggunakannya tanpa mengetahui

dengan detail tentang implementasinya. Lebih jauh, implementasi TDA bisa

diganti tanpa mempengaruhi jalannya program secara keseluruhan. Dengan cara

ini, program bisa lebih mudah untuk dipelihara dan didebug. TDA adalah alat

penting dalam rekayasa perancang lunak.

Pada bagian ini dan yang akan datang, kita akan lihat TDA lain, yaitu tumpukan

dan antrian. Tumpukan dan antrian sering diimplementasikan dalam bentuk list

berantai, akan tetapi ini bukan satu-satunya cara implementasi. Mari kita anggap

bagian ini sebagai studi kasus dari TDA.

Tumpukan (stack) terdiri dari kumpulan item yang disusun sedemikian rupa

sehingga satu item ditumpuk di atas item lainnya, mirip seperti tumpukan boks.

Hanya item paling atas yang bisa diakses pada suatu saat.

Item tersebut bisa diambil dari tumpukan dengan operasi yang disebut "ambil"

(atau dalam bahasa Inggris, istilah untuk mengeluarkan item dari tumpukan

disebut "pop"). Item di bawah hanya bisa diambil jika semua item di atasnya telah

dikeluarkan dari tumpukan. Suatu item hanya bisa ditambahkan di atas tumpukan

dengan perintah "dorong" (atau "push").

Kita bisa membuat tumpukan dari berbagai macam data. Misalnya, jika itemnya

bertipe int, maka operasi dorong dan keluar bisa diimplementasikan dalam metode

instansi

void dorong(int itemBaru) // Tambah itemBaru di atas tumpukan int ambil() //

Mengambil int paling atas pada tumpukan.

Kita tidak bisa mengambil item dari tumpukan yang kosong, jadi kita juga perlu

memberi tahu apakah suatu tumpukan kosong atau tidak. Kita perlu operasi lain

untuk mengujinya, yang diimplementasikan dalam metode instansi boolean

isKosong() // Kembalikan true jika tumpukan kosong

Ilustrasi berikut menggambarkan tumpukan int, sebagai tipe data abstrak. TDA ini

bisa diimplementasikan dengan berbagai cara, akan tetapi gambar tumpukan di

dalam imaginasi kita akan tetap sama.

Pada implementasi dengan list berantai, tumpukan atas adalah simpul kepala dari

list. Kita bisa menambah dan mengurangi simpul pada kepala list berantai -- jauh

lebih mudah daripada menyisipkan atau menghapus simpul dari tengah-tengah

list.

Berikut ini adalah kelas "tumpukan int" yang mengimplementasikan TDA

menggunakan list berantai. (Kelas ini menggunakan kelas bertingkat sebagai kelas

simpul dari list berantai. Lihat bagian sebelumnya tentang kelas bertingkat. Jika

Anda masih belum paham atau merasa tidak nyaman menggunakan kelas

bertingkat, Anda bisa juga memisahkannya sebagai kelas terpisah.)

public class TumpukanInt {

private static class Simpul {

// Objek dengan tipe Simpul menyimpan

// satu item di dalam list berantai

int item;

Simpul berikut;

}

// Referensi ke simpul paling atas dari tumpukan

// jika atas == null, maka tumpukan tidak berisi

// apa-apa (kosong)

private Simpul atas;

public void dorong( int N ) {

// Letakkan N di tumpukan paling atas

Simpul atasBaru; // Simpul baru untuk menyimpan item baru

atasBaru = new Simpul();

atasBaru.item = N; // Simpan N di simpul baru

atasBaru.berikut = atas; // Simpul baru menunjuk pada atas lama

atas = atasBaru; // Simpul baru sekarang menjadi atas

}

public int ambil() {

// Ambil item paling atas dari dalam tumpukan

// dan kembalikan nilainya. Catatan bahwa rutin ini akan

// melempar NullPointerException jika kita mencoba untuk

// mengambil item dari tumpukan kosong

int itemAtas = atas.item; // Item yang akan diambil

atas = atas.berikut; // Item yang dulunya di posisi kedua sekarang di atas

return itemAtas;

}

public boolean isKosong() {

// Kembalikan true jika tumpukan kosong.

// Kembalikan false jika ada satu atau lebih item di dalam tumpukan

return (atas == null);

}

} // akhir kelas TumpukanInt

Anda perlu memahami bagaimana operasi dorong dan ambil dilaksanakan.

Mungkin sedikit oret-oretan akan membantu. Lihat bahwa list berantai merupakan

bagian private dari kelas TumpukanInt. Program yang menggunakan kelas ini

tidak perlu tahu bahwa list berantai digunakan dalam implementasinya.

Sekarang, kita bisa juga mengimplementasikan tumpukan dalam bentuk array,

bukan hanya list berantai. Karena banyaknya item di dalam tumpukan bervariasi

dan tidak bisa ditentukan, maka kita perlu memiliki variabel lain yang melacak

berapa banyak tempat dalam array yang sudah digunakan.

Jika variabel ini kita namakan atas, maka item akan disimpan dalam tumpukan

pada posisi 0, 1, ..., atas - 1. Item pada posisi 0 adalah item paling bawah dalam

tumpukan, sedangkan item atas - 1 adalah item paling atas.

Untuk mendorong item baru ke dalam tumpukan, kita bisa meletakkan item di

posisi atas kemudian nilai atas ditambahkan 1. Jika kita tidak ingin memberi limit

banyaknya item di dalam tumpukan, kita bisa menggunakan array dinamis yang

telah dibahas sebelumnya.

Berikut ini adalah implementasi kelas TumpukanInt dengan menggunakan array

dinamis:

public class TumpukanInt {

private int[] item = new int[10]; // Menyimpan item dalam tumpukan

private int atas = 0; // Banyaknya item dalam tumpukan

public void dorong( int N ) {

// Tambahkan N ke dalam tumpukan

if (atas == item.length) {

// Array sudah penuh, jadi buat array yang lebih besar dan

// kopi isi tumpukan sekarang ke dalam array baru

int[] arrayBary = new int[ 2*item.length ];

System.arraycopy(item, 0, arrayBary, 0, item.length);

item = arrayBaru;

}

item[atas] = N; // Letakkan N di tempat kosong berikutnya

atas++; // Jumlah item bertambah 1

}

public int ambil() {

// Mengambil item teratas dari tumpukan dan mengembalikannya

// Ingat bahwa rutin ini akan melempar pengecualian

// ArrayIndexOutOfBoundsException jika mencoba mengambil

// item dari tumpukan kosong

int itemAtas = item[top - 1] // Item teratas di dalam tumpukan

atas--; // Jumlah item dalam tumpukan berkurang 1

return itemAtas;

}

public boolean isKosong() {

// Kembalikan true jika tumpukan kosong

// Kembalikan false jika ada satu atau lebih item di dalam tumpukan

return (atas == 0);

}

} // akhir kelas TumpukanInt

Sekali lagi, implementasi tumpukan (dalam bentuk array) bersifat private. Kedua

versi kelas TumpukanInt bisa digunakan dalam suatu program. Jika suatu program

menggunakan versi pertama, maka kita bisa menggantinya dengan versi kedua

tanpa mengubah isi program lain. Akan tetapi, ada satu kasus di mana kedua kelas

akan berbeda, yaitu jika mencoba mengambil item dari tumpukan kosong, maka

versi pertama akan melemparkan NullPointerException sedangkan versi kedua

akan melemparkan ArrayIndexOutOfBoundsException.

Mungkin akan lebih baik untuk mendefinisikan jenis pengecualian baru, misalnya

EmptyStackException di kedua versi. Dan sebetulnya TDA harusnya memberikan

spesifikasi apa yang harus dilakukan jika program mencoba mengambil item dari

tumpukan kosong. Ini yang sering dilupakan ketika seseorang membuat

spesifikasi untuk interface, yang akhirnya masalah lain akan muncul di kemudian

hari.

Apa contoh kegunaan tumpukan dalam keadaan sehari-hari? Misalnya, lihat apa

yang terjadi jika suatu rutin memanggil subrutin. Rutin pertama akan dihentikan

sementara ketika subrutin yang dipanggil dieksekusi, dan akan diteruskan apabila

subrutin yang dipanggil selesai dijalankan.

Sekarang, misalnya subrutin tersebut memanggil subrutin kedua, dan subrutin

kedua memanggil subrutin ketiga, dan seterusnya. Setiap subrutin akan berhenti

untuk sementara ketika subrutin berikutnya dipanggil. Komputer harus bisa

melacak subrutin yang dihentikan. Bagaimana caranya? Yaitu dengan

menggunakan tumpukan.

Ketika subrutin dipanggil, catatan aktivasi (activation record) dibuat untuk

subrutin tersebut. Catatan aktivasi ini berisi informasi yang relevan tentang

eksekusi dari subruti tersebut, misalnya parameter dan variabel lokalnya. Catatan

aktivasi ini ditempatkan dalam tunpukan. Catatan ini akan dibuang ketika subrutin

selesai dipanggil.

Jika subrutin ini memanggil subrutin lain, maka catatan aktivasi dari subrutin

kedua akan didorong ke dalam tumpukan, di atas catatan aktivasi subrutin

pertama. Tumpukan akan semakin besar jika semakin banyak subrutin yang

dipanggil, dan semakin kecil jika subrutin-subrutin itu selesai dijalankan.

Contoh lainnya, tumpukan digunakan untuk mengevaluasi ekspresi postfix

(postfix expresssion). Ekspresi matematika biasa seperti 2+(15-12)*17 disebut

ekspresi infix. Dalam ekspresi infix, operator berada di tengah nilai yang akan

dihitung, misalnya "2 + 2". Dalam ekspresi postfix, operator ada di akhir nilai,

misalnya "2 2 +".

Ekspresi 2+(15-12)*17" dapat ditulis dalam bentuk postfix menjadi "2 15 12 - 17

* +". Di sini operator "-" dilakukan pada dua nilai sebelumnya, yaitu "15" dan

"12". Tanda * dilakukan pada dua nilai sebelumnya, yaitu "15 12 -" dan "17". Dan

operator "+" dilakukan pada 2 dan "15 12 - 17 *". Hasilnya akan persis sama

dengan ekspresi infix awalnya.

Meskipun lebih mudah bagi manusia untuk melakukan perhitungan dengan

ekspresi infix, ekspresi postfix memiliki beberapa keuntungan. Satu hal, ekspresi

postfix tidak memerlukan tanda kurung atau aturan perhitungan (tanda kali harus

dilakukan lebih dulu sebelum tambah misalnya). Aturan penghitungan hanya

ditentukan berdasarkan urutannya saja. Sehingga algoritma yang menghitung

ekspresi postfix dapat menjalankannya dengan lebih cepat dan tepat.

Sekarang misalnya kita akan menghitung ekspresi "2 15 12 - 17 * +" dari kiri ke

kanan. Nilai yang kita temui pertama adalah 2, tapi apa yang bisa kita lakukan

dengan 2? Di sini kita belum tahu operatornya, dan selain itu kita juga belum tahu

nilai lainnya. Kita akan ingat nilai 2 ini untuk sementara, yaitu dengan

mendorongnya ke dalam tumpukan.

Berikutnya, kita akan melihat nilai 15, yang kita juga masukkan ke dalam

tumpukan di atas nilai 2. Kemudian nilai 12 juga dimasukkan ke dalam tumpukan

di atas 15.

Sekarang kita sampai pada operator "-". Operasi ini dilakukan pada dua nilai

sebelumnya. Kita telah menyimpan 2 nilai sebelumnya ke dalam tumpukan, yaitu

15 dan 12. Sekarang kita ambil 2 nilai tersebut dari dalam tumpukan, dan kita

lakukan perhitungan 15 - 12 yaitu 3.

Nilai 3 ini kita simpan lagi ke dalam tumpukan. Ingat bahwa 15 dan 12 sudah

diambil dari dalam tumpukan, sehingga hanya nilai 2 yang ada di dalam

tumpukan. Setelah nilai 3 dimasukkan ke dalam tumpukan, maka 3 ada di atas 2

di dalam tumpukan.

Item berikutnya adalah 17, yang juga dimasukkan ke dalam tumpukan di atas nilai

3. Untuk menghitung item berikutnya "*", kita ambil 2 nilai dari dalam tumpukan,

yaitu 3 dan 17. Hasil dari 3 * 17, yaitu 51 dimasukkan kembali ke dalam

tumpukan (di atas 2 yang masih ada di dalam tumpukan).

Item berikutnya adalah "+", yang akan mengambil 51 dan 2 dari dalam tumpukan,

menghitung hasilnya, yaitu 53, kemudian menyimpannya lagi ke dalam

tumpukan. Sekarang kita sampai pada akhir ekspresi. Nilai pada tumpukan itu

adalah hasil perhitungan keseluruhan ekspresi. Kita cukup mengambil nilainya

dan melaporkan hasilnya, yaitu 53.

Algoritma untuk melakukan perhitungan ekspresi postfix adalah sebagai berikut :

Mulai dengan tumpukan kosong

untuk setiap item di dalam ekspresi:

jika item berupa bilangan:

Dorong item ke dalam tumpukan

jika item berupa operator

Ambil dua nilai dari tumpukan // bisa terjadi kesalahan

Lakukan perhitungan dua nilai dengan operator tersebut

Dorong hasil perhitungan ke dalam tumpukan

else

Ada kesalahan dalam ekspresi

Ambil nilai dari tumpukan

Jika tumpukan tidak kosong:

Ada kesalahan dalam ekspresi

else:

Nilai terakhir adalah hasil perhitungan

Kesalahan ekspresi dapat dideteksi dengan mudah. Misalnya, dalam ekspresi "2 3

+ *", tidak cukup nilai untuk menghitung operasi "*". Ini akan dideteksi oleh

algoritma ketika mencoba mengambil nilai kedua dari dalam tumpukan, karena

pada saat itu tumpukan sudah kosong.

Kesalahan lain bisa juga muncul ketika menghitung ekspresi "2 3 4 +", di mana

tidak cukup operator untuk menghitung semua nilai. Ini akan dideteksi ketika 2

masih ada di dalam tumpukan di akhir algoritma.

Ekspresi postfix sering digunakan secara internal oleh komputer. Dan sebenarnya,

mesin virtual Java adalah "mesin tumpukan", yang menggunakan tumpukan untuk

melakukan perhitungan yang telah kita diskusikan. Algoritma ini bisa diperluas

untuk menangani variabel dan konstanta. Ketika variabel ditemukan di dalam

ekspresi, isi variabel ini didorong ke dalam tumpukan.

Algoritma ini juga bisa dikembangkan untuk operator yang membutuhkan kurang

atau lebih dari dua operator. Banyaknya nilai yang diambil dari dalam tumpukan

bisa disesuaikan dengan berapa banyak nilai yang dibutuhkan. Misalnya, operator

"-" sebagai operator negasi, misalnya "-x" hanya membutuhkan satu nilai.

BAB IV

LINGKED LIST

Linked adalah koleksi obyek heterogen dengan sifat setiap obyek (kecuali obyek

terakhir) mempunyai penerus dan setiap obyek (kecuali obyek pertama)

mempunyai pendahulu. Salah satu penggunaan pointer adalah untuk membuat

linked list atau senarai berantai. Linked list sendiri dapat diartikan sebagai

sekumpulan komponen yang saling berhubungan (berantai) dengan bantuan

pointer. Perhatikan ilustrasi berikut untuk lebih jelasnya.

Single Linked List merupakan jenis Linked List yang hanya menggunakan satu

variabel pointer untuk menyimpan banyak data.Double Linked List Merupakan

linked list yang tiap-tiap nodenya menyimpan node sebelumnya dan node yang

selanjutnya, atau biasa disebut dengan linked list berpointer ganda Circular

Linked adalah linked list yang node awalnya menunjuk ke node akhir dan node

akhirnya menunjuk ke node awal. Sehingga membentuk link list tersebut

membentuk suatu siklus seperti lingkaran.

BAB V

QUEUE

A. DEFINISI QUEUE

Jika diartikan secara harafiah, queue berarti antrian, queue merupakan salah satu

contoh aplikasi dari pembuatan double linked list yang cukup sering kita temui

dalam kehiduypan sehari-hari, misalnya saat Anda mengantri di loket untuk

membeli tiket. Istilah yang cukup sering dipakai seseorang masuk dalam sebuah

antrian adalah enqueue. Dalam suatu antrian, yang dating terlebih dahulu akan

dilayani lebih dahulu. Istilah yang sering dipakai bila seseorang keluar dari antrian

adalah dequeue. Walaupun berbeda implementasi, struktur data queue setidaknya

harus memiliki operasi-operasi sebagai berikut :

EnQueue : Memasukkan data ke dalam antrian

DeQueue : Mengeluarkan data terdepan dari antrian

Clear : Menghapus seluruh antrian

IsEmpty : Memeriksa apakah antrian kosong

IsFull : Memeriksa apakah antrian penuh

1. Implementasi Queue dengan Linear Array

Linear array adalah suatu array yang dibuat seakan-akan merupakan suatu garis

lurus dengan satu pintu masuk dan satu pintu keluar. Berikut ini diberikan

deklarasi kelas Queue Linear sebagai implementasi dari Queue menggunakan

linear array. Dalam prakteknya, anda dapat menggantinya sesuai dengan

kebutuhan Anda. Data diakses dengan field data, sedangkan indeks item

pertama dan terakhir disimpan dalam field Head dan Tail. Konstruktor akan

menginisialisasikan nilai Head dan Tail dengan -1 untuk menunjukkan bahwa

antrian masih kosong dan mengalokasikan data sebanyak MAX_QUEUE yang

ditunjuk oleh Data. Destruktor akan mengosongkan antrian kembali dan

mendealokasikan memori yang digunakan oleh antrian.

Operasi-Operasi Queue dengan Linear Array

a. IsEmpty

Fungsi IsEmpty berguna untuk mengecek apakah queue masih kosong atau

sudah berisi data. hal ini dilakukan dengan mengecek apakah tail bernilai -1

atau tidak. Nilai -1 menandakan bahwa queue masih kosong.

b. Is Full

Fungsi IsFull berguna untuk mengecek apakah queue sudah penuh atau

masih bisa menampung data dengan cara mengecek apakah nilai tail sudah

sama dengan jumlah maksimal queue. Jika nilai keduanya sama, berarti

queue sudah penuh.

c. EnQueue

Fungsi EnQueue berguna untuk memasukkan sebuah elemen dalam queue.

d. DeQueue

Fungsi DeQueue berguna untuk mengambil sebuah elemen dari queue.

Operasi ini sering disebut juga serve. Hal ini dilakukan dengan cara

memindahkan sejauh satu langkah ke posisi di depannya sehingga otomatis

elemen yang paling depan akan tertimpa dengan elemen yang terletak di

belakangnya.

e. Clear

Fungsi Clear berguna untuk menghapus semua lemen dalam queue dengan

jalan mengeluarkan semua elemen tersebut satu per satu hingga queue

kosong dengan memanfaatkan fungsi DEQueue.

2. Implementasi Queue dengan Circular Array

Circular array adalah suatu array yang dibuat seakan-akan merupakan sebuah

lingkaran dengan titik awal (head) dan titik akhir (tail) saling bersebelahan jika

array tersebut masih kosong. Posisi head dan tail pada gambar diatas adalah

bebas asalkan saling bersebelahan. Berikut ini diberikan deklarasi kelas Queue

Circular sebagai implementasi circular array. Dalam prakteknya, Anda dapat

menggantikanny sesuai dengan kebutuhan Anda. Data diakses dengan field

data, sedangkan indeks itemn pertama dan terakhir disimpan dalam field Head

dan Tail. Konstruktor akan menginisialisasi nilai Head dan Tail dengan 0 dan

MAX-QUEUE-1 untuk menunjukkan bahwa antrian masih kosong dan

mengalokasikan data sebanyak MAX-QUEUE yang ditunjuk oleh Data.

destruktor akan mengosongkan antrian kembali dan mendealokasikan memori

yang digunakan oleh antrian.

Operasi-Operasi Queue dengan Circular Array

a. Is Empty

Fungsi IsEmpty berguna untuk mengecek apakah Queue masih kosong atau

sudah berisi. Hal ini dilakukan dengan mengecek apakah tail masih terletak

bersebelahan dengan head dan tail lebih besar dari head atau tidak. Jika

benar, maka queue masih kosong.

b. IsFull

Fungsi IsFull berguna untuk mengecek apakah queue sudah penuh atau

masih bisa menampung data dengan cara mengecek apakah tempat yang

masih kosong tinggal satu atau tidak (untuk membedakan dengan empty

dimana semua tempat kosong). Jika benar berarti queue penuh.

c. EnQueue

Fungsi EnQueue berguna untuk memasukkan sebuah elemen ke dalam

queue tail dan head mula-mula bernilai nol (0).

d. DeQueue

DeQueue berguna untuk mengambil sebuah elemen dari queue. Hal ini

dilakukan dengan cara memindahkan posisi head satu langkah ke belakang.

3. Implementasi Queue dengan Double Linked List

Selain menggunakan array, queue juga dapat dibuat dengan linked list. Metode

linked list yang digunakan adalah double linked list.

Operasi-operasi Queue dengan Double Linked List

a. IsEmpty

Fungsi IsEmpty berguna untuk mengecek apakah queue masih kosong atau

sudah berisi data. Hal ini dilakukan dengan mengecek apakah head masih

menunjukkan pada Null atau tidak. Jika benar berarti queue masih kosong.

b. IsFull

Fungsi IsFull berguna untuk mengecek apakah queue sudah penuh atau

masih bias menampung data dengan cara mengecek apakah Jumlah Queue

sudah sama dengan MAX_QUEUE atau belum. Jika benar maka queue

sudah penuh.

c. EnQueue

Fungsi EnQueue berguna untuk memasukkan sebuah elemen ke dalam

queue (head dan tail mula-mula meunjukkan ke NULL).

d. DeQueue

Procedure DeQueue berguna untuk mengambil sebuah elemen dari queue.

Hal ini dilakukan dengan cara menghapus satu simpul yang terletak paling

depan (head).

Antrian

Posted Sab, 03/28/2009 - 23:23 by belajarprogram

Versi ramah cetak

Antrian (queue) adalah struktur data mirip dengan tumpukan, yaitu terdiri dari

item dalam urutan tertentu. Antrian memiliki dua ujung, yang disebut ujung depan

dan ujung belakang. Item selalu dimasukkan dari belakang antrian, dan selalu

dikeluarkan dari depan antrian. Operasi memasukkan dan mengeluarkan item dari

dalam antrian disebut "masuk" dan "keluar" (dalam bahasa Inggris disebut

enqueue dan dequeue).

Suatu item yang ditambahkan di belakang antrian tidak bisa dihapus sebelum item

di depannya dihapus. Mirip seperti antrian pada kasir atau pada customer service

di bank misalnya. Customer akan dilayani dalam urutan ketika mereka datang.

Antrian bisa menampung item dengan jenis apa saja. Untuk antrian int, operasi

masuk dan keluar dapat diimplementasikan sebagai metode instansi dalam kelas

"AntrianInt". Kita juga membutuhkan metode instansi untuk menguji apakah

antrian kosong atau tidak:

void masul(int N) // Tambah N di belakang antrian

int keluar() // Keluarkan antrian dari depan dan kembalikan isinya

boolean isKosong() // Kembalikan true jika antrian kosong

Antrian bisa diimplementasikan dalam bentuk list berantai atau array. Akan tetapi

implementasi yang efisien dalam bentuk array sedikit lebih sulit, sehingga akan

kita abaikan dalam diskusi kita.

Dalam implementas dalam bentuk list berantai, item bertama adalah item di depan

antrian. Untuk mengeluarkan item dari depan antrian, kita dapat lakukan seperti

mengambil item dari atas tumpukan.

Belakang antrian adalah akhir dari list. Unutk memasukkan item ke dalam antrian,

kita harus mengeset pointer di akhir simpul untuk menunjuk ke simpul baru yang

berisi item yang akan kita tambahkan. Kita bisa menggunakan perintah seperti

"buntut.berikut = simpulBaru;", di mana buntut adalah pointer ke simpul terakhir

dari list.

Jika kepala adalah pointer ke simpul pertama, maka kita bisa mendapat pointer ke

simpul terakhir dengan menggunakan :

Simpul buntut; // Pointer ini akan menunjuk ke simpul terakhir

buntut = kepala; // Mulai dari simpul pertama

while (buntut.berikut != null) {

buntut = buntut.berikut;

}

// Di sini, buntut.berikut berisi null, artinya buntut adalah

// simpul terakhir di dalam list

Akan tetapi, tentunya akan sangat tidak efisien jika kita harus melakukan

perulangan terus menerus setiap kali kita memasukkan item baru ke dalam

antrian. Dengan alasan efisiensi, kita akan menyimpan pointer ke akhir simpul

sebagai variabel instansi. Kita harus selalu ingat untuk terus mengupdate isi

variabel ini setiap kali simpul baru ditambahkan ke akhir list.

Dengan pengetahuan di atas, kita bisa membuat kelas "AntrianInt" dengan mudah

sebagai berikut :

public class AntrianInt {

private static class Simpul {

// Objek bertipe Simpul berisi item dalam bentuk

// list berantai

int item;

Simpul berikut;

}

// Menunjuk ke simpul pertama pada antrian

// Jika antrian kosong, maka kepala berisi null

private Simpul kepala = null;

private Simpul buntut = null; // Menunjuk ke simpul akhir pada antrian

void masuk( int N ) {

// Menambahkan N ke akhir antrian

Simpul buntutBaru = new Simpul(); // Simpul baru untuk menampung item

baru

buntutBaru.item = N;

if (kepala == null) {

// Antrian kosong, sehingga simpulBaru menjadi

// satu-satunya simpul di dalam list. Sehingga

// kepala dan buntut sama-sama menunjuk ke simpulBaru

kepala = buntutBaru;

buntut = buntutBaru;

}

else {

// Simpul baru menjadi buntut antrian

// (kepala tidak berpengaruh apa-apa)

buntut.berikut = buntutBaru;

buntut = buntutBaru;

}

}

int keluar() {

// Keluarkan item dari kepala antrian

// Bisa melempar NullPointerException.

int itemPertama = kepala.item;

kepala = kepala.berikut; // Sekarang item kedua menjadi kepala

if (kepala == null) {

// Sekarang antrian kosong. Simpul yang telah dihapus adalah

// kepala sekaligus buntut, karena simpul ini adalah satu-satunya

// yang ada di dalam antrian. Isi buntut dengan null.

buntut = null;

}

return itemPertama;

}

boolean isKosong() {

// Kembalikan true jika antrian kosong

return (kepala == null);

}

} // akhir kelas AntrianInt

Antrian digunakan dalam komputer (dan juga dalam kehidupan nyata) ketika

hanya satu item yang bisa diproses pada suatu saat, akan tetapi banyak item bisa

menunggu untuk diproses, misalnya :

Dalam Java program yang memiliki banyak threads, thread yang ingin diolah

dalam CPU disimpan di dalam antrian. Ketika thread baru dimulai, thread ini

ditambahkan ke dalam antrian. Thread akan dihapus dari depan antrian, diolah

oleh CPU, dan kemudian -- jika belum selesai -- diletakkan kembali di belakang

antrian untuk menunggu giliran berikutnya.

Event seperti ketikan tombol dan klik mouse disimpan dalam antrian yang disebut

"antrian event". Program akan menghapus item dari antrian item dan

mengolahnya satu per satu. Mungkin saja terjadi beberapa event diterima ketika

satu event sedang diproses, akan tetapi event akan diolah berdasarkan urutan

kedatangannya

ServerSocket, memiliki antrian di dalamnya yang berisi permintaan sambungan

yang diterima akan tetapi belum dilayani. Metode accept() pada kelas

ServerSocket menerima permintaan sambungan berikutnya dari depan antrian ini.

Antrian disebut mengikuti kebijakan FIFO (First In First Out, atau Pertama Masuk

Pertama Keluar). Atau dalam bahasa awam, pertama datang dan pertama dilayani.

Di lain pihak, tumpukan mengikuti prinsip LIFO (Last In First Out, Terakhir

Masuk Pertama Keluar). Item yang bisa keluar dari tumpukan adalah item

terkakhir yang dimasukkan. Seperti antrian, tumpukan juga bisa digunakan untuk

menampung item yang sedang menunggu untuk diproses (walaupun dalam

aplikasi di mana antrian biasa digunakan, tumpukan adalah antrian yang tidak

adil).

BAB VI

Binary Tree

Binary Tree adalah tree dengan syarat bahwa tiap node hanya boleh memiliki

maksimal dua subtree dan kedua subtree tersebut harus terpisah. Sesuai dengan

definisi tersebut tiap node dalam binary tree hanya boleh memiliki paling banyak

dua child.

A. Jenis- Jenis Binary Tree

1. Full Binary Tree

Jenis binary tree ini tiap nodenya (kecuali leaf) memiliki dua child dan tiap

subtree harus mempunyai panjang path yang sama.

2. Complete Binary Tree

Jenis ini mirip dengan Full Binary Tree, namun tiap subtree boleh memiliki

panjang path yang berbeda dan setiap node kecuali leaf hanya boleh memiliki 2

child.

3. Skewed Binary Tree

Skewed Binary Tree adalah Binary Tree yang semua nodenya (kecuali leaf)

hanya memiliki satu child.

4. Implementasi Binary Tree

Binary tree dapat diimplementasikan dalam C++ dengan menggunakan double

linkedlist.

Operasi-Operasi pada Binary Tree

Create : Membentuk binary tree baru yang masih kosong

Clear : Mengosongkan binary tree yang sudah ada

Empty : Function untuk memeriksa apakah binary tree masih kosong

Insert : Memasukkan sebuah node ke dalam tree. Ada tiga pilihan insert :

sebagai root, left child, atau right child. Khusus insert sebagai root, tree harus

dalam keadaan kosong

Find : Mencari root, parent, left child, atau right child dari suatu node. (tree

tidak boleh kosong).

Update : Mengubah isi dari node yang ditunjuk oleh pointer curret (Tree tidak

boleh kosong)

Retrieve : Mengetahui isi dari node yang ditunjuk oleh pointer current (Tree

tidak boleh kosong)

DeleteSub : Menghapus sebuah subtree (node beserta seluruh descendantnya)

yang ditunjuk current. Tree tidak boleh kosong. Setelah itu, pointer current

dakan berpindah ke parent dari node yang dihapus. Characteristic Mengetahui

karakteristik dari suatu tree, yakni: size, height, serta average length. Tree tidak

boleh kosong. Traverse Mengunjungi seluruh node-node pada tree, masing-

masing sekali. Hasilnya adalah urutan informasi secara linear yang tersimpan

dalam tree. Ada tiga cara traverse,yaitu PreOrder, InOrder, dan PostOrder.

Langkah-langkah Tranverse :

· PreOrder : cetak isi node yang dikunjungi, kunjungi Left Child, kunjungi

Right

Child

· InOrder : kunjungi Left Child, cetak isi node yang dikunjungi, kunjungi Right

Child

· PostOrder : kunjungi Left Child, kunjungi Right Child cetak isi node yang

dikunjungi.

5. Binary Search Tree

Binary Tree ini memiliki sifat dimana semua left child harus lebih kecil dari

pada right child dan parentnya. Semua right child juga harus lebih besar dari

left child serta parentnya. Binary search tree dibuat untuk mengatasi kelemahan

pada binary tree biasa, yaitu kesulitan dalam searching / pendarian node

tertentu dalam binary tree. Pada dasarnya operasi dalam Binary Search Tree

sama dengan Binary Tree biasa, kecuali pada operasi insert, update, dan delete.

6. Insert

Pada Binary Search Tree insert dilakukan setelah lokasi yang tepat ditemukan

(lokasi tidak ditentukan oleh user sendiri ).

7. Update

Update ini seperti yang ada pada Binary Tree biasa, namun di sini update akan

berpengaruh pada posisi node tersebut selanjutnya. Bila update mengakibatkan

tree tersebut bukan Binary Search Tree lagi, harus dilakukan perubahan pada

tree dengan melakukan rotasi supaya tetap menjadi Binary Search Tree.

8. Delete

Seperti halnya update, delete dalam Binary Search Tree juga turut

mempengaruhi struktur dari tree tersebut.

B. AVL TREE

AVL Tree adalah Binary Search Tree yang memiliki perbedaan tinggi/ level

maksimal 1antara subtree kiri dan subtree kanan. AVL Tree muncul untuk

menyeimbangkan Binary Search Tree. Dengan AVL Tree, waktu pencarian dan

bentuk tree dapat dipersingkat dan disederhanakan.

Selain AVL Tree, terdapat pula Height Balanced n Tree, yakni Binary Search

Tree yang memiliki perbedaan level antara subtree kiri dan subtree kanan

maksimal adalah sehingga dengan kata lain AVL Tree adalah Height Balanced 1

Tree. Untuk memudahkan dalam menyeimbangkan tree, digunakan simbol-simbol

Bantu :

- (tanda minus) : digunakan apabila Subtree kiri lebih panjang dari Subtree kanan.

+ (tanda plus) : digunakan apabila Subtree kanan lebih panjang dari Subtree kiri.

0 (nol) : digunakan apabila Subtree kiri dan Subtree kanan mempunyai height

yang sama.

Kita telah melihat di beberapa bagian sebelumnya bagaimana objek bisa dikaitkan

satu sama lain menjadi list berantai. Ketika suatu objek memiliki 2 pointer ke

objek dengan tipe yang sama, kita bisa membuat struktur data yang lebih

kompleks dari list berantai. Dalam bagian ini kita akan melihat salah satu struktur

dasar dan paling berguna: pohon biner (binary tree).

Setiap objek dalam pohon biner memiliki dua pointer, yang biasa disebut kiri dan

kanan. Selain itu, tentunya simpul pada pohon memiliki data yang bisa bertipe apa

saja. Misalnya, pohon biner integer bisa dibuat dalam bentuk :

class SimpulPohon {

int item; // Data pada simpul ini

SimpulPohon kiri; // Pointer ke cabang sebelah kiri

SimpulPohon kanan; // Pointer ke cabang sebelah kanan

}

Pointer kiri dan kanan dalam SimpulPohon bisa beriis null atau menunjuk pada

objek lain dengan tipe SimpulPohon. Simpul yang menunjuk pada simul lain

disebut induk (parent), sedangkan yang ditunjuk disebut anak (child). Dalam

gambar di atas, simpul 3 adalah induk dari simpul 6, dan simpul 4 dan 5 adalah

anak dari simpul 2.

Tidak semua struktur yang terdiri dari simpul pohon merupakan pohon biner.

Pohon biner harus memiliki sifat :

Harus ada satu simpul di dalam pohon yang tidak memiliki induk. Simpul ini

disebut simpul akar (root).

Simpul lain harus memiliki hanya satu induk

Tidak boleh ada perulangan dalam pohon biner, artinya tidak boleh ada rantai

pointer yang dimulai dari satu simpul dan berakhir di simpul yang sama.

Simpul yang tidak memiliki anak disebut simpul daun (leaf). Simpul daun dapat

dikenali karena kedua pointer kiri dan kanannya berisi null. Dalam ilustrasi suatu

pohon biner, biasanya simpul akar terletak di atas dan simpul daun terletak di

bawah -- tidak sama seperti pohon sungguhan. Akan tetapi, kita bisa melihat

cabang-cabang, seperti pohon, yang merupakan cikal bakal nama pohon biner ini.

Misalnya, mari kita lihat suatu simpul pada pohon biner. Lihat simpul tersebut

beserta seluruh simpul turunannya (yaitu anak, anak dari anaknya, dan

seterusnya). Simpul-simpul ini juga membentuk pohon biner, yang disebut pohon

cabang (subtree) dari pohon awalnya. Misalnya, pada gambar di atas, simpul 2, 4,

dan 5 membentuk pohon cabang. Pohon cabang ini disebut pohon cabang sebelah

kiri dari simpul akarnya. Hal yang sama, simpul 3 dan 6 adalah pohon cabang

sebelah kanan dari simpul akarnya. Salah satu atau kedua pohon cabang bisa

kosong. Ini adalah definisi rekursif. Jadi tidak heran apabila kita menerapkan

subrutin rekursif untuk mengolah struktur data pohon.

Mari kita lihat bagaimana caranya menghitung banyaknya simpul di dalam pohon

biner. Sebagai latihan, kita mungkin bisa membuat algoritma untuk menghitung

simpul. Inti permasalahannya adalah, bagaimana melacak simpul mana yang

belum dihitung. Ini bukan hal sepele. Dan mungkin kita tidak mungkin

menyelesaikannya tanpa menggunakan tumpukan atau antrian.

Dengan rekursi, algoritmanya akan jauh lebih mudah. Suatu pohon bisa kosong,

atau bisa terdiri dari akar dan dua pohon cabang. Jika pohon kosong, maka

banyaknya simpul adalah nol. (Ini merupakan kasus dasar dari rekursi). Kemudian

kita bisa menggunakan rekursi untuk menghitung jumlah simpul pada masing-

masing pohon cabang. Jumlahkan hasil dari kedua cabang, kemudian tambah satu

simpul akarnya. Ini adalah jumlah simpul di dalam pohon.

Dalam Java bisa kita tuliskan sebagai :

static int hitungSimpul( SimpulPohon akar ) {

// Hitung berapa simpul yang dimiliki suatu pohon

// biner, termasuk akarnya

if ( akar == null )

return 0; // Pohon kosong, tidak ada simpul di dalamnya

else {

int jumlah = 1; // Mulai dengan menghitung akarnya

// Tambahkan dengan simpul dari pohon cabang sebelah kiri

jumlah += hitungSimpul(akar.kiri);

// Tambahkan dengan simpul dari pohon cabang sebelah kanan

jumlah += hitungSimpul(akar.kanan);

return hitung; // Kembalikan jumlahnya

}

} // akhir hitungSimpul()

Juga, mari kita lihat bagaimana mencetak isi item di dalam pohon biner. Jika

pohon kosong, kita tidak melakukan apa-apa. Jika pohon tidak kosong, maka

mungkin ia berisi akar dan dua pohon cabangnya. Cetak item pada akarnya, dan

gunakan rekursi untuk mencetak item di dalam pohon cabangnya. Berikut ini

adalah subrutin untuk mencetak semua item dalam satu baris cetakan.

static void preorderCetak( SimpulPohon akar ) {

// Cetak semua item di dalam pohon yang ditunjuk oleh akar.

// Item pada akar dicetak dahulu, kemudian item di sebelah kiri

// dan baru item di pohon cabang sebelah kanan

if ( akar != null ) { // (Jika null, kita tidak melakukan apa-apa.)

System.out.print( akar.item + " " ); // Print item akar

preorderCetak( akar.kiri ); // Print item di pohon cabang kiri

preorderCetak( akar.kanan ); // Print items di pohon cabang kanan

}

} // akhir preorderCetak()

Rutin ini disebut "preorderCetak" karena ia menelusuri pohon secara preorder.

Dalam penelusuran preorder, simpul akan diproses terlebih dahulu, kemudian

pohon cabang sebelah kiri ditelusuri, dan kemudian cabang sebelah kanan. Dalam

penelusuran postorder, cabang kiri ditelusuri, kemudian cabang kanan, baru

kemudian simpul akar. Dan dalam penelusuran inorder, cabang kiri dikunjungi

dahulu, kemudian akar, dan kemudian cabang kanan.

Subrutin yang mencetak postorder dan inorder berbeda dengan preorder dalam

urutan pencetakannya di layar :

static void postorderCetak( SimpulPohon akar ) {

// Cetak semua item di dalam pohon yang ditunjuk oleh akar.

// Cabang pohon sebelah kiri dicetak dahulu, kemudian kanan,

// dan baru simpul akarnya

if ( akar != null ) { // (Jika null, kita tidak melakukan apa-apa.)

postorderCetak( akar.kiri ); // Print item di pohon cabang kiri

postorderCetak( akar.kanan ); // Print items di pohon cabang kanan

System.out.print( akar.item + " " ); // Print item akar

}

} // akhir postorderCetak()

static void inorderCetak( SimpulPohon akar ) {

// Cetak semua item di dalam pohon yang ditunjuk oleh akar.

// Cabang pohon cabang sebelah kiri dicetak dahulu,

// kemudian simpul akarnya, baru pohon cabang sebelah kanan

if ( akar != null ) { // (Jika null, kita tidak melakukan apa-apa.)

inorderCetak( akar.kiri ); // Print item di pohon cabang kiri

System.out.print( akar.item + " " ); // Print item akar

inorderCetak( akar.kanan ); // Print items di pohon cabang kanan

}

} // akhir inorderCetak()

Subrutin ini bisa dijalankan pada pohon biner yang diilustrasikan di awal bagian

ini. Urutan item ketika dicetak akan berbeda, di mana :

preorderCetak mencetak: 1 2 4 5 3 6

postorderCetak mencetak: 4 5 2 6 3 1

inorderCetak mencetak: 4 2 5 1 3 6

Dalam preorderCetak misalnya, itam pada akar pohon, yaitu 1, dicetak paling

awal. Akan tetapi urutan preorder juga dilakukan untuk setiap pohon cabangnya.

Simpul akar pada pohon cabang sebelah kiri, yaitu 2, dicetak terlebih dahulu

sebelum pohon cabangnya 4 dan 5. Sedangkan untuk cabang sebelah kanan,

akarnya 3 akan dicetak sebelum 6. Penelusuran preorder dilakukan pada semua

cabang pohon. Urutan penelusuran yang lainnya bisa dianalisis dengan cara yang

sama.

BAB VII

SORTING

Pengurutan data dalam struktur data sangat penting untuk data yang beripe data

numerik ataupun karakter. Pengurutan dapat dilakukan secara ascending (urut

naik) dan descending (urut turun) pengurutan (Sorting) adalah proses menyusun

kembali data yang sebelumnya telah disusun dengan suatu pola tertentu, sehingga

tersusun secara teratur menurut aturan tertentu.

Contoh:

Data Acak : 5 6 8 1 3 25 10

Ascending : 1 3 5 6 8 10 25

Descending : 25 10 8 6 5 3 1

A. BUBBLE SORT

Metode sorting termudah

Diberi nama “Bubble” karena proses pengurutan secara berangsur-angsur

bergerak/berpindah ke posisinya yang tepat, seperti gelembung yang keluar dari

sebuah gelas bersoda.

Bubble Sort mengurutkan data dengan cara membandingkan elemen sekarang

dengan elemen berikutnya.

B. EXCHANGE SORT

Sangat mirip dengan Bubble Sort Banyak yang mengatakan Bubble Sort sama

dengan Exchange Sort

Pebedaan : dalam hal bagaimana membandingkan antar elemen-elemennya.

Exchange sort membandingkan suatu elemen dengan elemen-elemen lainnya

dalam array tersebut, dan melakukan pertukaran elemen jika perlu. Jadi ada

elemen yang selalu menjadi elemen pusat (pivot). sedangkan Bubble sort akan

membandingkan elemen pertama/terakhir dengan elemen

sebelumnya/sesudahnya, kemudian elemen tersebut itu akan menjadi pusat \

(pivot) untuk dibandingkan dengan elemen sebelumnya/sesudahnya lagi, begitu

seterusnya.

C. INSERTION SORT

Mirip dengan cara orang mengurutkan kartu, selembar demi selembar kartu

diambil dan disisipkan (insert) ke tempat yang seharusnya. Pengurutan dimulai

dari data ke-2 sampai dengan data terakhir, jika ditemukan data yang lebih kecil,

maka akan ditempatkan (diinsert) diposisi yang seharusnya. Pada penyisipan

elemen, maka elemen-elemen lain akan bergeser ke belakang

D. SELECTION SORT

Merupakan kombinasi antara sorting dan searchingUntuk setiap proses, akan

dicari elemen-elemen yang belum diurutkan yang memiliki nilai terkecil atau

terbesar akan dipertukarkan ke posisi yang tepat di dalam array.Misalnya untuk

putaran pertama, akan dicari data dengan nilai terkecil dan data ini akan

ditempatkan di indeks terkecil (data[0]), pada putaran kedua akan dicari data

kedua terkecil, dan akan ditempatkan di indeks kedua (data[1]). Selama proses,

pembandingan dan pengubahan hanya dilakukan pada indeks pembanding saja,

pertukaran data secara fisik terjadi pada akhir proses.

Perbandingan

Tabel Perbandingan Kecepatan Metode Pengurutan Data Untuk data sejumlah

10.000 data pada komputer Pentium II 450 MHz

E. MASIH BANYAK LAGI

Merge Sort

Heap Sort

Quick Sort