Menu

Výukový program Java Stack: Implementace třídy zásobníku s příklady

  • Hlavní
  • Jiný
  • Výukový program Java Stack: Implementace třídy zásobníku s příklady

java stack tutorial stack class implementation with examples

Vyzkoušejte Náš Nástroj Pro Odstranění Problémů

Tento výukový program vysvětluje, co je Stack v Javě, Java Stack Class, Stack API Methods, Stack Implementation using Array & Linked List s pomocí příkladů:

Zásobník je uspořádaná datová struktura patřící do Java Collection Framework. V této kolekci jsou prvky přidávány a odebírány pouze z jednoho konce. Konec, na kterém jsou prvky přidávány a odebírány, se nazývá „Top of the Stack“.

Protože přidávání a mazání se provádí pouze na jednom konci, stane se první prvek přidaný do zásobníku posledním prvkem odebraným ze zásobníku. Zásobník se tedy nazývá datová struktura LIFO (Last-in, First-out).

=> Prohlédněte si příručku Java Beginners Guide zde

Stack Collection v Javě

Co se naučíte:

Sbírka Java Stack

Níže je uvedeno obrázkové znázornění zásobníku.

obrazové znázornění zásobníku

Jak je znázorněno ve výše uvedené sekvenci znázornění, zpočátku je zásobník prázdný a horní část zásobníku je nastavena na -1. Poté zahájíme operaci „push“, která se používá k přidání prvku do zásobníku.

Takže ve druhé reprezentaci tlačíme prvek 10. V tomto bodě je vrchol zvýšen. Znovu zatlačíme prvek 20 do stohu, čímž dále navýšíme horní část.

V poslední reprezentaci iniciujeme operaci „pop“. Tato operace se používá k odebrání prvku ze zásobníku. Prvek aktuálně označený jako „Nahoře“ je odstraněn operací pop.

Struktura dat zásobníku podporuje následující operace:

  • Tam: Přidá prvek do zásobníku. Ve výsledku se zvýší hodnota vrcholu.
  • Pop: Prvek je odebrán ze zásobníku. Po operaci pop se hodnota vrcholu sníží.
  • Peek: Tato operace se používá k vyhledání nebo hledání prvku. Hodnota vrcholu se nezmění.

Horní část zásobníku, která se používá jako konec pro přidání / odebrání prvků ze zásobníku, může mít v určitém okamžiku také různé hodnoty. Pokud je velikost zásobníku N, pak horní část zásobníku bude mít následující hodnoty za různých podmínek v závislosti na tom, v jakém stavu je zásobník.

Stav zásobníkuŠpičková hodnota
Zásobník prázdný-1
Jeden prvek v zásobníku0
Zásobník plnýN-1
Přetečení (prvky> N)N

Hromadná třída v Javě

Java Collection Framework poskytuje třídu s názvem „Stack“. Tato třída Stack rozšiřuje třídu Vector a implementuje funkčnost datové struktury Stack.

Níže uvedený diagram ukazuje hierarchii třídy Stack.

Hierarchie třídy zásobníku v Javě

Jak je znázorněno ve výše uvedeném diagramu, třída Stack dědí třídu Vector, která zase implementuje rozhraní List Interface of Collection.

Třída Stack je součástí balíčku java.util. Chcete-li do programu zahrnout třídu Stack, můžeme použít příkaz import následovně.

import java.util.*;

nebo

import java.util.Stack;

Vytvořte hromadu v Javě

Jakmile importujeme třídu Stack, můžeme vytvořit objekt Stack, jak je znázorněno níže:

Stack mystack = new Stack();

Můžeme také vytvořit obecný typ objektu třídy Stack následujícím způsobem:

Stack myStack = new Stack;

Zde data_type může být jakýkoli platný datový typ v Javě.

Například ,můžeme vytvořit následující objekty třídy Stack.

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

Stack API Methods in Java

