Menu

Výukový program Java Stack: Implementácia triedy Stack s príkladmi

  • Hlavná
  • Iné
  • Výukový program Java Stack: Implementácia triedy Stack s príkladmi

java stack tutorial stack class implementation with examples

Vyskúšajte Náš Nástroj Na Odstránenie Problémov

V tomto výučbe sa pomocou príkladov vysvetľuje, čo je stohovanie v Jave, trieda Java Stack, metódy Stack API, implementácia stohov pomocou poľa a prepojeného zoznamu:

Zásobník je usporiadaná dátová štruktúra patriaca do Java Collection Framework. V tejto kolekcii sú prvky pridávané a odstraňované iba z jedného konca. Koniec, pri ktorom sa prvky pridávajú a odoberajú, sa nazýva „Top of the Stack“.

Pretože pridávanie a mazanie sa vykonáva iba na jednom konci, stane sa prvý prvok pridaný do stohu posledným prvkom odstráneným zo stohu. Zásobník sa teda nazýva dátová štruktúra LIFO (Last-in, First-out).

=> Tu si pozrite príručku Java Beginners Guide

Hromadná zbierka v Jave

Čo sa dozviete:

ako pridať hodnotu do poľa

Zbierka Java Stack

Obrázkové znázornenie zásobníka je uvedené nižšie.

obrazové znázornenie stohu

Ako je znázornené vo vyššie uvedenej postupnosti znázornenia, spočiatku je stoh prázdny a horná časť stohovania je nastavená na -1. Potom iniciujeme operáciu „push“, ktorá sa používa na pridanie prvku do zásobníka.

Takže v druhom znázornení stlačíme prvok 10. V tomto okamihu je vrchol zvýšený. Opäť vtlačíme prvok 20 do stohu, čím sa horná časť ďalej zvyšuje.

V poslednej reprezentácii iniciujeme operáciu „pop“. Táto operácia sa používa na odstránenie prvku zo zásobníka. Operácia pop odstráni prvok, ktorý je momentálne označený ako „Top“.

Štruktúra údajov zásobníka podporuje nasledujúce operácie:

  • Tam: Pridá prvok do zásobníka. Vo výsledku sa zvýši hodnota hornej časti.
  • Pop: Element je odstránený zo stohu. Po operácii pop sa hodnota vrcholu zníži.
  • Nakuknúť: Táto operácia sa používa na vyhľadanie alebo vyhľadanie prvku. Hodnota hornej časti sa nemení.

Horná časť stohu, ktorá sa používa ako koniec na pridanie / odstránenie prvkov zo stohu, môže mať v konkrétnom okamihu tiež rôzne hodnoty. Ak je veľkosť stohu N, potom horná časť stohu bude mať nasledujúce hodnoty za rôznych podmienok v závislosti od toho, v akom stave sa zásobník nachádza.

Stav zásobníkaŠpičková hodnota
Zásobník prázdny-1
Jeden prvok v zásobníku0
Stoh plnýN-1
Prepad (prvky> N)N

Hromadná trieda v Jave

Java Collection Framework poskytuje triedu s názvom „Stack“. Táto trieda Stack rozširuje triedu Vector a implementuje funkčnosť dátovej štruktúry Stack.

Nasledujúci diagram zobrazuje hierarchiu triedy Stack.

Hierarchia triedy zásobníkov v Jave

Ako je zrejmé z vyššie uvedeného diagramu, trieda Stack dedí triedu Vector, ktorá zase implementuje rozhranie List Interface of Collection.

Trieda Stack je súčasťou balíka java.util. Na zahrnutie triedy Stack do programu môžeme použiť príkaz import nasledovne.

import java.util.*;

alebo

import java.util.Stack;

Vytvorte stoh v prostredí Java

Po importovaní triedy Stack môžeme vytvoriť objekt Stack, ako je uvedené nižšie:

Stack mystack = new Stack();

Môžeme tiež vytvoriť všeobecný typ objektu triedy Stack nasledovne:

Stack myStack = new Stack;

Tu data_type môže byť akýkoľvek platný údajový typ v Jave.

Napríklad ,môžeme vytvoriť nasledujúce objekty triedy Stack.

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

Stack API Methods in Java

