Pilha Java

Pilha em Java geralmente significa a classe do Collection Framework que implementa a interface List. Ele funciona com base no princípio da estrutura de dados Stack, que é usada para organizar um dos tipos de memória. Também pode ser a parte da memória para manter os dados. Neste artigo, prestaremos atenção primeiro à classe Stack , consideraremos seus métodos e daremos exemplos. Mas também falaremos sobre uma estrutura de dados como Stack e para que ela é usada.

O que é Estrutura de Dados Stack

Em primeiro lugar, vamos dar uma olhada rápida no que é uma estrutura de dados de pilha. É uma estrutura de dados linear baseada no princípio Last-in-First-out (LIFO). É uma espécie de anti-fila. Imagine um baralho de cartas ou uma pilha de livros em uma caixa. O livro que você colocou primeiro na pilha está no fundo, e o primeiro que tiraremos da caixa é o livro que estava no topo - ou seja, aquele que entrou na caixa por último. Aqui está uma imagem gif para demonstrar este princípio. O que está acontecendo aqui? Temos um frasco no qual apenas uma bola pode atingir por vez. A primeira no frasco é uma bola laranja, depois roxa e finalmente verde (peço desculpas a quem conhece os nomes mais precisos dessas cores). Porém para extrair uma bola laranja do nosso frasco-stack, precisamos primeiro extrair a bola que chegou lá por último (a verde), depois aquela que foi a penúltima (mas na hora da extração é a última um). A estrutura de dados da pilha em Java ou em qualquer outro lugar na programação tem as duas operações mais importantes, push e pop . A operação push insere um elemento na pilha e a operação pop remove um elemento do topo da pilha.

Para que serve a estrutura de dados Stack?

Um dos usos mais importantes da pilha é organizar chamadas de sub-rotina. O ponto de chamada na pilha armazena o endereço de retorno da sub-rotina depois que ela termina (e possivelmente os parâmetros passados). Com cada chamada aninhada (incluindo recursiva) de sub-rotinas, novos endereços de retorno são adicionados à pilha. A cada operação de retorno da sub-rotina (return), o endereço de retorno é removido da pilha e o controle é transferido para ele. Esta aplicação é tão importante para a programação que, na maioria dos processadores, a pilha de retorno é implementada em hardware no conjunto de instruções. No entanto, em outros casos, a pilha deve ser modelada em estruturas de dados mais gerais.

Classe de pilha Java da estrutura de coleção

Em Java Stack Class é uma classe do framework Collection que implementa a interface List e estende a classe Vector. Também implementa as interfaces Collection, Iterable, Cloneable, Serializable. Como você provavelmente já adivinhou, esta classe representa a pilha LIFO de objetos. Aqui está a chamada ao construtor da classe Stack , ou seja, a criação de um objeto desta classe.

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

Onde E é o tipo de Objeto.

Métodos de Pilha Java

Essa classe possui apenas um construtor padrão e todos os métodos da classe Vector . Além disso, Stack tem seus próprios 5 métodos:

• boolean empty() o método verifica se a pilha está vazia ou não. Retorna true se a pilha estiver vazia, false se não estiver.

• Object peek() o método retorna o elemento que está no topo da pilha.

• Object pop() o método retorna o elemento que está no topo da pilha e o remove.

• Object push(Object element) o método adiciona o elemento especificado ao topo da pilha.

• int search(Object element) o método procura na pilha o elemento especificado. Se o elemento desejado for encontrado, sua “distância” do topo (número de série) é retornada. Se o elemento não for encontrado, -1 será retornado.

Exemplo de código de pilha

Vamos criar um exemplo de programa que funcione como a imagem gif acima. Colocaremos três “bolas”, laranja, roxa e verde, na pilha. Vamos verificar se a pilha está vazia. Então, vamos extrair as bolas da pilha até que a pilha fique vazia.

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

Aqui está a saída deste programa: Como Stack é herdado de Vector Class e implementa a interface List , Stack , além das clássicas operações push e pop para essa estrutura de dados para adicionar e extrair elementos, também possui um padrão para operações add() e remove() de estrutura de lista. Em nosso exemplo, adicionar elementos pode ser implementado da mesma forma usando o método add() . No entanto, você pode extrair usando remove() apenas com um elemento especificado, o que não faz sentido para a estrutura de dados da pilha.

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

O resultado do trabalho do programa, é claro, será exatamente o mesmo.

E quanto à sua própria implementação de pilha?

Você pode criar sua própria estrutura de dados de pilha em Java usando arrays ou classes de lista encadeada. No primeiro caso, um array contínuo de células é alocado para armazenar valores na memória, que são utilizados conforme a necessidade. Na segunda, para cada elemento da pilha, é ordenado um bloco de memória, suficiente para armazenar o valor e as referências aos elementos anteriores e posteriores da pilha. A implementação baseada em array é mais simples, mais eficiente e mais eficiente em termos de memória, mas requer um conhecimento prévio do limite de tamanho da pilha e pode levar a erros difíceis de encontrar. A implementação baseada em lista é mais robusta, mas menos eficiente. Vamos fazer uma implementação simples baseada em array da pilha. Ele incluirá funções.

• push — um método que garantirá a adição de um elemento (na posição superior)

• pop — um método que fornecerá a remoção de um elemento (da posição superior)

• readTop — um método que retornará o valor do elemento que está na posição superior

• sEmpty — um método que verificará se a pilha está vazia

• isFull — um método que verificará se nosso array no qual armazenamos a pilha não está cheio

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

Agora vamos implementar um exemplo com três bolas baseadas em nossa pilha:

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

}

A saída está aqui: Se você olhar de perto, a variável superior realmente contém o índice do último elemento e a referência ao objeto permanece na matriz. Portanto, esta implementação precisa de algumas melhorias. Pense na maneira mais fácil de fazer isso.

Devemos usar o Java Stack?

Na verdade, o Java Stack , como seu pai Vector , é uma classe herdada. Em vez disso, a classe ArrayList geralmente é usada. ArrayList não é sincronizado enquanto Vector é sincronizado. Isso significa que com Vector apenas um thread por vez pode acessar o código, enquanto ArrayList pode trabalhar com vários threads. Além disso, ArrayList é mais eficiente e rápido. Portanto, você provavelmente verá essa classe apenas no código legado. Mas a estrutura de dados Stack é usada na programação com muita frequência.