Tuesday, December 20, 2016

Bab 10. Java Struktur Data dan Pemrograman GUI



Bab.10 List, Tumpukan, Antrian, dan Antrian Prioritas

Tujuan Instruksional
·         Merancang fitur-fitur umum list di dalam suatu antarmuka dan menyediakan implementasi skeleton di dalam suatu kelas abstrak.
·         Merancang dan mengimplementasikan suatu list dinamis menggunakan suatu array.
·         Merancang dan mengimplementasikan suatu list dinamis menggunakan suatu struktur berantai.
·         Mengeksplorasi beberapa variasi list berantai.
·         Mendesain dan merancang suatu antrian menggunakan suatu list berantai.
·         Mendesain dan merancang suatu antrian prioritas menggunakan suatu heap.


10.1 Introduksi
List, tumpukan, antrian, dan antrian prioritas merupakan beberapa struktur data klasik yang sering diajarkan pada matakuliah struktur data. Semua struktur data ini didukung di dalam JAVA API dan kegunaannya telah didiskusikan pada Bab 8. Bab ini akan memeriksa bagaimana struktur-struktur data diimplementasikan dan menyajikan suatu aplikasi menarik untuk mengevaluasi ekspresi menggunakan tumpukan. Perangkat animasi online dapat membantu Anda untuk mempelajari topik bahasan pada bab ini, seperti tertampil pada Gambar 10.1.



Gambar 10.1 Perangkat animasi memampukan Anda untuk melihat bagaimana list array dan list berantai bekerja secara visual


10.2 Fitur-Fitur Umum List
List merupakan suatu struktur data populer untuk menyimpan data dengan urutan sekuensial, sebagai contoh, suatu list siswa, suatu list kamar hotel, dan suatu list buku. Di bawah ini merupakan operasi-operasi yang biasa diterapkan pada list:
·         Menarik suatu elemen dari suatu list.
·         Menyisipkan suatu elemen baru ke suatu list.
·         Menghapus suatu elemen dari suatu list.
·         Mencari berapa banyak elemen di dalam suatu list.
·         Menemukan apakah suatu elemen berada di dalam suatu list atau tidak.
·         Menemukan apakah suatu list kosong atau tidak.



Gambar 10.2 MyList mendefinisikan suatu antarmuka bersama untuk
MyAbstractList, MyArrayList, dan MyLinkedList


Ada dua cara untuk mengimplementasikan suatu list. Satu cara adalah dengan menggunakan suatu array untuk menyimpan elemen. Array diciptakan secara dinamis. Jika kapasitas array melebihi dari yang diperlukan, maka suatu array yang baru diciptakan dan semua elemen disalin dari array lama ke array baru. Pendekatan lain adalah dengan menggunakan suatu struktur berantai. Struktur berantai memiliki simpul-simpul. Setiap simpul secara dinamis diciptakan untuk memuat suatu elemen. Semua simpul dihubungkan atau dibuat berantai untuk membentuk suatu list. Jadi, Anda bisa mendefinisikan dua kelas list. Agar lebih mudah,kedua kelas tersebut dinamai MyArrayList dan MyLinkedList. Kedua kelas tersebut memiliki operasi-operasi bersama tetapi implementasi yang berbeda.   



Gambar 10.3 List mendukung banyak metode untuk memanipulasi suatu list. MyAbstractList menyediakan suatu implementasi parsial atas antarmuka List


Pada kasus ini, diberinama antarmuka MyList dan kelas MyAbstractList. Gambar 10.2 menunjukkan relasi antara MyList, MyAbstractList, MyArrayList, dan MyLinkedList. Metode-metode di dalam MyList dan metode-metode yang diimplementasikan di dalam MyAbstractList ditampilkan pada Gambar 10.3. Kode10.1 menyajikan kode sumber untuk MyList.

Kode10.1 MyList.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
public interface MyList<E> {
  /** Menambah suatu elemen baru di ujung list ini */
  public void add(E e);

  /** Menambah suatu elemen baru pada indeks tertentu di dalam list ini */
  public void add(int index, E e);

  /** Menghapus list */
  public void clear();

  /** Mengembalikan true jika list ini memuat elemen */
  public boolean contains(E e);

  /** Mengembalikan elemen dari list ini pada indeks tertentu */
  public E get(int index);

  /** Mengembalikan indeks dari elemen cocok pertama di dalam list ini.
    * Mengembalikan -1 jika tidak ada yang cocok. */
  public int indexOf(E e);

  /** Mengembalikan true jika list ini tidak memuat satupun elemen */
  public boolean isEmpty();

  /** Mengembalikan indeks dari elemen cocok terakhir di dalam list ini
    * Mengembalikan -1 jika tidak ada yang cocok. */
  public int lastIndexOf(E e);

  /** Menghapus kemunculan pertama dari elemen o pada lisi ini.
    * Menggeser elemen-elemen ke kiri.
    * Mengembalikan true jika elemen dihapus. */
  public boolean remove(E e);

  /** Menghapus elemen pada posisi tertentu di dalam list ini
    * Menggeser elemen-elemen ke kiri.
    * Mengembalikan elemen yang dihapus dari list ini. */
  public E remove(int index);

  /** Mengganti elemen pada posisi tertentu di dalam list ini
    * dengan elemen tertentu dan mengembalikan set yang baru. */
  public Object set(int index, E e);

  /** Mengembalikan jumlah elemen di dalam list ini */
  public int size();
}

MyAbstractList mendeklarasikan variabel size untuk mengindikasikan jumlah elemen di dalam list. Metode isEmpty(), size(), add(E), dan remove(E) dapat diimplementasikan di dalam kelas pada kode10.2.

Kode10.2 MyAbstractList.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
public abstract class MyAbstractList<E> implements MyList<E> {
  protected int ukuran = 0; // Ukuran list

  /** Menciptakan suatu list default */
  protected MyAbstractList() {
  }

  /** Menciptakan suatu list dari suatu array objek */
  protected MyAbstractList(E[] objek) {
    for (int i = 0; i < objek.length; i++)
      add(objek[i]);
  }

  /** Menambah suatu elemen baru di ujung list */
  public void add(E e) {
    add(ukuran, e);
  }

