LISTAS LINEARES, FILA E PILHA

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

*
Estrutura de Dados
José Marcos Barbosa da Silveira
jmarcosbs@hotmail.com
*
Objetivos
 Tipos de Listas Lineares 
Objetivo: Apresentar os vários tipos de listas lineares, aplicações e implementações.
*
Esquematicamente 
LISTA
PILHA
FILA
FILA DUPLA
*
Fundamentos 
Uma Lista Linear é uma coleção L:[a1, a2 ...an], n>=0
Podem ser:
Pilha: lista linear onde todas as inserções, remoções e acessos são realizados em um único extremo. Lista com esta característica são também denominadas listas LIFO (Last-In/First-Out).
Fila: lista linear onde todas as inserções são feitas num certo extremo e todas as remoções e acessos são realizados no outro. Filas são também denominadas listas FIFO (First-In/First-Out).
Fila Dupla: lista linear onde as inserções, remoções ou acessos são realizados em qualquer extremo. Filas Duplas são também denominadas DEQUE (Double-Ended QUEue).
*
Considerações 
Ao codificar um programa que utiliza listas para armazenar dados, dificilmente iremos usar todas as operações que podem ser feitas com listas lineares.
É extremamente difícil de se obter uma implementação onde todas as operações sejam realizadas com a mesma eficiência.
*
Pilhas - Conceitos 
As Pilhas são estruturas que tomam como regra a expressão LIFO (Last In First Out), ou seja, O último elemento a ser inserido será o primeiro elemento a ser retirado. Como uma pilha de livros o primeiro elemento da pilha não pode ser retirado até que os outros elementos acima sejam retirados antes e sempre que se incluir um elemento na estrutura este elemento é inserido no final ou no topo da pilha. 
*
Conceitos (cont.) 
É uma estrutura dinâmica – uma coleção que pode aumentar e diminuir durante a sua existência.
Solução para muitos problemas clássicos.
 Ex: Pilha de pratos.
Representações gráficas:
entra
sai
topo
base
a1
a2
a3
...
an-1
an
Topo
*
Operações 
Dessa forma, uma pilha tem as seguintes funções: 
Operações Associadas:
1. criar (P) - criar uma pilha P vazia;
2. inserir (x, P) - insere x no topo de P (push);
3. vazia (P) - testa se P está vazia;
4. topo (P) - acessa o elemento do topo da pilha (sem eliminar);
5. elimina (P) - elimina o elemento do topo de P (pop);
6. cheia (P) - testa se a pilha esta cheia.
*
Operações (cont.) 
Note que não há como eu tirar um elemento do meio da pilha. 
É como nossa pilha de livros, para retirar um livro do meio, tenho que desempilhar todos os que estão acima. Da mesma forma, para tirar um dado do meio da pilha, tenho que desempilhar os que estão antes dele. 
Um exemplo prático de Estruturas de Dados tipo Pilha pode ser demonstrado como, por exemplo, a lista de "últimas chamadas" (feitas ou recebidas) na memória de um telefone celular. Sempre a última chamada é a que aparece ao consultarmos esta lista, ou seja, o último valor a entrar é o primeiro a ser consultado (sair). E os seguintes são sempre nesta ordem de mais 'novos' até o mais 'antigo'.
*
IMPLEMENTAÇÃO DE UMA PILHA - Arranjo
	- Os elementos de uma pilha são armazenados sequencialmente;
	- A inclusão e remoção de elementos da pilha não exigem movimentação de dados;
	- O esquema de alocação de memória sequencial é adequado.
	
FORMA DE REPRESENTAR UMA PILHA NA MEMÓRIA
	- É necessário um vetor para armazenar os elementos;
	- É necessário um índice para indicar a posição corrente do topo da pilha;
	- É declarado um registro contendo o índice e o vetor.
*
/* Estrutura da Pilha */
using namespace std;
const int MAX=10;
typedef struct TipoItem{
 	int cpf;
 	char nome[30];
 }Tipo;
typedef struct tipoPilha{
 	TipoItem item[MAX];
 	int topo;
 }Pilha;
IMPLEMENTAÇÃO DE UMA PILHA - Arranjo
*
INICIALIZAÇÃO DE UMA PILHA
	- Colocar um valor 0 no índice, indicando que não há nenhum elemento na pilha;
	- Como ainda não há nenhum elemento na pilha, o vetor dos elementos não precisa ser inicializado.
CÓDIGO
void inicializa(Pilha &p){
 p.topo=0;
}
COMENTÁRIOS
	- Procedimento pois não há necessidade de retorno;
	- Parâmetro passado por referência pois deseja-se modificar o valor de p.topo;
	- Feito sob a forma de rotina para encapsular a inicialização de qualquer pilha desejada.	
*
VERIFICAÇÃO SE UMA PILHA ESTÁ VAZIA
	- Verificar se p.topo=0, se é verdade a pilha está vazia.