Třída Stack poskytuje metody pro přidání, odebrání a hledání dat v zásobníku. Poskytuje také metodu ke kontrole, zda je zásobník prázdný. O těchto metodách pojednáme v následující části.

Provoz zásobníku

Operace push se používá k vložení nebo přidání prvků do zásobníku. Jakmile vytvoříme instanci zásobníku, můžeme pomocí operace push přidat prvky typu objektu zásobníku do zásobníku.

Následující část kódu se používá k inicializaci celočíselného zásobníku s hodnotami.

manuální testování pohovorů na 5 let zkušeností
Stack myStack = new Stack(); myStack.push(10); myStack.push(15); myStack.push(20);

Níže je uveden počáteční zásobník získaný jako výsledek výše uvedeného provedení kódu:

počáteční zásobník

Pokud provedeme další operaci push (), jak je znázorněno níže,

push(25);

Výsledný zásobník bude:

Výsledný zásobník

Stack Pop Operation

Můžeme prvek odebrat ze zásobníku pomocí operace „pop“. Prvek, na který v současné době ukazuje horní část, je vyskakován ze zásobníku.

Následující část kódu toho dosahuje.

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

Proměnná val bude obsahovat hodnotu 200, protože to byl poslední prvek vložený do zásobníku.

Reprezentace zásobníku pro operaci push a pop je následující:

operace push a pop

Stack Peek Operation

Peek operace vrátí horní část zásobníku bez odebrání prvku. Ve výše uvedeném příkladu zásobníku vrátí funkce „intStack.peek ()“ 200.

Zásobník je prázdná operace

Operace isEmpty () třídy Stack kontroluje, zda je objekt zásobníku prázdný. Vrací true, pokud Stack neobsahuje žádné prvky, vrací false.

Operace hledání zásobníku

Můžeme vyhledat prvek v zásobníku pomocí operace search (). Operace search () vrací index hledaného prvku. Tento index se počítá od horní části zásobníku.

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

Velikost zásobníku

Velikost objektu Stack je dána java.util.Stack.size () metoda. Vrátí celkový počet prvků v zásobníku.

Následující příklad vytiskne velikost zásobníku.

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

Tisk / iterace prvků zásobníku

Můžeme deklarovat iterátor pro Stack a pak procházet celým Stackem pomocí tohoto iterátoru. Tímto způsobem můžeme navštívit a vytisknout každý prvek zásobníku jeden po druhém.

Následující program ukazuje způsob, jak iterovat Stack pomocí iterátoru.

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ýstup:

Stack elements:
PUNE MUMBAI NASHIK

Výstup zásobníku

Stack pomocí Java 8

Můžeme také tisknout nebo procházet prvky zásobníku pomocí funkcí Java 8, jako jsou Stream API, forEach a forEachRemaining konstrukty.

Následující program demonstruje použití konstruktů Java 8 k procházení stohem.

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ýstup:

Stack elements using Java 8 forEach:
PUNE MUMBAI NASHIK
Skládání prvků pomocí Java 8 forEachRemaining:
PUNE MUMBAI NASHIK

výstup - Stack pomocí Java 8

Stack Implementace v Javě

Následující program implementuje podrobný zásobník demonstrující různé operace zásobníku.

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ýstup:

Počáteční zásobník: ()
Je zásobník prázdný? : skutečný
Stoh po operaci stisknutí: (10, 20, 30, 40)
Vyskakovací prvek: 40
Stack after Pop Operation: (10, 20, 30)
Prvek 10 nalezen na pozici: 3
Je zásobník prázdný? : Nepravdivé

výstup - implementace zásobníku

Stack to Array v Javě

Strukturu dat zásobníku lze převést na pole pomocí metody ‚toArray () 'třídy Stack.

Následující program ukazuje tento převod.

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ýstup:

Obsah zásobníku: (PUNE, MUMBAI, NASHIK)
Obsah pole:
PUNE MUMBAI NASHIK

