Pilhas e Filas

Prévia do material em texto

1
Algoritmos
+
Estruturas de Dados
=
Programas
TIPO ABSTRATO DE DADOS
Tipos Abstratos de Dados
• Definição
– Um tipo abstrato de dados (TAD) é um tipo de 
dados definido através de suas operações.
– Exemplo: TAD Agenda
• Operações
void cadastrar (Agenda *a, char n[]);
void remover (Agenda *a, char n[]);
void alterar (Agenda a, char n[]);
void consultar (Agenda a, char n[]);
Estruturas de Dados
• Definição
– Uma estrutura de dados é um tipo de dados 
compostos (estruturado).
– Um tipo abstrato de dados é implementado 
utilizando-se uma estrutura de dados.
– Exemplo: Tipo Agenda
• Implementada utilizando uma estrutura de dados 
do tipo vetor (lista seqüencial);
• Implementada utilizando ponteiros e memória de 
alocação dinâmica (lista encadeada);
• Implementada utilizando arquivo.
– Exemplo: Implementação do TAD Agenda com lista 
seqüencial utilizando vetor
typedef struct pessoa {
char nome [100], fone [50], email [50];
}Pessoa;
typedef struct agenda {
Pessoa dados [200];
int cont;
}Agenda;
void inicializar (Agenda *a);
void cadastrar (Agenda *a, char n[]);
void remover (Agenda *a, char n[]);
void alterar (Agenda a, char n[]);
void consultar (Agenda a, char n[]);
Tipos Abstratos de Dados
– Exemplo: Implementação do TAD Agenda como lista 
encadeada
typedef struct pessoa {
char nome [100], fone [50], email [50]; pessoa * prox;
}Pessoa;
typedef struct agenda {
Pessoa *prim, *ult;
int qtd;
}Agenda;
void inicializar (Agenda *a);
void cadastrar (Agenda *a, char n[]);
void remover (Agenda *a, char n[]);
void alterar (Agenda a, char n[]);
void consultar (Agenda a, char n[]);
Tipos Abstratos de Dados
– Exemplo: Implementação do TAD Agenda 
utilizando arquivo
typedef struct pessoa {
char nome [100], fone [50], email [50];
}Pessoa;
typedef FILE * Agenda;
void inicializar (Agenda *a);
void cadastrar (Agenda *a, char n[]);
void remover (Agenda *a, char n[]);
void alterar (Agenda a, char n[]);
void consultar (Agenda a, char n[]);
Tipos Abstratos de Dados
2
Estruturas de Dados
• Utilização
– A utilização do TAD independe da forma como o 
mesmo foi implementado;
– Modificações na implementação do TAD não 
implicam em modificações nos programas que os 
utilizam.
– Exemplo: Tipo Agenda
Declaração de variáveis: Agenda myFriends;
Uso: inicializar (&myFriends);
cadastrar (&myFriends, nome);
consultar (myFriends, nome);
...
Pilhas (Stacks)
• Definições
– Uma pilha é um TAD que obedece a 
disciplina de acesso LIFO (“Last In First
Out”), ou seja, o último elemento a entrar é, 
obrigatoriamente, o primeiro a sair.
– TOPO da pilha:
• Posição na qual serão feitas as inserções e 
retiradas de elementos da pilha.
Pilhas (Stacks)
• Definições (cont.)
– O conjunto de operações que definem uma 
pilha são:
• PUSH : Empilhar, ou seja, colocar um elemento no 
topo da pilha;
• POP: Desempilhar, ou seja, retirar um elemento 
do topo da pilha;
• TOP: Informar que elemento encontra-se no topo 
da pilha;
• ISEMPTY: Verificar se a pilha está vazia.
Pilhas (Stacks)
• Exemplo de Implementação: Seqüencial
– Pilha implementada utilizando uma estrutura 
de dados do tipo vetor.
– Exemplo:
#define tam 10;
typedef struct stack {
int dados [tam];
int topo;
}Stack;
Stack minhaPilha;
Pilhas (Stacks)
• Exemplo de Implementação: Encadeada
– Pilha implementada utilizando o tipo de dados 
ponteiro e memória de alocação dinâmica.
– Exemplo:
typedef struct noPilha {
int info;
struct noPilha * prox;
} NoPilha;
typedef NoPilha * Stack; 
Stack minhaPilha;
Pilhas (Stacks)
• Exemplo de Implementação: Encadeada
– Operações:
void push (Stack *s, int n);
int pop (Stack *s);
int top (Stack s);
int isEmpty (Stack s);
void initialize (Stack *s);
3
Filas (Queues)
• Definições
– Uma fila é um TAD que obedece a disciplina 
de acesso FIFO (“First In First Out”), ou seja, 
o primeiro elemento a entrar é, 
obrigatoriamente, o primeiro a sair.
– HEAD (cabeça da fila):
• Elemento que se encontra no início da final
– TAIL (calda da fila);
• Elementos que compõem a fila menos o HEAD.
Filas (Queues)
• Definição(cont.)
– O conjunto de operações que definem uma 
fila são:
• ENQUEUE : Enfileirar, ou seja, colocar um 
elemento no final da fila;
• DEQUEUE: Desenfileirar, ou seja, retirar o 
elemento do início da fila (retirar o HEAD);
• HEAD: Informar que elemento encontra-se no 
início da fila;
• ISEMPTY: Verificar se a fila está vazia.
Filas (Queues)
• Exemplo de Implementação: 
Sequencial
– Fila implementada utilizando uma estrutura 
de dados do tipo vetor.
– Exemplo:
#define tam 10;
typedef struct queue {
int dados [tam];
int inicio, fim;
}Queue;
Queue filaBanco;
Filas (Queues)
• Exemplo de Implementação: Encadeada
– Fila implementada utilizando o tipo de dados ponteiro 
e memória de alocação dinâmica.
– Exemplo:
typedef struct noQueue {
int info; 
struct noQueue * prox;
} NoQueue;
typedef struct descritor {
NoQueue * inicio, * fim;
}Descritor;
typedef Descritor * Queue;
Queue filaBanco;
Filas (Queues)
• Exemplo de Implementação: Encadeada
– Operações:
void enqueue (Queue q, int n);
int dequeque (Queue q);
int head (Queue q);
int isEmpty (Queue q);
void initialize (Queue *q);