Pila de Java

Stack en Java generalmente significa la clase de Collection Framework que implementa la interfaz List. Funciona según el principio de la estructura de datos Stack, que se utiliza para organizar uno de los tipos de memoria. También podría ser parte de la memoria para guardar datos. En este artículo, prestaremos atención en primer lugar a la clase Stack , consideraremos sus métodos y daremos ejemplos. Pero también hablaremos sobre una estructura de datos como Stack y para qué se utiliza.

¿Qué es la estructura de datos de pila?

En primer lugar, echemos un vistazo rápido a lo que es una estructura de datos de pila. Es una estructura de datos lineal que se basa en el principio de último en entrar, primero en salir (LIFO). Es una especie de anti-cola. Imagina una baraja de cartas o una pila de libros en una caja. El libro que puso en la pila primero está en la parte inferior, y el primero que sacaremos de la caja es el libro que estaba en la parte superior, es decir, el último que entró en la caja. Aquí hay una imagen gif para demostrar este principio. ¿Que está pasando aqui? Tenemos un matraz en el que solo puede golpear una bola a la vez. La primera en el matraz es una bola naranja, luego morada y finalmente verde (pido disculpas a los que conocen los nombres más precisos de estos colores). Sin embargo, para extraer una bola naranja de nuestra pila de matraces, necesitamos extraer primero la bola que llegó en último lugar (la verde), luego la que fue la penúltima (pero en el momento de la extracción es la última). uno). La estructura de datos de pila en Java o en cualquier otra parte de la programación tiene las dos operaciones más importantes, empujar y sacar . La operación de inserción inserta un elemento en la pila y la operación de extracción elimina un elemento de la parte superior de la pila.

¿Para qué sirve la estructura de datos Stack?

Uno de los usos más importantes de la pila es organizar llamadas a subrutinas. El punto de llamada en la pila almacena la dirección de retorno de la subrutina después de que finaliza (y posiblemente los parámetros pasados). Con cada llamada anidada (incluida la recursiva) de subrutinas, se agregan nuevas direcciones de retorno a la pila. Con cada operación de retorno de la subrutina (retorno), la dirección de retorno se elimina de la pila y se le transfiere el control. Esta aplicación es tan importante para la programación que en la mayoría de los procesadores, la pila de retorno se implementa en hardware en el conjunto de instrucciones. Sin embargo, en otros casos, la pila debe modelarse en estructuras de datos más generales.

Clase de pila de Java del marco de colección

En Java Stack Class es una clase del marco Collection que implementa la interfaz List y amplía la clase Vector. También implementa las interfaces Collection, Iterable, Cloneable, Serializable. Como probablemente ya haya adivinado, esta clase representa la pila de objetos LIFO. Aquí está la llamada al constructor de la clase Stack , es decir, la creación de un objeto de esta clase.

Stack<E> stack = new Stack<E>();

Donde E es el tipo de Objeto.

Métodos de pila de Java

Esta clase tiene solo un constructor predeterminado y todos los métodos de la clase Vector . Además, Stack tiene sus propios 5 métodos:

• boolean empty() el método comprueba si la pila está vacía o no. Devuelve verdadero si la pila está vacía, falso en caso contrario.

• Object peek() el método devuelve el elemento que está en la parte superior de la pila.

• Object pop() el método devuelve el elemento que está en la parte superior de la pila y lo elimina.

• Empuje de objeto (elemento de objeto) el método agrega el elemento especificado a la parte superior de la pila.

• int search(Object element) el método busca en la pila el elemento especificado. Si se encuentra el elemento requerido, se devuelve su "distancia" desde la parte superior (número de serie). Si no se encuentra el elemento, se devuelve -1.

Ejemplo de código de pila

Vamos a crear un ejemplo de programa que funcione como la imagen gif de arriba. Pondremos tres “bolas”, naranja, morada y verde, en la pila. Revisemos la pila para ver si está vacía. Luego, extraeremos bolas de la pila hasta que la pila esté vacía.

import java.util.Stack;

public class myStackTest2 {

       public static void main(String[] args)
       {

           Stack myStack= new Stack<>();

           System.out.println("Is my stack empty? " + myStack.empty());
// pushing elements into stack
           myStack.push("Orange Ball");
           myStack.push("Violet Ball");
           myStack.push("Green Ball");

//prints elements of the stack
           System.out.println("Elements in Stack: " + myStack);
           System.out.println("Is my stack empty? " + myStack.empty());
           while (!myStack.isEmpty()) {
               myStack.pop();
               System.out.println("Elements in Stack: " + myStack);
               System.out.println("Is my stack empty? " + myStack.empty());
           }
       }
   }

