Mendefinisikan Char Stack di Java

1. Ikhtisar

Dalam tutorial ini, kita akan membahas cara membuat tumpukan karakter di Java. Pertama-tama kita akan melihat bagaimana kita dapat melakukan ini dengan menggunakan Java API, dan kemudian kita akan melihat beberapa implementasi kustom.

Stack adalah struktur data yang mengikuti prinsip LIFO (Last In First Out). Beberapa metode umumnya adalah:

  • push (E item) - mendorong item ke atas tumpukan
  • pop () - menghapus dan mengembalikan objek di bagian atas tumpukan
  • peek () - mengembalikan objek di bagian atas tumpukan tanpa menghapusnya

2. Char Stack Menggunakan Java API

Java memiliki API bawaan bernama java.util.Stack . Karena char adalah tipe data primitif , yang tidak dapat digunakan dalam generik, kita harus menggunakan kelas pembungkus java.lang.Character untuk membuat Stack :

Stack charStack = new Stack();

Sekarang, kita dapat menggunakan metode push , pop , dan peek dengan Stack .

Di sisi lain, kita mungkin diminta untuk membuat implementasi tumpukan kustom. Oleh karena itu, kita akan melihat beberapa pendekatan berbeda.

3. Penerapan Kustom Menggunakan LinkedList

Mari terapkan tumpukan karakter menggunakan LinkedList sebagai struktur data back-end kita:

public class CharStack { private LinkedList items; public CharStack() { this.items = new LinkedList(); } }

Kami membuat variabel item yang diinisialisasi di konstruktor.

Sekarang, kita harus menyediakan implementasi metode push , peek , dan pop :

public void push(Character item) { items.push(item); } public Character peek() { return items.getFirst(); } public Character pop() { Iterator iter = items.iterator(); Character item = iter.next(); if (item != null) { iter.remove(); return item; } return null; }

Metode push and peek menggunakan metode built-in dari LinkedList . Untuk pop , pertama-tama kami menggunakan Iterator untuk memeriksa apakah ada item di atas atau tidak. Jika ada, kami menghapus item dari daftar dengan memanggil metode hapus .

4. Implementasi Kustom Menggunakan Array

Kami juga dapat menggunakan array untuk struktur data kami:

public class CharStackWithArray { private char[] elements; private int size; public CharStackWithArray() { size = 0; elements = new char[4]; } }

Di atas, kami membuat array karakter , yang kami inisialisasi di konstruktor dengan kapasitas awal 4. Selain itu, kami memiliki variabel ukuran untuk melacak berapa banyak catatan yang ada di tumpukan kami.

Sekarang, mari kita terapkan metode push :

public void push(char item) { ensureCapacity(size + 1); elements[size] = item; size++; } private void ensureCapacity(int newSize) { char newBiggerArray[]; if (elements.length < newSize) { newBiggerArray = new char[elements.length * 2]; System.arraycopy(elements, 0, newBiggerArray, 0, size); elements = newBiggerArray; } }

Saat mendorong item ke tumpukan, pertama-tama kita perlu memeriksa apakah array kita memiliki kapasitas untuk menyimpannya. Jika tidak, kami membuat array baru dan menggandakan ukurannya. Kami kemudian menyalin elemen lama ke array yang baru dibuat dan menetapkannya ke variabel elemen kami .

Catatan: untuk penjelasan mengapa kami ingin menggandakan ukuran array, daripada hanya menambah ukuran satu per satu, silakan lihat posting StackOverflow ini.

Terakhir, mari terapkan metode mengintip dan pop :

public char peek() { if (size == 0) { throw new EmptyStackException(); } return elements[size - 1]; } public char pop() { if (size == 0) { throw new EmptyStackException(); } return elements[--size]; }

Untuk kedua metode, setelah memvalidasi bahwa tumpukan tidak kosong, kami mengembalikan elemen pada ukuran posisi - 1. Untuk pop , selain mengembalikan elemen, kami mengurangi ukuran sebesar 1.

5. Kesimpulan

Di artikel ini, kita belajar bagaimana membuat tumpukan karakter menggunakan Java API, dan kita melihat beberapa implementasi khusus.

Kode yang disajikan dalam artikel ini tersedia di GitHub.