Estrutura de Dados e Algoritmos e Programação e Computadores II aula 6: Pilhas e Filas

Estrutura de Dados e Algoritmos e Programação e Computadores II

• Aula 6: Pilhas e Filas

Pilhas e Filas

• Estruturas Heterogêneas

• Pilhas

• Filas

Pilhas

• Uma pilha é uma estrutura de dados que pode ser acessada somente por uma de suas extremidades para armazenar e recuperar dados.

• Por essa razão, uma pilha é chamada de estrutura LIFO (last in/first out).

Pilhas

• Operações sobre pilhas:

• clear() – limpa a pilha;
• isEmpty() – verifica se a pilha está vazia;
• push(elem) – coloca o elemento no topo da pilha;
• pop() – toma o elemento mais alto da pilha;
• topEl() – retorna o elemento mais alto da pilha sem removê-lo.

Pilhas

Pilhas

• Uma aplicação de pilhas é o casamento de delimitadores em um programa.

• O casamento de delimitadores é parte importante de qualquer compilador.

• while (m < (n[8] + o))
• { p = 7; /* inicializa p */ r = 6; }

Lê o caracter ch do arquivo file;

• Lê o caracter ch do arquivo file;
• while não é o fim de file
• if ch é ´(´,´[´ ou ´{´
• push(ch);
• else if ch é ´)´,´]´ ou ´}´
• if ch e o caracter extraído não se casam
• falha;
• else if ch é ´/´
• lê o próximo caracter;
• if este caracter é ´*´
• pule todos os caracteres até encontrar o
• final do contrário “*”;
• indique um erro se o final for encontrado
• antes do “*”;
• // else ignore os outros caracteres;
• lê o próximo caracter ch a partir de file;
• if a pilha está vazia
• sucesso;
• else falha;
• };

Filas

• Uma fila é simplesmente uma linha de espera que cresce somando elementos ao seu final e que diminui tomando elementos de sua frente.

• Em uma extremidade os nós são somente adicionados, e na outra os nós são somente removidos.

Filas

• Operações

• clear() – limpa a fila;
• isEmpty() – verifica se a fila está vazia;
• isFull() – verifica se a fila está cheia;
• enqueue(elem) – toma o elemento no final da fila;
• dequeue() – toma o primeiro elemento da fila;
• firstEl() – retorna o primeiro elemento da fila sem removê-lo.

Filas

Filas

• As filas são frequentemente usadas em simulações, uma vez que existe uma teoria das filas bem desenvolvida e matematicamente sofisticada na qual vários cenários são analisados e modelos que usam filas são construídos.

• Exemplos: clientes em filas de espera, peças em filas de montagem, conteiners em portos, sistemas de trânsito de grandes cidades, dentre outros.

Estudo de Caso

• Uma Biblioteca: incluir novos livros, registrar saída de livros pelas pessoas e retorná-los.
• Neste estudo de caso quase tudo é implementado em termos de listas.
• Ainda mais, ele usa listas de listas que também contêm referências cruzadas.

Estudo de Caso

• O problema usa um vetor catalogo de todos os autores de livros incluídos na biblioteca e um vetor pessoas de todas as pessoas que usaram a biblioteca pelo menos uma vez.
• Os vetores são indexados por letras de modo que uma posição refere-se a lista de nomes com a letra correspondente.
• Pode-se ter diversos livros de um mesmo autor, e por isso um dos membros do nó autor aponta para uma lista de livros escritos.

Estudo de Caso

• Da mesma forma, uma pessoa pode retirar diversos livros, e assim o nó desta pessoa possui um membro que aponta para a lista de livros retirados.
• Este fato também é indicado ajustando-se o membro do nó livro para o nó da pessoa que o retirou.
• O problema possui 4 classes: Autor, Livro, Pessoa e LivroRetirado.

Estudo de Caso

• 5 operações possíveis no Estudo de Caso:
• Incluir um livro;
• Registrar a saída de um livro;
• Retornar um livro;
• Mostrar uma listagem dos livros da biblioteca;
• Sair do programa.