Aquí está la salida de este programa: Dado que Stack se hereda de Vector Class e implementa la interfaz List , Stack , además de las clásicas operaciones push y pop para esta estructura de datos para agregar y extraer elementos, también tiene operaciones estándar para agregar () y eliminar () de estructura de lista. En nuestro ejemplo, la adición de elementos se puede implementar de la misma manera utilizando el método add() . Sin embargo, puede extraer usando remove() solo con un elemento especificado, lo que no tiene sentido para la estructura de datos de la pila.

import java.util.Stack;

public class myStackTest2 {

       public static void main(String[] args)
       {

           Stack myStack= new Stack<>();

           System.out.println("Is my stack empty? " + myStack.empty());
// pushing elements into stack
           myStack.add("Orange Ball");
           myStack.add("Violet Ball");
           myStack.add("Green Ball");

//prints elements of the stack
           System.out.println("Elements in Stack: " + myStack);
           System.out.println("Is my stack empty? " + myStack.empty());
           while (!myStack.isEmpty()) {
               myStack.pop();
               System.out.println("Elements in Stack: " + myStack);
               System.out.println("Is my stack empty? " + myStack.empty());
           }
       }
   }

El resultado del trabajo del programa, por supuesto, será exactamente el mismo.

¿Qué pasa con su propia implementación de Stack?

Puede crear su propia estructura de datos de pila en Java utilizando matrices o clases de listas vinculadas. En el primer caso, se asigna una matriz continua de celdas para almacenar valores en la memoria, que se utilizan según sea necesario. En el segundo, para cada elemento de la pila, se ordena un bloque de memoria, suficiente para almacenar el valor y las referencias a los elementos anterior y siguiente de la pila. La implementación basada en matrices es más simple, más eficiente y más eficiente en memoria, pero requiere un conocimiento previo del límite de tamaño de pila y puede generar errores difíciles de encontrar. La implementación basada en listas es más robusta pero menos eficiente. Hagamos una implementación simple de la pila basada en arreglos. Incluirá funciones.

• push — un método que asegurará la adición de un elemento (en la posición superior)

• pop — un método que proporcionará la eliminación de un elemento (desde la posición superior)

• readTop — un método que devolverá el valor del elemento que está en la posición superior

• sEmpty : un método que verificará si la pila está vacía

• isFull : un método que verificará si nuestra matriz en la que almacenamos la pila no está llena

import java.util.Arrays;

public class MyStack {

   private int maxSize;
   private String[] stackArray;
   private int top;

   public MyStack(int size) {
       this.maxSize = size;
       stackArray = new String[maxSize];
       top = -1;
   }

   public String push (String element) {
       return stackArray[++top] = element;

   }

   public String pop (String element) {

       if (isEmpty())
       {
           System.out.println("Underflow\nProgram Terminated");
           System.exit(-1);
       }

       System.out.println("Removing " + readTop());

       return stackArray[top--];

   }

   public String readTop() {
       return stackArray[top];

   }

   public boolean isEmpty() {
       return (top ==  -1);
   }

   public boolean isFull() {
       return (top == maxSize - 1);
   }

   public void printStack(){
       System.out.println(Arrays.toString(stackArray));
   }
}

Ahora implementemos un ejemplo con tres bolas basado en nuestra pila:

public class myStackTest {
   public static void main(String[] args) {
       MyStack  myStack = new MyStack(3);
       System.out.println("Is my stack empty? " + myStack.isEmpty());

       myStack.push("Orange Ball");
       myStack.push("Violet Ball");
       myStack.push("Green Ball");

      myStack.printStack();

       System.out.println("Is my stack empty? " + myStack.isEmpty());
       while (!myStack.isEmpty()) {
           myStack.pop(myStack.readTop());
           System.out.println("Is my stack empty? " + myStack.isEmpty());
       }
   }

}

La salida está aquí: Si observa detenidamente, la variable superior en realidad contiene el índice del último elemento y la referencia al objeto permanece en la matriz. Así que esta implementación necesita algunas mejoras. Piense en la manera más fácil de hacer esto.

¿Deberíamos usar Java Stack?

De hecho, Java Stack , como su padre Vector , es una clase heredada. En su lugar, se suele utilizar la clase ArrayList . ArrayList no está sincronizado mientras Vector está sincronizado. Eso significa que con Vector solo un subproceso a la vez puede acceder al código, mientras que ArrayList puede trabajar con varios subprocesos. Además, ArrayList es más eficiente y rápido. Por lo tanto, lo más probable es que vea esta clase solo en el código heredado. Pero la estructura de datos Stack se usa muy a menudo en la programación.