Pilhas

Afluentes: Estrutura de Dados

Vídeo aulas

• Pilha Estática em Java
• Pilha Dinâmica em Java

Introdução

A estrutura de dados Pilha emula a forma de organização de objetos intuitiva que é utilizada diariamente nos mais diversos contextos da vida humana. Containeres são empilhados e desempilhados diariamente em todos os portos do mundo, processos nas mesas de advogados, produtos em supermercados são apenas alguns dos milhares de exemplos da utilização de pilhas.

Essencialmente, Pilha é uma estrutura de dados amplamente utilizada em diversos escopos computacionais. Por exemplo, toda função em um programa de computador possui uma pilha onde são alocadas as variáveis estáticas pertinentes ao escopo da função e endereço de retorno para o ponto de invocação da função, dentre outras informações.

O funcionamento de uma pilha é simples e intuitivo: Itens são empilhados um a um, e sempre o último elemento sobre todos os que já se encontram na pilha. Apenas o último elemento empilhado pode ser removido da pilha, pois se tentarmos remover um elemento, digamos, que se encontra no meio da pilha, corremos o risco de desestruturar toda a estrutura (imagine remover uma latinha de atum que se encontra debaixo de outras 200!). A figura abaixo exemplifica uma pilha de diversos tamanhos. Ela serve para nos informar de duas características muito importantes a respeito de pilhas: a) seu topo; e b) seu tamanho.

Em um ambiente computacional utilizamos pilhas para agrupar dados que devem se comportar (armazenados e acessados) tal como lidamos com pilhas no mundo real. Para tal, as seguintes operações básicas são previstas:

• criar uma pilha vazia;
• inserir um novo elemento;
• retirar o elemento do topo da pilha;
• verificar qual é o elemento no topo da pilha;
• verificar se a pilha está vazia.

Existem diversas formas de se programar a estrutura de dados Pilha em um programa de computador. Dentre elas as mais utilizadas são: a)implementação via um array estático; e b) implementação dinâmica utilizando listas encadeadas.

Pilha Estática: implementando uma pilha usando arrays

A idéia que permeia a programação de pilhas utilizando arrays (método estático) é criar um array estático de N posições e uma variável topo que aponta para o topo da pilha. Alternativamente pode-se criar uma estrutura de dados para acomodar ambas as variáveis. Elementos devem ser alocados (empilhados) a partir da posição inicial (vet[0]) até potencialmente que o tamanho máximo do array seja atingido. Elementos podem ser removidos (desempilhados) desde que a pilha não esteja vazia por meio da remoção do ultimo elemento alocado (elemento que se encontra na posição topo). Durante todas as interações com a pilha é imprescindível que a variável topo seja mantida atualizada.

 1public class PilhaEstatica {
 2	String vet[];
 3	int topo;
 4	
 5	PilhaEstatica(int tamanho) {	// Criar uma pilha vazia
 6		vet = new String[tamanho];	// Cria a pilha com um tamanho
 7		topo = 0;					// Topo 0 significa pilha vazia
 8	}
 9	
10	boolean vazia() {				// Verifica se a pilha está vazia 
11		return topo == 0;			// Se topo for 0, pilha está vazia
12	}
13	
14	boolean cheia() {				// Verifica se a pilha está cheia
15		return vet.length == topo;	// Se o topo é igual ao tamanho da pilha
16	}
17
18	boolean inserir(String valor) {	// Inserir um novo elemento na pilha
19		if (cheia()) {				// Se a pilha está cheia retorna falso
20			return false;
21		}
22		vet[topo] = valor;			// Coloca a informação no topo
23		topo++;						// O topo agora é mais em cima da pilha
24		return true;				// Se conseguiu excluir, retorna verdadeiro
25	}
26
27	String retirar() {				// Retira o elemento do topo da pilha
28		if (vazia()) {				// Se a pilha está vazia, retorna nulo
29			return null;					
30		}
31		topo--;						// Agora o topo vai descer pra tirar o elemento do topo
32		return vet[topo];			// Retorna o elemento que estava no topo
33	}
34}

