Menu

Samouczek dotyczący stosu Java: Implementacja klas stosu z przykładami

  • Główny
  • Inny
  • Samouczek dotyczący stosu Java: Implementacja klas stosu z przykładami

java stack tutorial stack class implementation with examples

Wypróbuj Nasz Instrument Do Eliminowania Problemów

Ten samouczek wyjaśnia, czym jest stos w Javie, klasa stosu Java, metody interfejsu API stosu, implementacja stosu przy użyciu tablicy i listy połączonej za pomocą przykładów:

Stos to uporządkowana struktura danych należąca do środowiska Java Collection Framework. W tej kolekcji elementy są dodawane i usuwane tylko z jednego końca. Zakończenie dodawania i usuwania elementów nosi nazwę „Początek stosu”.

Ponieważ dodawanie i usuwanie odbywa się tylko na jednym końcu, pierwszy element dodany do stosu jest ostatnim elementem usuwanym ze stosu. Dlatego stos nazywany jest strukturą danych LIFO (Last-in, First-out).

=> Zapoznaj się z podręcznikiem Java dla początkujących tutaj

Kolekcja stosów w Javie

Czego się nauczysz:

Kolekcja Java Stack

Graficzne przedstawienie stosu podano poniżej.

obrazowe przedstawienie stosu

Jak pokazano na powyższej sekwencji reprezentacji, początkowo stos jest pusty, a wierzchołek stosu jest ustawiony na -1. Następnie inicjujemy operację „push”, która służy do dodania elementu do stosu.

Zatem w drugiej reprezentacji wciskamy element 10. W tym momencie wierzchołek jest zwiększany. Ponownie wsuwamy element 20 do stosu, zwiększając tym samym dodatkowo górę.

W ostatniej reprezentacji inicjujemy operację „pop”. Ta operacja służy do usuwania elementu ze stosu. Element aktualnie wskazywany na „Góra” jest usuwany przez operację wyskakiwania.

Struktura danych stosu obsługuje następujące operacje:

  • Pchać: Dodaje element do stosu. W rezultacie wartość szczytu jest zwiększana.
  • Muzyka pop: Element jest usuwany ze stosu. Po operacji pop wartość góry jest zmniejszana.
  • Zerkać: Ta operacja służy do wyszukiwania lub wyszukiwania elementu. Wartość góry nie jest modyfikowana.

Wierzchołek stosu, który jest używany jako koniec dodawania / usuwania elementów ze stosu, może również mieć różne wartości w określonej chwili. Jeśli rozmiar stosu to N, wówczas wierzchołek stosu będzie miał następujące wartości w różnych warunkach, w zależności od stanu stosu.

Stan stosuNajwyższa wartość
Stos pusty-1
Jeden element w stosie0
Pełny stosN-1
Przepełnienie (elementy> N)N

Klasa stosu w Javie

Java Collection Framework udostępnia klasę o nazwie „Stack”. Ta klasa Stack rozszerza klasę Vector i implementuje funkcjonalność struktury danych Stack.

Poniższy diagram przedstawia hierarchię klasy Stack.

Hierarchia klas stosu w Javie

Jak pokazano na powyższym diagramie, klasa Stack dziedziczy klasę Vector, która z kolei implementuje interfejs List Interface of Collection.

Klasa Stack jest częścią pakietu java.util. Aby dołączyć klasę Stack do programu, możemy użyć instrukcji import w następujący sposób.

import java.util.*;

lub

import java.util.Stack;

Utwórz stos w Javie

Po zaimportowaniu klasy Stack możemy utworzyć obiekt Stack, jak pokazano poniżej:

Stack mystack = new Stack();

Możemy również utworzyć ogólny typ obiektu klasy Stack w następujący sposób:

Stack myStack = new Stack;

Tutaj data_type może być dowolnym poprawnym typem danych w Javie.

Na przykład ,możemy stworzyć następujące obiekty klasy Stack.

Stack stack_obj = new Stack(); Stack str_stack = new Stack();

Stosuj metody API w Javie

Klasa Stack udostępnia metody dodawania, usuwania i wyszukiwania danych w Stack. Zapewnia również metodę sprawdzania, czy stos jest pusty. Omówimy te metody w poniższej sekcji.

Operacja wypychania stosu

Operacja wypychania służy do umieszczania lub dodawania elementów do stosu. Po utworzeniu instancji stosu możemy użyć operacji wypychania, aby dodać elementy typu obiektu stosu do stosu.

