EDA 4

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

*
Estrutura de Dados e Arquivos
(adaptado do material do prof.Nicolas Anquetil)
Unidade 3
Pilha e fila
© Nicolas Anquetil,2002
Unidade 3
Pilha
Conceito
Operações
Implementação seqüencial
Implementação com lista encadeada
Exercícios
Fila
Conceito
Operações
Implementação seqüencial
Implementação com lista encadeada
Exercícios
Aplicações
© Nicolas Anquetil,2002
Pilha (conceito)
(1)
(2)
(3)
(4)
(5)
(6)
(7)
(8)
© Nicolas Anquetil,2002
Pilha (conceitos)
“Definição” de pilha:
Um conjunto ordenado de elementos
Primeiro elemento introduzido é o ultimo a sair e ultimo introduzido é o primeiro a sair
Também chamada de lista LIFO (“Last In/First Out”)
Uma pilha é uma lista para qual os elementos são acrescentados e removidos sempre na mesma extremidade
© Nicolas Anquetil,2002
Pilha (operações)
Operações (P sendo uma pilha e x um elemento):
push(P,x) - Acrescenta o elemento x no topo da pilha P (o tamanho de P aumenta)
pop (P) - Remove e retorna o elemento no topo da pilha (o tamanho de P diminui)
top(P) - Retorna o elemento no topo da pilha sem removê-lo (o tamanho de P permanece o mesmo)
vazia(P) - Verifica se a pilha está vazia (não tem nenhum elemento nela)
© Nicolas Anquetil,2002
Pilha (operações)
Outras operações podem ser necessárias dependentemente da implementação:
inicializa(P) - Inicializa a pilha para receber elementos. Uma pilha é inicializada no estado “vazia”.
cheia(P) - Verifica se a pilha está cheia (não pode aceitar mais elementos).
Nota: cheia não é o oposto de vazia, a pilha pode não ser vazia e também não ser cheia (ex: estados (2) e (3) da apresentação anterior)
© Nicolas Anquetil,2002
Pilha (implementação seqüencial)
Pode ser implementada com um vetor:
vazia(P):
cheia(P):
vazia(P):
cheia(P):
© Nicolas Anquetil,2002
Pilha (implementação seqüencial)
Declaração:
#define MAX_PILHA 4 /* tamanho da pilha */
#define SEMVALOR MAXINT /* “erro” p/ pop e top */
typedef struct { int dados[MAX_PILHA]; int numElem; } pilha;
Operação “init”:
void inicializa(pilha *P) {
 P->numElem = 0;
}
Operação “push” …
© Nicolas Anquetil,2002
Pilha (implementação seqüencial)
Operação “push”:
bool push(pilha *P, int x) {
 if (! cheia(*P)) { P->dados[P->numElem] = x;
	 P->numElem++; return true;
	}
	return false;
}
Operação “top” …
© Nicolas Anquetil,2002
Pilha (implementação seqüencial)
Operação “top”:
int top(pilha *P) {
 if (! vazia(*P)) return(P->dados[P->numElem-1]); else return(SEMVALOR);
}
Operação “pop” …
© Nicolas Anquetil,2002
Pilha (implementação seqüencial)
Operação “pop”:
int pop(pilha *P) {
 if (! vazia(*P)) { P->numElem--; return(P->dados[P->numElem]); } else 	return(SEMVALOR);
}
Operação “vazia” …
Operação “cheia” …
© Nicolas Anquetil,2002
Pilha (implementação seqüencial)
Operação “vazia”:
bool vazia(pilha P) {
 return(P.numElem == 0);
}
Operação “cheia”:
bool cheia(pilha p) {
 return(p.numElem == MAX_PILHA);
}
© Nicolas Anquetil,2002
Pilha (com lista encadeada)
Podemos também implementar pilhas usando listas encadeadas
A lista encadeada se adapta muito bem porque, numa pilha, elementos estão inseridos e removidos na mesma extremidade: a cabeça da lista
Basta usar os métodos de inserção e remoção de um elemento na cabeça da pilha que já vimos
© Nicolas Anquetil,2002
Pilha (com lista encadeada)
Declaração:
#define SEMVALOR MAXINT /* “erro” p/ pop e top*/
typedef struct s_cel { int elem; struct s_cel *prox; } cel;
 typedef cel* pilha;
