10 Estruturas de dados lista linear, pilha e fila, implementações com vetor e ponteiro

Prévia do material em texto

*
Ementário
Noções de hardware e software.
Conceitos Fundamentais.
Vetores, cadeia de caracteres e registros.
Definição e manipulação de arquivos externos.
Subprogramação.
Alocação dinâmica de memória. 
Estruturas de dados básicas: listas lineares, pilha e fila. 
*
Abstração de Dados
Um processo é qualquer sequência finita ordenada de
passos que visa promover transformações definidas
sobre uma determinada matéria-prima.
ENTRADA
(estado inicial)
PROCESSO
SAÍDA
(estado final)
*
Processamento de Dados
Quando a matéria-prima usada no processo é abstrata, isto é,
apresenta-se sob a forma de valores, quantidades ou símbolos,
então denomina-se processamento de dados. Quando o
processamento é realizado por um computador, entrada 
refere-se aos dados que são colhidos do mundo real, externo
ao computador, e processo refere-se a uma série finita de
operações que são realizadas a partir destes dados, a fim
de transformá-los em alguma informação desejada (saída).
DADOS
CONHECIMENTO
INFORMAÇÃO
*
Processamento de Dados
É importante notar que dado e informação são conceitos
relativos: dado é o que entra no processo, enquanto 
informação é o que sai. A informação gerada pelo processo, 
pode, em outra situação, servir como dado para um outro
processo.
Questões básicas para o programador:
1. Como representar a abstração da realidade dentro do 
 computador ?			Estrutura de Dados
2. Como representar o conhecimento necessário para
 manipular esta abstração ?	Algoritmo (ou Programa)
Salário bruto
do funcionário
FGTS = Sal. Bruto * 8%
Depósito 
do F.G.T.S
*
Algoritmos
Os algoritmos fazem parte do dia-a-dia das pessoas.
As instruções para o uso de medicamentos, as
indicações de como montar um aparelho qualquer,
uma receita de culinária são alguns exemplos de
algoritmos. 
Segundo Ziviani, um algoritmo pode ser visto como
uma sequência de ações executáveis para a obtenção
de uma solução para um determinado tipo de
problema.
*
Estrutura de Dados
Estrutura de dados e algoritmos estão intimamente ligados.
Não se pode estudar estruturas de dados sem considerar os
algoritmos associados a elas, assim como a escolha dos
algoritmos em geral depende da representação e da estrutura
de dados. 
Para resolver um problema é necessário escolher uma
abstração da realidade, em geral através da definição de um
conjunto de dados que representa a situação real. A seguir
deve ser escolhida a forma de representar estes dados.
A escolha da representação dos dados é determinada, entre
outras, pelas operações a serem realizadas sobre os dados.
*
Programas
O processamento de dados é feito pela execução de programas.
Um programa é uma sequência de instruções codificadas em
uma linguagem de programação e para ser executado precisa
ser armazenado na memória do computador.
Segundo Ziviani, programar é basicamente estruturar dados e
construir algoritmos. 
De acordo com Wirth, programas são formulações concretas
de algoritmos abstratos, baseados em representações e
estruturas específicas de dados. Em outras palavras, programas
representam uma classe especial de algoritmos capazes de
serem seguidos por computadores.
*
Linguagens de Programação
Um computador só é capaz de seguir programas em linguagem
de máquina, que correspondem a uma sequência de instruções
obscuras e desconfortáveis. 
Para controlar tal problema é necessário construir linguagens
mais adequadas para facilitar a tarefa de programar um
computador. 
Segundo Dijkstra, uma linguagem de programação é uma
técnica de notação para programar, com a intenção de servir
de veículo tanto para a expressão do raciocínio algorítmico
quanto para a execução automática de um algoritmo por um
computador.
*
Tipos de Dados
Em linguagens de programação é importante classificar
constantes, variáveis, expressões e funções de acordo com
certas características, as quais indicam o seu tipo de dados.
Este tipo deve caracterizar o conjunto de valores a que uma
constante pertence, ou que podem ser assumidos por uma
variável ou expressão, ou que podem ser gerados por uma
função (Wirth, 1976, pp.4-40).
Tipos simples de dados são grupos de valores indivisíveis,
como os tipos básicos int, char e float do C. Por exemplo, 
uma variável do tipo int pode assumir um valor numérico
do intervalo dos inteiros, e nenhum outro valor. Os tipos 
estruturados em geral definem uma coleção de valores
simples (vetor), ou um agregado de valores de tipos 
diferentes (registro, ou struct).
*
Tipos Abstratos de Dados, Segundo Ziviani
Um Tipo Abstrato de Dados (TAD) pode ser visto como um
modelo matemático, acompanhado das operações definidas
sobre o modelo. O conjunto dos inteiros acompanhado das
operações de adição, subtração e multiplicação forma um
exemplo de um TAD.
TAD podem ser considerados generalizações de tipos
primitivos de dados, da mesma forma que procedimentos são
generalizações de operações primitivas tais como adição,
subtração e multiplicação. Assim como um procedimento é
usado para encapsular partes de um algoritmo, o tipo abstrato
de dados pode ser usado para encapsular tipos de dados. Neste
caso a definição do tipo e todas as operações definidas sobre
ele podem ser localizadas em uma única seção do programa.
*
Tipos Abstratos de Dados, Segundo Pereira
Um TAD é formado por um conjunto de valores e por uma
série de funções que podem ser aplicadas sobre estes valores.
Funções e valores, em conjunto, constituem um modelo
matemático que pode ser empregado para “modelar”e
solucionar problemas do mundo real; servindo para 
especificar as características relevantes dos objetos
envolvidos no problema, de que forma eles se relacionam
e como podem ser manipulados.
Entretanto, sendo o TAD apenas um modelo matemático, sua
definição não leva em consideração como os valores serão
representados na memória do computador (organização dos
bits), nem se preocupa com o “tempo” que será gasto para
aplicar as funções (rotinas) sobre tais valores. 
*
Tipos Abstratos de Dados, Segundo Pereira
Para que se possa realmente aplicar um modelo matemático
na resolução de problemas por computador, é preciso antes
transformá-lo em um tipo de dados concreto (ou
simplesmente, tipo de dados).
A transformação de um tipo de dados abstrato em um tipo
de dados concreto é chamada implementação. É durante
o processo de implementação que a estrutura de
armazenamento dos valores é especificada, e que os
algoritmos que desempenharão o papel das funções são 
projetados.
TIPO DE DADOS
ABSTRATO
(modelo matemático)
IMPLEMENTAÇÃO
TIPO DE DADOS
CONCRETO
(padrão de bits/rotinas)
*
Implementação de um TAD
Frequentemente, nenhuma implementação é capaz de
representar um modelo matemático completamente; assim,
é necessário reconhecer as limitações, vantagens e 
desvantagens, de uma implementação particular.
O projetista deve ser capaz de escolher aquela mais adequada
para resolver o problema específico proposto, tomando como
medidas de eficiência da implementação sobretudo, as suas
necessidades de espaço de armazenamento e tempo de
execução.
As representações mais utilizadas para os TAD, que serão
estudados a seguir, são as implementações através de arranjos
(vetores) e de apontadores.
*
Estrutura de Dados Básicas
Uma das formas mais comumente usadas para se manter
dados agrupados é a lista. 
Afinal, quem nunca organizou uma lista de compras antes de
ir ao mercado, ou então uma lista de amigos que irão
participar do futebol no final-de-semana.
Lista são estruturas muito flexíveis porque podem crescer ou
diminuir de tamanho durante a execução de um programa, de
acordo com a demanda. Itens podem ser acessados, inseridos
ou retirados de um lista. Duas listas podem ser concatenadas
para formar uma lista única, assim como uma lista pode ser
partida em duas ou mais listas.*
Listas Lineares
Uma lista linear é uma sequência de zero ou mais itens: x1 ,
x2, ..., xn, onde xi é de um determinado tipo e n representa o
tamanho da lista linear.
Sua principal propriedade estrutural basea-se apenas na
posição relativa dos elementos, que são dispostos linearmente.
Se n = 0, dizemos que a lista está vazia; caso contrário, são
válidas as seguintes propriedades:
1. x1 é o primeiro elemento da lista;
2. xn é o último elemento da lista;
3. xk, 2  k  n-1, é precedido pelo elemento xk-1 e seguido por
 xk+1 na lista.
