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.
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:
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:
GO TO FULL VERSION