Introdução ao Conceito de Pilhas e Filas Utilizando Listas Encadeadas

INSTITUTO FEDERAL FLUMINENSE IFF Campus Itaperuna Disciplina de Estruturas de Dados Professor Leandro Fernandes dos Santos Assunto Introducao ao conceito de Pilhas e Filas utilizando listas encadeadas Listas Encadeadas Uma lista encadeada pode ser descrita como sendo uma estrutura de dados organizada de modo linear sendo todos de um mesmo tipo Segundo Thomas Cormen em uma lista encadeada a ordem de seus componentes e determinada pela existˆencia de um ponteiro que cada objeto possui diferentemente de um arranjo onde a ordem dos elementos e de crita pelo seu ındice Este tipo de estrutura de dados fornece uma visao bastante flexıvel para conjuntos onde o dinamismo e predominante As listas encadeadas suportam varias operacoes tais como busca insercao delecao etc A Figura 1 mostra a representacao esquematica comumente utilizada na literatura para representar uma lista encadeada Figura 1 Representacao de uma lista encadeada Onde InıcioL Ponteiro para o inıcio da lista Elemento Campo que guarda o elemento neste caso um numero inteiro Proximo Ponteiro para o proximo item da lista O ultimo ponteiro da lista do modelo apresentado na Figura 1 apontapara um local especıfico denominado NULL Este tipo de referˆencia e utilizada quando se quer dizer que o ponteiro nao ira apontar para lugar algum na memoria Dependendo dos requisitos podese tambem possuir listas duplamente encadeadas neste tipo de lista existem dois ponteiros de referˆencias para cada no sendo um para o proximo elemento e outro para o elemento anterior Podese tambem implementar listas do tipo circular onde o ultimo ponteiro da lista ao inves de apontarpara NULL ira referenciar o primeiro elemento Fila E um conceito comum que pode ser observado em alguns contextos como a fila de um banco ou a fila para entrada em um estadio de futebol Em computacao a fila queue e um tipo abstrato de dados que tem por principal caracterıstica que o primeiro elemento a ser inserido sera tambem o primeiro a ser removido First In First Out FIFO 1 Instituto Federal FluminenseIFF Campus Itaperuna Segundo Aaron Tenenbaum uma fila pode ser descrita como um conjunto ordenado de itens sobre o qual podese eliminar itens dequeue em uma determinada extremidade tambem chamada de inıcio da fila e inserılos enqueue em outra tambem chamada de final da fila A Figura 2 mostra um representacao de uma fila implementada com listas encadeadas Figura 2 Representacao de uma fila usando lista encadeada Onde InıcioF Ponteiro para o inıcio da fila Fim Ponteiro que marca o final da fila Elemento Campo que guarda o elemento da fila Proximo Ponteiro para o proximo item da fila As filas tambem podem variar dependendo do problema a ser resolvido desta maneira podese ter filas circulares e filas duplamente encadeadas Pilha Este e tambem outro tipo abstrato de dados muito utilizado no meio computacional Uma estrutura do tipo pilha possui a seguinte premissa O primeiro elemento a ser inserido sera o ultimo a ser removido First In Last Out FILO Deste modo as principais operacoes realizadas sobre uma pilha sao empilhar Push e desempilhar Pop A Figura 3 mostra como uma pilha pode ser vista quando implementada usando o conceito de listas encadeadas 2 Instituto Federal FluminenseIFF Campus Itaperuna Figura 3 Representacao de uma pilha usando lista encadeada Onde TopoP Constitui um ponteiro para o topo da pilha neste caso referenciando o ultimo elemento inserido Elemento Campo que guarda o elemento da pilha Proximo Ponteiro para o proximo item da pilha A implementacao de cada dos tipos de estruturas apresentadas fila e pilha podera ser diferenciada pois ira depender do objetivo em especıfico para o qual as estruturas serao utilizadas Possıveis representacoes e definicao de implementacoes Nesta secao sera definido como as estruturas de fila e pilha podem ser implementadas Definicao da implementacao da Fila A estrutura de fila pode ser implementada como uma lista encadeada circular Nesta estrutura podese tambem fazer o uso de uma celula cabeca Deste modo A celula cabeca nao e removida nem mesmo se a fila estiver vazia O primeiro elemento da fila ficara na segunda celula e o ultimo ficara na celula anterior ao no cabeca O ponteiro inıcio guardara o endereco do no cabeca O ponteiro fim guardara o endereco do ultimo elemento da fila A Figuras 4 5 6 e 7 mostram como esta abstracao pode ser vista 3 Instituto Federal FluminenseIFF Campus Itaperuna Figura 4 Representacao de fila vazia Figura 5 Representacao da fila com 3 elementos Figura 6 Representacao da fila apos a insercao de um novo elemento Figura 7 Representacao da fila apos a remocao de um elemento Definicao da implementacao da Pilha Na implementacao da pilha tambem pode ser utilizada uma lista encadeada com uma celula cabeca Sendo assim Um ponteiro chamado topoguarda o endereco do topo da pilha A celula cabeca nao e removida nem mesmo se a pilha estiver vazia 4 Instituto Federal FluminenseIFF Campus Itaperuna O ultimo elemento da pilha topo ficara na segunda celula e o primeiro ficara no final base da pilha As Figuras 8 9 10 e 11 mostram como esta abstracao pode ser vista Figura 8 Representacao da pilha vazia Figura 9 Representacao da pilha com 3 elementos Figura 10 Representacao da pilha apos a insercao de um novo elemento Figura 11 Representacao da pilha apos a remocao de um elemento 5 Instituto Federal FluminenseIFF Campus Itaperuna Referˆencias Tenenbaum A M and Langsam Y and Augenstein M J Estruturas de dados usando C Pearson Makron Books 2004 Leiserson C E and Stein C and Rivest R L and Cormen T H Algoritmos Teoria e Pratica Editora Campus 2002 6