  /** Mengembalikan true jika list ini tidak memuat satupun elemen */
  public boolean isEmpty() {
    return ukuran == 0;
  }

  /** Mengembalikan jumlah elemen di dalam list ini */
  public int ukuran() {
    return ukuran;
  }

  /** Menghapus kemunculan pertama elemen o dari list ini.
    * Menggeser elemen-elemen ke kiri.
    * Mengembalikan true jika elemen dihapus. */
  public boolean remove(E e) {
    if (indexOf(e) >= 0) {
      remove(indexOf(e));
      return true;
    }
    else
      return false;
  }
}



10.3 List Array
Array merupakan suatu struktur data dengan ukuran-tetap. Begitu array diciptakan, ukurannya tidak lagi bisa diubah. Akan tetapi, Anda masih bisa menggunakan array untuk mengimplementasikan struktur data dinamis. Triknya adalah menciptakan suatu array baru yang lebih besar untuk menggantikan array sekarang, jika array sekarang tidak bisa menampung elemen-elemen di dalam list.

Awalnya, suatu array, katakanlah data bertipe E[], diciptakan dengan suatu ukuran default. Ketika menyisipkan suatu elemen baru ke dalam array, pertama-tama perlu dipastikan bahwa terdapat cukup tempat di dalam array. Jika tidak, suatu array baru dengan ukuran dua kali lipat diciptakan untuk menggantikan array sekarang. Elemen-elemen array sekarang disalin ke array baru tersebut. Array baru menjadi array sekarang. Sebelum menyisipkan suatu elemen baru pada indeks tertentu, semua elemen setelah indeks digeser ke kanan dan ukuran list ditambah 1, seperti tertampil pada Gambar 10.4.



Gambar 10.4 Menyisipkan suatu elemen baru ke dalam array mensyaratkan bahwa semua elemen setelah titik penyisipan digeser satu posisi ke kanan, sehingga elemen baru tersebut dapat disisipkan ke titik penyisipan 


Untuk menghapus suatu elemen pada indeks tertentu, semua elemen setelah indeks tersebut digeser ke kiri sejauh satu posisi dan ukuran list dikurangi 1, seperti tertampil pada Gambar 10.5.

MyArrayList menggunakan suatu array untuk mengimplementasikan MyAbstractList, seperti tertampil pada Gambar 10.6. Implementasinya diberikan pada kode10.3.



Gambar 10.5 Menghapus suatu elemen dari array mensyaratkan bahwa semua elemen setelah titik penghapusan digeser satu posisi ke kiri



Gambar 10.6 MyArrayList mengimplementasikan list menggunakan array


Kode10.3 MyArrayList.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
public class MyArrayList<E> extends MyAbstractList<E> {
  public static final int KAPASITAS_AWAL = 16;
  private E[] data = (E[]) new Object[KAPASITAS_AWAL];

  /** Menciptakan suatu list default */
  public MyArrayList() {
  }

  /** Menciptakan suatu list dari array objek */
  public MyArrayList(E[] objek) {
    for (int i = 0; i < objek.length; i++)
      add(objek[i]); // Peringatan: jangan gunakan super(objek)!
  }

  /** Menambah suatu elemen baru pada indeks tertentu di dalam list */
  public void add(int indeks, E e) {
    ensureCapacity();

    // Memindahkan elemen-elemen ke kanan setelah indeks tertentu
    for (int i = ukuran - 1; i >= indeks; i--)
      data[i + 1] = data[i];

    // Menyisipkan elemen baru ke data[indeks]
    data[indeks] = e;

    // Menambah ukuran sebesar 1
    ukuran++;
  }

  /** Menciptakan array yang lebih besar, menggandakan ukuran sekarang + 1 */
  private void ensureCapacity() {
    if (ukuran >= data.length) {
    E[]dataBaru = (E[])(new Object[ukuran * 2 + 1]);
    System.arraycopy(data, 0, dataBaru, 0, ukuran);
    data = dataBaru;
    }
  }

  /** Membersihkan list */
  public void clear() {
    data = (E[])new Object[KAPASITAS_AWAL];
    ukuran = 0;
  }

  /** Mengembalikan true jika list ini memuat elemen */
  public boolean contains(E e) {
    for (int i = 0; i < ukuran; i++)
      if (e.equals(data[i])) return true;

    return false;
  }

  /** Mengembalikan elemen dari list ini pada indeks tertentu */
  public E get(int indeks) {
    return data[indeks];
  }

  /** Mengembalikan indeks dari elemen cocok pertama di dalam list ini.
    * Mengembalikan -1 jika tidak ada yang cocok. */
  public int indexOf(E e) {
    for (int i = 0; i < ukuran; i++)
      if (e.equals(data[i])) return i;

    return -1;
  }

  /** Mengembalikan indeks dari elemen cocok terakhir di dalam list ini.
    * Mengembalikan -1 jika tidak ada yang cocok. */
  public int lastIndexOf(E e) {
    for (int i = ukuran - 1; i >= 0; i--)
      if (e.equals(data[i])) return i;

    return -1;
  }

  /** Menghapus pada posisi tertentu di dalam list ini
    * Menggeser elemen-elemen ke kiri.
    * Mengembalikan elemen yang dihapus dari list. */
  public E remove(int indeks) {
    E e = data[indeks];

    // Menggeser data ke kiri
    for (int j = indeks; j < ukuran - 1; j++)
      data[j] = data[j + 1];

    data[ukuran - 1] = null; // Elemen ini sekarang null

    // Mendekremen ukuran
    ukuran--;

    return e;
  }

  /** Mengganti elemen pada posisi tertentu di dalam list ini
    * dengan elemen tertentu. */
  public E set(int indeks, E e) {
    E old = data[indeks];
    data[indeks] = e;
    return old;
  }

  /** Mengoverride metode toString(), mengembalikan elemen di dalam list */
  public String toString() {
    StringBuilder hasil = new StringBuilder("[");

    for (int i = 0; i < ukuran; i++) {
      hasil.append(data[i]);
      if (i < ukuran - 1) hasil.append(", ");
    }

    return hasil.toString() + "]";
  }

