Estruturas de Dados - A Pilha (Parte 1)

Prévia do material em texto

CIC/UnB - Estruturas de dados
A Pilha
(stack)
Definição de Pilha
● É um dos conceitos mais importantes no 
mundo da computação, particularmente 
para o processamento de linguagens de 
programação.
● Uma pilha é um conjunto ordenado no qual 
os ítens só podem ser inseridos ou 
eliminados através de uma única 
extremidade (denominada topo).
Exemplos
● 
 topo
 pilha vazia
Exemplos
● 
 topo
 a
 
 pilha com 1 elemento
Exemplos
● 
 topo
 b 
 a
 
 pilha com 2 elementos
Exemplos
● 
 topo
 c 
 b 
 a
 
 pilha com 3 elementos
Exemplos
● 
 topo
 b 
 a
 
 pilha com 2 elementos
Observações
● Não existe limite teórico para inserções na 
pilha
● Na prática, a pilha será um vetor e terá que 
ter um limite
● Existem duas operações básicas em uma 
pilha: push e pop
Push
● Usado para inserir (ou empilhar) um novo 
elemento na pilha p
● Na prática, um novo elemento é colocado no 
lugar apontado pela variável topo, sendo a 
mesma incrementada de uma unidade:
 push (p, ''a'')
● Como a pilha na prática tem limite, deve se 
verificar se a inserção é possível – caso não 
seja, ocorre uma condição de ''stack overflow''
Pop
● Usado para retirar (ou desempilhar) um 
elemento existente no topo da pilha p
● O elemento é copiado para uma variável 
fornecida x e a variável topo, será 
decrementada de uma unidade:
 x:=pop(p)
● Se a pilha estiver vazia ocorre a condição de 
''stack underflow''
Funções adicionais
● A função empty(p) pode ser implementada, 
devolvendo TRUE caso não existam 
elementos na pilha (caso contrário FALSE)
● A função full(p) pode ser implementada para 
indicar que variável topo atingiu o valor 
máximo de elementos da pilha
● Em algumas aplicações é possível consultar-
se o valor de um elemento qualquer da pilha: 
val (i) , sendo i um valor entre 0 e máximo-1
Funções adicionais
● A função stacktop(p) também pode ser útil: 
ela devolve o valor do topo da pilha, porém 
sem removê-lo: i:=stacktop(p)
● Ela pode ser implementada com um pop e um 
push:
i:=pop(p)
 push(p,i) 
Uma aplicação simples
● A precedência de operações em expressões 
aritméticas pode ser feita com parênteses e 
colchetes:
 (i*([z+w] / [i+j])*2) / ((a+b)*c)