Operação “inicializa”:
void inicializa(pilha *P) {
 *P = NULL;
}
Operação “push” …
© Nicolas Anquetil,2002
Pilha (com lista encadeada)
Operação “push”:
void push(pilha *P, int x) {
 pilha tmp;
 tmp = (pilha)malloc(sizeof(cel)); tmp->prox = *P; *P = tmp; (*P)->elem = x;
}
Operação “top” …
© Nicolas Anquetil,2002
Pilha (com lista encadeada)
Operação “top”:
int top(pilha P) {
 if (! vazia(P)) return(P->elem); else return(SEMVALOR);
}
Operação “pop” …
© Nicolas Anquetil,2002
Pilha (com lista encadeada)
Operação “pop”:
int pop(pilha *P) {
 pilha tmp;
	int ret;
 if (! vazia(*P)) { 	ret = (*P)->elem;
		tmp=*P;
 		*P=(*P)->prox; free(tmp);
		return ret; }
 else return(SEMVALOR);
}
© Nicolas Anquetil,2002
Pilha (com lista encadeada)
Operação “vazia”:
bool vazia(pilha P) {
 return(P == NULL);
}
Operação “cheia”:
Retorna sempre falso pois com a alocação dinâmica não existe limite de tamanho
bool cheia(pilha P) {
 return(false);
}
© Nicolas Anquetil,2002
Exercícios
 Mostre os estados de uma pilha depois de cada operação a seguir. Considerando que a pilha tem 5 posições, em que estado(s) ela está vazia ou cheia? inicializa(&P); pop(&P); push(&P,’a’); push(&P,’e’); push(&P,top(&P)); pop(&P); push(&P,pop(&P))