  /** Memotong kapasitas menjadi ukuran sekarang */
  public void trimToSize() {
    if (ukuran != data.length) {
      // Jika ukuran == kapasitas, tidak diperlukan pemotongan
      E[] dataBaru = (E[])(new Object[ukuran]);
      System.arraycopy(data, 0, dataBaru, 0, ukuran);
      data = dataBaru;
    }
  }
}

Konstanta KAPASITAS_AWAL (baris 2) digunakan untuk menciptakan suatu array awal data (baris 3). Karena tipe erasure atau penghapusan generik, Anda tidak bisa menciptakan suatu array generik menggunakan new e[KAPASITAS_AWAL]. Untuk mengatasi keterbatasan ini, suatu array bertipe Object diciptakan pada baris 3 dan melakukan cast menjadi E[].

Perhatikan bahwa implementasi konstruktor kedua di dalam MyArrayList sama dengan konstruktor untuk MyAbstractList. Dapatkah Anda mengganti baris 11-12 dengan super(objek)?  Jawabannya tentu tidak.

Metode add(int indeks, E e) (baris 16-28) menambah elemen e pada indeks tertentu indeks di dalam array. Metode ini pertama-tama memanggil ensureCapacity (baris 17), yang memastikan bahwa masih terdapat ruang di dalam array untuk elemen baru. Kemudian metode menggeser semua elemen setelah indeks satu posisi ke kanan sebelum menyisipkan elemen baru (baris 20-21). Setelah elemen ditambah, ukuran diinkremen sebesar 1 (baris 27). Perhatikan bahwa variabel ukuran didefinisikan sebagai protected di dalam MyAbstractList, sehingga bisa diakses dari MyArrayList.

Metode ensureCapacity() (baris 31-37) memeriksa apakah array sudah penuh atau tidak. Jika penuh, metode ini menciptakan suatu array baru dengan ukuran array dua kali lipat dari array sekarang ditambah 1. Kemudian metode menyalin semua elemen di dalam array sekarang ke array baru menggunakan metode System.arraycopy dan menetapkan array baru sebagai array sekarang.

Metode clear() (baris 40-43) menciptakan suatu array baru sebagai array sekarang.

Metode contains(E e) (baris 46-51) memeriksa apakah elemen e dimuat di dalam array atau tidak dengan membandingkan setiap elemen di dalam array menggunakan metode equals.

Metode get(int indeks) (baris 54-56) berfungsi hanya mengembalikan data[indeks]. Implementasi metode ini cukup sederhana dan efisien.

Metode indexOf(E e) (baris 60-65) membandingkan elemen e dengan elemen-elemen di dalam array, dimulai dari elemen pertama. Jika kecocokan ditemukan, indeks elemen dikembalikan (dijadikan nilai balik), sebaliknya -1 dijadikan nilai balik.

Metode remove(int indeks) (baris 79-92) menggeser semua elemen sebelum indeks sejauh satu posisi ke kiri dan mendekremen ukuran sebesar 1.
Metode set(int indeks, E e) (baris 96-100) hanya menugaskan e kepada data[indeks] untuk menggantikan elemen pada indeks tertentu dengan e.

Metode toString() (baris 103-112) mengoverride metode toString() yang didefinisikan di dalam kelas Object untuk mengembalikan suatu string yang merepresentasikan semua elemen di dalam list.

Metode trimToSize() menciptakan suatu array baru yang memiliki ukuran yang cocok ukuran list array sekarang (baris 117), menyalin array sekarang ke array baru menggunakan metode System.arraycopy (baris 118), dan menetapkan array yang baru tersebut sebagai array sekarang (baris 119). Perhatikan bahwa jika ukuran == kapasitas, maka tidak perlu ada pemotongan ukuran.

Kode10.4 menyajikan suatu contoh yang menciptakan suatu list menggunakan MyArrayList. Program kemudian menggunakan metode add untuk menambah beberapa string ke dalam list dan metode remove untuk menghapus string.

Kode10.4 TestList.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public class TestList {
  public static void main(String[] args) {
    // Menciptakan suatu list
    MyList<String> list = new MyArrayList<String>();

    // Menambah elemen-elemen ke list
    list.add("Siantar"); // Menambahnya ke list
    System.out.println("(1) " + list);

    list.add(0, "Klaten"); // Menambahnya pada awal list
    System.out.println("(2) " + list);

    list.add("Balige"); // Menambahnya pada ujung list
    System.out.println("(3) " + list);

    list.add("Jogja"); // Menambahnya pada ujung list
    System.out.println("(4) " + list);

    list.add(2, "Batam"); // Menambahnya ke list pada indeks 2
    System.out.println("(5) " + list);

    list.add(5, "Mataram"); // Menambahnya ke list pada indeks 5
    System.out.println("(6) " + list);

    // Menghapus elemen-elemen dari list
    list.remove("Klaten"); // Sama dengan list.remove(0)
    System.out.println("(7) " + list);

    list.remove(2); // Menghapus elemen pada indeks 2
    System.out.println("(8) " + list);

    list.remove(list.size() - 1); // Menghapus elemen terakhir
    System.out.println("(9) " + list);
  }
}

Keluaran

(1) [Siantar]
(2) [Klaten, Siantar]
(3) [Klaten, Siantar, Balige]
(4) [Klaten, Siantar, Balige, Jogja]
(5) [Klaten, Siantar, Batam, Balige, Jogja]
(6) [Klaten, Siantar, Batam, Balige, Jogja, Mataram]
(7) [Siantar, Batam, Balige, Jogja, Mataram]
(8) [Siantar, Batam, Jogja, Mataram]
(9) [Siantar, Batam, Jogja]


10.4 List Berantai
Karena MyArrayList diimplementasikan menggunakan array, metode get(int indeks) dan set(int indeks, Object o) untuk mengakses dan memodifikasi elemen melalui indeks dan metode add(Object o) untuk menambah suatu elemen di ujung list menjadi efisien. Tetapi, metode add(int indeks, Object o) dan remove(int indeks) tidak efisien, karena memerlukan operasi penggeseran jumlah elemen yang banyak. Anda bisa menggunakan suatu struktur berantai untuk mengimplementasikan suatu list untuk memperbaiki efisiensi dalam menambah dan menghapus elemen di mana saja di dalam list.

