Estruturas de dados - pilhas, filas e deques

UNIUBE – UNIVERSIDADE DE UBERABA

ESTRUTURAS DE DADOS E ALGORITMOS – RESUMO DO CAPÍTULO VI

UBERABA - MG
2014

1. PILHAS, FILAS E DEQUES

De início, o autor faz uma breve definição do funcionamento de cada uma desses esquemas de sobreposição de itens. Para entender todos os temas abordados no capítulo é necessário fazer uma leitura prévia dos capítulos anteriores, principalmente o quinto. No quinto capítulo o autor aborda o tema container e também abstração de dados, conceitos fundamentais para entender o funcionamento dos códigos apresentados durante o sexto capítulo.
1.1 Pilhas
Nessa seção foram explicados o funcionamento de todos os processos de manipulação de uma pilha: a inserção, a remoção e a consulta. Como dito anteriormente, todos os códigos se baseiam em uma estrutura pré-definida, sendo assim os métodos e parâmetros podem parecer bem diferentes do que estamos acostumados a utilizar durante as aulas.
O conceito de pilha não muda. O autor identifica a pilha como sendo uma estrutura LIFO (last in first out), onde um dado novo é o último a entrar e o primeiro a sair. Além disso, relata os dois tipos de implementação que podem acontecer em uma pilha: a inserção por meio de vetores e por meio de listas encadeadas.
1.1.1 Implementação por vetor
Para a implementação desse tipo de pilha, foram definidos os métodos construtor e purge; no construtor é inicializado o vetor e no método purge é feita uma exclusão de todos os elementos contidos na pilha.
Em seguida o autor aborda os métodos mais comuns na manipulação dessa estrutura, os métodos push, pop e getTo. O método push é responsável pela inserção de elementos no vetor; primeiramente ele verifica se há espaço para alocar um valor, se existe, o valor é adicionado e a pilha passa a ter o valor um somado ao seu tamanho, se não existe é chamada uma exceção.
O método pop remove um elemento da pilha, diferentemente do purge. Ele também trata as exceções,