výstup - STACK TO ARRAY IN JAVA

Stack Implementace v Javě pomocí pole

Zásobník lze implementovat pomocí pole. Všechny operace zásobníku se provádějí pomocí pole.

Níže uvedený program demonstruje implementaci Stack pomocí pole.

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ýstup:

Initial Stack Empty: true
Po stisknutí tlačítka…
Tisk prvků stohu… ..
40 30 20 10
Vyskakovací položka: 40

Vyskakovací položka: 30
Po popové operaci…
Tisk prvků stohu… ..
20 10

výstup - implementace zásobníku v Javě pomocí pole

Implementace zásobníku pomocí propojeného seznamu

Zásobník lze také implementovat pomocí propojeného seznamu, stejně jako jsme to udělali pomocí polí. Jednou z výhod použití propojeného seznamu pro implementaci zásobníku je, že se může dynamicky zvětšovat nebo zmenšovat. Nepotřebujeme omezení maximální velikosti jako v polích.

Následující program implementuje propojený seznam k provádění operací zásobníku.

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ýstup:

Stack elements:
1-> 3-> 5-> 7-> 9->

Vrch zásobníku: 1
Pop dva prvky
Stack elements:
5-> 7-> 9->

Nová horní část zásobníku: 5

výstup - implementace zásobníku pomocí propojeného seznamu

Často kladené otázky

Otázka č. 1) Co jsou hromádky v Javě?

Odpovědět: Zásobník je datová struktura LIFO (Last in, First out) pro ukládání prvků. Prvky zásobníku se přidávají nebo odebírají ze zásobníku z jednoho konce zvaného Horní část zásobníku.

Přidání prvku do zásobníku se provádí pomocí operace Push. Odstranění prvků se provádí pomocí popové operace. V Javě je zásobník implementován pomocí třídy Stack.

Otázka 2) Je Stack kolekce v Javě?

Odpovědět: Ano. Zásobník je starší kolekce v Javě, která je k dispozici od Collection API v Javě 1.0 a dále. Stack dědí třídu Vector rozhraní seznamu.

Otázka č. 3) Je Stack rozhraní?

Odpovědět: Zásobník rozhraní je rozhraní, které popisuje strukturu last-in, first-out a slouží k ukládání stavu rekurzivních problémů.

Otázka č. 4) Na co se balíčky používají?

Odpověď: Níže jsou uvedeny hlavní aplikace zásobníku:

  • Vyhodnocení výrazů a převody: Zásobník se používá pro převod výrazů na postfix, infix a prefix. Používá se také k vyhodnocení těchto výrazů.
  • Zásobník se také používá k analýze syntaxových stromů.
  • Zásobník se používá ke kontrole závorek ve výrazu.
  • Zásobník se používá k řešení problémů se zpětným sledováním.
  • Volání funkcí se vyhodnocuje pomocí zásobníků.

Otázka č. 5) Jaké jsou výhody zásobníku?

Odpovědět: Proměnné uložené v zásobníku se po vrácení automaticky zničí. Zásobníky jsou lepší volbou, když je paměť přidělena a uvolněna. Zásobníky také vyčistí paměť. Kromě toho lze komíny efektivně použít k vyhodnocení výrazů a analýze výrazů.

Závěr

Tím je dokončen náš výukový program Stacks in Java. Třída zásobníku je součástí rozhraní API kolekce a podporuje operace push, pop, peek a search. Prvky se přidávají nebo odebírají do / ze zásobníku pouze na jednom konci. Tento konec se nazývá horní část zásobníku.

jak zobrazit soubor eps

V tomto kurzu jsme viděli všechny metody podporované třídou zásobníku. Zásobník jsme také implementovali pomocí polí a propojených seznamů.

V dalších výukách budeme pokračovat s dalšími třídami kolekce.

=> Přečtěte si řadu Easy Java Training Series

Doporučené čtení

^