Pilhas
Pilhas
Uma pilha é um conjunto ordenado de itens, na qual novos item podem ser inseridos ou extraídos a partir de seu topo [1].
Uma pilha é um objeto dinâmico, constantemente mutável a partir da inserção ou extração de itens, sempre a partir de seu topo.
Quando um novo item é inserido na pilha, ele passa a ocupar seu topo. Neste caso, o topo é deslocado para cima de modo a corresponder ao novo primeiro elemento. Quando um item é removido, o topo da pilha é deslocado para baixo, para apontar ao novo primeiro elemento.
Uma pilha é também chamada de uma lista LIFO (Last In First Out), ou último que entra é o primeiro que sai.
Operações primitivas com pilhas
As duas operações primitivas para lidar com pilhas são [1]:
- push: Quando um elemento é inserido, ou empilhado, na pilha;
- pop: Quando um elemento é extraído, ou desempilhado, da pilha.
- Funções para operar com pilhas
Considere uma pilha s e um item i, a função
push(s, i);
insere o item na pilha.
Por sua vez a função
i = pop(s);
extrai um item do topo da pilha.
Outra operação que pode ser utilizada é verificar o item do topo da pilha, sem extrai-lo
i = top(s);
Não existe um limite máximo para o número de item em uma pilha. Entretanto, se uma pilha tiver um só elemento e ele for extraído, teremos a pilha vazia. Portanto, antes de utilizar o operador pop, precisamos verificar se a pilha não está vazia.
A operação
empty(s);
verifica se a pilha está vazia ou não.
Imlementação de pilhas em linguagem C
Antes de programar a solução de um problema usando pilhas, é preciso definir como a pilha será representada na linguagem de programação que estamos utilizando.
Na linguagem C, uma das maneiras de implememtar uma pilha é utilizando vetores. Contudo, pilhas e vetores são tipos de dados diferentes:
- Uma pilha é um conjunto ordenado de itens de tamanho é variável e, a princípio, não tem limite de tamanho.
- Um vetor, por sua vez, é um conjunto ordenado de itens, cujo tamanho é fixado na declaração do vetor.
Entretando, podemos utilizar um vetor para implementar uma pilha, desde que este vetor seja declarado suficientemente grande para conter a pilha que pretendemos implementar. Uma extremidade do vetor será o final fixo da pilha, enquanto o topo da pilha se desloca constantemente a medida que elementos são inseridos ou extraídos da pilha[1] [2].
Implementando pilhas com vetores
Uma implementação de uma pilha em C pode ser realizada a partir da declaração de uma estrutura com dois campos[3]:
- Um vetor de items para armazenar os elementos da pilha;
- Um inteiro que aponta para o topo da pilha dentro do vetor.
Declaração da pilha
Uma pilha de inteiros p pode ser declarada usando uma estrutura, com um campo indicando o topo e outro com um vetor que implementa a pilha:
#define TAM 100
struct pilha {
int topo;
int vetor[TAM];
} p;
- No programa principal, depois de declarada a variável de pilha o topo deve ser inicializado com zero.
Operação push
Insere item recebido como argumento no topo da pilha.
void push(struct pilha *p, int item)
{
p->vetor[p->topo] = item;
p->topo = p->topo + 1;
}
- Note que o campo p->vetor[] é um vetor que implementa a pilha e item é um parâmetro da função que recebe um item para ser inserido na pilha.
ou, de forma mais compacta
void push(struct pilha *p, int item)
{
p->vetor[p->topo++] = item;
}
- Esta operação faz p->vetor[p->topo] = item e depois incrementa topo.
Poderia também fazer um controle de erro para verificar se o tamanho da pilha são será ultrapassado:
void push(struct pilha *p, int item)
{
if (p->topo == TAM) {
fputs("Erro: overflow\n", stderr);
abort();
} else
p->vetor[p->topo++] = item;
}
Operação pop
Extrai e retorna item no topo da pilha.
int pop(struct pilha *p)
{
p->topo = p->topo -1;
return p->vetor[p->topo];
}
ou, de forma mais compacta
int pop(struct pilha *p)
{
return p->vetor[--p->topo];
}
- Esta operação decrementa topo e depois retorna p->vetor[topo].
A operação pop() somente pode ser utilizada se a pilha não estiver vazia. Para isto, verificar antes com a função empty().
Operação top
Retorna o item do topo da pilha, sem extraí-lo.
int top(struct pilha *p)
{
return p->vetor[p->topo - 1];
}
Operação empty
Verifica se a pilha está vazia.
int empty(struct pilha *p)
{
if (p->topo == 0)
return -1;
else
return 0;
}
Exemplos de aplicação de pilhas
Análise de expressões com chaves, colchetes e parêntesis
Um exemplo de aplicação de pilhas pode ser para verificar se uma expressão escrita com chaves, colchetes e parêntesis aninhados está bem escrita.
Por exemplo, a expressão:
{a * (b + c) * [d / (e + f)]} + g
está escrita corretamente, pois, para cada chave, colchete ou parêntesis abertos, há um correspondente que se fecha.
Para verificar se a expressão está correta, cada chave, colchete ou parêntesis que for aberto deve ser adicionado no topo da pilha. Quando encontrar um elemento que fecha, deve-se verificar a pilha. Se a pilha estiver vazia o elemento que fecha não terá um correspondente que abre e a expressão será inválida. Se a pilha não estiver vazia, deve-se extrair o elemento que está no topo e verificar se ele corresponde ao elemento que fecha. Se ocorrer coincidência, continua a análise, senão a expressão será inválida. Quando o final da expressão for alcançado, a pilha deve estar vazia. Senão, é sinal que foram abertos chaves, colchetes ou parêntesis sem correspondentes para fechar.
Backtracking
Outro exemplo de aplicação para pilhas pode ser para guardar um caminho de volta (backtracking), por exemplo, quando percorremos um labirinto. A cada decisão tomada, guardamos a informação na pilha. Caso chegarmos a um fim de caminho, podemos retornar recuperando a informação de volta do topo da pilha.
Notação polonesa ou posfixa
Normalmente as calculadoras comuns usam a notação infixa para expressar uma operação matemática, por exemplo:
A + B
ou
A * (B + C)
Algumas calculadoras, como as calculadoras HP, usam notação polonesa ou posfixa para expressar operações matemáticas, por exemplo:
A B +
ou
A B C + *
Uma calculadora HP tem uma pilha de tamanho 4 e funciona da seguinte maneira. Para efetuar a última expressão, primeiro insire A na pilha, depois B e depois C. Faço a operação de soma entre B e C e o resultado ocupa o topo da pilha. Faço a operação de multiplicação do topo da pilha com A.
Exercícios
- Implementar uma pilha em linguagem C;
- Implementar uma função que receba uma string, com uma expressão com chaves, colchetes e parêntesis, e que faça a análise da expressão, verificando se as chaves, colchetes e parêntesis aninhados estão escritos corretamente, usando pilhas.
- Exercício resolvido
- Por aluno Luiz Felipe
#include <stdio.h>
#include <string.h>
#define TAM 100
struct lifo{
int topo;
int pilha[TAM];
};
void push(struct lifo *p, int item){
if(p->topo == TAM){
fputs("Erro: overflow\n", stderr);
}else p->pilha[p->topo++] = item;
}
int empty(struct lifo *p){
if(p->topo == 0) return -1;
else return 0;
}
int pop(struct lifo *p){
if(empty(p)){
fputs("Nenhum elemento na pilha.\n", stdout);
}else return p->pilha[--p->topo];
}
int top(struct lifo *p){
if(empty(p)){
fputs("Nenhum elemento na pilha.\n", stdout);
}else return p->pilha[p->topo-1];
}
void main(){
struct lifo arquivo;
int abre, fecha, id, i;
char expressao[TAM];
i = abre = fecha = arquivo.topo = 0;
printf("Informe uma expressao matematica com parenteses, chaves e/ou colchetes: ");
fgets(expressao, TAM, stdin);
for(i; expressao[i] != '\n'; i++){
if((expressao[i] == '(') || (expressao[i] == '[') || (expressao[i] == '{')){
abre++;
if(expressao[i] == '(') id = 1;
else if(expressao[i] == '[') id = 2;
else id = 3;
push(&arquivo, id);
}else if((expressao[i] == ')') || (expressao[i] == ']') || (expressao[i] == '}')){
fecha++;
if(expressao[i] == ')') id = 1;
else if(expressao[i] == ']') id = 2;
else id = 3;
if(id == top(&arquivo)) pop(&arquivo);
} }
if(empty(&arquivo)){
if(abre == fecha) printf("\nA expressao foi escrita corretamente!\n");
else printf("\nHa parenteses, colchetes e/ou chaves fechando nada. Tente retira-los.\n");
}else{
printf("\nA expressao esta desordenada.\n");
if(abre < fecha) printf("Alem disso, ha parenteses, colchetes e/ou chaves abertos sem fechar.\n");
else if(abre > fecha) printf("Alem disso, ha mais parenteses, colchetes e/ou chaves de fechamento do que de abertura.\n");
}
if(i - abre - fecha < abre + fecha + 1) printf("Apenas um observacao e uma sugestao: os parenteses, colche... voce sabe. Ha mais do que o necessario. Entao, porque nao os tira logo da expressao?\n");
}
Referências
- ↑ 1,0 1,1 1,2 TENENBAUM, A. A.; LANGSAM, Y.; AUGENSTEIN, M.J. Estruturas de dados usando C, capítulo 2: A Pilha, São Paulo: Makron Books, 1995.
- ↑ FEOFILOFF, p. Projeto de algoritmos em C: Pilhas. http://www.ime.usp.br/~pf/algoritmos/aulas/pilha.html
- ↑ Wikipedia: Stack. http://en.wikipedia.org/wiki/Stack_%28abstract_data_type%29#Implementation
--Evandro.cantu (discussão) 16h49min de 17 de julho de 2014 (BRT)