Poniższy fragment kodu służy do inicjalizacji stosu liczb całkowitych z wartościami.

algorytm scalania i sortowania c ++
Stack myStack = new Stack(); myStack.push(10); myStack.push(15); myStack.push(20);

Początkowy stos uzyskany w wyniku wykonania powyższego fragmentu kodu pokazano poniżej:

początkowy stos

Jeśli wykonamy kolejną operację push (), jak pokazano poniżej,

push(25);

Wynikowy stos będzie:

Wynikowy stos

Operacja Stack Pop

Możemy usunąć element ze stosu za pomocą operacji „pop”. Element wskazywany obecnie przez Top jest zdejmowany ze stosu.

Osiąga to następujący fragment kodu.

Stack intStack = new Stack(); intStack.push(100); intStack.push(200); int val = intStack.pop();

Zmienna val będzie zawierać wartość 200, ponieważ był ostatnim elementem umieszczonym w stosie.

Reprezentacja stosu operacji push i pop jest następująca:

operacja push i pop

Operacja Stack Peek

Operacja wglądu zwraca górę stosu bez usuwania elementu. W powyższym przykładzie stosu „intStack.peek ()” zwróci 200.

Operacja Stack isEmpty

Operacja isEmpty () klasy Stack sprawdza, czy obiekt stosu jest pusty. Zwraca true, jeśli stos nie zawiera żadnych elementów, w przeciwnym razie zwraca false.

Operacja wyszukiwania stosu

Możemy wyszukać element na stosie za pomocą operacji search (). Operacja search () zwraca indeks szukanego elementu. Ten indeks jest liczony od góry stosu.

Stack intStack = new Stack (); intStack.push (100); intStack.push (200); int index = inStack.search(100); //index will have the value 2.

Rozmiar stosu

Rozmiar obiektu Stack jest określony przez java.util.Stack.size () metoda. Zwraca całkowitą liczbę elementów w stosie.

Poniższy przykład drukuje rozmiar stosu.

Stack myStack = new Stack(); myStack.push(100); myStack.push(200); myStack.push(300); System.out.println('Stack size:' + myStack.size()); //Stack size: 3

Drukuj / powtarzaj elementy stosu

Możemy zadeklarować iterator dla stosu, a następnie przejść przez cały stos, używając tego iteratora. W ten sposób możemy odwiedzać i drukować każdy element stosu jeden po drugim.

Poniższy program przedstawia sposób iteracji stosu przy użyciu iteratora.