CÓDIGO
int vazia(Pilha &p){
 if(p.topo==0) return 0;
 else
 return p.topo;
}
COMENTÁRIOS
	- Função pois há necessidade de retorno;
	- Parâmetro passado por referência. 
	
*
VERIFICAÇÃO SE UMA PILHA ESTÁ CHEIA
	- Verificar se p.topo=MAX, se é verdade a pilha está cheia.
CÓDIGO
int cheia(Pilha &p){
	if (p.topo= MAX)
		return 0;
	else
		return 1;
}
COMENTÁRIOS
	- Função pois há necessidade de retorno;
	- Parâmetro passado por referência. 
*
INSERIR UM ELEMENTO NUMA PILHA 
	- Verificar se a pilha está cheia, caso negativo inserir senão não efetivar a inserção. 
CÓDIGO
int push(Pilha &p, int cpf,char nome[]){
 if (p.topo==MAX) return 1;
 else{
 p.item[p.topo].cpf=cpf;
 strcpy( p.item[p.topo].nome, nome);
 p.topo=p.topo+1;
 return 0;
 }	
}
COMENTÁRIOS
	- Função pois há necessidade de retorno;
	- Parâmetros cpf e nome passados por valor pois não precisa serem modificados.
*
REMOVER UM ELEMENTO DE UMA PILHA 
	- Verificar se a pilha está vazia, caso negativo remover senão não efetivar a remoção.
 
CÓDIGO
int pop(Pilha &p){
 if (vazia(p)==0)return 0;
 else
 return (p.topo=p.topo-1);
}
COMENTÁRIOS
	- Função pois há necessidade de retorno do elemento removido;
	- A remoção é lógica, mas o elemento não pode ser acessado.
*
ACESSANDO O ELEMENTO DO TOPO DE UMA PILHA 
	- Verificar se a pilha não está vazia, caso positivo acessar senão não efetivar o acesso.
 
CÓDIGO
TipoItem topo(Pilha &p){
	return (p.item[p.topo-1]);
}
COMENTÁRIOS
	- Função pois há necessidade de retorno do elemento acessado;
	- Não há alteração no estado da pilha.
	
*
IMPLEMENTAÇÃO DE UMA PILHA - Apontador
Assim como na implementação de listas lineares por meio de apontadores, uma célula cabeça é mantida no topo da pilha para facilitar a implementação das operações empilha (push) desempilha (pop) quando a pilha está vazia. Para desempilhar o item xn 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. 
*
IMPLEMENTAÇÃO DE UMA PILHA - Apontador
/* Criação da estrutura */
struct pilha 
{ 
 int valor; 
 pilha *prox; 
}; 
pilha *topo;
/* Inicializa a Pilha */
 void init(){
 	pilha *topo = NULL; /* Topo aponta para nada */ 
 }
*
IMPLEMENTAÇÃO DE UMA PILHA - Apontador
/* inserção no início: retorna a pilha atualizada */
void push(int valor){ 
 pilha * no; 
 no = new pilha; 
 if(no==NULL){ 
 printf("Pilha Cheia !"); 
 } 
 else{ 
 no->valor = valor; 
 no->prox = topo; 
 topo = no; 
 } 
} 
*
IMPLEMENTAÇÃO DE UMA PILHA - Apontador
/* Desempilha a pilha*/
int pop(void){ 
 int valor; 
 pilha * temp; 
 if(topo==NULL){ 
 printf("Pilha Vazia"); 
 } 
 else{ 
 valor = topo->valor; 
 temp = topo->prox; 
 delete topo; 
 topo = temp; 
 return(valor); 
 } 
} 
*
IMPLEMENTAÇÃO DE UMA PILHA - Apontador
/* função imprime: elementos da Pilha*/
void imprime (void){
	pilha* p; /* variável auxiliar para percorrer a Pilha */
	printf("\nImpressão da Pilha\n");
	for (p = topo; p != NULL; p = p->prox)
		printf("Valor = %d\n", p->valor);
}
*
Exercício
Implementar a Pilha através de arranjo e apontadores, todos os métodos:
1. criar (P) - criar uma pilha P vazia;
2. inserir (x, P) - insere x no topo de P (push);
3. vazia (P) - testa se P está
vazia;
4. topo (P) - acessa o elemento do topo da pilha (sem eliminar);
5. elimina (P) - elimina o elemento do topo de P (pop);
6. cheia (P) - testa se a pilha esta cheia.
*
Bibliografia
Veloso, P. A.S. ESTRUTURAS DE DADOS. CAMPUS, 2000.
Pereira, Silvio do Lago. Estrutura de dados Fundamentais. ÉRICA, 1996.
Bucknall, J. ALGORITIMOS E ESTRUTURAS DE DADOS COM DELPHI. BERKELEY BRASIL, 2002.
Wirth, N. ALGORITMOS E ESTRUTURAS DE DADOS. LTC, 1989.
Szwarcfiter, J. L. ESTRUTURAS DE DADOS E SEUS ALGORITMOS. LTC, 1994.
*
*
*
*
*
*
*
*
*
*
*
*
*