Trieda Stack poskytuje metódy na pridávanie, odstraňovanie a vyhľadávanie údajov v zásobníku. Poskytuje tiež metódu kontroly, či je zásobník prázdny. O týchto metódach sa budeme baviť v nasledujúcej časti.

Prevádzka stláčania

Operácia tlačenia sa používa na tlačenie alebo pridávanie prvkov do stohu. Hneď ako vytvoríme inštanciu zásobníka, môžeme pomocou operácie stlačenia pridať do zásobníka prvky typu objektu zásobníka.

Nasledujúca časť kódu sa používa na inicializáciu celého čísla s hodnotami.

Stack myStack = new Stack(); myStack.push(10); myStack.push(15); myStack.push(20);

Počiatočný zásobník získaný ako výsledok vyššie uvedeného vykonania kódu je uvedený nižšie:

počiatočný stack

Ak vykonáme ďalšiu operáciu push (), ako je uvedené nižšie,

push(25);

Výsledný zásobník bude:

Výsledný zásobník

Stack Pop Operation

Element môžeme odstrániť zo stohu pomocou operácie „pop“. Prvok, na ktorý v súčasnosti ukazuje vrchol, je vyradený zo zásobníka.

Nasledujúca časť kódu to dosahuje.

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

Premenná val bude obsahovať hodnotu 200, pretože bola posledným prvkom vloženým do zásobníka.

Zásobníková reprezentácia pre operácie push a pop je nasledovná:

push a pop operácia

Stack Peek Operation

Peek operácia vráti vrchol zásobníka bez odstránenia prvku. V príklade vyššie uvedeného zásobníka funkcia „intStack.peek ()“ vráti hodnotu 200.

Zásobník je prázdna operácia

Operácia isEmpty () triedy Stack kontroluje, či je objekt zásobníka prázdny. Ak zásobník nemá žiadne prvky, vráti hodnotu true, vráti hodnotu false.

Operácia hľadania zásobníka

Element v zásobníku môžeme vyhľadať pomocou operácie search (). Operácia search () vráti index hľadaného prvku. Tento index sa počíta od hornej časti stohu.

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

Veľkosť stohu

Veľkosť objektu Stack je daná znakom java.util.Stack.size () metóda. Vráti celkový počet prvkov v zásobníku.

Nasledujúci príklad vytlačí veľkosť stohu.

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

Tlač / Iterácia prvkov zásobníka

Môžeme deklarovať iterátor pre zásobník a potom pomocou tohto iterátora prechádzať celým zásobníkom. Týmto spôsobom môžeme navštíviť a vytlačiť každý prvok zásobníka jeden po druhom.

Nasledujúci program ukazuje spôsob, ako iterovať Stack pomocou iterátora.

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() + ' '); } } }

Výkon:

Skladovacie prvky:
PUNE MUMBAI NASHIK

Výstup zásobníka

Skladanie pomocou Javy 8

Môžeme tiež tlačiť alebo prechádzať elementy zásobníka pomocou funkcií Java 8, ako sú Stream API, forEach a forEachRemaining.

Nasledujúci program demonštruje použitie konštrukcií Java 8 na prechádzanie zásobníkom.

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 + ' '); }); } }

Výkon:

Skladanie prvkov pomocou Java 8 forEach:
PUNE MUMBAI NASHIK
Skladanie prvkov pomocou Java 8 forEachRemaining:
PUNE MUMBAI NASHIK

výstup - stohovanie pomocou Java 8

Stack Implementácia v Jave

Nasledujúci program implementuje podrobný zásobník demonštrujúci rôzne operácie so zásobníkom.

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()); } }

Výkon:

Počiatočný zásobník: ()
Je zásobník prázdny? : pravda
Stoh po operácii stlačenia: (10, 20, 30, 40)
Element vyskočený: 40
Stack after Pop Operation: (10, 20, 30)
Element 10 nájdený na pozícii: 3
Je zásobník prázdny? : nepravdivé

výstup - implementácia zásobníka

ako spustiť súbory jar v systéme Windows 10

Stack to Array v Jave

Štruktúru dát zo zásobníka je možné previesť na pole pomocou metódy ‘toArray ()‘ triedy Stack.

Nasledujúci program demonštruje túto konverziu.

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

Výkon:

Obsah zásobníka: (PUNE, MUMBAI, NASHIK)
Obsah poľa:
PUNE MUMBAI NASHIK

