Tema 03 - 02 - TEXTO DE APOIO AO ESTUDO

Prévia do material em texto

DISCIPLINA: ESTRUTURA DE DADOS
TEMA 03: Listas com disciplinas de acesso
TEXTO PARA APOIO AO ESTUDO
Objetivos: entender o que são as disciplinas de acesso nas listas lineares e conhecer as principais
estrutura de dados decorrentes dessas disciplinas nas listas lineares.
1. Introdução
Como visto em aulas anteriores, as listas lineares, como outras estruturas de dados, possuem como
principais operações a inserção, a remoção e a busca de elementos. Entretanto, dependendo da política de
acesso a uma lista linear, ou seja, dependendo das restrições sobre as inserções e remoções de dados, tal
lista pode ser conhecida como ou uma fila, ou uma pilha, ou um deque. A figura abaixo, também presente
no material da aula passada, mostra que fila, pilha e deque são casos particulares de uma lista linear, onde,
como já citado, restrições de acesso são impostas. Uma observação importante é que tais listas (fila, pilha e
deque) podem ser implementadas por alocação estática (lista sequencial) ou alocação dinâmica (lista
encadeada) de memória. Listas encadeadas é um assunto que veremos nas próximas aulas.
2. Pilha
Pilhas são estruturas de dados do tipo LIFO (last-in first-out): o último elemento a ser inserido, será
o primeiro a ser removido. Manipulação dos elementos em apenas uma das extremidades chamada de
topo, ou seja, Inserção e remoção apenas em um extremo. Situações reais que remetem à ideia pilha: pilha
de pratos, pilha de livros, pilha de cartas de um baralho, etc.
 
1 Estrutura de dados
Operações:
 Inserção: Empilha() ou Push()
 Remoção: Desempilha() ou Pop() 
As duas mudanças que podem ser introduzidas numa pilha recebem nomes especiais. Quando um item é
incluído numa pilha, ele é empilhado sobre a pilha e, quando um item é removido, ele é desempilhado.
Em função de uma pilha s e de um item i, executar a operação push(s, i) incluirá o item i no topo da pilha
s. De modo semelhante, a operação pop(s) removerá o elemento superior e o retornará como valor da
função. Assim, a operação de atribuição:
i = pop(s);
remove o elemento posicionado no topo de s e atribui seu valor a i.
Por exemplo, se s for a pilha da figura abaixo, executaremos a operação push(s, G), ao passar do quadro
(a) para o (b). Em seguida, executamos sucessivamente as seguintes operações:
Outra operação que pode ser executada sobre uma pilha é a determinação do item superior da pilha, sem
removê-lo. Essa operação é escrita como stacktop(s) e retorna o elemento superior da pilha s. Na verdade,
a operação stacktop(s) não representa uma nova operação porque ela pode ser decomposta em um pop e
um push. 
Como acontece com a operação pop, stacktop não é definida para uma pilha vazia. O resultado de
uma tentativa inválida de desempilhar ou acessar um item de uma pilha vazia é chamado underflow. O
underflow pode ser evitado assegurando que empty(s) seja falso antes de tentar a operação pop(s) ou
stacktop(s).
Apesar de ser uma estrutura de dados decepcionantemente simples ela pode desempenha um
proeminente papel nas áreas de programação e de linguagens de programação. É usada em aplicações
onde os dados são obtidos na ordem inversa àquela em que foram fornecidos.
 Exemplos de aplicações computacionais:
 Calculadora para expressões matemáticas;
 Conversão de número decimal para binário;
 Mecanismo de fazer/desfazer do Word;
 Mecanismo de navegação de páginas na Internet (avançar e retornar).
2 Estrutura de dados
3. Fila
São listas em que todas as inserções ocorrem em uma extremidade e as remoções em outra
extremidade. Estruturas de dados do tipo FIFO (first-in first-out): o primeiro elemento a ser inserido, será
o primeiro a ser removido. Situações reais que remetem à ideia de fila: filas de banco, supermercado, fila
de impressão de arquivos , etc.
4. Deque
Definições:
Início da fila: extremidade onde ocorrem as remoções.
Final da fila: extremidade onde ocorrem as inserções.
Três operações primitivas podem ser aplicadas a uma fila. A operação insert(q,x) insere o item x no
início da fila q. A operação x = remove(q) elimina o último elemento da fila q e define x com seu conteúdo.
A terceira operação, empty(q), retorna falso ou verdadeiro, dependendo de a fila conter ou não algum
elemento. A fila que aparece na figura a baixo pode ser obtida pela seguinte sequência de operações.
Pressupomos que a fila esteja inicialmente vazia.
Aplicações:
 Da mesma forma que as pilhas, apesar de ser uma estrutura de dados decepcionantemente simples
ela pode ser de suma importância nas áreas de programação e de linguagens de programação. 
 Exemplos de aplicações computacionais:
 Fila de arquivos para impressão;
 Atendimento de processos requisitados ao um sistema operacional;
 Processos de reserva e compra online;
 Buffer para gravação de dados em mídia;
 Processos de comunicação em redes de computadores.
3 Estrutura de dados
4. Deque
DEQUE (do inglês Double Ended Queue) é um tipo de dado abstrato que generaliza uma fila, para a
qual os elementos podem ser inseridos ou removidos da frente (cabeça) ou de trás (cauda) da lista. Também
é chamada de lista cabeça-cauda.
Lista do tipo Deque duplamente encadeado (com descritor)
Bibliografia:
CORMEN, T. et al. Algoritmos – teoria e prática. 3. ed. Rio de Janeiro: Campus, 2012.
SZWARCFITER, J. Luiz e MARKENZON, Lilian. Estrutura de Dados e seus Algoritmos. Rio de
Janeiro: LTC, 1997.
VELOSO, Paulo. Estruturas de Dados. Rio de Janeiro: Campus, 1998.
Aaron M. Tenenbaum (Autor), Yedidyah Langsam (Autor), Moshe J. Augenstein (Autor); Estruturas De
Dados Usando C, Person, 1995
4 Estrutura de dados