java stack tutorial stack class implementation with examples
Aquest tutorial explica què és la pila a Java, la classe de pila de Java, els mètodes API de pila, la implementació de la pila mitjançant Array & Linked List amb l'ajut d'exemples:
Una pila és una estructura de dades ordenada pertanyent a Java Collection Framework. En aquesta col·lecció, els elements només s’afegeixen i s’eliminen d’un extrem. El final en què s’afegeixen i s’eliminen els elements s’anomena “Top of the Stack”.
Com que l'addició i la supressió es fan només en un extrem, el primer element afegit a la pila passa a ser l'últim element eliminat de la pila. Així, la pila s’anomena estructura de dades LIFO (Last-in, First-out).
=> Feu una ullada a la guia per a principiants de Java aquí
Què aprendreu:
- Col·lecció Java Stack
- Conclusió
Col·lecció Java Stack
A continuació es mostra una representació pictòrica de la pila.
Com es mostra a la seqüència de representació anterior, inicialment la pila està buida i la part superior de la pila es posa a -1. A continuació, iniciem una operació 'push' que s'utilitza per afegir un element a la pila.
com obrir fitxers .torrent
Així doncs, a la segona representació, empenyem l'element 10. En aquest punt, la part superior s'incrementa. Tornem a empènyer l'element 20 a la pila incrementant així la part superior.
A la darrera representació, iniciem una operació 'pop'. Aquesta operació s'utilitza per eliminar un element de la pila. L'operació pop elimina un element que apunta actualment a 'Top'.
Una estructura de dades de pila admet les operacions següents:
- Empenta: Afegeix un element a la pila. Com a resultat, el valor de la part superior s’incrementa.
- pop: S'elimina un element de la pila. Després de l'operació pop, el valor de la part superior es disminueix.
- Ullada: Aquesta operació s'utilitza per buscar o cercar un element. El valor de la part superior no es modifica.
La part superior de la pila que s’utilitza com a final per afegir / eliminar elements de la pila també pot tenir diversos valors en un instant concret. Si la mida de la pila és N, la part superior de la pila tindrà els següents valors en diferents condicions, en funció de l'estat en què es trobi la pila.
| Estat de la pila | Valor màxim |
|---|---|
| Pila buida | -1 |
| Un element a la pila | 0 |
| Pila plena | N-1 |
| Desbordament (elements> N) | N |
Classe de pila a Java
Java Collection Framework proporciona una classe anomenada 'Stack'. Aquesta classe Stack amplia la classe Vector i implementa la funcionalitat de l'estructura de dades Stack.
El diagrama següent mostra la jerarquia de la classe Stack.
Com es mostra al diagrama anterior, la classe Stack hereta la classe Vector que al seu torn implementa la interfície de la interfície de llista de la col·lecció.
La classe Stack forma part del paquet java.util. Per incloure la classe Stack al programa, podem utilitzar la declaració d’importació de la següent manera.
import java.util.*; o bé
import java.util.Stack; Creeu una pila a Java
Un cop importem la classe Stack, podem crear un objecte Stack com es mostra a continuació:
Stack mystack = new Stack(); També podem crear un tipus genèric d'objecte de classe Stack de la següent manera:
Stack myStack = new Stack; Aquí data_type pot ser qualsevol tipus de dades vàlid a Java.
Per exemple ,podem crear els següents objectes de classe Stack.
Stack stack_obj = new Stack(); Stack str_stack = new Stack(); Stack API Methods a Java
La classe Stack proporciona mètodes per afegir, eliminar i cercar dades a la Stack. També proporciona un mètode per comprovar si la pila està buida. Discutirem aquests mètodes a la secció següent.
Operació Push Push
L'operació d'empenta s'utilitza per empènyer o afegir elements a la pila. Una vegada que creem una instància de pila, podem utilitzar l’operació push per afegir a la pila els elements del tipus d’objecte de pila.
El següent fragment de codi s'utilitza per inicialitzar una pila sencera amb els valors.
Stack myStack = new Stack(); myStack.push(10); myStack.push(15); myStack.push(20); A continuació es mostra la pila inicial obtinguda com a resultat de l’execució anterior del codi:
Si realitzem una altra operació push () com es mostra a continuació,
push(25); La pila resultant serà:
Operació Stack Pop
Podem eliminar l'element de la pila mitjançant l'operació 'pop'. Actualment, l'element assenyalat per la part superior apareix de la pila.
La següent peça de codi ho aconsegueix.
Stack intStack = new Stack(); intStack.push(100); intStack.push(200); int val = intStack.pop(); La variable val contindrà el valor 200 ja que va ser l'últim element empès a la pila.
La representació de la pila per a l'operació push i pop és la següent:
Operació Stack Peek
L’operació d’observació torna la part superior de la pila sense treure l’element. A l'exemple de pila anterior, 'intStack.peek ()' retornarà 200.
La pila és operació buida
L'operació isEmpty () de la classe Stack comprova si l'objecte de la pila està buit. Es torna cert si la pila no inclou cap element, sinó que es torna fals.
Operació de cerca de pila
Podem buscar un element a la pila mitjançant l’operació search (). L'operació search () retorna l'índex de l'element que es busca. Aquest índex es compta des de la part superior de la pila.
Stack intStack = new Stack (); intStack.push (100); intStack.push (200); int index = inStack.search(100); //index will have the value 2.Mida de la pila
La mida de l'objecte Stack ve donada per java.util.Stack.size () mètode. Retorna el nombre total d'elements a la pila.
L'exemple següent imprimeix la mida de la pila.
Stack myStack = new Stack(); myStack.push(100); myStack.push(200); myStack.push(300); System.out.println('Stack size:' + myStack.size()); //Stack size: 3 Imprimir / Iterar elements de la pila
Podem declarar un iterador de la pila i després recórrer tota la pila mitjançant aquest iterador. D’aquesta manera podem visitar i imprimir cada element de pila un per un.
El programa següent mostra la manera d’iterar Stack mitjançant un iterador.
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() + ' '); } } }Sortida:
Elements de la pila:
PUNE MUMBAI NASHIK
Apilar utilitzant Java 8
També podem imprimir o recórrer els elements de la pila mitjançant funcions de Java 8, com ara les API de flux, forEach i forEachRemaining.
El programa següent mostra l'ús de les construccions de Java 8 per recórrer la pila.
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 + ' '); }); } } Sortida:
Apilar elements amb Java 8 per a cadascun:
PUNE MUMBAI NASHIK
Apilar elements amb Java 8 forEachRemaining:
PUNE MUMBAI NASHIK
Implementació de pila a Java
El programa següent implementa la pila detallada que demostra les diverses operacions de la pila.
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()); } } Sortida:
Pila inicial: ()
La pila és buida? : cert
Pila després de l'operació d'empenta: (10, 20, 30, 40)
Element aparegut: 40
Pila després de l'operació Pop: (10, 20, 30)
Element 10 que es troba a la posició: 3
Stack està buit? : fals
Stack To Array a Java
L'estructura de dades de la pila es pot convertir a una matriu mitjançant el mètode 'toArray ()' de la classe Stack.
El programa següent mostra aquesta conversió.
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 Sortida:
El contingut de la pila: (PUNE, MUMBAI, NASHIK)
El contingut de la matriu:
PUNE MUMBAI NASHIK
Implementació de pila a Java mitjançant Array
La pila es pot implementar mitjançant una matriu. Totes les operacions de pila es realitzen mitjançant una matriu.
El programa següent mostra la implementació de la pila mitjançant una matriu.
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(); } } Sortida:
Pila inicial buida: cert
Després de l'operació Push ...
Impressió d’elements de pila ...
40 30 20 10
S'ha publicat l'element: 40
S'ha publicat l'element: 30
Després de l'operació Pop ...
Impressió d’elements de pila ...
octubre 20
Implementació de la pila mitjançant la llista enllaçada
La pila també es pot implementar mitjançant una llista enllaçada tal com ho hem fet amb matrius. Un dels avantatges d’utilitzar una llista enllaçada per implementar la pila és que pot créixer o reduir-se dinàmicament. No cal que tinguem una restricció de mida màxima com a les matrius.
El programa següent implementa una llista enllaçada per realitzar operacions de pila.
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()); } } Sortida:
Elements de la pila:
1-> 3-> 5-> 7-> 9->
Pila superior: 1
Esclateu dos elements
Elements de la pila:
5-> 7-> 9->
Nou top Stack: 5
Preguntes freqüents
P # 1) Què són les piles a Java?
Resposta: Una pila és una estructura de dades LIFO (Last in, First out) per emmagatzemar elements. Els elements de la pila s’afegeixen o s’eliminen de la pila des d’un extrem anomenat Part superior de la pila.
L’addició d’un element a la pila es fa mitjançant l’operació Push. La supressió d'elements es fa mitjançant l'operació pop. A Java, s’implementa una pila mitjançant la classe Stack.
Q # 2) Stack és una col·lecció a Java?
Resposta: Sí. La pila és una col·lecció heretada a Java que està disponible des de l'API de col·lecció a partir de Java 1.0. Stack hereta la classe Vector de la interfície de la llista.
P # 3) Stack és una interfície?
Resposta: La pila d’interfícies és una interfície que descriu l’estructura d’entrada i sortida anterior i s’utilitza per emmagatzemar l’estat dels problemes recursius.
P # 4) Per a què serveixen les piles?
Resposta: A continuació es mostren les principals aplicacions de la pila:
- Avaluació i conversions d’expressions: la pila s’utilitza per convertir expressions en postfix, infix i prefix. També s’utilitza per avaluar aquestes expressions.
- La pila també s'utilitza per analitzar arbres de sintaxi.
- La pila s’utilitza per comprovar parèntesis en una expressió.
- La pila s’utilitza per resoldre problemes de retrocés.
- Les trucades de funcions s’avaluen mitjançant piles.
P # 5) Quins són els avantatges de la pila?
Resposta: Les variables emmagatzemades a la pila es destrueixen automàticament quan es retornen. Les piles són una millor opció quan s’assigna i es reparteix la memòria. Les piles també netegen la memòria. A part, les piles es poden utilitzar eficaçment per avaluar expressions i analitzar-les.
Conclusió
Això completa el nostre tutorial sobre piles a Java. La classe Stack és una part de l’API de col·lecció i admet operacions push, pop, peek i search. Els elements s’afegeixen o s’eliminen a / de la pila només en un extrem. Aquest extrem s’anomena part superior de la pila.
En aquest tutorial, hem vist tots els mètodes compatibles amb la classe de pila. També hem implementat la pila mitjançant matrius i llistes enllaçades.
Continuarem amb altres classes de recollida en els nostres tutorials posteriors.
=> Llegiu la sèrie de formació Java fàcil
Lectura recomanada
- Tutorial de reflexió de Java amb exemples
- Tutorial de classe de Java Scanner amb exemples
- Què és un Java HashTable: implementació i exemple de HashTable
- Què és Java Vector | Tutorial de Java Vector Class amb exemples
- Tutorial de classe Java Array: classe java.util.Arrays amb exemples
- Conceptes bàsics de Java: sintaxi de Java, Java Class i conceptes bàsics de Java
- LinkedHashMap a Java: exemple i implementació de LinkedHashMap
- Tutorial Java SWING: Gestió de contenidors, components i esdeveniments
