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): Insere o item x no topo da pilha
2. Pop(): Elimina o item do topo da pilha
3. Top():Retorna o item do 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 que é representada pelo ponteiro prim.
Para desempilhar um item basta eliminar a célula cabeça da lista, fazendo o ponteiro prim passar a ser o segundo elemento da lista.
Para empilhar um novo item, basta fazer a operação contrária, criando uma nova célula cabeça e fazendo o ponteiro prim passar a ser esta célula.
*
O Algoritmo de uma Pilha
*
#include<iomanip.h>
//REGISTROS
struct ItemPilha{
 	int Item;
 	struct ItemPilha *prox;
}*prim, *ult, *aux;
//ASSINATURAS
void Push(int x);
void Pop();
struct ItemPilha *Top();
*
main(){
	prim = ult = NULL; 
	int op=-1, n; 
	while(op!=0){
		cout << "1-PUSH\n2-POP\n3-TOP\n0-Sair\n\n";
	 	cout << "Digite uma opcao: ";
 	cin >> op;fflush(stdin);
 	if(op==1){
			cout << "Digite um numero inteiro a ser empilhado: ";
			cin >> n; 
			Push(n);
		}
		else if(op==2){
			if(Top()){
				aux = Top();
				cout << "Elemento "<<aux->Item<<" desenpilhado!\n";
 		Pop();
 	}
			else cout << "Pilha vazia\n";
	 	}
		else if(op==3){
			if(Top()){
				aux = Top();
				cout << "Topo da pilha: "<<aux->Item<<"\n";
			}
			else cout << "Pilha vazia\n";
		}		
	} 
} 
*
void Push(int x)
{
	aux = (struct ItemPilha *) malloc(sizeof(struct ItemPilha));
	if(!ult)
	{
 aux->prox = NULL;
 ult = aux; 
 }
	else
 aux->prox = prim;
	prim = aux;
	prim->Item = x;
}
*
void Pop()
{
	struct ItemPilha *aux;
	if (!prim)
 { 
		cout << "Erro lista vazia\n";
	}
	else
	{ 
		aux = prim;
		if(prim == ult)		
 prim = ult = NULL;
 else
		 prim = prim->prox;
 free(aux);
	} 
}
*
struct ItemPilha *Top()
{
 return(prim);
}
*
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). Insere o item x no final da fila.
2. Desenfileirar(). Retira da fila o primeiro item da mesma.
3. Cabeca():Retorna o primeiro elemento 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 início da fila que é representada pelo ponteiro prim.
Para desenfileirar um item basta eliminar a célula cabeça da lista, fazendo o ponteiro prim passar a ser o segundo elemento da lista.
Para enfileirar um novo item, basta criar uma nova célula que deverá ser adicionada no final da fila (novo último elemento).
*
O Algoritmo de uma Fila
*
#include<iomanip.h>
//REGISTROS
struct ItemFila{
 	int Item;
 	struct ItemFila *prox;
}*prim, *ult, *aux;
//ASSINATURAS
void Enfileirar(int x);
void Desenfileirar();
struct ItemFila *Cabeca();
*
main(){
	prim = ult = NULL;
	int op=-1, n; 
	while(op!=0)
	{
	 cout << "1-Enfileirar\n2-Desenfileirar\n3-Cabeça da Fila\n0-Sair\n\n";
	 cout << "Digite uma opcao: ";
 cin >> op;fflush(stdin);
	 if(op==1){
		cout << "Digite um numero inteiro a ser enfileirado: ";
		cin >> n; 
		Enfileirar(n);
 }
 else if(op==2){
		aux = Cabeca();
		if(aux){
 cout << "Elemento \n" << aux->Item<< " desenfileirado!\n";
 Desenfileirar();
		}
		else cout << "Fila vazia\n";
	 }
	 else if(op==3){
		aux = Cabeca();
		if(aux)
		 cout << "Cabeca da fila: " << aux->Item << endl;
		else 
		 cout << "Fila vazia\n";
	 }
	}
} 
*
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;
}
*
void Desenfileirar()
{
	struct ItemFila *aux;
	if (!prim)
	{ 
		cout << "Erro lista vazia\n";
	}
	else
	{ 
		aux = prim;
		if(prim == ult)		
		 prim = ult = NULL;
 else
		 prim = prim->prox;
		free(aux);
	}
}
*
struct ItemFila *Cabeca()
{
 return(prim);
}