10.4.1 Simpul
Di dalam suatu list berantai, setiap elemen dimuat di dalam suatu struktur, yang disebut dengan simpul atau node. Ketika suatu elemen baru ditambahkan ke list, suatu simpul diciptakan untuk menampungnya. Setiap simpul dihubungkan ke simpul tetangganya, seperti tertampil pada Gambar 10.7.



Gambar 10.7 Suatu list berantai memuat sejumlah simpul yang dirantai atau dihubungkan satu sama lain


Suatu simpul didefinisikan sebagai kelas, sebagai berikut:

class Node<E> {
  E elemen;
  Node<E> next;

  public Node(E e) {
    elemen = e;
  }
}

Variabel kepala merujuk ke simpul pertama di dalam list, dan variabel ekor merujuk ke simpul terakhir. Jika list kosong, maka kepala dan ekor keduanya bernilai null. Berikut adalah suatu contoh yang menciptakan suatu list berantai untuk memuat tiga simpul. Setiap simpul menyimpan suatu elemen string.

Langkah 1: Mendeklarasikan kepala dan ekor:

Node<E> kepala = null;
Node<E> ekor = null;

kepala dan ekor keduanya bernilai null. List kosong.

Langkah 2: Menciptakan simpul pertama dan menyambungkannya ke dalam list.
Setelah simpul pertama disisipkan di dalam list, kepala dan ekor menunjuk ke simpul tersebut, seperti tertampil pada Gambar 10.8.

kepala = new Node<E>("Balige");
ekor = kepala;


Gambar 10.8 Menyambung simpul pertama ke list

Langkah 3: Menciptakan simpul kedua dan menyambungkannya ke list.
Untuk menyambung simpul kedua ke dalam list, hubungkan simpul pertama dengan simpul baru tersebut, seperti ditunjukkan pada Gambar 10.9a. Simpul baru sekarang menjadi simpul ekor. Jadi, Anda harus memindahkan ekor untuk menunjuk simpul baru ini, seperti tertampil pada Gambar 10.9b.



Gambar 10.9 Menyambung simpul kedua ke list


Langkah 4: Menciptakan simpul ketiga dan menyambungkannya ke list.
Untuk menyambung simpul baru ke list,  simpul terakhir tersebut di dalam list dihubungkan ke simpul baru, seperti tertampil pada Gambar 10.10a. Simpul baru sekarang menjadi simpul ekor. Jadi, Anda harus memindahkan ekor agar menunjuk ke simpul baru ini, seperti ditunjukkan pada Gambar 10.10b.


Gambar 10.10 Menyambung simpul ketiga ke list


Setiap simpul memuat elemen dan bidang data yang dinamai next yang menunjuk ke elemen berikutnya. Jika simpul adalah yang terakhir di dalam list, maka next memuat nilai null. Anda bisa menggunakan sifat ini untuk mendeteksi simpul terakhir. Sebagai contoh, Anda bisa menulis loop berikut untuk menjelajah semua simpul di dalam list:

1 Node sekarang = kepala;
2 while (sekarang!= null) {
3   System.out.println(sekarang.elemen);
4   sekarang = sekarang.next;
5 }

Variabel sekarang awalnya menunjuk simpul pertama di dalam list (baris 1). Di dalam loop, elemen dari simpul sekarang diambil (baris 3), dan kemudian sekarang menunjuk ke simpul berikutnya (baris 4). Loop berlanjut sampai simpul sekarang menjadi null.



10.4.2 Kelas LinkedList
MyLinkedList menggunakan suatu struktur berantai untuk mengimplementasikan list dinamis, yang mewarisi MyAbstractList. Kelas ini menyediakan beberapa metode seperti addFirst, addLast, removeFirst, removeLast, getFirst, dan getLast, seperti tertampil pada Gambar 10.11.

Diasumsikan bahwa kelas telah diimplementasikan, kode10.5 memberikan suatu program uji yang menggunakan kelas MyLinkedList.

Kode10.5 TestLinkedList.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public class TestLinkedList {
  /** Metode uji */
  public static void main(String[] args) {
    // Menciptakan suatu list
    MyLinkedList<String> list = new MyLinkedList<String>();

    // Menambah elemen-elemen ke list
    list.add("Siantar"); // Menambahnya ke list
    System.out.println("(1) " + list);

    list.add(0, "Klaten"); // Menambahnya pada awal list
    System.out.println("(2) " + list);

    list.add("Balige"); // Menambahnya pada ujung list
    System.out.println("(3) " + list);

    list.addLast("Jogja"); // Menambahnya pada ujung list
    System.out.println("(4) " + list);

    list.add(2, "Batam"); // Menambahnya ke list pada indeks 2
    System.out.println("(5) " + list);

    list.add(5, "Mataram"); // Menambahnya ke list pada indeks 5
    System.out.println("(6) " + list);

    // Menghapus elemen-elemen dari list
    list.remove("Klaten"); // Sama dengan list.remove(0)
    System.out.println("(7) " + list);

    list.remove(2); // Menghapus elemen pada indeks 2
    System.out.println("(8) " + list);

    list.remove(list.size() - 1); // Menghapus elemen terakhir
    System.out.println("(9) " + list);
  }
}

Keluaran

(1) [Siantar]
(2) [Klaten, Siantar]
(3) [Klaten, Siantar, Balige]
(4) [Klaten, Siantar, Balige, Jogja]
(5) [Klaten, Siantar, Batam, Balige, Jogja]
(6) [Klaten, Siantar, Batam, Balige, Jogja, Mataram]
(7) [Siantar, Batam, Balige, Jogja, Mataram]
(8) [Siantar, Batam, Jogja, Mataram]
(9) [Siantar, Batam, Jogja]



Gambar 10.11 MyLinkedList mengimplementasikan list menggunakan list simpul berantai


10.4.3 Implementasi MyLinkedList
Sekarang saatnya untuk mengimplementasikan kelas MyLinkedList. Selanjutnya akan didiskusikan tentang bagaimana mengimplementasikan beberapa metode seperti addFirst, addLast, add(index e), removeFirst, removeLast, dan remove(index) dan meninggalkan implementasi metode-metode lainnya sebagai latihan bagi pembaca.


10.4.3.1 Implementasi addFirst(e)
Metode addFirst(e) menciptakan suatu simpul baru untuk memuat elemen e. Simpul baru itu menjadi simpul pertama di dalam list. Metode ini dapat diimplementasikan sebagai berikut:

1 public void addFirst(E e) {
2   Node<E> simpulBaru = new Node<E>(e); // Menciptakan suatu simpul baru
3   simpulBaru.next = kepala; // Menghubungkan simpul baru dengan kepala
4   kepala = simpulBaru; // kepala menunjuk ke simpul baru
5   ukuran++; // Menginkremen ukuran list
6
7   if(ekor == null) // simpul baru satu-satunya simpul di dalam list
8     ekor = kepala;
9 }

Metode addFirst(e) menciptakan suatu simpul baru untuk menampung elemen (baris 2) dan menyisipkan simpul ke awal list (baris 3), seperti tertampil pada Gambar 10.12a. Setelah penyisipan, kepala harus menunjuk ke simpul baru ini (baris 4), seperti tertampil pada Gambar 10.12b.

Jika list kosong (baris 7), kedua kepala dan ekor akan menunjuk ke simpul baru ini (baris 8). Setelah simpul diciptakan, ukuran harus diinkremen sebesar 1 (bars 5).

Gambar 10.12 Suatu elemen baru ditambahkan di awal list


10.4.3.2 Implementasi addLast(e)
Metode addLast(e) menciptakan suatu simpul baru untuk memuat elemen e. Simpul baru itu menjadi simpul terakhir di dalam list. Metode ini dapat diimplementasikan sebagai berikut:

1  public void addLast(E e) {
2    Node<E> simpulBaru = new Node<E>(e); // Menciptakan suatu simpul baru untuk e
3
4    if(ekor == null) { // simpul baru satu-satunya simpul di dalam list
5      ekor = kepala = simpulBaru; // simpul baru satu-satunya simpul di dalam list
6    }
7    else {
8      ekor.next = simpulBaru; // Menghubungkan simpul baru ke simpul akhir
9      ekor = ekor.next; // ekor sekarang menunjuk ke simpul akhir
10   }
11
12   ukuran++; // Menginkremen ukuran
13 }

Metode addLast(e) menciptakan suatu simpul baru untuk menampung elemen (baris 2) dan menyambungkannya ke akhir list (baris 8). Perhatikan dua kasus berikut:
1.  Jika list kosong, kedua ekor dan kepala akan menunjuk ke simpul baru (baris 5).
2.  Sebaliknya, simpul baru dihubungkan ke simpul akhir di dalam list (baris 8). ekor sekarang menunjuk ke simpul baru ini (baris 9), seperti ditunjukkan pada Gambar 10.13b.

Gambar 10.13 Suatu elemen baru ditambahkan ke ujung list


10.4.3.3 Implementasi add(index,e)
Metode add(index, e) menyisipkan suatu elemen ke list pada indeks tertentu. Metode ini dapat diimplementasikan sebagai berikut:

1 public void add(int index, E e) {
2    if (index == 0) addFirst(e); // Menyisipkan ke awal list
3    else if (index >= size) addLast(e); // Menyisipkan ke akhir list
4    else { // menyisipkan di tengah list
5      Node<E> sekarang = kepala;
6      for (int i = 1; i < index; i++)
7        sekarang = sekarang.next;
8      Node<E> temp = sekarang.next;
9      sekarang.next = new Node<E>(e);
10    (sekarang.next).next = temp;
11     ukuran++;
12   }
13 }

Ada tiga kasus ketika menyisipkan suatu elemen ke dalam list:
1.  Jika index bernilai 0, maka dipanggil metode addFirst(e) (baris 2) untuk menyisipkan elemen di awal list.
2.  Jika index lebih besar dari ukuran, maka metode addLast(e) (baris 3) dipanggil untuk menyisipkan elemen di akhir list.
3.  Sebaliknya, suatu simpul baru diciptakan untuk menyimpan elemen baru dan lokasi untuk menempatkannya ditentukan. Seperti tertampil pada Gambar 10.14b, simpul baru disisipkan antara simpul sekarang dan temp. Metode kemudian menugaskan simpul baru kepada sekarang.next dan menugaskan temp kepada next dari simpul baru, seperti tertampil pada Gambar 10.14b. Variabel ukuran kemudian diinkremen sebesar 1 (baris 11).


Gambar 10.14 Suatu simpul baru disisipkan di tengah list


10.4.3.4 Implementasi removeFirst()
Metode removeFirst() digunakan untuk menghapus elemen pertama di dalam list. Metode ini dapat diimplementasikan dengan:

1  public E removeFirst() {
2    if (size == 0) return null; // Tidak ada yang dihapus
3  else {
4    Node<E> temp = kepala; // Simpan sementara simpul pertama
5    kepala = kepala.next; // Memindahkan kepala untuk menunjuk simpul berikutnya
6    ukuran--; // Mengurangi ukuran sebesar 1
7    if (kepala == null) tail = null; // List menjadi kosong
8      return temp.elemen; // Menjadikan elemen terhapus sebagai nilai balik
9    }
10 }

Ada dua kasus yang perlu dipertimbangkan di sini:
1.  Jika list kosong, maka tidak ada yang dihapus, sehingga metode mengembalikan null (baris 2).
2.  Sebaliknya, simpul pertama dihapus dari list dengan menunjuk kepala pada simpul kedua, seperti tertampil pada Gambar 10.15. Variabel ukuran direduksi 1 setelah penghapusan (baris 6). Jika hanya ada satu elemen, setelah menghapus elemen, maka ekor harus ditetapkan sebagai null (baris 7).




Gambar 10.15 Simpul pertama dihapus dari list


10.4.3.5 Implementasi removeLast()
Metode removeFirst() digunakan untuk menghapus elemen terakhir di dalam list. Metode ini dapat diimplementasikan dengan:

1  public E removeLast() {
2    if (ukuran == 0) return null; // Tidak ada yang dihapus
3    else if (ukuran == 1) // Hanya satu elemen di dalam list
4    {
5      Node<E> temp = kepala;
6      kepala = ekor = null; // list menjadi kosong
7      ukuran = 0;
8      return temp.elemen;
9    }
10   else
11   {
12     Node<E> sekarang = kepala;
13
14     for (int i = 0; i < size - 2; i++)
15     sekarang = sekarang.next;
16
17     Node<E> temp = ekor;
18     ekor = sekarang;
19     ekor.next = null;
20     ukuran--;
21     return temp.element;
22   }
23 }