4. xi é dito estar na i-ésima posição da lista.
*
TAD Lista Linear (1/2)
Para criar um tipo abstrato de dados Lista, é necessário definir um
conjunto de operações sobre os objetos do tipo Lista. O conjunto de
operações a ser definido depende de cada aplicação, não existindo um
conjunto de operações que seja adequado a todas as aplicações. 
1. Criar um lista linear vazia.
2. Inserir um novo item imediatamente após o i-ésimo item.
3. Retirar o i-ésimo item.
4. Localizar o i-ésimo item para examinar e/ou alterar o conteúdo de
 seus componentes.
5. Combinar duas ou mais listas lineares em uma lista única.
6. Partir uma lista linear em duas ou mais listas.
7. Fazer uma cópia da lista linear.
8. Ordenar os itens da lista em ordem ascendente ou descendente, 
 de acordo com alguns de seus componentes.
9. Pesquisar a ocorrência de um item com um valor particular em algum
 componente.
*
TAD Lista Linear (2/2)
Restringindo o conjunto de operações necessário para uma aplicação
que utilize o TAD Lista Linear:
1. FazListaVazia(Lista). Faz a lista ficar vazia.
2. ListaVazia(Lista). Esta função retorna 1 (true) se a lista está vazia; 
 senão retorna 0 (false).
3. Imprime(Lista). Imprime os itens da lista na ordem de
 ocorrência.
4. Insere(x, Lista). Insere x após o último item da lista. (ou)
4. Insere(x, Lista, p). Insere x na posição p da lista.
5. Retira(p, Lista, x). Retira o item x que está na posição p da lista,
 retirando-o da lista e deslocando os itens a partir da posição p+1
 para as posições anteriores.
Existem várias estruturas de dados que podem ser usadas para
representar listas lineares, cada uma com vantagens e desvantagens
particulares. As duas representações mais utilizadas são as
implementações através de arranjos (vetores) e de apontadores.
*
Implementação de Listas através de Arranjos
Em um tipo estruturado arranjo, 
os itens da lista são armazenados
em posições contíguas de memória,
conforme ilustra a Figura ao lado. 
Neste caso a lista pode ser percorrida 
em qualquer direção. A inserção de um
novo item pode ser realizada após o
último item com custo constante. A
inserção de um novo item no meio da
lista requer um deslocamento de todos
os itens localizados após o ponto de
inserção. Da mesma forma, retirar um
item do início da lista requer um
deslocamento de itens para preencher
o espaço deixado vazio.
xn
x1
.
.
.
0
1
Ultimo = (n – 1)
.
.
.
.
.
.
 (maxTam – 1)