Escrever um programa que leia números de uma pilha e os escreva em ordem inversa. Lê: 1 2 3 4 5 e escreve: 5 4 3 2 1.
Escreva um programa que receba duas pilhas p1 e p2 como entrada e que adicione o conteúdo de p1 em p2 respeitando a mesma ordem. Ou seja, ao final o topo de p2 será o mesmo topo de p1 ne entrada. P1 deve terminar a rotina exatamente como começou. 
Adapte a pilha implementada usando lista encadeada para que manipule um número qualquer de entradas e saídas, ou seja, que receba como parâmetro o número de elementos a entrar ou sair de uma só vez.
© Nicolas Anquetil,2002
Exercícios
Implementar uma calculadora usando a notação posfixa: 2 3 + 5 4 - * = 5
© Nicolas Anquetil,2002
Notação Posfixa
Representação infixa: A + B
Representação prefixa: +AB
Representação posfixa: AB+
O operador sucede os operandos
Não necessita o uso de parênteses para determinar a ordem de solução da expressão
Exemplos:
Infixa posfixa
A + (B*C) ABC * +
(A + B) * C AB + C *
(A+B)*(C-D) AB + CD - *
A$B*C–D+E/F/(G+H) AB $ C * D – EF / GH + / + 
A$B = AB
© Nicolas Anquetil,2002
Implementação da calculadora posfixa
Dicas:
Leia a expressão valor a valor vindo do teclado
Para simplificar o problema vamos considerar que os valores serão ou números ou um dos seguintes caracteres: + - * / $
Para facilitar a leitura da expressão considere que o usuário digita sempre um caracter de controle (#) antes de inserir um número
Para cada valor lido faça:
Se um valor lido for um número empilhe-o
Se o valor lido for um operando desempilhe os dois últimos números da pilha e aplique a operação correspondente e empilhe o resultado
Se o valor lido for ‘.’ considere a expressão terminada
Quando a entrada acabar retorne como resultado o número que estiver no topo da pilha.
Críticas de validação da expressão:
Se ao tentar desempilhar os dois últimos números a pilha tiver menos de dois elementos retorne um erro
Se ao final do cálculo a pilha não tiver exatamente um número retorne erro.
© Nicolas Anquetil,2002
Fila (conceito)
(1)
(2)
(3)
(4)
(5)
(6)
(7)
(8)
(9)
© Nicolas Anquetil,2002
Fila (conceitos)
“Definição” de fila:
Um conjunto ordenado de elementos
Primeiro elemento introduzido é o primeiro a sair e ultimo introduzido é o ultimo a sair
Também chamada de lista FIFO (“First In/First Out”)
Uma fila é uma lista para qual os elementos são sempre acrescentados numa extremidade (final) e sempre removidos na outra extremidade (inicio)
© Nicolas Anquetil,2002
Fila (operações)
Operações (F sendo uma fila e x um elemento):
enqueue(F,x) - Acrescenta o elemento x na fila F (o tamanho de F aumenta)
dequeue (F) - Remove e retorna o primeiro elemento da fila (o tamanho de F diminui)
vazia(F) - Verifica se a fila está vazia (não tem nenhum elemento nela)
Outras operações :
inicializa(F) - Inicializa a fila para receber elementos. Uma fila é inicializada no estado “vazia”.
cheia(F) - Verifica se a fila está cheia (não pode aceitar
mais elementos)
Nota: vazia e cheia não são opostos
© Nicolas Anquetil,2002
Fila (implementação seqüencial)
Primeira implementação com um vetor:
vazia(P):
cheia(P):
vazia(P):
cheia(P):
não
sim
dequeue(F)=a
d
c
b
final
inicio
© Nicolas Anquetil,2002
Fila (implementação seqüencial)
Implementação com um vetor
Declaração:
#define MAX_FILA 4 	 /* tamanho da fila */
#define SEMVALOR MAXINT /* “erro” p/ dequeue */
typedef struct cell { int dados[MAX_FILA]; int inicio, final; } fila;
Operação “inicializa”:
void inicializa(fila *F) {
 F->inicio = 0; F->final = 0;
}
Operação “enqueue” …
© Nicolas Anquetil,2002
Fila (implementação seqüencial)
Operação “enqueue”:
void enqueue(fila *F, int x) {
 if (! cheia(*F)) { F->dados[F->final] = x; F->final++; 
 }
}
Operação “dequeue” …
© Nicolas Anquetil,2002
Fila (implementação seqüencial)
Operação “dequeue”:
int dequeue(fila *F) {
 if (! vazia(*F)) { F->inicio++; return(F->dados[F->inicio-1]); }
	else return(SEMVALOR);
}
Operação “isEmpty” …
Operação “isFull” …
© Nicolas Anquetil,2002
Fila (implementação seqüencial)
Operação “vazia”:
bool vazia(fila F) {
 return(F.inicio == F.final);
}
Operação “cheia”:
bool cheia(fila F) {
 return(F.final > MAX_FILA);
}
© Nicolas Anquetil,2002
Problema com a primeira implementação: 			Fila não cheia 			Mas não pode acrescentar elementos
Solução, implementação circular:
Fila (implementação seqüencial)
0
1
2
3
MAX
0
1
2
3
inicio
final
b
c
d
…
© Nicolas Anquetil,2002
Fila (implementação seqüencial)
Operação “enqueue”:
void enqueue(fila *F, int x) {
 if (! cheia(*F)) { F->dados[F->final] = x;
	 F->final = (F->final+1)% MAX_FILA; }
}
Operação “dequeue” …
© Nicolas Anquetil,2002
Fila (implementação seqüencial)
Operação “dequeue”:
int dequeue(fila *F) {
 if (! vazia(F)) {
	 int tmp=F->inicio; F->inicio = (F->inicio+1)% MAX_FILA;
 return(F->dados[tmp]); }
	else return(SEMVALOR);
}
Operação “isEmpty” …
Operação “isFull” …
© Nicolas Anquetil,2002
Problema com a segunda implementação:
 Fila cheia ou vazia?
Fila (implementação seqüencial)
final
inicio
e
i
o
a
x
z
w
v
t
s
y
u
© Nicolas Anquetil,2002
Fila (implementação seqüencial)
Declaração (casa vazia):
#define MAX_FILA 4 /* tamanho da fila */
#define SEMVALOR MAXINT /* “erro” p/ dequeue */
typedef struct { int dados [MAX_FILA]; int inicio, final; } fila;
Operação “init” (casa vazia):
void inicializa(fila *F) { F->inicio = 0; F->final = 0;
}
© Nicolas Anquetil,2002
Fila (implementação seqüencial)
Operação “vazia” (casa vazia):
bool vazia(fila F) { return(F.inicio == F.final); }
Operação “cheia” (casa vazia):
bool cheia(fila F) { return( (F.final == (F.inicio-1)) || 	 ((F.final==MAX_FILA-1) && (F.inicio==0)) );
}
© Nicolas Anquetil,2002
Fila (implementação seqüencial)
Declaração (contador):
#define MAX_FILA 4 /* tamanho da fila */
#define SEMVALOR MAXINT /* “erro” p/ dequeue */
typedef struct { int dados[MAX_FILA]; int inicio, total; } fila;
Operação “inicializa” (contador):
void inicializa(fila *F) { F->inicio = 0; F->total = 0;
}
© Nicolas Anquetil,2002
Fila (implementação seqüencial)
Operação “vazia” (contador):
bool vazia(fila F) { return(F.total == 0);
}
Operação “cheia” (contador):
bool cheia(fila F) { return(F.total == MAX_FILA);
}
© Nicolas Anquetil,2002
Fila (implementação seqüencial)
Operação “enqueue” (contador):
void enqueue(fila *F, int x) { int final; if (! cheia(*F)) { 	final = (F->inicio+F->total) % MAX_FILA; 	F->dados[final] = x; 	F->total++; }
}
Operação “dequeue” (contador) não muda
© Nicolas Anquetil,2002
Fila (com lista encadeada)
Para implementar uma fila com uma lista encadeada, a definição de lista que usamos até agora não se adapta bem
A fila precisa ter acesso às suas duas extremidades (uma para acrescentar elementos, outra para tirá-los)
Por isso é mais fácil usar uma lista encadeada com dois ponteiros
Dequeue 
 Enqueue 
© Nicolas Anquetil,2002
Fila (com lista encadeada)
Declaração:
#define SEMVALOR MAXINT; /* “erro” p/ dequeue */
typedef struct cel { int elem; struct cel *prox; } *lista;
typedef struct { lista inicio, final; } fila
Operação “inicializa”:
void inicializa(fila *F) {
 F->inicio = NULL; F->final = NULL;
}
© Nicolas Anquetil,2002
Fila (com lista encadeada)
Operação “vazia”:
bool vazia(fila F) {
 return(F.inicio == NULL);
}
Operação “cheia”:
bool cheia(fila F) {
 return(false);
}
© Nicolas Anquetil,2002
Fila (com lista encadeada)
Operação “enqueue”:
void enqueue(fila *F, int x) { lista tmp; tmp = (lista)malloc(sizeof(struct cel)); tmp->prox=NULL; tmp->elem=x; if (vazia(*F)) { /* inicio==final==NULL */ F->inicio=tmp; F->final=tmp; } else { F->final->prox=tmp; F->final=tmp; }
}
Operação “dequeue”
© Nicolas Anquetil,2002
Fila (com lista encadeada)
Operação “dequeue”:
int dequeue(fila *F) { lista tmp; int retorno; if (vazia(*F)) retorno = SEMVALOR; else { tmp=F->inicio->prox; retorno=F->inicio->elem; free(F->inicio);
	 F->inicio=tmp; if (F->inicio == NULL) F->final=NULL;
	} return(retorno);
}
© Nicolas Anquetil,2002
Exercícios
Mostre estados de uma fila depois de cada operação a seguir. Considerando que a fila tem 5 posições, em que estado(s) ela está vazia ou cheia? inicializa(&F); enqueue(&F,’a’); enqueue(&F,dequeue(&F)); dequeue(&F); vazia(F); enqueue(&F,’b’); enqueue(&F,’c’)
Implemente uma rotina que receba uma fila e ao final nessamesma fila os impares venham antes dos pares além da sua ordem estar invertida com relação à ordem na entrada.
Como poderíamos implementar uma estrutura semelhante a uma fila usando duas pilhas? (Definir a estrutura de dados e as funções básicas da fila).
Escrever um programa que receba duas filas com dados ordenados em ordem crescente e retorne uma terceira fila, também ordenada em ordem crescente, com todos os dados das filas de entrada. Ao final as filas de entrada devem estar inalteradas. (para implementar essa rotina considere a adição de uma nova função de fila chamada head(F) que retorna o dado do início da fila sem retira-lo da fila).
© Nicolas Anquetil,2002
Exercícios
Implementar outros tipos de fila:
Fila com prioridade onde os elementos têm uma prioridade e estão inseridos no lugar certo dentro da fila (e não automaticamente no final). As funções são as mesmas, mas o “enqueue” precisa mais um parâmetro enqueue(&aFila,oElemento,aPrioridade).
Fila dupla onde os elementos estão inseridos e extraídos dos dois lados da fila. As funções “enqueue” e “dequeue” precisam de mais um parâmetro para indicar qual extremidade da fila queremos usar enqueue(&aFila,oElemento,Extremidade1ou2) dequeue(&aFila,oElemento,Extremidade1ou2)
*
*