Terdapat tiga kasus yang perlu dipertimbangkan:
1.  Jika list kosong, maka null akan dikembalikan metode (baris 2).
2.  Jika list hanya memuat satu elemen, maka simpul tersebut dihapus; kepala dan ekor sekarang bernilai null (baris 6).
3.  Sebaliknya, simpul terakhir dihapus (baris 18) dan ekor diposisikan-ulang agar menunjuk elemen kedua terakhir, seperti tertampil pada Gambar 10.16a. Untuk dua kasus terakhir, ukuran direduksi sebesar 1 setelah penghapusan (baris 7, 20) dan nilai elemen dari simpul terhapus dijadikan nilai balik.

Gambar 10.16 Simpul terakhir dihapus dari list


10.4.3.6 Implementasi remove(index)
Metode remove(index) menemukan simpul pada indeks tertentu dan kemudian menghapusnya. Metode ini dapat diimplementasikan sebagai berikut:

1  public E remove(int index) {
2    if (index < 0 || index >= size) return null; // Di luar rentang yang ada
3    else if (index == 0) return removeFirst(); // Menghapus simpul pertama
4    else if (index == ukuran - 1) return removeLast(); // Menghapus simpul terakhir
5    else {
6      Node<E> sebelumnya = kepala;
7
8      for (int i = 1; i < index; i++) {
9        sebelumnya = sebelumnya.next;
10     }
11
12     Node<E> sekarang = sebelumnya.next;
13     sebelumnya.next = sekarang.next;
14     ukuran --;
15     return sekarang.elemen;
16   }
17 }

Perhatikan empat kasus berikut:
1.  Jika index di luar rentang list (yaitu, index<0 || index> ukuran), maka null yang akan dikembalikan metode (baris 2).
2.  Jika index bernilai 0, maka removeFirst() dipanggil untuk menghapus simpul pertama (baris 3).
3.  Jika index bernilai ukuran – 1, maka removeLast() dipanggil untuk menghapus simpul terakhir (baris 4).
4.  Sebaliknya, simpul pada index tertentu akan dicari. Dimisalkan sekarang menandai simpul ini dan sebelumnya menandai simpul sebelum simpul ini, seperti tertampil pada Gambar 10.17a. Kemudian menugaskan sekarang.next kepada sebelumnya.next untuk menghapus simpul sekarang, seperti tertampil pada Gambar 10.17b.

Kode10.6 memberikan implementasi MyLinkedList. Implementasi dari get(index), indexOf(e), lastIndexOf(e), contains(e), dan set(index,e) diabaikan sebagai latihan bagi pembaca.



Gambar 10.17 Suatu simpul dihapus dari list


Kode10.6 MyLinkedList.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
17
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
public class MyLinkedList<E> extends MyAbstractList<E> {
  private Node<E> kepala, ekor;

  /** Menciptakan suatu list default */
  public MyLinkedList() {
  }

  /** Menciptakan suatu list dari array objek */
  public MyLinkedList(E[] objek) {
    super(objek);
  }

  /** Mengembalikan elemen kepala di dalam list */
  public E getFirst() {
    if (ukuran == 0) {
    return null;
    }
    else {
      return kepala.elemen;
    }
  }

  /** Mengembalikan elemen terakhir di dalam list */
  public E getLast() {
    if (ukuran == 0) {
      return null;
    }
    else {
      return ekor.elemen;
    }
  }

  /** Menambah suatu elemen di awal list */
  public void addFirst(E e) {
    Node<E> simpulBaru = new Node<E>(e); // Menciptakan suatu simpul baru
    simpulBaru.next = kepala;// Menghubungkan simpul baru dengan kepala
    kepala = simpulBaru;// kepala menunjuk ke simpul baru
    ukuran++;// Menginkremen ukuran list

    if(ekor == null) // simpul baru satu-satunya simpul di dalam list
      ekor = kepala;
  }

  /** Menambah suatu elemen ke akhir list */
  public void addLast(E e) {
    Node<E> simpulBaru = new Node<E>(e); // Menciptakan simpul baru untuk e

    if (ekor == null) {
      kepala = ekor = simpulBaru; // Satu-satunya simpul di dalam list
    }
    else {
      ekor.next = simpulBaru;// Menghubungkan simpul baru dengan simpul terakhir
      ekor = ekor.next; // ekor sekarang menunjuk ke simpul terakhir
    }

    ukuran++; // Menginkremen ukuran
  }

  /** Menambah suatu elemen baru pada indeks tertentu di dalam list
    * Indeks elemen kepala adalah 0 */
  public void add(int index, E e) {
    if (index == 0) addFirst(e);// Menyisikan ke simpul pertama
    else if (index >= ukuran) addLast(e); // Menyisikan ke simpul terakhir
    else { // Menyisikan ke simpul tengah
      Node<E> sekarang = kepala;
      for (int i = 1; i < index; i++)
        sekarang = sekarang.next;
      Node<E> temp = sekarang.next;
      sekarang.next = new Node<E>(e);
      (sekarang.next).next = temp;
      ukuran++;
    }
  }

  /** Menghapus simpul kepala dan
    * mengembalikan objek yang dimuat di dalam simpul terhapus. */
  public E removeFirst() {
    if (ukuran == 0) return null;// Tidak ada yang dihapus
    else {
      Node<E> temp = kepala; // Menyimpan sementara simpul pertama
      kepala = kepala.next; // Memindahkan kepala agar menunjuk ke simpul berikutnya
      ukuran--; // Mendekremen ukuran sebesar 1
      if (kepala == null) ekor = null; // List menjadi kosong
        return temp.elemen; // Menjadikan elemen terhapus sebagai nilai balik
    }
  }

  /** Menghapus simpul terakhir dan
    * mengembalikan objek yang dimuat di dalam simpul terhapus. */
  public E removeLast() {
    if (ukuran == 0) return null;// Tidak ada yang dihapus
    else if (ukuran == 1) { // Satu-satunya elemen di dalam list
      Node<E> temp = kepala;
      kepala = ekor = null; // list menjadi kosong
      ukuran = 0;
      return temp.elemen;
    }
    else {
      Node<E> sekarang = kepala;

      for (int i = 0; i < ukuran - 2; i++)
        sekarang = sekarang.next;

      Node<E> temp = ekor;
      ekor = sekarang;
      ekor.next = null;
      ukuran--;
      return temp.elemen;
    }
  }

