Java Stack 101: zagłębianie się w klasę stosu

Stack w Javie to struktura danych, podobnie jak kolejka, tablica, połączona lista lub drzewo . Różni się od innych tym, że Java Stack jest oparty na zasadzie Last In, First Out (LIFO). Oznacza to, że gdy użyjesz tych dwóch poleceń do dodania i usunięcia elementu ze stosu, pierwszy usunięty element będzie zawsze dodany jako ostatni. Przyjrzyjmy się bliżej klasie Java Stack

Eksploracja klasy Java Stack

Klasa Java Stack jest rozszerzeniem klasy Vector , która z kolei jest rozszerzeniem klasy List . Ponieważ wektory są zmienne i mogą rosnąć i kurczyć się wraz z wymaganiami elementów wewnątrz, Stack s może również zmieniać rozmiary na żądanie. Rozszerzenie klasy Vector dodaje pięć operacji, które przekształcają Vector w Stack . Te pięć operacji to:

• .push(E item) – umieszcza element na wierzchu stosu
• .pop() – usuwa element ze szczytu stosu i zwraca go jako wartość funkcji
• .peek() – patrzy na element na szczycie stosu bez usuwania go
• .empty() – funkcja logiczna sprawdzająca, czy stos jest pusty, czy nie. Zwraca 0 lub 1.
• .search(Object o) – szuka o i zwraca jego pozycję. Wartość jest oparta na 1, a nie na 0

Stack dziedziczy również wszystkie metody, które są częścią Vector , w tym między innymi toString() , zawiera() , indexOf() i lastElement() .

Kodowanie przykładu stosu Java

Teraz, gdy znamy funkcje dla Stack , zakodujmy przykład stosu Java. Stosy są bardzo przydatne do obsługi danych, które muszą być tymczasowo przechowywane i szybko pobierane. Ponieważ stos jest LIFO, jest wyjątkowo przydatny do przechodzenia między węzłami podczas eksploracji drzewiastej struktury danych. Zanim przejdziemy do tego wszystkiego, stwórzmy podstawowy stos. Kod implementujący stos jest następujący:

import java.util.*;

class Main {
  public static void main(String[] args) {
    Stack<Integer> stackExample = new Stack<Integer>();

To wszystko, co musisz zrobić, aby utworzyć pusty Stack . Możesz także po prostu zadeklarować to bez deklarowania typu danych, używając:

Stack example = new Stack();

Pamiętaj, że ponieważ Stack s są zmienne, gdy umieszczamy elementy na stosie, jego rozmiar automatycznie dopasowuje się. Przyjrzyjmy się teraz, jak używać funkcji stosu .

Implementacja stosu Java

Przyjrzyjmy się, jak korzystać z pięciu metod, które pokrótce omówiliśmy wcześniej. Implementacja stosu Java jest łatwa do zapamiętania, jeśli pomyślisz o niej jako o stosie talerzy. Kładziesz talerze na stosie, ale aby dostać talerz, nie schodzisz na dół, dostajesz jeden z góry. Ostatnia, którą założysz, jest pierwszą, którą zdejmiesz. Rozszerzając nasz poprzedni przykład o stackExample , funkcje są następujące:

Naciskać

// pushing integers onto the Stack
    stackExample.push(5);
    stackExample.push(10);

W tym momencie pokażemy inne funkcje tak, jakbyśmy za każdym razem umieszczali te dwie liczby całkowite na przykładowym stosie Java.

Muzyka pop

//popping integers off of the Stack
System.out.println(stackExample.pop());
System.out.println(stackExample.pop());

Wyjście:

10
5

Jest pusty

Załóżmy teraz, że chcesz usunąć wszystkie elementy ze stosu, ale nie masz pewności, ile jest elementów. Możesz połączyć funkcję Boolean.isEmpty() z warunkiem wstępnym pętli while, aby usunąć wszystkie elementy ze Stack . Zobacz, jak przebiega ta implementacja stosu java.

while(!stackExample.isEmpty()) {      
  System.out.println(stackExample.pop());
}

Wyjście

10
5

Zerkać

Możemy użyć .peek() jako implementacji stosu w Javie, aby spojrzeć na następny element na stosie bez usuwania go.

System.out.println(stackExample.peek());

Wyjście

10

Jeśli wyciągniemy i wydrukujemy Stack , zwróci 10 i 5, ponieważ 10 wciąż jest na stosie. Po prostu spojrzeliśmy na to, nie usunęliśmy go za pomocą funkcji pop. Funkcja peek jest doskonałym narzędziem dla Stack s w Javie.

Szukaj

Jeśli chcemy znaleźć określony element, implementacja stosów w Javie używa .search(e); znaleźć to.

System.out.println(stackExample.search(5));

Wyjście

2

Pamiętaj, że dzieje się tak, ponieważ liczymy od góry Stack, a Java Stack zaczyna się od 1, a nie od 0 jak Array . Tak więc, patrząc na stos, jest to (10) --> (5), a 5 jest na miejscu numer 2. Jeśli spróbujesz znaleźć element, którego nie ma w Stack , otrzymasz -1 jako wynik.

Iteracja

Podczas pracy z dowolną kolekcją może się zdarzyć, że będziesz musiał wyszukać wiele elementów. Aby zaoszczędzić złożoności i konieczności wielokrotnego przeszukiwania stosu , możesz użyć iteracji. Ponieważ Stack w Javie rozszerza klasę List , istnieje kilka opcji iteracji. Jednym z najłatwiejszych jest użycie funkcji ListIterator . ListIterator jest fajny, ponieważ umożliwia przeglądanie stosu od góry do dołu lub od dołu do góry za pomocą .hasPrevious() lub .hasNext() . Oto jak to wygląda:

ListIterator<Integer> exampleIterator = stackExample.listIterator(stackExample.size());

  while (exampleIterator.hasPrevious()) {
    int iteration = exampleIterator.previous();
    System.out.println(iteration);
  }

Wyjście

10
5

Pamiętaj, że kiedy przeglądasz Stack s w Javie, nie usuwasz w nim żadnych elementów. Iteracja zasadniczo pozwala zerknąć na każdy element w stosie w kolejności. Kiedy to zrobisz, możesz szukać miejsc, w których znajdują się określone elementy, a następnie przechodzić przez nie i manipulować nimi. Możesz je policzyć, usunąć, a nawet zmienić, jeśli zajdzie taka potrzeba.