Baixe o app para aproveitar ainda mais
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); } }
Compartilhar