  /** Menghapus elemen pada posisi tertentu di dalam list.
    * Mengembalikan elemen yang dihapus dari list. */
  public E remove( int index) {
    if (index < 0 || index >= ukuran) return null;// Di luar rentang
    else if (index == 0) return removeFirst(); // Menghapus simpul pertama
    else if (index == ukuran - 1) return removeLast(); // Menghapus simpul terakhir
    else {
      Node<E> sebelumnya = kepala;

      for (int i = 1; i < index; i++) {
        sebelumnya = sebelumnya.next;
      }

    Node<E> sekarang = sebelumnya.next;
    sebelumnya.next = sekarang.next;
    ukuran--;
    return sekarang.elemen;
    }
  }

  /** Mengoverride metode toString() untuk mengembalikan elemen di dalam list */
  public String toString() {
    StringBuilder result = new StringBuilder("[");

    Node<E> sekarang = kepala;
    for (int i = 0; i < ukuran; i++) {
      result.append(sekarang.elemen);
      sekarang = sekarang.next;
      if (sekarang != null) {
        result.append(", "); // Memisahkan dua elemen dengan koma
      }
      else {
        result.append("]"); // Menyisipkan ] di dalam string
      }
    }

    return result.toString();
  }

  /** Membersihkan list */
  public void clear() {
    kepala = ekor = null;
  }

  /** Mengembalikan true jika list ini memuat elemen o */
  public boolean contains(E e) {
    System.out.println("Implementasi dijadikan latihan");
    return true;
  }

  /** Mengembalikan elemen dari list ini pada indeks tertentu */
  public E get(int index) {
    System.out.println("Implementasi dijadikan latihan");
    return null;
  }

  /** Mengembalikan indeks dari kepala elemen cocok di dalam list ini.
    * Mengembalikan -1 jika tidak ada yang cocok. */
  public int indexOf(E e) {
    System.out.println("Implementasi dijadikan latihan");
    return 0;
  }

  /** Mengembalikan indeks dari elemen cocok terakhir di dalam list ini
    * Mengembalikan -1 jika tidak ada yang cocok. */
  public int lastIndexOf(E e) {
    System.out.println("Implementasi dijadikan latihan");
    return 0;
  }

  /** Mengganti elemen pada posisi tertentu di dalam list ini
    * dengan elemen tertentu. */
  public E set(int index, E e) {
    System.out.println("Implementasi dijadikan latihan");
    return null;
  }

  private static class Node<E> {
    E elemen;
    Node<E> next;

    public Node(E elemen) {
      this.elemen = elemen;
    }
  }
}


10.5 Tumpukan dan Antrian
Tumpukan dapat dipandang sebagai kasus spesial dari list yang memiliki elemen-elemen yang dapat diakses, disisipkan, dan dihapus hanya dari akhir (atas), seperti terlihat pada Gambar  10.19a. Antrian merepresentasikan suatu waiting list, yang dapat dipandang sebagai kasus spesial dari list, dimana elemen-elemennya disisipkan ke ekor antrian, dan diakses dan dihapus dari kepala antrian, seperti tertampil pada Gambar 10.19b.



Gambar 10.19 (a) simulai tumpukan, (b) simulasi antrian


Karena operasi-operasi penyisipan dan penghapusan pada suatu tumpukan dilakukan pada akhir tumpukan, maka akan lebih efisien untuk mengimplementasikannya menggunakan list array daripada menggunakan list berantai. Karena operasi penghapusan dilakukan pada awal list, maka akan lebih efisien untuk mengimplementasikan suatu antrian menggunakan list berantai daripada menggunakan list array. Bagian ini akan mengimplementasikan suatu kelas tumpukan menggunakan list array dan suatu kelas antrian menggunakan list berantai.



Gambar 10.20 (a) GenericStack dan GenericQueue diimplementasikan menggunakan pewarisan atau menggunakan komposisi


Ada dua cara mendesain kelas tumpukan dan kelas antrian:
·         Menggunakan pewarisan: Anda dapat mendefinisikan suatu kelas tumpukan dengan mewarisi ArrayList, dan suatu kelas antrian dengan warisi LinkedList, seperti tertampil pada Gambar 10.20a.
·         Menggunakan komposisi: Anda bisa mendefinisikan suatu list array sebagai bidang data di dalam kelas tumpukan, dan suatu list berantai sebagai bidang data di dalam kelas antrian, seperti tertampil pada Gambar 10.20b.
Secara perancangan, keduanya baik, tetapi menggunakan komposisi lebih baik daripada menggunakan pewarisan, karena memampukan Anda untuk mendefinisikan kelas tumpukan dan kelas antrian yang baru sama sekali tanpa perlu mewarisi metode-metode yang tidak perlu dari list array dan list berantai. Implementasi kelas tumpukan menggunakan pendekatan komposisi diberikan pada kode7.1, GenericStack.java. Kode10.7 mengimplementasikan kelas antrian menggunakan pendekatan komposisi. Gambar 10.21 menunjukkan diagram UML dari kelas yang dirancang.



Gambar 10.21 GenericQueue menggunakan suatu list berantai yang menyediakan suatu struktur data dengan gaya FIFO (first-in, first-out)



Kode10.7 GenericQueue.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class GenericQueue<E>{
  private java.util.LinkedList<E> list
    = new java.util.LinkedList<E>();

  public void enqueue(E e) {
    list.addLast(e);
  }

  public E dequeue() {
    return list.removeFirst();
  }

  public int getSize() {
    return list.size();
  }

  public String toString() {
    return "Antrian: " + list.toString();
  }
}

Suatu list berantai diciptakan untuk menyimpan elemen-elemen di dalam suatu antrian (baris 2-3). Metode enqueue(e) (baris 5-7) menambah suatu elemen e ke ekor antrian. Metode dequeue (baris 9-11) menghapus suatu elemen dari kepala antrian dan menjadikan elemen terhapus sebagai nilai balik. Metode getSize() (baris 13-15) mengembalikan (menjadikan sebagai nilai balik) jumlah elemen di dalam antrian.