● A correção de uma expressão como essa é 
às vezes difícil de ser avaliada
Uma aplicação simples
● Com uma pilha é possível verificar se os 
parênteses e colchetes estão balanceados:
● À medida em que vamos lendo a expressão, 
vamos inserindo os símbolos ''esquerdos'' 
encontrados na pilha. Quando encontrarmos 
os correspondentes símbolos ''direitos'', 
retiramos os ''esquerdos'' da pilha
 
 
Uma aplicação simples
● ( i *([z+w] / [i+j])*2) / ((a+b)*c)
 ^
 (
Uma aplicação simples
● ( i *([z+w] / [i+j])*2) / ((a+b)*c)
 ^
 (
 (
Uma aplicação simples
● ( i *([z+w] / [i+j])*2) / ((a+b)*c)
 ^
 [
 (
 (
Uma aplicação simples
● ( i *([z+w] / [i+j])*2) / ((a+b)*c)
 ^
 
 (
 (
Uma aplicação simples
● ( i *([z+w] / [i+j])*2) / ((a+b)*c)
 ^
 [ 
 (
 (
Uma aplicação simples
● ( i *([z+w] / [i+j])*2) / ((a+b)*c)
 ^
 
 (
 (
Uma aplicação simples
● ( i *([z+w] / [i+j])*2) / ((a+b)*c)
 ^
 
 
 (
Uma aplicação simples
● ( i *([z+w] / [i+j])*2) / ((a+b)*c)
 ^
 
 
 
Uma aplicação simples
● ( i *([z+w] / [i+j])*2) / ((a+b)*c)
 ^
 
 
 (
Uma aplicação simples
● ( i *([z+w] / [i+j])*2) / ((a+b)*c)
 ^
 
 (
 (
Uma aplicação simples
● ( i *([z+w] / [i+j])*2) / ((a+b)*c)
 ^
 
 
 (
Uma aplicação simples
● ( i *([z+w] / [i+j])*2) / ((a+b)*c)
 ^
 
 
 
Uma aplicação simples
● Como chegamos ao final da expressão com a 
pilha vazia, podemos decidir que, pelo menos 
ao ponto de vista de balanceamento, ela está 
correta.
● Uma expressão como a seguinte jamais seria 
considerada correta. (Porque?)
 (a*b+[c-d)*(3-e*5)]
Representando pilhas em C
● Em C, uma pilha pode ser representada como 
uma estrutura com uma variável que aponta 
para o topo e um vetor com os ítens:
#define STKSZ 100
typedef struct {
 int top;
 int items[STKSZ];
} stack;
stack s;
Representando pilhas em C
● O tipo de elementos da pilha pode ser 
qualquer, incluindo structures com ou sem 
unions.
● A posição do topo (s.top) deve representar o 
índice do elemento que está no topo da pilha. 
Assim, uma pilha vazia terá s.top ==-1; com 
um elemento terá s.top==0; com dois 
elementos terá s.top==1; e assim por diante.
Representando pilhas em C
● A função empty pode ser assim representada:
#define TRUE 1
#define FALSE 0
int empty(s)
stack *s; 
{
if (s->top== -1)
return (TRUE);
 else
 return (FALSE);
}
● Alternativa: return(s->top== -1)
Representando pilhas em C
● A função pop pode ser assim representada:
pop (s)
stack *s; 
{
if (empty(s)) {
printf(''%s'', ''Stack underflow'');
exit(1);
}
 else
 return (s->items[s->top--]);
}
● A chamada será:
x=pop(&s) para alguma variável int x
Representando pilhas em C
● Para evitar excessão na função pop, o 
programador pode se precaver codificando:
if (!empty (&s))
 x=pop(&s);
else
 /* toma atitude para remediar */
Representando pilhas em C
● A função push pode ser assim representada:
push (s,x)
stack *s; int x;
{
 if (s->top==STKSZ-1) {
printf(''%s'', ''Stack overflow'');
exit(1);
 }
 else
 s->items[++s->top] = x;
 return;
}
● A chamada será:
push(&s,x) para alguma variável int x
Representando pilhas em C
● Da mesma forma, para evitar excessões, 
podemos ter uma função full:
full (s)
stack *s; {
return(s->top==STKSZ-1);
}
● A chamada seria então:
if (!full(s)) push(&s,x);
 else /* trata-se a alternativa */
 Neste último caso, push não precisater o teste de pilha 
 cheia...
Representando pilhas em C
● Finalmente, a função stacktop já mencionada, 
usada somente para consultar o elemento do 
topo da pilha, pode ser assim implementada:
stacktop(s)
stack *s; 
{
if (empty(s)) {
printf(''%s'', ''Stack underflow'');
exit(1);
}
 else
 return (s->items[s->top]);
}
Exercício
● Podem fazer em duplas
● Imaginem um estacionamento em uma rua 
sem saída, com largura para apenas um carro 
e comprimento para até dez carros. O 
primeiro que chega, pára no fim da rua. O 
próximo logo atrás, e assim por diante:
 ...
Exercício
● Quando alguém deseja sair, todos os que 
estão estacionados atrás devem ser ser 
retirados, um a um, até que o interessado em 
sair possa ser retirado. Depois, os que foram 
manobrados devem voltar, na mesma ordem, 
porém ocupando a vaga liberada. Dessa 
forma, é criada uma nova vaga no fim da fila. 
 ...
Exercício
● Faça um programa que simule o 
estacionamento usando os conceitos de pilha. 
Os carros deverão ser identificados por um 
número inteiro. Os carros que chegarem com 
o estacionamento cheio deverão dar uma 
volta no quarteirão...
 ...
Próximos Passos da Ação
●