Filas

Livro de Sedgewick e Wayne: sec.1.3, p.120.  Website do livro: resumo sec.1.3, slides.  Veja também a página algs4.cs.​princeton.edu/​code/, que tem o código fonte, a documentação, e dados de teste de todos os programas do livro.

Esta aula examina o conceito de fila (que o leitor já conhece muito bem) como exemplo de ADT.

Fila (= queue) e sua API

• Uma fila (= queue) é um ADT que consiste em uma coleção de coisas munida de duas operações:  enqueue, que insere uma coisa na coleção, e dequeue, que remove a coisa mais antiga da coleção.  (Portanto, a primeira coisa a entrar é a primeira a sair.)
• As coisas de que uma fila é feita serão chamadas itens. Os itens podem ser números, strings, structs, etc., etc.
• Exemplo: fila de pessoas esperando por atendimento no caixa de um banco.
• Eis a API de nossa fila de itens  (além das operações fundamentais enqueue e dequeue, temos algumas operações auxiliares):

  public class Queue<Item>
  	Queue()	construtor: cria uma fila de Items vazia
  void	enqueue(Item item)	coloca item nesta fila
  Item	dequeue()	remove o item mais antigo desta fila
  boolean	isEmpty()	esta fila está vazia?
  int	size()	número de Items nesta fila

• Exemplo de aplicação: cálculo da distância entre dois vértices de em grafo (busca em largura).

Exercícios 1

1. Escreva um exemplo de cliente para fila análogo ao que usamos para pilha.

Fila implementada em vetor com redimensionamento

• Não é difícil implementar uma fila em um vetor, à maneira do que fizemos para pilha.
• A classe ResizingArrayQueue do livro é uma implementação de fila em vetor. A correspondente API é um pouco mais ampla que a descrita acima.

Exercícios 2

1. Escreva uma implementação QueueRA de fila usando um vetor circular com redimensionamento.  Faça isso sem olhar o código ResizingArrayQueue.java do livro.

Fila implementada em lista ligada

• Inserção na fila (enqueue):

  

• Classe QueueL: fila implementada em lista ligada:

  public class QueueL<Item> {
     private Node first; // mais recente
     private Node last;  // mais antigo
     private int N;
  
     private class Node {
        private Item item;
        private Node next;
     }
  
     public boolean isEmpty() {
        return first == null;
     }
  
     public int size() {
        return N;
     }
  
     public void enqueue(Item item) {
        Node oldlast = last;
        last = new Node();
        last.item = item;
        last.next = null;
        if (isEmpty()) first = last;
        else oldlast.next = last;
        N++;
     }
  
     public Item dequeue() {
        Item item = first.item;
        first = first.next;
        N--;
        if (isEmpty()) last = null;
        return item;
     }
  
     public static void main(String[] args) {
        QueueL<String> q = new QueueL<String>();
        while (!StdIn.isEmpty()) {
           String item = StdIn.readString();
           if (!item.equals("-")) q.enqueue(item);
           else if (!q.isEmpty()) StdOut.print(q.dequeue() + " ");
        }
        StdOut.println("(" + q.size() + " left on queue)");
     }
  
  }
  

• Teste:

  % more tobe.txt
  to be or not to - be - - that - - - is
  
  % java QueueL < tobe.txt
  to be or not to be (2 left on queue)
  

• O website do livro tem implementações mais completas que a classe QueueL exibida acima. Veja a classe LinkedQueue e a correspondente API.  A classe Queue é uma implementação mais profissional; veja a API correspondente.

Exercícios 3

1. Imprima as últimas k linhas de um arquivo (grande) de texto. Faça isso sem desperdiçar memória. Use uma (ou mais) das ADTs que já estudamos.