výstup - STACK TO ARRAY IN JAVA

Skladanie implementácie v Jave pomocou poľa

Zásobník je možné implementovať pomocou poľa. Všetky operácie so zásobníkom sa vykonávajú pomocou poľa.

Nasledujúci program demonštruje implementáciu Stack pomocou poľa.

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(); } }

Výkon:

Počiatočné vyprázdnenie stohu: pravda
Po zatlačení…
Tlač prvkov stohu ... ..
40 30 20 10
Vyskakujúca položka: 40

Vyskakujúca položka: 30
Po popovej operácii…
Tlač prvkov stohu ... ..
20 10

scenár založený na testovaní softvéru, otázky a odpovede na otázky pre skúsených

výstup - implementácia zásobníka v jave pomocou poľa

Implementácia zásobníka pomocou prepojeného zoznamu

Zásobník je možné implementovať aj pomocou prepojeného zoznamu, rovnako ako sme to urobili pomocou polí. Jednou z výhod použitia prepojeného zoznamu na implementáciu zásobníka je, že sa môže dynamicky zväčšovať alebo zmenšovať. Nemusíme mať obmedzenie maximálnej veľkosti ako v poliach.

Nasledujúci program implementuje prepojený zoznam na vykonávanie operácií zásobníka.

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()); } }

Výkon:

Skladovacie prvky:
1-> 3-> 5-> 7-> 9->

Vrchná strana stohu: 1
Pop dva prvky
Skladovacie prvky:
5-> 7-> 9->

Nový vrch zásobníka: 5

výstup - implementácia zásobníka pomocou prepojeného zoznamu

často kladené otázky

Otázka 1) Čo sú komíny v Jave?

Odpoveď: Zásobník je dátová štruktúra LIFO (Last in, First out) na ukladanie prvkov. Prvky stohu sa pridávajú alebo odoberajú zo stohu z jedného konca, ktorý sa nazýva Horná časť stohu.

Pridanie prvku do stohu sa vykonáva pomocou operácie Push. Vymazanie prvkov sa vykonáva pomocou operácie pop. V Jave je zásobník implementovaný pomocou triedy Stack.

Otázka 2) Je hromadná zbierka v Jave?

Odpoveď: Áno. Zásobník je staršia kolekcia v prostredí Java, ktorá je k dispozícii od API Collection v prostredí Java 1.0 a novších. Stack dedí triedu Vector rozhrania List.

Otázka č. 3) Je zásobník rozhraním?

Odpoveď: Zásobník rozhraní je rozhranie, ktoré popisuje štruktúru last-in, first-out a používa sa na ukladanie stavu rekurzívnych problémov.

Otázka č. 4) Na čo sa používajú stohy?

Odpoveď: Nasledujú hlavné aplikácie zásobníka:

  • Vyhodnotenie výrazov a prepočty: Zásobník sa používa na prevod výrazov na postfix, infix a prefix. Používa sa tiež na vyhodnotenie týchto výrazov.
  • Zásobník sa používa aj na analýzu stromov syntaxe.
  • Zásobník sa používa na kontrolu zátvoriek vo výraze.
  • Zásobník sa používa na riešenie problémov so spätným sledovaním.
  • Volania funkcií sa vyhodnocujú pomocou zásobníkov.

Otázka č. 5) Aké sú výhody zásobníka?

Odpoveď: Premenné uložené v zásobníku sa po vrátení automaticky zničia. Stohy sú lepšou voľbou, keď je pamäť pridelená a uvoľnená. Zásobníky tiež vyčistia pamäť. Okrem toho je možné stohy efektívne použiť na vyhodnotenie výrazov a na ich analýzu.

Záver

Týmto sa dokončuje náš návod Stacks v Jave. Trieda Stack je súčasťou rozhrania API na zhromažďovanie a podporuje operácie push, pop, peek a search. Prvky sa pridávajú alebo odoberajú do / zo stohu iba na jednom konci. Tento koniec sa nazýva horná časť stohu.

V tomto tutoriáli sme videli všetky metódy podporované triedou zásobníka. Zásobník sme implementovali aj pomocou polí a prepojených zoznamov.

V ďalších príručkách budeme pokračovať v ďalších triedach zbierania.

=> Prečítajte si sériu Easy Java Training Series

Odporúčané čítanie

^