Panduan Cepat untuk Java Stack

1. Ikhtisar

Dalam artikel singkat ini, kami akan memperkenalkan kelas java.util.Stack dan mulai melihat bagaimana kami dapat memanfaatkannya.

Stack adalah struktur data generik yang merepresentasikan kumpulan objek LIFO (terakhir masuk, keluar pertama) yang memungkinkan elemen mendorong / muncul dalam waktu konstan.

Untuk implementasi baru, kita harus lebih memilih antarmuka Deque dan implementasinya . Deque mendefinisikan rangkaian operasi LIFO yang lebih lengkap dan konsisten. Namun, kita mungkin masih perlu berurusan dengan kelas Stack , terutama di kode lama, apakah penting untuk mengetahuinya lebih baik.

2. Buat Stack

Mari kita mulai dengan membuat instance Stack kosong , dengan menggunakan default, konstruktor tanpa argumen:

@Test public void whenStackIsCreated_thenItHasSizeZero() { Stack intStack = new Stack(); assertEquals(0, intStack.size()); }

Ini akan membuat Stack dengan kapasitas default 10. Jika jumlah elemen yang ditambahkan melebihi ukuran Stack total , itu akan digandakan secara otomatis. Namun, ukurannya tidak akan pernah menyusut setelah elemen dihapus.

3. Sinkronisasi untuk Stack

Stack adalah subclass langsung dari Vector ; ini berarti mirip dengan superclass-nya, ini adalah implementasi yang disinkronkan .

Namun, sinkronisasi tidak selalu diperlukan, dalam kasus seperti itu, disarankan untuk menggunakan ArrayDeque .

4. Tambahkan ke dalam Stack

Mari kita mulai dengan menambahkan elemen ke atas Stack , dengan metode push () - yang juga mengembalikan elemen yang telah ditambahkan:

@Test public void whenElementIsPushed_thenStackSizeIsIncreased() { Stack intStack = new Stack(); intStack.push(1); assertEquals(1, intStack.size()); }

Menggunakan metode push () memiliki efek yang sama seperti menggunakan addElement (). T ia hanya perbedaan adalah bahwa addElement () mengembalikan hasil dari operasi, bukan elemen yang ditambahkan.

Kami juga dapat menambahkan beberapa elemen sekaligus:

@Test public void whenMultipleElementsArePushed_thenStackSizeIsIncreased() { Stack intStack = new Stack(); List intList = Arrays.asList(1, 2, 3, 4, 5, 6, 7); boolean result = intStack.addAll(intList); assertTrue(result); assertEquals(7, intList.size()); }

5. Ambil dari Stack

Selanjutnya, mari kita lihat cara mendapatkan dan menghapus elemen terakhir di Stack :

@Test public void whenElementIsPoppedFromStack_thenElementIsRemovedAndSizeChanges() { Stack intStack = new Stack(); intStack.push(5); Integer element = intStack.pop(); assertEquals(Integer.valueOf(5), element); assertTrue(intStack.isEmpty()); }

Kita juga bisa mendapatkan elemen terakhir dari taktik S tanpa menghapusnya:

@Test public void whenElementIsPeeked_thenElementIsNotRemovedAndSizeDoesNotChange() { Stack intStack = new Stack(); intStack.push(5); Integer element = intStack.peek(); assertEquals(Integer.valueOf(5), element); assertEquals(1, intStack.search(5)); assertEquals(1, intStack.size()); }

6. Cari Elemen di Stack

6.1. Cari

Stack memungkinkan kita mencari elemendan dapatkan jaraknya dari atas:

@Test public void whenElementIsOnStack_thenSearchReturnsItsDistanceFromTheTop() { Stack intStack = new Stack(); intStack.push(5); intStack.push(8); assertEquals(2, intStack.search(5)); }

Hasilnya adalah indeks dari objek tertentu. Jika ada lebih dari satu elemen, indeks satupaling dekat ke atas dikembalikan . Item yang ada di atas tumpukan dianggap berada di posisi 1.

Jika objek tidak ditemukan, search () akan mengembalikan -1.

6.2. Mendapatkan Indeks Elemen

Untuk mendapatkan indeks elemen pada taktik S , kita juga bisa menggunakan metode indexOf () dan lastIndexOf () :

@Test public void whenElementIsOnStack_thenIndexOfReturnsItsIndex() { Stack intStack = new Stack(); intStack.push(5); int indexOf = intStack.indexOf(5); assertEquals(0, indexOf); }