Como pode-se imaginar, a implementação estática de pilhas impõe várias restrições no que se refere a capacidade de crescimento da estrutura de dados e com relação ao tipo de dados a ser alocado. Adicionalmente, a implementação de pilhas utilizando arrays impõe uma restrição adicional referente ao fato de que toda a estrutura deve ser alocada sequencialmente na memória. Uma forma de lidar com tais limitações, ou seja, flexibilizar esta estrutura de dados é utilizar listas encadeadas em sua implementação.

Atividade

Altere a implementação de pilha estática acima para que a informação seja do tipo int e faça um programa uando pilhas estáticas com o seguinte comportamento:

• Enquanto a pilha não está cheia, você pode entrar com números. Quando a pilha estiver cheia, informar o usuário.
• Você pode retirar um número da pilha. Para isso, deve entrar com um número e se ele for encontrado na pilha, retira-o, os outros devem permanecer.
  • Observação 1: você não pode retirar elementos que estão no meio diretamente, tem que ir retirando os elementos de cima.
  • Observação 2: os elementos que foram retirados de cima, do número entrado pelo usuário, devem ser devolvidos, agora sem o elemento retirado. Pense que você tem 5 caixas empilhadas e você quer pegar/retirar a terceira de baixo pra cima. Você deve ir pegando as de cima e ir empilhando em outro lugar e, depois de conseguir sua caixa, deve devolver as outras para essa pilha.

Pilha Dinâmica: Implementando uma pilha usando estruturas dinâmicas

Essencialmente a implementação dinâmica de pilhas pode ser feita de diversas maneiras. Neste contexto, estudaremos a implementação dinâmica usando listas encadeadas. Note que, essencialmente, o funcionamento e os mesmos métodos relacionados as pilhas implementadas via arrays serão exatamente os mesmos a serem implementados em pilhas dinâmicas. O único ponto de divergência entre tais implementações reside no fato de que os elementos da pilha serão alocados e gerenciados de maneiras diversas. Em suma, a interface da estrutura de dados, independentemente de como a mesma é implementada, permanece a mesma.

Na implementação dinâmica, duas estruturas de dados são necessárias. Uma para representar as células individuais que compõem a pilha e uma estrutura de cabeçalho que contem a referência para o primeiro elemento da pilha, referência para seu topo e facultativamente o número de elementos existentes na pilha.

1public class No {
2	Object info;
3	No proximo;
4}

Veja que a classe No tem a informacao sendo do tipo Object. Isso permite que possamos colocar qualquer tipo de objeto alí. Para usarmos a informação, precisaremos usar um type casting que veremos mais a frente.

1public class Pilha {
2	No topo;
3	int tamanho;
4}

A regra de funcionamento da pilha é clara, elementos só podem ser inseridos (empilhados) sobre o último elemento já existente na pilha. Isso é feito da seguinte maneira:

novo_no->proximo = topo
topo = novo_no
tamanho = tamanho + 1

A remoção de elementos da pilha é feita da seguinte maneira:

no = topo
topo = topo->proximo 
tamanho = tamanho - 1
retorna no

Para verificar qual o último elemento empilhado, basta que retornemos uma referência para topo.

Para checarmos o tamanho da pilha basta acessarmos o campo tamanho da estrutura da pilha.

Implementação da pilha dinâmica