Item
Lista
.
.
.
x2
*
Implementação de Listas através de Arranjos
// modelo matemático (estrutura de dados)
struct TipoItem {	// cada item da lista corresponde a um
 char nome[30];	// registro (TipoItem) composto apenas
};			// do campo nome
const maxTam = 10; 	// tamanho máximo da lista
struct TipoLista {
 TipoItem Item[maxTam];
 int Ultimo;
};
O campo Item é o principal componente do registro TipoLista. Os itens
são armazenados em um vetor de tamanho suficiente para armazenar a
lista. Já o campo Ultimo do registro TipoLista contém o valor da 
posição do último elemento da lista. O i-ésimo item da lista está 
armazenado na i-ésima posição do vetor, 0  i  Ultimo. A constante
maxTam define o tamanho máximo permitido para a lista.
*
Implementação de Listas através de Arranjos
A implementação de listas através de arranjos tem como
vantagem o acesso indexado e a economia de memória, pois
os apontadores, ou índices, são implícitos nesta estrutura. 
Como desvantagens pode-se citar: 
1. o custo para inserir ou retirar itens da lista, pode causar
 um deslocamento de todos os itens, no pior caso;
2. em aplicações em que não existe previsão sobre o
 crescimento da lista, a utilização de arranjos em
 linguagens como o C pode ser problemática porque
 neste caso o tamanho máximo da lista tem que ser definido
 em tempo de compilação.