The lastIndexOf () akan selalu menemukan indeks elemen yang paling dekat dengan bagian atas tumpukan . Ini bekerja sangat mirip dengan search () - dengan perbedaan penting yang mengembalikan indeks, bukan jarak dari atas:

@Test public void whenMultipleElementsAreOnStack_thenIndexOfReturnsLastElementIndex() { Stack intStack = new Stack(); intStack.push(5); intStack.push(5); intStack.push(5); int lastIndexOf = intStack.lastIndexOf(5); assertEquals(2, lastIndexOf); }

7. Hapus Elemen dari Stack

Selain operasi pop () , digunakan baik untuk menghapus dan mengambil elemen, kita juga bisa menggunakan beberapa operasi yang diwarisi dari kelas Vektor untuk menghapus elemen.

7.1. Menghapus Elemen Tertentu

Kita bisa menggunakan metode removeElement () untuk menghapus kejadian pertama dari elemen yang diberikan:

@Test public void whenRemoveElementIsInvoked_thenElementIsRemoved() { Stack intStack = new Stack(); intStack.push(5); intStack.push(5); intStack.removeElement(5); assertEquals(1, intStack.size()); }

Kita juga bisa menggunakan removeElementAt () untuk menghapus elemen di bawah indeks yang ditentukan di Stack:

 @Test public void whenRemoveElementAtIsInvoked_thenElementIsRemoved() { Stack intStack = new Stack(); intStack.push(5); intStack.push(7); intStack.removeElementAt(1); assertEquals(-1, intStack.search(7)); }

7.2. Menghapus Banyak Elemen

Mari kita lihat sekilas cara menghapus beberapa elemen dari Stack menggunakan removeAll () API - yang akan menjadikan Collection sebagai argumen dan menghapus semua elemen yang cocok dari Stack :

@Test public void givenElementsOnStack_whenRemoveAllIsInvoked_thenAllElementsFromCollectionAreRemoved() { Stack intStack = new Stack(); List intList = Arrays.asList(1, 2, 3, 4, 5, 6, 7); intStack.addAll(intList); intStack.add(500); intStack.removeAll(intList); assertEquals(1, intStack.size()); assertEquals(1, intStack.search(500)); }

Ini juga mungkin untuk menghapus semua elemen dari Stack menggunakan jelas () atau removeAllElements () metode ; kedua metode tersebut bekerja sama:

@Test public void whenRemoveAllElementsIsInvoked_thenAllElementsAreRemoved() { Stack intStack = new Stack(); intStack.push(5); intStack.push(7); intStack.removeAllElements(); assertTrue(intStack.isEmpty()); }

7.3. Menghapus Elemen Menggunakan Filter

Kami juga dapat menggunakan kondisi untuk menghapus elemen dari Stack. Mari kita lihat bagaimana melakukan ini menggunakan removeIf () , dengan ekspresi filter sebagai argumen:

@Test public void whenRemoveIfIsInvoked_thenAllElementsSatysfyingConditionAreRemoved() { Stack intStack = new Stack(); List intList = Arrays.asList(1, 2, 3, 4, 5, 6, 7); intStack.addAll(intList); intStack.removeIf(element -> element < 6); assertEquals(2, intStack.size()); }

8. Iterasi Selama Stack

Stack allows us to use both an Iterator and a ListIterator. The main difference is that the first one allows us to traverse Stack in one direction and second allows us to do this in both directions:

@Test public void whenAnotherStackCreatedWhileTraversingStack_thenStacksAreEqual() { Stack intStack = new Stack(); List intList = Arrays.asList(1, 2, 3, 4, 5, 6, 7); intStack.addAll(intList); ListIterator it = intStack.listIterator(); Stack result = new Stack(); while(it.hasNext()) { result.push(it.next()); } assertThat(result, equalTo(intStack)); }

All Iterators returned by Stack are fail-fast.

9. Stream API for the Java Stack

Stack is a collection, which means we can use it with Java 8 Streams API. Using Stream with the Stack is similar to using it with any other Collection:

@Test public void whenStackIsFiltered_allElementsNotSatisfyingFilterConditionAreDiscarded() { Stack intStack = new Stack(); List inputIntList = Arrays.asList(1, 2, 3, 4, 5, 6, 7, 9, 10); intStack.addAll(inputIntList); List filtered = intStack .stream() .filter(element -> element <= 3) .collect(Collectors.toList()); assertEquals(3, filtered.size()); }

10. Summary

This tutorial is a quick and practical guide to understand this core class in Java – the Stack.

Tentu saja, Anda dapat menjelajahi API lengkap di Javadoc.

Dan, seperti biasa, semua contoh kode dapat ditemukan di GitHub.