Assim, a nossa implementação fica da seguinte forma:

 1public class PilhaDinamica {
 2	No topo;
 3	int tamanho;
 4	
 5	PilhaDinamica() { 				// Criar uma pilha vazia. Seu tamanho é variável
 6		tamanho = 0;				// A pilha está vazia, o tamanho inicial é 0
 7		topo = null;				// Topo null significa significa que ninguém está no topo
 8	}
 9	
10	boolean vazia() {				// Verifica se a pilha está vazia. Não precisaremos ver se está cheia
11		return topo == null;		// Se topo for NULO, pilha está vazia
12	}
13
14	void inserir(Object info) {		// Inserir um novo elemento na pilha
15		No no = new No();			// Criamos um novo nó
16		no.info = info;				// A informação vem por parâmetro
17		no.proximo = topo;			// O próximo é o último elemento que era o topo
18		topo = no;					// O topo é agora o nó atual
19		tamanho++;					// O tamanho da pilha é incrementado
20	}
21
22	Object retirar() {				// Retira o elemento do topo da pilha
23		if (vazia()) {				// Se a pilha está vazia, retorna nulo
24			return null;			// Retorna nulo
25		}
26		Object info = topo.info;	// Salva a informação do nó que está no topo
27		topo = topo.proximo;		// agora o topo é o elemento que está em baixo do topo atual
28		tamanho--;					// Decrementa o tamanho da lista
29		return info;				// Retorna a informação do nó retirado
30	}
31}

Veja que:

• Estamos usando a classe Nó, apresentada mais acima;
• Não precisamos mais retornar se a pilha está cheia. Ela é dinâmica e seu tamanho varia;
• A operação de inserir não precisa mais retornar verdadeiro ou falso porque a pilha não estará cheia (não estamos pensando no estouro da memória aqui);
• Retirar vai retornar um Object, ou seja, qualquer tipo de objeto.

Usando a pilha dinâmica

 1public class Programa {
 2	public static void main(String [] argumentos) {
 3		PilhaDinamica pilha = new PilhaDinamica();	// Criamos uma pilha
 4		pilha.inserir("A");							// Inserimos elementos String
 5		pilha.inserir("B");							
 6		pilha.inserir("C");
 7		while (!pilha.vazia()) {					// Enquanto a pilha não estiver vazia 
 8			System.out.println(						// Mostra no console
 9					(String) pilha.retirar() +		// retira o elemento do topo e faz type casting pra String
10					" - " +							// Só um tracinho pra não ficar junto
11					pilha.tamanho);					// retorna o tamanho da pilha
12		}
13	}
14}

Resultado:

C - 2
B - 1
A - 0

Veja que colocamos os elementos na ordem A, B e C. Como C foi o último elemento a ser colocado, ele está no topo, então é o primeiro a ser retirado.

Na linha 9, vemos que ao retornar a informação, colocamos um (String) antes. Isso se chama type casting. Como definimos que nossa informação seria qualquer tipo de Object, o java aceitou, pois String é um objeto. Contudo, para usarmos essa String, precisamos dizer para o programa que o objeto é uma String. Se fossemos colocar a informação em uma variável, ficaria assim:

String nome = (Object) pilha.retirar();

Atividades

1. Crie uma função que recebe como argumento uma string contendo parênteses encadeados:

Ex: “(((()))(((((()))))((((()))))))”

Utilize uma pilha para decidir se o número de parênteses encadeados está certo ou errado. A função dever retornar verdadeiro em caso afirmativo, e falso em caso negativo. A função deve ignorar qualquer outro caractere existente na string que não seja "(" ou ")". Um parêntese encadeado significa que para cada "(" deve existir um ")".

2. Com relação a pilhas estáticas (que utilizam um array) o que poderíamos fazer para remediar uma situação em que durante a execução do programa descobrimos que precisamos de uma pilha maior do que a que foi alocada inicialmente (estaticamente)?

3. Qual a importância do campo topo, na estrutura pilha estática apresentada?

4. Considere a representação pictográfica de uma estrutura de pilha dinâmica dada abaixo e explique o que há de errado com esta estrutura. Porque ela não funcionaria para a implementação de uma pilha?

Resolução

