DAS5102 - Pilhas

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.

Implementando uma pilha usando arrays

A idEia 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.

Abaixo é apresentada a implementação da pilha descrita acima para acomodar variáveis do tipo float.

 1#define SIZE	5
 2
 3struct pilha
 4{
 5	int vet[SIZE];
 6	int topo;
 7};
 8
 9typedef struct pilha Pilha;
10
11Pilha* pilha_criar()
12{
13	Pilha* p = malloc (sizeof(Pilha));
14	p->topo = 0;
15	return p;
16}
17
18int pilha_vazia(Pilha* p)
19{
20	return (p->topo == 0);
21}
22
23int pilha_cheia(Pilha* p)
24{
25	return (p->topo == SIZE);
26}
27
28int pilha_inserir(Pilha* p, int valor)
29{
30	if (pilha_cheia(p))
31	{
32		return 0;
33	}
34	p->vet[p->topo] = valor;
35	p->topo++;
36	return 1;
37}
38
39int pilha_retira(Pilha* p)
40{
41	if (pilha_vazia(p))
42	{
43		return 0;
44	}
45	p->topo--;
46	return p->vet[p->topo];
47}

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.

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.

 1struct no
 2{
 3	int info;
 4	struct no* proximo;
 5};
 6
 7typedef struct no No;
 8
 9struct pilha
10{
11	No* topo;
12	int tamanho;
13};
14
15typedef struct pilha Pilha;

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.

Exercícios

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 1 em caso afirmativo, e 0 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. Crie uma implementação estática da pilha, tal como a vista anteriormente, para acomodar variáveis do tipo int.

5. Considere a representação pictográfica de uma estrutura de pilha dinâmica dada abaixo:

Explique o que há de errado com esta estrutura. Porque ela não funcionaria para a implementação de uma pilha?

Roteiro

Objetivos

Revisar os conceitos de pilhas vistos em sala de aula.

Descrição

Crie uma TAD que Implemente uma Pilha dinâmica.

• Crie funções para:
  • 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.
  • 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 1 em caso afirmativo, e 0 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 “)”;