java stack tutorial stack class implementation with examples
Denne vejledning forklarer, hvad der er Stack i Java, Java Stack Class, Stack API-metoder, Stack Implementation ved hjælp af Array & Linked List ved hjælp af eksempler:
En stak er en ordnet datastruktur, der hører til Java Collection Framework. I denne samling tilføjes og fjernes elementerne kun fra den ene ende. Den ende, hvor elementerne tilføjes og fjernes, kaldes 'Top of the Stack'.
Da tilføjelse og sletning kun udføres i den ene ende, er det første element, der føjes til stakken, tilfældigvis det sidste element, der fjernes fra stakken. Således kaldes stack en LIFO (Last-in, First-out) datastruktur.
=> Se på Java Beginners Guide her
Hvad du lærer:
- Java Stack-samling
- Konklusion
Java Stack-samling
En billedlig gengivelse af stakken er givet nedenfor.
Som vist i ovenstående repræsentationssekvens er stakken oprindeligt tom, og toppen af stakken er indstillet til -1. Derefter indleder vi en “push” -operation, der bruges til at tilføje et element til stakken.
Så i den anden repræsentation skubber vi element 10. På dette tidspunkt er toppen inkrementeret. Vi skubber igen element 20 i stakken, hvorved toppen yderligere øges.
I den sidste repræsentation indleder vi en 'pop' -operation. Denne handling bruges til at fjerne et element fra stakken. Et element, der i øjeblikket peges på 'Top', fjernes af pop-operationen.
En stack-datastruktur understøtter følgende operationer:
char til streng c ++
- Skubbe: Føjer et element til stakken. Som et resultat øges værdien af toppen.
- Pop: Et element fjernes fra stakken. Efter popoperationen mindskes værdien af toppen.
- Kig: Denne handling bruges til at slå op eller søge efter et element. Værdien af toppen er ikke ændret.
Den øverste del af stakken, der bruges som en ende til at tilføje / fjerne elementer fra stakken, kan også have forskellige værdier på et bestemt tidspunkt. Hvis størrelsen på stakken er N, vil toppen af stakken have følgende værdier under forskellige forhold afhængigt af hvilken tilstand stakken er i.
Stackens status | Top værdi |
---|---|
Stak tom | -1 |
Et element i stakken | 0 |
Stak fuld | N-1 |
Overløb (elementer> N) | N |
Stak klasse i Java
Java Collection Framework giver en klasse med navnet “Stack”. Denne Stack-klasse udvider Vector-klassen og implementerer funktionaliteten i Stack-datastrukturen.
Nedenstående diagram viser hierarkiet for Stack-klassen.
Som vist i ovenstående diagram arver Stack-klassen Vector-klassen, som igen implementerer grænsefladen List Interface of Collection.
Stack-klassen er en del af java.util-pakken. For at inkludere Stack-klassen i programmet kan vi bruge importerklæringen som følger.
import java.util.*;
eller
import java.util.Stack;
Opret en stak i Java
Når vi først har importeret Stack-klassen, kan vi oprette et Stack-objekt som vist nedenfor:
Stack mystack = new Stack();
Vi kan også oprette en generisk type Stack-klasseobjekt som følger:
Stack myStack = new Stack;
Her kan data_type være en hvilken som helst gyldig datatype i Java.
For eksempel ,Vi kan oprette følgende Stack-klasseobjekter.
Stack stack_obj = new Stack(); Stack str_stack = new Stack();
Stak API-metoder i Java
Stakklassen indeholder metoder til at tilføje, fjerne og søge data i stakken. Det giver også en metode til at kontrollere, om stakken er tom. Vi vil diskutere disse metoder i nedenstående afsnit.
Stack Push-operation
Push-operationen bruges til at skubbe eller tilføje elementer i stakken. Når vi har oprettet en stakforekomst, kan vi bruge push-operationen til at tilføje elementerne af stakobjektypen til stakken.
Følgende stykke kode bruges til at initialisere en hel stak med værdierne.
Stack myStack = new Stack(); myStack.push(10); myStack.push(15); myStack.push(20);
Den indledende stak opnået som et resultat af ovenstående stykke kodeudførelse er vist nedenfor:
Hvis vi udfører en anden push () -operation som vist nedenfor,
push(25);
Den resulterende stak vil være:
Stack Pop-operation
Vi kan fjerne elementet fra stakken ved hjælp af 'pop' -operationen. Elementet, der peges af toppen på nuværende tidspunkt, springer fra stakken.
Det følgende stykke kode opnår dette.
Stack intStack = new Stack(); intStack.push(100); intStack.push(200); int val = intStack.pop();
Den variable val vil indeholde værdien 200, da det var det sidste element, der blev skubbet ind i stakken.
Stakrepræsentationen til push- og pop-operation er som følger:
Stack Peek-operation
Peek-operationen returnerer toppen af stakken uden at fjerne elementet. I ovenstående stakeksempel returnerer “intStack.peek ()” 200.
Stack er tom drift
Funktionen isEmpty () i Stack-klassen kontrollerer, om stack-objektet er tomt. Det returnerer sandt, hvis stakken ikke har nogen elementer i det ellers returnerer falsk.
Stack-søgning
Vi kan søge efter et element på stakken ved hjælp af søgningen (). Funktionen søgning () returnerer indekset for det element, der søges efter. Dette indeks tælles fra toppen af stakken.
Stack intStack = new Stack (); intStack.push (100); intStack.push (200); int index = inStack.search(100); //index will have the value 2.
Stakstørrelse
Størrelsen på Stack-objektet er angivet af java.util.Stack.size () metode. Det returnerer det samlede antal elementer i stakken.
I det følgende eksempel udskrives stakstørrelsen.
Stack myStack = new Stack(); myStack.push(100); myStack.push(200); myStack.push(300); System.out.println('Stack size:' + myStack.size()); //Stack size: 3
Udskriv / gentag stakelementer
Vi kan erklære en iterator for stakken og derefter krydse gennem hele stakken ved hjælp af denne iterator. På denne måde kan vi besøge og udskrive hvert stakelement en efter en.
Det følgende program viser, hvordan man gentager Stack ved hjælp af en iterator.
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() + ' '); } } }
Produktion:
Stakelementer:
PUNE MUMBAI NASHIK
Stak ved hjælp af Java 8
Vi kan også udskrive eller gennemgå stakelementerne ved hjælp af Java 8-funktioner som Stream API'er, forEach og forEachRemaining-konstruktioner.
Det følgende program demonstrerer brugen af Java 8-konstruktioner til at krydse gennem stakken.
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 + ' '); }); } }
Produktion:
Stak elementer ved hjælp af Java 8 forEach:
PUNE MUMBAI NASHIK
Stakelementer ved hjælp af Java 8 forEachRemaining:
PUNE MUMBAI NASHIK
Stakimplementering i Java
Det følgende program implementerer den detaljerede stak, der demonstrerer de forskellige stakoperationer.
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()); } }
Produktion:
Indledende stak: []
Er stakken tom? : sand
Stak efter skubbetjening: [10, 20, 30, 40]
Element sprang ud: 40
Stak efter popoperation: [10, 20, 30]
Element 10 fundet ved position: 3
Er stack tom? : falsk
bedste youtube til mp3 konverter gratis
Stak til matrix i Java
Stakdatastrukturen kan konverteres til en Array ved hjælp af 'toArray ()' -metoden i Stack-klassen.
Følgende program viser denne konvertering.
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 Produktion:
Stakens indhold: [PUNE, MUMBAI, NASHIK]
Matrixindholdet:
PUNE MUMBAI NASHIK
Stakimplementering i Java ved hjælp af Array
Stakken kan implementeres ved hjælp af en Array. Alle stakoperationer udføres ved hjælp af en matrix.
Nedenstående program demonstrerer Stack-implementeringen ved hjælp af en matrix.
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(); } }
Produktion:
Indledende stak tom: sand
Efter Push-operation ...
Udskriver stakelementer ... ..
40 30 20 10
Vare poppet: 40
Vare poppet: 30
Efter popoperation ...
Udskriver stakelementer ... ..
20 10
Stakimplementering ved hjælp af sammenkædet liste
Stakken kan også implementeres ved hjælp af en sammenkædet liste, ligesom hvordan vi har gjort ved hjælp af arrays. En fordel ved at bruge en linket liste til implementering af stack er, at den kan vokse eller krympe dynamisk. Vi behøver ikke have en maksimal størrelsesbegrænsning som i arrays.
Det følgende program implementerer en sammenkædet liste til at udføre stakoperationer.
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()); } }
Produktion:
Stakelementer:
1-> 3-> 5-> 7-> 9->
Stack top: 1
Pop to elementer
Stakelementer:
5-> 7-> 9->
Ny stak top: 5
Ofte stillede spørgsmål
Q # 1) Hvad er stakke i Java?
Svar: En stak er en LIFO (Last in, First out) datastruktur til lagring af elementer. Stakelementerne tilføjes eller fjernes fra stakken fra den ene ende kaldet Top of the stack.
Tilføjelsen af et element til stakken sker ved hjælp af Push-operationen. Sletning af elementer sker ved hjælp af pop-operation. I Java implementeres en stak ved hjælp af klassen Stack.
Q # 2) Er stack en samling i Java?
boble sorteringsalgoritme c ++
Svar: Ja. Stakken er en ældre samling i Java, der er tilgængelig fra Collection API i Java 1.0 og fremefter. Stack arver Vector-klassen i grænsefladen List.
Q # 3) Er Stack et interface?
Svar: Interface stack er en interface, der beskriver den sidste-i-først-ud-struktur og bruges til at lagre tilstanden for rekursive problemer.
Spørgsmål nr. 4) Hvad bruges stakke til?
Svar: Følgende er de vigtigste anvendelser af stakken:
- Ekspression evaluering og konverteringer: Stack bruges til at konvertere udtryk til postfix, infix og præfiks. Det bruges også til at evaluere disse udtryk.
- Stakken bruges også til at analysere syntaks træer.
- Stakken bruges til at kontrollere parenteser i et udtryk.
- Stakken bruges til at løse problemer med backtracking.
- Funktionsopkald evalueres ved hjælp af stakke.
Q # 5) Hvad er fordelene ved stakken?
Svar: Variabler, der er gemt på stakken, destrueres automatisk, når de returneres. Stakke er et bedre valg, når hukommelsen tildeles og deallokeres. Stakke renser også hukommelsen. Bortset fra at stakke kan bruges effektivt til at evaluere udtryk og analysere udtrykkene.
Konklusion
Dette fuldender vores tutorial om stakke i Java. Stack-klassen er en del af samlingens API og understøtter push-, pop-, peek- og søgefunktioner. Elementerne tilføjes eller fjernes kun til / fra stakken i den ene ende. Denne ende kaldes toppen af stakken.
I denne vejledning har vi set alle de metoder, der understøttes af stack-klassen. Vi har også implementeret stakken ved hjælp af arrays og sammenkædede lister.
Vi fortsætter med andre indsamlingsklasser i vores efterfølgende tutorials.
=> Læs gennem Easy Java Training Series
Anbefalet læsning
- Java Reflection Tutorial med eksempler
- Java Scanner-klassevejledning med eksempler
- Hvad er en Java HashTable - HashTable-implementering og eksempel
- Hvad er Java Vector | Java Vector Class Tutorial med eksempler
- Java Array Class Tutorial - java.util.Arrays-klasse med eksempler
- Java Basics: Java Syntax, Java Class og Core Java Concepts
- LinkedHashMap i Java - LinkedHashMap Eksempel og implementering
- Java SWING Tutorial: Container, komponenter og håndtering af begivenheder