Atividade 1

 1public class Atividade1 {
 2    public static boolean verificaParenteses(String entrada) {
 3        Pilha pilha = new Pilha();                          // Cria uma pilha (dinâmica)
 4        for (int i = 0; i < entrada.length(); i++) {        // Para cada caracter da entrada
 5            if (entrada.charAt(i) == '(') {                 // Se o caracter for (
 6                pilha.inserir("(");                         //      Insere ele na pilha
 7            } else if (entrada.charAt(i) == ')') {          // Senão
 8                if (pilha.retirar() == null) {              //   Retira ele da pilha e se der erro
 9                    return false;                           //   Retorna falso porque não tem nada na pilha
10                }
11            }
12        }
13        if (!pilha.vazia()) {                               // Se a pilha não está fazia
14            return false;                                   //   Retorna falso porque ainda tem coisa na pilha
15        }
16        return true;                                        // Se tudo deu certo, retorna verdadeiro
17    }
18
19    public static void main(String [] args) {
20        boolean valida = verificaParenteses("(((()))(((((()))))((((()))))))");
21        if (valida) {
22            System.out.println("Parenteses válidos...");
23        } else {
24            System.out.println("Parenteses inválidos...");
25        }
26    }
27}

Atividade 2

A função (método) abaixo deve ser colocada dentro da classe PilhaEstatica

	// ...
	boolean aumentaTamanho(int tamanho) {
		if (tamanho <= vet.length) {			// Se o novo tamanho é menor ou igual ao atual
			return false;						//    Retorna falso
		}
		String vet2[] = new String[tamanho];	// Cria um novo vetor com o novo tamanho
		for (int i = 0; i < vet.length; i++) {	// Para cada elemento do vetor antigo
			vet2[i] = vet[i];					//   copia ele na posição relativa do novo vetor
		}
		vet = vet2;								// O vetor antigo vai apontar para o novo vetor
		return true;							// Retorna verdadeiro
	}
	// ...

Coloquei a seguir um exemplo de aplicação usando a pilha estática com o método aumentaTamanho. É bastante simples, mas já dá para perceber o potencial da função. Nesse programa, leio strings do teclado (pode ser nomes de pessoas, estados, etc.) em modo texto (uso o Scanner pra isso). Essas strings vou colocando na pilha uma a uma. Quando percebo que a pilha está cheia, antes de inserir a entrada de dados nela, aumento com mais 5 espaços e depois faço a inserção da entrada. Depois, quando eu digitar sair entro em um novo loop que, enquando a pilha não estiver vazia, retiro um elemento e mostro na tela.

 1import java.util.Scanner;
 2
 3public class Atividade2 {
 4    public static void main(String [] args) {
 5        Scanner scanner = new Scanner(System.in);                   // Scanner para ler teclado modo texto
 6        PilhaEstatica pilha = new PilhaEstatica(5);                 // Cria uma instância de PilhaEstatica
 7        System.out.println("Tamanho: " + pilha.vet.length);         // Mostra o tamanho atual da Pilha
 8        String entrada = "";                                        // Cria uma string para receber a entrada
 9        while (entrada.compareTo("sair") != 0) {                    // Enquando a entrada não for 'sair'
10            System.out.print("entrada: ");                          // Mostra o texto 'entrada: '
11            entrada = scanner.nextLine();                           // Usuário deve digitar string e ENTER
12            if (pilha.cheia()) {                                    // Se a pilha estiver cheia
13                pilha.aumentaTamanho(pilha.vet.length + 5);         // Aumenta o tamanho para mais 5
14                System.out.println("Tamanho: " + pilha.vet.length); // Mostra o novo tamanho da Pilha
15            }
16            pilha.inserir(entrada);                                 // Inserir a entrada do usuário na pilha
17        }
18        while (!pilha.vazia()) {                                    // Enquanto a pilha não estiver vazia
19            System.out.println("Retirando: " + pilha.retirar());    // Retira o elemento do topo e mostra
20        }
21        scanner.close();                                            // Fecha a leitura modo texto
22    }
23}

Atividade 3

O campo topo é importante para indicar qual o item da pilha deve ser retirado ou em cima de onde o próximo elemento deve ser colocado. Sem esse elemento, não temos como saber de onde tirar ou onde colocar elementos na pilha.

Atividade 4

A pilha está invertida e não temos o elemento topo. Mesmo que coloquemos um ponteiro para o elemento mais de cima, não temos como ir para o próximo elemento em baixo, pois do elemento do topo não há nada apontando para o próximo (elemento de baixo), e assim acontece com todos os elementos dessa estrutura.