import java.util.*; public class Main { public static void main(String() args) { //declare and initialize a stack object Stack stack = new Stack(); stack.push('PUNE'); stack.push('MUMBAI'); stack.push('NASHIK'); System.out.println('Stack elements:'); //get an iterator for the stack Iterator iterator = stack.iterator(); //traverse the stack using iterator in a loop and print each element while(iterator.hasNext()){ System.out.print(iterator.next() + ' '); } } }

Wynik:

Elementy stosu:
PUNE MUMBAI NASHIK

Wyjście stosu

Stosuj za pomocą Java 8

Możemy również drukować lub przechodzić przez elementy stosu przy użyciu funkcji Java 8, takich jak Stream API, konstrukcje forEach i forEachRemaining.

Poniższy program demonstruje użycie konstrukcji Java 8 do przechodzenia przez stos.

import java.util.*; import java.util.stream.*; public class Main { public static void main(String() args) { //declare and initialize a stack object Stack stack = new Stack(); stack.push('PUNE'); stack.push('MUMBAI'); stack.push('NASHIK'); System.out.println('Stack elements using Java 8 forEach:'); //get a stream for the stack Stream stream = stack.stream(); //traverse though each stream object using forEach construct of Java 8 stream.forEach((element) -> { System.out.print(element + ' '); // print element }); System.out.println(' Stack elements using Java 8 forEachRemaining:'); //define an iterator for the stack Iterator stackIterator = stack.iterator(); //use forEachRemaining construct to print each stack element stackIterator.forEachRemaining(val -> { System.out.print(val + ' '); }); } }

Wynik:

Stosuj elementy przy użyciu Java 8 forEach:
PUNE MUMBAI NASHIK
Stosuj elementy przy użyciu języka Java 8 forEachRemaining:
PUNE MUMBAI NASHIK

dane wyjściowe - stosuj przy użyciu Java 8

Implementacja stosu w Javie

Poniższy program implementuje szczegółowy stos, demonstrujący różne operacje na stosie.

import java.util.Stack; public class Main { public static void main(String a()){ //declare a stack object Stack stack = new Stack(); //print initial stack System.out.println('Initial stack : ' + stack); //isEmpty () System.out.println('Is stack Empty? : ' + stack.isEmpty()); //push () operation stack.push(10); stack.push(20); stack.push(30); stack.push(40); //print non-empty stack System.out.println('Stack after push operation: ' + stack); //pop () operation System.out.println('Element popped out:' + stack.pop()); System.out.println('Stack after Pop Operation : ' + stack); //search () operation System.out.println('Element 10 found at position: ' + stack.search(10)); System.out.println('Is Stack empty? : ' + stack.isEmpty()); } }

Wynik:

Początkowy stos: ()
Czy stos jest pusty? : prawdziwe
Stos po operacji wypychania: (10, 20, 30, 40)
Wyskoczył element: 40
Stos po operacji pop: (10, 20, 30)
Element 10 znaleziony w pozycji: 3
Czy stos jest pusty? : fałszywy

wyjście - Implementacja stosu

Stos do tablicy w języku Java

Strukturę danych stosu można przekonwertować na Array przy użyciu metody „toArray ()” klasy Stack.

Poniższy program demonstruje tę konwersję.

import java.util.*; import java.util.stream.*; public class Main { public static void main(String() args) { //declare and initialize a stack object Stack stack = new Stack(); stack.push('PUNE'); stack.push('MUMBAI'); stack.push('NASHIK'); //print the stack System.out.println('The Stack contents: ' + stack); // Create the array and use toArray() method to convert stack to array Object() strArray = stack.toArray(); //print the array System.out.println('The Array contents:'); for (int j = 0; j

Wynik:

Zawartość stosu: (PUNE, MUMBAI, NASHIK)
Zawartość tablicy:
PUNE MUMBAI NASHIK

wyjście - STACK TO ARRAY IN JAVA

Implementacja stosu w języku Java przy użyciu tablicy

Stos można zaimplementować za pomocą Array. Wszystkie operacje na stosie są wykonywane przy użyciu tablicy.

Poniższy program demonstruje implementację stosu przy użyciu tablicy.

import java.util.*; //Stack class class Stack { int top; //define top of stack int maxsize = 5; //max size of the stack int() stack_arry = new int(maxsize); //define array that will hold stack elements Stack(){ //stack constructor; initially top = -1 top = -1; } boolean isEmpty(){ //isEmpty () method return (top <0); } boolean push (int val){ //push () method if(top == maxsize-1) { System.out.println('Stack Overflow !!'); return false; } else { top++; stack_arry(top)=val; return true; } } boolean pop () { //pop () method if (top == -1) { System.out.println('Stack Underflow !!'); return false; } else { System.out.println(' Item popped: ' + stack_arry(top--)); return true; } } void display () { //print the stack elements System.out.println('Printing stack elements .....'); for(int i = top; i>=0;i--) { System.out.print(stack_arry(i) + ' '); } } } public class Main { public static void main(String() args) { //define a stack object Stack stck = new Stack(); System.out.println('Initial Stack Empty : ' + stck.isEmpty()); //push elements stck.push(10); stck.push(20); stck.push(30); stck.push(40); System.out.println('After Push Operation...'); //print the elements stck.display(); //pop two elements from stack stck.pop(); stck.pop(); System.out.println('After Pop Operation...'); //print the stack again stck.display(); } }

Wynik:

Początkowy stos pusty: prawda
Po operacji wypychania…
Drukowanie elementów stosu…
40 30 20 10
Pojawił się przedmiot: 40

Pozycja pojawiła się: 30
Po operacji pop…
Drukowanie elementów stosu…
20 10

wyjście - implementacja stosu w java przy użyciu tablicy

Implementacja stosu przy użyciu listy połączonej

Stos można również zaimplementować za pomocą połączonej listy, tak jak zrobiliśmy to przy użyciu tablic. Jedną z zalet używania listy połączonej do implementacji stosu jest to, że może ona dynamicznie rosnąć lub kurczyć. Nie musimy mieć ograniczenia maksymalnego rozmiaru, jak w przypadku tablic.

Poniższy program implementuje połączoną listę do wykonywania operacji na stosie.

import static java.lang.System.exit; // Stack class using LinkedList class Stack_Linkedlist { // Define Node of LinkedList private class Node { int data; // node data Node nlink; // Node link } // top of the stack Node top; // stack class Constructor Stack_Linkedlist() { this.top = null; } // push () operation public void push(int val) { // create a new node Node temp = new Node(); // checks if the stack is full if (temp == null) { System.out.print(' Stack Overflow'); return; } // assign val to node temp.data = val; // set top of the stack to node link temp.nlink = top; // update top top = temp; } // isEmpty () operation public boolean isEmpty() { return top == null; } // peek () operation public int peek() { // check if the stack is empty if (!isEmpty()) { return top.data; } else { System.out.println('Stack is empty!'); return -1; } } // pop () operation public void pop() { // check if stack is out of elements if (top == null) { System.out.print(' Stack Underflow!!'); return; } // set top to point to next node top = (top).nlink; } //print stack contents public void display() { // check for stack underflow if (top == null) { System.out.printf(' Stack Underflow!!'); exit(1); } else { Node temp = top; System.out.println('Stack elements:'); while (temp != null) { // print node data System.out.print(temp.data + '->'); // assign temp link to temp temp = temp.nlink; } } } } public class Main { public static void main(String() args) { // Create a stack class object Stack_Linkedlist stack_obj = new Stack_Linkedlist(); // push values into the stack stack_obj.push(9); stack_obj.push(7); stack_obj.push(5); stack_obj.push(3); stack_obj.push(1); // print Stack elements stack_obj.display(); // print current stack top System.out.println(' Stack top : ' + stack_obj.peek()); // Pop elements twice System.out.println('Pop two elements'); stack_obj.pop(); stack_obj.pop(); // print Stack elements stack_obj.display(); // print new stack top System.out.println(' New Stack top:' + stack_obj.peek()); } }

Wynik:

Elementy stosu:
1-> 3-> 5-> 7-> 9->

Góra stosu: 1
Rozbij dwa elementy
Elementy stosu:
5-> 7-> 9->

Nowy wierzchołek stosu: 5

wyjście - implementacja stosu przy użyciu połączonej listy

Często Zadawane Pytania

Pytanie 1) Co to są stosy w Javie?

Odpowiedź: Stos jest strukturą danych LIFO (Last in, First out) do przechowywania elementów. Elementy stosu są dodawane lub usuwane ze stosu z jednego końca zwanego wierzchołkiem stosu.

Dodanie elementu do stosu odbywa się za pomocą operacji Push. Usuwanie elementów odbywa się za pomocą operacji pop. W Javie stos jest implementowany przy użyciu klasy Stack.

Pytanie 2) Czy stosuj kolekcję w Javie?

Odpowiedź: Tak. Stos jest starszą kolekcją w języku Java, która jest dostępna w interfejsie Collection API od wersji Java 1.0. Stack dziedziczy klasę Vector interfejsu List.

P # 3) Czy stos jest interfejsem?

Odpowiedź: Stos interfejsów to interfejs, który opisuje strukturę „ostatni na wejściu, pierwszy na wyjściu” i służy do przechowywania stanu problemów rekurencyjnych.

P # 4) Do czego służą stosy?

Odpowiedź: Poniżej przedstawiono główne zastosowania stosu:

  • Obliczanie i konwersje wyrażeń: Stos służy do konwertowania wyrażeń na przyrostek, wrostek i przedrostek. Służy również do oceny tych wyrażeń.
  • Stos jest również używany do analizowania drzew składni.
  • Stos jest używany do sprawdzania nawiasów w wyrażeniu.
  • Stos jest używany do rozwiązywania problemów z wycofywaniem.
  • Wywołania funkcji są oceniane przy użyciu stosów.

P # 5) Jakie są zalety stosu?

Odpowiedź: Zmienne przechowywane na stosie są automatycznie niszczone po zwróceniu. Stosy są lepszym wyborem, gdy pamięć jest przydzielana i zwalniana. Stosy również czyszczą pamięć. Oprócz tego stosy mogą być skutecznie używane do oceny wyrażeń i analizowania wyrażeń.

Wniosek

To kończy nasz samouczek dotyczący stosów w Javie. Klasa Stack jest częścią interfejsu API kolekcji i obsługuje operacje wypychania, wyskakiwania, wglądu i wyszukiwania. Elementy są dodawane lub usuwane ze stosu tylko na jednym końcu. Ten koniec nazywa się wierzchołkiem stosu.

W tym samouczku widzieliśmy wszystkie metody obsługiwane przez klasę stosu. Zaimplementowaliśmy również stos przy użyciu tablic i połączonych list.

W kolejnych samouczkach będziemy kontynuować inne klasy kolekcji.

=> Przeczytaj serię szkoleń Easy Java

rekomendowane lektury

^