*
Implementação de Listas através de Arranjos
// Faz a ‘Lista’ ficar vazia
void FazListaVazia(TipoLista *Lista) {
 Lista->Ultimo = -1;
}
// Esta função retorna 1 (true) se a ‘Lista’
// está vazia; senão retorna 0 (false)
int ListaVazia(TipoLista *Lista) {
 return(Lista->Ultimo == -1);
}
// Imprime os itens da 'Lista'
void Imprime(TipoLista *Lista) {
 clrscr();
 for (int i=0; i<=Lista->Ultimo; i++)
 printf("%d- %s\n", i, Lista->Item[i].nome);
}
*
Implementação de Listas através de Arranjos
// Insere o item 'x' na final da 'Lista'.
int Insere(TipoItem x, TipoLista *Lista) {
 if (Lista->Ultimo == (maxTam – 1))
 return(0);	 // Erro: Lista Cheia !
 else {
 Lista->Ultimo = Lista->Ultimo + 1;
// item inserido no final da lista
 Lista->Item[Lista->Ultimo] = x;
 return(1); // Item inserido com sucesso
 }
}
*
Implementação de Listas através de Arranjos
// Insere o item 'x' na posição ‘p’ da 'Lista'.
int Insere(TipoItem x, TipoLista *Lista, int p) {
 if (Lista->Ultimo == (maxTam – 1))
 return(0);	 // Erro: Lista Cheia !
 else {
 Lista->Ultimo = Lista->Ultimo + 1;
 for (int i=Lista->Ultimo; i<p; i--)
 Lista->Item[i] = Lista->Item[i-1];
 
// item inserido na posição ‘p’ da lista
 Lista->Item[p] = x;
 return(1); // Item inserido com sucesso
 }
}
desloca os itens a partir da última posição até p para as posições seguintes, liberando a posição ‘p’ para inserir o item
*
Implementação de Listas através de Arranjos
// Retira o item ‘x’ que está na posição ‘p’ da ‘Lista’
int Retira(int p, TipoLista *Lista, TipoItem *x) {
 if ((ListaVazia(Lista)) || (p < 0) || 
 (p > Lista->Ultimo))
 return(0); 	// Erro: Lista vazia ou 
			// posição não existe.
 else {
 *x = Lista->Item[p]; // item retornado
 for (int i=p; i<=(Lista->Ultimo-1); i++)
 Lista->Item[i] = Lista->Item[i+1];
 Lista->Ultimo = Lista->Ultimo - 1;
 return(1); // Item retirado com sucesso
 }
}
desloca os itens a partir da posição
p+1 para as posições anteriores, ocupando a posição do item retirado
*
Implementação de Listas através de Apontadores
Em uma implementação de listas através de apontadores, cada item da
lista é encadeado com o seguinte através de uma variável do tipo
Apontador. Este tipo de implementação permite utilizar posições não
contíguas de memória, sendo possível inserir e retirar elementos sem
haver necessidade de deslocar os itens seguintes da lista. A Figura 
abaixo ilustra uma lista representada desta forma. Observe que existe
uma célula cabeça que aponta para a célula que contém x1.
Item
Apontador
NULL
Celula
Célula
Cabeça
Primeiro
prox
...
x1
x2
xn
Ultimo
*
Implementação de Listas através de Apontadores
// modelo matemático (estrutura de dados)
struct TipoItem {	// cada item da lista corresponde a um
 char nome[30];	// registro (TipoItem) composto apenas
};			// do campo nome
typedef struct Celula *Apontador;
struct Celula {
 TipoItem Item;
 Apontador prox;
};
struct TipoLista {
 Apontador Primeiro;
 Apontador Ultimo;
};
A lista é constituída de células, onde cada registro célula contém um 
Item da lista e um “apontador” para a célula seguinte (prox). O registro 
TipoLista contém um “apontador” para a célula cabeça (Primeiro) e um 
“apontador” para a última célula da lista (Ultimo).
*
Implementação de Listas através de Apontadores
A implementação através deapontadores permite inserir ou
retirar itens do meio da lista a um custo constante, aspecto
importante quando a lista tem que ser mantida em ordem. 
Em aplicações em que não existe previsão sobre o
crescimento da lista é conveniente usar listas encadeadas
por apontadores, porque neste caso o tamanho máximo da
lista não precisa ser definido a priori. 
A maior desvantagem deste tipo de implementação é a
utilização de memória extra para armazenar os apontadores.
*
Implementação de Listas através de Apontadores
// Faz a 'Lista' ficar vazia criando a célula cabeça
void FazListaVazia(TipoLista *Lista) {
 Lista->Primeiro = (Apontador) malloc(sizeof(Celula));
 Lista->Primeiro->prox = NULL;
 Lista->Ultimo = Lista->Primeiro;
}
// Esta função retorna 1 (true) se a ‘Lista’ está vazia; 
// senão retorna 0 (false)
int ListaVazia(TipoLista *Lista) {
 return(Lista->Primeiro == Lista->Ultimo);
}
*
NULL
Implementação de Listas através de Apontadores
void FazListaVazia(TipoLista *Lista) {
 1. Lista->Primeiro = (Apontador) malloc(sizeof(Celula));
 2. Lista->Primeiro->prox = NULL;
 3. Lista->Ultimo = Lista->Primeiro;
}
Lista->
Primeiro
Ultimo
1
2
3
*
Implementação de Listas através de Apontadores
// Insere o item 'x' no final da 'Lista'
void Insere(TipoItem x, TipoLista *Lista) {
 Lista->Ultimo->prox = (Apontador) malloc(sizeof(Celula));
 Lista->Ultimo = Lista->Ultimo->prox;
 Lista->Ultimo->Item = x;
 Lista->Ultimo->prox = NULL;
}
a instrução malloc cria uma nova célula
insere x após o último item da lista
*
NULL
Implementação de Listas através de Apontadores
void Insere(TipoItem x, TipoLista *Lista) {
1. Lista->Ultimo->prox = (Apontador) malloc(sizeof(Celula));
2. Lista->Ultimo = Lista->Ultimo->prox;
3. Lista->Ultimo->Item = x;
4. Lista->Ultimo->prox = NULL;
}
Item
Apontador
NULL
Celula
Célula
Cabeça
prox
...
x1
xn
Lista->
Primeiro
Ultimo
1
2
3
4
x
*
Implementação de Listas através de Apontadores
// Retira o item ‘x’ que o seguinte ao apontador por ‘p’
int Retira(Apontador p, TipoLista *Lista, TipoItem *x) {
 if ((ListaVazia(Lista)) || (p == NULL) || 
 (p->prox == NULL))
 return(0); // Erro: Lista vazia ou posição inválida.
 else {
 Apontador q = p->prox;
 *x = q->Item; // item retornado
 p->prox = q->prox;
// se retirando a última célula da lista 
 if (p->prox == NULL)
 Lista->Ultimo = p;
 free(q); 
 return(1); // Item retirado com sucesso
 }
}
a instrução free libera da memória a célula do item retirado da lista
*
prox
Implementação de Listas através de Apontadores
// Retira o item ‘x’ que é o seguinte ao apontador por ‘p’
int Retira(Apontador p, TipoLista *Lista, TipoItem *x) {
1. Apontador q = p->prox;
2. *x = q->Item; // item retornado
3. p->prox = q->prox;
4. free(q); 
xP-1
xp
xp+2
p
xp+1
q
1
3
4
...
...
lixo
x
xp+1
2
Item
prox
*
Implementação de Listas através de Apontadores
// Imprime os itens da ‘Lista’
void Imprime(TipoLista *Lista) {
 clrscr();
 int i = 1;
 Apontador p = Lista->Primeiro->prox;
 while (p != NULL) {
 printf("%d- %s\n", i, p->Item.nome);
 i = i + 1;
 p = p->prox;
 }
}
posiciona no início da lista
avança para a próxima célula da lista
*
TAD Pilha (1/4)
Existem aplicações para listas lineares nas quais inserções,
retiradas e acessos a itens ocorrem sempre em um dos
extremos da lista. Uma pilha é uma lista linear em que todas
as inserções, retiradas e geralmente todos os acessos são
feitos em apenas um extremo da lista.
Os itens em uma pilha estão colocados um sobre o outro, com
o item inserido mais recentemente no topo e o item inserido
menos recentemente no fundo. 
O modelo intuitivo de uma pilha é o de um monte de pratos
em uma prateleira, sendo conveniente retirar os pratos ou
adicionar novos pratos na parte superior.
*
TAD Pilha (2/4)
As pilhas possuem a seguinte propriedade: O ÚLTIMO ITEM
INSERIDO É O PRIMEIRO ITEM QUE PODE SER RETIRADO
DA LISTA. Por esta razão as pilhas são chamadas de listas LIFO,
termo formado a partir de “Last-In, First-Out”.
 
Existe uma ordem linear para pilhas, que é a ordem do "mais recente
para o menos recente". 
Esta propriedade torna a pilha uma ferramenta ideal para processamento
de estruturas aninhadas de profundidade imprevisível, situação em
que é necessário garantir que subestruturas mais internas sejam
processadas antes da estrutura que as contenham. A qualquer instante
uma pilha contém uma sequência de obrigações adiadas, cuja ordem de
remoção da pilha garante que as estruturas mais internas serão
processadas antes das estruturas mais externas.
*
TAD Pilha (3/4)
Estruturas aninhadas ocorrem frequentemente na prática. Um
exemplo simples é a situação em que é necessário caminhar
em um conjunto de dados e guardar uma lista de coisas a fazer
posteriormente. 
O controle de chamadas de subprogramas e sintaxe de
expressões aritméticas são exemplos de estruturas aninhadas.
As pilhas ocorrem também em conexão com algoritmos
recurssivos e estrutura de natureza recursiva, tais como as
árvores.
Em Síntese: Pilha é um caso especial de Lista Linear.
*
TAD Pilha (4/4)
Um tipo abstrato de dados Pilha, acompanhado de um conjunto de
operações, é apresentado a seguir.
1. FazPilhaVazia(Pilha). Faz a pilha ficar vazia.
2. PilhaVazia(Pilha). Esta função retorna 1 (true) se a pilha está vazia; 
 senão retorna 0 (false).
3. Empilha(x, Pilha). Insere o item x no topo da pilha.
4. Desempilha(Pilha, x). Retira o item x que esta no topo da pilha.
5. ImprimePilha(Pilha). Imprime os itens da pilha (do mais recente
 para o menos recente).
Como no caso do tipo abstrato de dados Lista, existem várias opções de
estruturas de dados que podem ser usadas para representar Pilhas. As
duas representações mais utilizadas são as implementações através de
arranjos (vetores) e de apontadores.
*
Implementação de Pilhas através de Arranjos
Em uma implementação através de 
arranjo, os itens da pilha são 
armazenados em posições contíguas de 
memória, conforme ilustra a Figura ao 
lado. Devido as características da pilha
as operações de inserção e de retirada de 
itens devem ser implementadas de forma
diferente das implementações 
apresentadas anteriormente para listas.
Como as inserções e as retiradas ocorrem
no topo da pilha, um campo chamado
Topo é utilizado para controlar a posição
do item no topo da pilha.
 (maxTam – 1)
x1
x2
xn
.
.
.
.
.
.
0
1
Topo = (n – 1)
.
.
.
.
.
.
Item
Pilha
*
Implementação de Pilhas através de Arranjos
// modelo matemático (estrutura de dados)
struct TipoItem {	// cada item da pilha corresponde a um
 char nome[30];	// registro (TipoItem) composto apenas
};			// do campo nome
const maxTam = 10; 	// tamanho máximo da pilha
struct TipoPilha {
 TipoItem Item[maxTam];
 int Topo;
};
O campo Item é o principal componente do registro TipoPilha. Os itens
são armazenados em um vetor de tamanho suficiente para armazenar a
pilha. Já o campo Topo do registro TipoPilha contém o valor da posição 
do item que está no topo da pilha. A constante maxTam define o 
tamanho máximo permitido para a pilha.
*
Implementação de Pilhas através de Arranjos
// Faz a ‘Pilha’ ficar vazia
void FazPilhaVazia(TipoPilha *Pilha) {
 Pilha->Topo = -1;
}
// Esta função retorna 1 (true) se a ‘Pilha’
// está vazia; senão retorna 0 (false)
int PilhaVazia(TipoPilha *Pilha) {
 return(Pilha->Topo == -1);
}
*
Implementação de Pilhas através de Arranjos
// Insere o item 'x' no 'Topo' da 'Pilha'.
int Empilha(TipoItem x, TipoPilha *Pilha) {
 if (Pilha->Topo == (maxTam – 1))
 return(0); // Erro: Pilha Cheia !
 else {
 Pilha->Topo = Pilha->Topo + 1;
// item inserido no topo da pilhaPilha->Item[Pilha->Topo] = x; 
 return(1); // Item inserido com sucesso
 }
}
*
Implementação de Pilhas através de Arranjos
// Retira o item ‘x’ que está no topo da ‘Pilha’
int Desempilha(TipoPilha *Pilha, TipoItem *x) {
 if (PilhaVazia(Pilha))
 return(0); // Erro: Pilha vazia.
 else {
// item retornado
 *x = Pilha->Item[Pilha->Topo];
 Pilha->Topo = Pilha->Topo - 1;
 return(1); // Item retirado com sucesso
 }
}
*
Implementação de Pilhas através de Arranjos
// Imprime os itens da pilha (do mais recente
// para o menos recente).
void ImprimePilha(TipoPilha *Pilha) {
 TipoItem x;
 TipoPilha PilhaAux;
 FazPilhaVazia(&PilhaAux);
 clrscr();
 while (!PilhaVazia(Pilha)) {
 Desempilha(Pilha, &x);
 printf("%s\n", x.nome);
// salva os itens desempilhados da 'Pilha' na 'PilhaAux'
 Empilha(x, &PilhaAux); 	 
 }
// retorna o itens para a pilha original (Pilha)
 while (!PilhaVazia(&PilhaAux)) {
 Desempilha(&PilhaAux, &x);
 Empilha(x, Pilha);
 }
}
*
Implementação de Pilhas através de Apontadores
Uma célula cabeça é mantida no topo 
da pilha para facilitar a implementação
das operações empilha e desempilha
quando uma pilha está vazia. 
Para desempilhar o item xn da pilha 
basta desligar a célula cabeça da lista
e a célula que contém xn passa a ser a
célula cabeça. 
Para empilhar um novo item basta fazer
a operação contrária, criando uma nova
célula cabeça e colocando o novo item 
na antiga célula cabeça.
Item
Apontador
NULL
Celula
Célula
Cabeça
prox
x1
x2
xn
Topo
...
*
Implementação de Pilhas através de Apontadores
// modelo matemático (estrutura de dados)
struct TipoItem {	// cada item da pilha corresponde a um
 char nome[30];	// registro (TipoItem) composto apenas
};			// do campo nome
typedef struct Celula *Apontador;
struct Celula {
 TipoItem Item;
 Apontador prox;
};
struct TipoPilha {
 Apontador Topo;
};
Cada célula de uma pilha contém um item da pilha (campo Item) e um
“apontador” para outra célula (campo prox). O registro TipoPilha 
possui o campo Topo que é o “apontador” para o topo da pilha (célula 
cabeça).
*
Implementação de Pilhas através de Apontadores
// Faz a ‘Pilha’ ficar vazia criando a célula cabeça
void FazPilhaVazia(TipoPilha *Pilha) {
 Pilha->Topo = (Apontador) malloc(sizeof(Celula));
 Pilha->Topo->prox = NULL;
}
// Esta função retorna 1 (true) se a ‘Pilha’ está vazia; 
// senão retorna 0 (false)
int PilhaVazia(TipoPilha *Pilha) {
 return(Pilha->Topo->prox == NULL);
}
*
Implementação de Pilhas através de Apontadores
void FazPilhaVazia(TipoPilha *Pilha) {
 1. Pilha->Topo = (Apontador) malloc(sizeof(Celula));
 2. Pilha->Topo->prox = NULL; 
}
NULL
Pilha->
Topo
1
2
*
Implementação de Pilhas através de Apontadores
// Insere o item 'x' no 'Topo' da 'Pilha'.
void Empilha(TipoItem x, TipoPilha *Pilha) {
 Apontador p;
// cria uma nova célula cabeça
 p = (Apontador) malloc(sizeof(Celula)); 
// coloca o item "x" no topo da pilha, ou seja,
// na antiga célula cabeça
 Pilha->Topo->Item = x;
// atualiza o topo da pilha
 p->prox = Pilha->Topo; 
 Pilha->Topo = p;
}
*
Implementação de Pilhas através de Apontadores
void Empilha(TipoItem x, TipoPilha *Pilha) {
Apontador p;
1. p = (Apontador) malloc(sizeof(Celula)); 
2. Pilha->Topo->Item = x;
3. p->prox = Pilha->Topo; 
4. Pilha->Topo = p;
Pilha->
Topo
xn
...
Apontador
p
1
3
Celula
Item
prox
4
x
2
*
Implementação de Pilhas através de Apontadores
// Retira o item ‘x’ que está no topo da ‘Pilha’
int Desempilha(TipoPilha *Pilha, TipoItem *x) {
 if (PilhaVazia(Pilha))
 return(0); // Erro: Pilha vazia.
 else {
// retira o item xn do topo da pilha e desliga 
// a célula cabeça, a célula que contém xn 
// torna-se a nova célula cabeça
 Apontador p;
 p = Pilha->Topo;
 Pilha->Topo = Pilha->Topo->prox;
 *x = Pilha->Topo->Item; // item retornado
 free(p);
 return(1); // Item retirado com sucesso
 }
}
*
Implementação de Pilhas através de Apontadores
int Desempilha(TipoPilha *Pilha, TipoItem *x) {
Apontador p;
1. p = Pilha->Topo;
2. Pilha->Topo = Pilha->Topo->prox;
3. *x = Pilha->Topo->Item;
4. free(p);
Pilha->
Topo
xn
...
Apontador
p
1
Celula
Item
prox
4
lixo
x
xn
2
3
*
Implementação de Pilhas através de Apontadores
// Imprime os itens da pilha (do mais recente
// para o menos recente).
void ImprimePilha(TipoPilha *Pilha) {
 TipoItem x;
 TipoPilha PilhaAux;
 FazPilhaVazia(&PilhaAux);
 clrscr();
 while (!PilhaVazia(Pilha)) {
 Desempilha(Pilha, &x);
 printf("%s\n", x.nome);
// salva os itens desempilhados da 'Pilha' na 'PilhaAux'
 Empilha(x, &PilhaAux); 	 
 }
// retorna o itens para a pilha original (Pilha)
 while (!PilhaVazia(&PilhaAux)) {
 Desempilha(&PilhaAux, &x);
 Empilha(x, Pilha);
 }
}
*
TAD Fila (1/2)
Uma fila é uma lista linear em que todas as inserções são realizadas em
um extremo da lista, e todas as retiradas e geralmente os acessos são
realizados no outro extremo da lista. 
O modelo intuitivo de uma fila é o de uma fila de espera em que as
pessoas no início da fila são servidas primeiro e as pessoas que chegam
entram no fim da fila. Por esta razão as filas são chamadas de listas
FIFO, termo formado a partir de “First-In, First-Out”.
Existe uma ordem linear para filas que é a “ordem de chegada”. 
Filas são utilizadas quando desejamos processar itens de acordo com a 
ordem “PRIMEIRO-QUE-CHEGA, PRIMEIRO-ATENDIDO”. 
Sistemas operacionais utilizam filas para regular a ordem na qual tarefas
devem receber processamento e recursos devem ser alocados a
processos.
*
TAD Fila (2/2)
Um possível conjunto de operações, definido sobre um tipo abstrato
de dados Fila, é definido a seguir.
1. FazFilaVazia(Fila). Faz a fila ficar vazia.
2. FilaVazia(Fila). Esta função retorna 1 (true) se a fila está vazia; 
 senão retorna 0 (false).
3. Enfileira(x, Fila). Insere o item x no final da fila.
4. Desenfileira(Fila, x). Retira o item x que está no início da fila.
5. ImprimeFila(Fila). Imprime os itens da fila (obedecendo a ordem
 de chegada).
Como no caso do tipo abstrato de dados Lista, existem várias opções de
estruturas de dados que podem ser usadas para representar filas. As
duas representações mais utilizadas são as implementações através de
arranjos (vetores) e de apontadores.
*
Implementação de Filas através de Arranjos
Em uma implementação através de arranjos os itens são armazenados em
posições contíguas de memória. Devido às características da fila, a
operação Enfileira faz a parte final da fila expandir-se, e a operação
Desenfileira faz a parte da frente da fila contrair-se. Conseqüentemente,
a fila tende a caminhar pela memória do computador, ocupando espaço
na parte final e descartando espaço na parte da frente. Com poucas
inserções e retiradas de itens a fila vai de encontro ao limite do espaço
da memória alocado para ela.
A solução para o problema de caminhar pelo espaço alocado para uma
fila é imaginar o vetor com um círculo, onde a primeira posição segue
a última. A fila se encontra em posições contíguas de memória, em
alguma posição do círculo, delimitada pelos apontadores Frente e Final.
Para enfileirar um item basta mover o apontador Final uma posição no
sentido horário; para desenfileirar um item basta mover o apontador
Frente uma posição no sentido horário.
*
Implementação de Filas através de Arranjos
* *
* *
* *
* *
Frente
Final
 .
 .
 .
 .
 .
 .
0
1
(maxTam – 1)
Fila
Item
Tamanho = n
*
Implementação de Filas através de Arranjos
// modelo matemático (estrutura de dados)
struct TipoItem {	// cada item da fila corresponde a um
 char nome[30];	// registro (TipoItem) composto apenas
};			// do campo nome
constmaxTam = 10; 	// tamanho máximo da fila
struct TipoFila {
 TipoItem Item[maxTam];
 int Frente;
 int Final;
 int Tamanho;
};
O campo Item é o principal componente do registro TipoFila. O 
tamanho máximo do vetor circular é definido pela constante maxTam. 
Os outros campos do registro TipoFila contêm apontadores para a parte
da frente (campo Frente) e final (campo Final) da fila. O campo 
Tamanho indica a quantidade de itens armazenados na fila.
*
Implementação de Filas através de Arranjos
Na representação circular da Fila existe um pequeno problema: não há
uma forma de distinguir uma fila vazia de um fila cheia, pois nos dois 
casos os apontadores Frente e Final apontam para a mesma posição do
círculo. 
Uma possível saída para este problema é utilizar um campo extra 
(Tamanho) para indicar a quantidade de itens armazenados na fila.
Neste caso:
1) a fila está cheia quando Tamanho for igual a maxTam, e, 
2) a fila está vazia quando Tamanho for igual a 0 (zero).
*
Implementação de Filas através de Arranjos
// Faz a ‘Fila’ ficar vazia
void FazFilaVazia(TipoFila *Fila) {
 Fila->Frente = 0;
 Fila->Final = 0;
 Fila->Tamanho = 0;
}
// Esta função retorna 1 (true) se a ‘Fila’
// está vazia; senão retorna 0 (false)
int FilaVazia(TipoFila *Fila) {
 return(Fila->Tamanho == 0);
}
*
Implementação de Filas através de Arranjos
// Insere o item 'x' no 'Final' da 'Fila'.
int Enfileira(TipoItem x, TipoFila *Fila) {
 if (Fila->Tamanho == maxTam)
 return(0);		// Erro: Fila Cheia !
 else {
// item inserido no final da fila
 Fila->Item[Fila->Final] = x; 
 Fila->Final = Fila->Final + 1;
// se última posição então volta para a primeira 
// posição do vetor (vetor circular)
 if (Fila->Final == maxTam)
 Fila->Final = 0; 
 Fila->Tamanho = Fila->Tamanho + 1; 
 return(1); // Item inserido com sucesso
 }
}
*
Implementação de Filas através de Arranjos
// Retira o item ‘x’ que está na frente da ‘Fila’
int Desenfileira(TipoFila *Fila, TipoItem *x) {
 if (FilaVazia(Fila))
 return(0); // Erro: Fila vazia.
 else {
// item retornado
 *x = Fila->Item[Fila->Frente]; 
 Fila->Frente = Fila->Frente + 1;
// se última posição então volta para a primeira 
// posição do vetor (vetor circular)
 if (Fila->Frente == maxTam)
 Fila->Frente = 0;
 Fila->Tamanho = Fila->Tamanho - 1; 
 return(1); // Item retirado com sucesso
 }
}
*
Implementação de Filas através de Arranjos
// Imprime os itens da fila obedecendo
// a ordem de chegada.
void ImprimeFila(TipoFila *Fila) {
 TipoItem x;
 clrscr();
 for (int i=1; i<=Fila->Tamanho; i++) {
 Desenfileira(Fila, &x);
 printf("%s\n", x.nome);
 Enfileira(x, Fila);
 }
}
*
Implementação de Filas através de Apontadores
Uma célula cabeça é mantida para facilitar a implementação das
operações Enfileira e Desinfileira quando a fila está vazia. Quando a
fila está vazia os Apontadores Frente e Final apontam para a célula
cabeça. Para enfileirar um novo item basta criar uma célula nova,
ligá-la após a célula que contém xn e colocar nela o novo item. Para
desenfileirar o item x1 basta desligar a célula cabeça da lista e a célula
que contém x1 passa a ser a célula cabeça.
Item
Apontador
Celula
Célula
Cabeça
Frente
prox
...
x1
x2
xn
Final
NULL
Tamanho = n
*
Implementação de Filas através de Apontadores
// modelo matemático (estrutura de dados)
struct TipoItem {	// cada item da fila corresponde a um
 char nome[30];	// registro (TipoItem) composto apenas
};			// do campo nome
typedef struct Celula *Apontador;
struct Celula {
 TipoItem Item;
 Apontador prox;
};
struct TipoFila {
 Apontador Frente;
 Apontador Final;
 int Tamanho;
};
A fila é implementada através de células, onde cada célula contém um
item da fila (campo Item) e um “apontador” para outra célula (campo 
prox). O registro TipoFila contém um “apontador” para a Frente da fila 
(célula cabeça) e um “apontador” para a parte Final da fila. O campo 
Tamanho indica a quantidade de itens armazenados na fila.
*
Implementação de Filas através de Apontadores
// Faz a ‘Fila’ ficar vazia criando a célula cabeça
void FazFilaVazia(TipoFila *Fila) {
 Fila->Frente = (Apontador) malloc(sizeof(Celula));
 Fila->Final = Fila->Frente;
 Fila->Frente->prox = NULL;
 Fila->Tamanho = 0;
}
// Esta função retorna 1 (true) se a ‘Fila’ está vazia; 
// senão retorna 0 (false)
int FilaVazia(TipoFila *Fila) {
 return(Fila->Tamanho == 0);
}
*
Implementação de Filas através de Apontadores
void FazFilaVazia(TipoFila *Fila) {
1. Fila->Frente = (Apontador) malloc(sizeof(Celula));
2. Fila->Final = Fila->Frente;
3. Fila->Frente->prox = NULL;
4. Fila->Tamanho = 0;
}
Fila->
Frente
Final
Tamanho
1
3
0
4
2
NULL
*
Implementação de Filas através de Apontadores
// Insere o item 'x' no 'Final' da 'Fila'.
void Enfileira(TipoItem x, TipoFila *Fila) {
// cria uma nova célula no final da fila
 Fila->Final->prox = (Apontador) malloc(sizeof(Celula));
 Fila->Final = Fila->Final->prox;
// coloca o item ‘x’ na nova célula
 Fila->Final->Item = x;
 Fila->Final->prox = NULL;
// atualiza o tamanho da fila
 Fila->Tamanho = Fila->Tamanho + 1;
}
*
Implementação de Filas através de Apontadores
void Enfileira(TipoItem x, TipoFila *Fila) {
1. Fila->Final->prox = (Apontador) malloc(sizeof(Celula));
2. Fila->Final = Fila->Final->prox;
3. Fila->Final->Item = x;
4. Fila->Final->prox = NULL;
5. Fila->Tamanho = Fila->Tamanho + 1;
}
Item
Apontador
NULL
Celula
Célula
Cabeça
prox
...
x1
xn
1
Fila->
Frente
Final
Tamanho
n
n + 1
4
NULL
x
3
5
2
*
Implementação de Filas através de Apontadores
// Retira o item ‘x’ que está na frente da ‘Fila’
int Desenfileira(TipoFila *Fila, TipoItem *x) {
 if (FilaVazia(Fila))
 return(0); // Erro: Fila vazia.
 else {
// retira o item x1 da frente da fila e desliga 
// a célula cabeça, a célula que contém x1 
// torna-se a nova célula cabeça
 Apontador p;
 p = Fila->Frente;
 Fila->Frente = Fila->Frente->prox;
// item retornado
 *x = Fila->Frente->Item; 
 free(p);
// atualiza o tamanho da fila
 Fila->Tamanho = Fila->Tamanho - 1;
 return(1); // Item retirado com sucesso
 }
}
*
Implementação de Filas através de Apontadores
int Desenfileira(TipoFila *Fila, TipoItem *x) {
Apontador p;
1. p = Fila->Frente;
2. Fila->Frente = Fila->Frente->prox;
3. *x = Fila->Frente->Item; 
4. free(p);
5. Fila->Tamanho = Fila->Tamanho - 1;
Item
Apontador
NULL
Celula
Célula
Cabeça
prox
...
x1
xn
1
Fila->
Frente
 Final
Tamanho
n
n - 1
4
p
5
2
lixo
x
x1
3
*
Implementação de Filas através de Arranjos
// Imprime os itens da fila obedecendo
// a ordem de chegada.
void ImprimeFila(TipoFila *Fila) {
 TipoItem x;
 int n = Fila->Tamanho;
 clrscr();
 for (int i=1; i<=n; i++) {
 Desenfileira(Fila, &x);
 printf("%s\n", x.nome);
 Enfileira(x, Fila);
 }
}
*
Casos Especiais de Listas Encadeadas (1/2)
Lista Circular Encadeada
Uma pequena modificação na estrutura física da lista pode ser de grande auxílio: obrigar o último nó da lista a apontar para o nó cabeça, criando assim uma lista circular encadeada.
Item
Apontador
Celula
Célula 
Cabeça
Primeiro
prox
...
x1
x2
xn
Ultimo
*
Casos Especiais de Listas Encadeadas (2/2)
Lista Duplamente Encadeada
A estrutura da célula de uma lista duplamente encadeada, com os campos prox- aponta para o próximo nó, ou sucessor e ant- aponta para o nó anterior, ou antecessor; é possível percorrer a lista nos dois sentidos indiferentemente.
Item
Apontador
Celula
Primeiro
prox
...
x1
x2
xn
Ultimo
NULL
NULL
ant
...
*
Referências
Projeto de Algoritmos: com implementações em C e Pascal.
Nivio Ziviani.4ª ed. - São Paulo: Pioneira - 1999.
Estrutura de Dados Fundamentais: conceitos e aplicações.
Silvio do Lago Pereira.
2ª ed. - São Paulo: Érica, 1996.