Pilhas e Filas

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

*
Pilhas
*
O que é uma pilha?
1
4
3
2
Pilha
1
4
3
2
*
O que é uma pilha?
Pilha
1
4
3
2
*
Pilha
Tipo Abstrato de dados com a seguinte característica:
O primeiro elemento a entrar é o último a ser retirado/ removido
(FILO – First in Last Out)
Analogia: pilha de pratos, livros, etc.
Usos: Chamada de subprogramas, avalição de expressões aritméticas, etc.
*
Pilha
Operações comuns:
1. Push(x, Pilha). Insere o item x no topo da pilha.
2. Pop(Pilha, x). Retorna o item x no topo da pilha, retirando-o da pilha.
3. Top(Pilha):Retorna o topo da pilha
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 por meio de arranjos e de apontadores
*
Implementação de Pilhas 
através de Arranjos
Os itens da pilha são armazenados em posições contíguas de memória.
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.
*
Implementação de Pilhas 
por meio de Apontadores
Há uma célula cabeça no topo (ponteiro prim).
Para desempilhar o item xn basta eliminar 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.
Nesta implementação teremos as seguintes funções: Push, Pop e Top (retorna o topo da pilha)
*
Estrutura da Pilha Usando Apontadores
struct ItemPilha{
 	int Item;
 	struct ItemPilha *prox;
}*prim, *ult;
*
Operações sobre Pilhas
usando Apontadores
void Push(int x)
{
	struct ItemPilha *aux;
	aux = (struct ItemPilha *) malloc(sizeof(struct ItemPilha));
	if(!ult)
	{
		ult = aux;
		ult->prox = NULL;
	}
	else
 	aux->prox = prim;
	prim = aux;
	prim->Item = x;
	cout << “Elemento empilhado”;
}
*
Operações sobre Pilhas
usando Apontadores
int Pop()
{
	int ret;
	struct ItemPilha *aux;
	if (! prim)
 { 
		return(-1);
 }
	else
	{ 
		ret = prim->Item;
		aux = prim;
		if(prim == ult)		
			prim = ult = NULL;
 else
		 	prim = prim->prox;
		free(aux);
		return(ret);
	}
}
*
Operações sobre Pilhas
usando Apontadores
int Top()
{
 if (!prim)
 { 
 return(-1);
 }
 else
 {
 return(prim->Item);
 }
}
*
Filas
*
O que é uma fila?
1
4
3
2
*
O que é uma fila?
1
4
3
2
*
O que é uma fila?
1
4
3
2
*
O que é uma fila?
1
4
3
2
*
O que é uma fila?
1
4
3
2
*
O que é uma fila?
1
4
3
2
*
O que é uma fila?
1
4
3
2
*
O que é uma fila?
1
4
3
2
*
O que é uma fila?
1
4
3
2
*
Fila
Tipo Abstrato de dados com a seguinte característica:
O primeiro elemento a ser inserido é o primeiro a ser retirado/ removido
(FIFO – First in First Out)
Analogia: filas de qualquer natureza, de bancos, de supermercados, etc.
Exemplo de uso: Filas de execução de processos em sistemas operacionais.
*
Fila
Operações comuns:
1. Enfileirar(x, Fila). Insere o item x no final da fila.
2. Desenfileirar(Fila, x). Retorna o item x do início da fila, retirando-o da mesma.
3. Cabeca(Fila):Retorna o elemento do início da fila
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 por meio de arranjos e de apontadores
*
Implementação de Filas 
através de Arranjos
Os itens da fila são armazenados em posições contíguas de memória.
Nesta implementação um campo chamado Topo será utilizado para controlar a posição do item no final da fila.
*
Implementação de Filas 
por meio de Apontadores
Há uma célula cabeça no topo (ponteiro prim).
Para desenfileirar o item xn basta eliminar a célula final da lista 
Para enfileirar um novo item, basta criar uma nova célula e anexá-la no final da lista.
Nesta implementação teremos as seguintes funções: Enfileirar, Desenfileirar e Cabeca (retorna o topo da fila)
*
Estrutura da Fila Usando Apontadores
struct ItemFila{
 	int Item;
 	struct ItemFila *prox;
} *prim, *ult;
*
Operações sobre Filas
usando Apontadores
void Enfileirar(int x)
{
	struct ItemFila *aux;
	aux = (struct ItemFila *) malloc(sizeof(struct ItemFila));
	if(! prim)
		prim = aux;
	else
		ult->prox = aux;
	ult = aux;
	ult->Item = x;
	ult->prox = NULL;
	cout << “Elemento enfileirado!”;
}
*
Operações sobre Filas
usando Apontadores
int Desenfileirar()
{
 int ret;
	struct ItemFila *aux;
	if (! prim)
	{ 
		return(-1);
	}
	else
	{ 
		ret = prim->Item;
		aux = prim;
		if(prim == ult)		
			prim = ult = NULL;
 else
		 	prim = prim->prox;
		free(aux);
		return(ret);
	}
}
*
Operações sobre Pilhas
usando Apontadores
int Cabeca()
{
 if (! prim)
 { 
		return(-1);
 }
 else
 {
		return(prim->Item);
 }
}