Kode10.8 menyajikan suatu contoh yang menciptakan suatu tumpukan menggunakan GenericStack dan suatu antrian menggunakan GenericQueue. Program menggunakan metode push(enqueue) untuk menambah string ke tumpukan (antrian) dan menggunakan metode pop(dequeue) untuk menghapus string dari tumpukan (antrian).

Kode10.8 UjiTumpukanAntrian.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
public class UjiTumpukanAntrian {
  public static void main(String[] args) {
    // Menciptakan suatu tumpukan
    GenericStack<String> tumpukan =
       new GenericStack<String>();

    // Menambah elemen ke tumpukan
    tumpukan.push("Jodi"); // Mendorongnya ke tumpukan
    System.out.println("(1) " + tumpukan);

    tumpukan.push("Andri"); // Mendorongnya ke tumpukan
    System.out.println("(2) " + tumpukan);

    tumpukan.push("Aurora"); // Mendorongnya ke tumpukan
    tumpukan.push("Adam"); // Mendorongnya ke tumpukan
    System.out.println("(3) " + tumpukan);

    // Menghapus elemen dari tumpukan
    System.out.println("(4) " + tumpukan.pop());
    System.out.println("(5) " + tumpukan.pop());
    System.out.println("(6) " + tumpukan);

    // Menciptakan suatu antrian
    GenericQueue<String> antrian = new GenericQueue<String>();

    // Menambah elemen ke antrian
    antrian.enqueue("Jodi"); // Menambahnya ke antrian
    System.out.println("(7) " + antrian);

    antrian.enqueue("Andri"); // Menambahnya ke antrian
    System.out.println("(8) " + antrian);

    antrian.enqueue("Aurora"); // Menambahnya ke antrian
    antrian.enqueue("Adam"); // Menambahnya ke antrian
    System.out.println("(9) " + antrian);

    // Menghapus elemen dari elemen
    System.out.println("(10) "+ antrian.dequeue());
    System.out.println("(11) " + antrian.dequeue());
    System.out.println("(12) " + antrian);
  }
}

Keluaran

(1) Antrian: [Jodi]
(2) Antrian: [Jodi, Andri]
(3) Antrian: [Jodi, Andri, Aurora, Adam]
(4) Adam
(5) Aurora
(6) Antrian: [Jodi, Andri]
(7) Antrian: [Jodi]
(8) Antrian: [Jodi, Andri]
(9) Antrian: [Jodi, Andri, Aurora, Adam]
(10) Jodi
(11) Andri
(12) Antrian: [Aurora, Adam]

Dalam tumpukan, metode push(e) menambah suatu elemen ke atas tumpukan,dan metode pop() menghapus elemen teratas dari tumpukan dan menjadikannya sebagai nilai balik.

Dalam antrian, metode enqueue(o) menambah suatu elemen ke ekor antrian,dan metode dequeue() menghapus elemen dari kepala antrian.


10.6 Antrian Prioritas
Antrian biasa merupakan suatu struktur data dengan gaya FIFO (first-in, first-out). Elemen-elemen ditambahkan ke ujung antrian dan dihapus dari awal antrian. Di dalam antrian prioritas, setiap elemen ditugasi suatu prioritas. Ketika mengakses elemen, elemen dengan prioritas tertinggi dihapus pertama kali. Antrian prioritas merupakan suatu struktur data dengan gaya largest-in, first-out. Sebagai contoh, di ruang gawat darurat diterapkan tingkatan prioritas terhadap pasien; pasien dengan prioritas tertinggi akan dirawat lebih dahulu.



Gambar 10.22 Kelas MyPriorityQueue menggunakan heap untuk menyediakan suatu struktur data dengan gaya largest-in, first-out


Antrian prioritas dapat diimplementasikan menggunakan heap, dimana akar merupakan objek dengan prioritas tertinggi di dalam antrian. Heap telah dikenalkan pada Bab 9.5. Diagram kelas untuk antrian prioritas ditunjukkan pada Gambar 10.22. Implementasinya diberikan pada kode10.9.

Kode10.9 MyPriorityQueue.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class MyPriorityQueue<E extends Comparable> {
  private Heap<E> heap = new Heap<E>();

  public void enqueue(E objekBaru) {
    heap.add(objekBaru);
  }

  public E dequeue() {
    return heap.remove();
  }

  public int getSize() {
    return heap.getSize();
  }
}

Kode10.10 menyajikan suatu contoh penggunaan antrian prioritas untuk pasien. Kelas Pasien didefinisikan pada baris 18-34. Empat pasien diciptakan dengan nilai-nilai prioritas pada baris 3-6. Baris 8 menciptakan suatu antrian prioritas. Pasien dijadikan antrian pada baris 9-12. Baris 15 menghapus seorang pasien dari antrian.

Kode10.9 UjiAntrianPrioritas.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public class UjiAntrianPrioritas {
  public static void main(String[] args) {
    Pasien pasien1 = new Pasien("Aurora", 2);
    Pasien pasien2 = new Pasien("Adam", 1);
    Pasien pasien3 = new Pasien("Andri", 5);
    Pasien pasien4 = new Pasien("Jody", 7);

    MyPriorityQueue antrianPrioritas = new MyPriorityQueue();
    antrianPrioritas.enqueue(pasien1);
    antrianPrioritas.enqueue(pasien2);
    antrianPrioritas.enqueue(pasien3);
    antrianPrioritas.enqueue(pasien4);

    while(antrianPrioritas.getSize() > 0)
      System.out.print(antrianPrioritas.dequeue() + " ");
  }

  static class Pasien implements Comparable {
    private String nama;
    private int prioritas;

    public Pasien(String nama, int prioritas) {
      this.nama = nama;
      this.prioritas = prioritas;
    }

    public String toString() {
      return nama + "(prioritas:" + prioritas + ")";
    }

    public int compareTo(Object o) {
      return this.prioritas - ((Pasien)o).prioritas;
    }
  }
}

Keluaran
Jody(prioritas:7) Andri(prioritas:5) Aurora(prioritas:2) Adam(prioritas:1)








Posted by at

3 comments:

Subscribe to: Post Comments (Atom)