Aula Prática #07 - Listas, Pilhas e Filas

Exercício 1) Listas Circulares

Nas teóricas falamos de mais tipos de listas ligadas, incluindo a noção de listas circulares, onde o último elemento "aponta" para o primeiro, de forma circular:

1. Verifique o seguinte código que implementa em Java um conjunto de operações sobre listas circulares
   

   Node.java

   // -----------------------------------------------------------
   // Estruturas de Dados 2023/2024 (CC1007) - DCC/FCUP
   // https://www.dcc.fc.up.pt/~miguel-areias/teaching/2324/ed/
   // -----------------------------------------------------------
   // Classe com um no generico (Pedro Ribeiro @ DCC-FCUP)
   // -----------------------------------------------------------
   
   public class Node<T> {
      private T value;      // Valor guardado no no
      private Node<T> next; // Referencia para o proximo no da lista
   
      // Construtor
      Node(T v, Node<T> n) {
         value = v;
         next = n;
      }
   
      // Getters e Setters
      public T getValue() { return value; }
      public Node<T> getNext()  { return next; }
      public void setValue(T v) { value=v; }
      public void setNext(Node<T> n) { next = n; }
   }
   

   ---

   CircularLinkedList.java

   // -----------------------------------------------------------
   // Estruturas de Dados 2023/2024 (CC1007) - DCC/FCUP
   // https://www.dcc.fc.up.pt/~miguel-areias/teaching/2324/ed/
   // -----------------------------------------------------------
   // Lista ligada circular simples
   // (implementada apenas com "last": o primeiro e o last.next)
   // (Pedro Ribeiro @ DCC-FCUP)
   // -----------------------------------------------------------
   
   public class CircularLinkedList<T> {
      private Node<T> last; // Ultimo no da lista
      private int size;     // Tamanho da lista
   
      // Construtor (cria lista vazia)
      CircularLinkedList() {
         last = null;
         size = 0;
      }
   
      // Retorna o tamanho da lista
      public int size() {
         return size;
      }
   
      // Devolve true se a lista estiver vazia ou falso caso contrario
      public boolean isEmpty() {
         return (size == 0);
      }
   
      // Retorna o primeiro valor da lista (ou null se a lista for vazia)
      public T getFirst() {
         if (isEmpty()) return null;
         return last.getNext().getValue();
      }
   
      // Retorna o ultimo valor da lista (ou null se a lista for vazia)
      public T getLast() {
         if (isEmpty()) return null;
         return last.getValue();
      }
   
      // Roda a lista (o primeiro passa a ser o novo ultimo da lista)
      public void rotate() {
         if (!isEmpty()) // Se estiver vazia nao faz nada
            last = last.getNext();
      }
      
      // Adiciona v ao inicio da lista
      public void addFirst(T v) {
         if (isEmpty()) {
            last = new Node<T>(v, null);
            last.setNext(last); // Apontar para si proprio em "loop"
         } else {
            Node<T> newNode = new Node<T>(v, last.getNext());
            last.setNext(newNode);
         }
         size++;
      }
   
      // Adiciona v ao final da lista
      public void addLast(T v) {
         addFirst(v);
         last = last.getNext();
      }
   
      // Remove o primeiro elemento da lista (se for vazia nao faz nada)
      public void removeFirst() {
         if (isEmpty()) return;
         if (size == 1) last = null;
         else last.setNext(last.getNext().getNext());
         size--;
      }
   
      // Remove o ultimo elemento da lista (se for vazia nao faz nada)
      public void removeLast() {
         if (isEmpty()) return;
         if (size == 1) {
            last = null;
         } else {
            Node<T> cur = last.getNext();
            for (int i=0; i<size-2; i++)
               cur = cur.getNext();
            last = cur;
            last.setNext(last.getNext().getNext());
         }
         size--;
      }
      
      // Converte a lista para uma String
      public String toString() {
         String str = "{";      
         if (!isEmpty()) {
            Node<T> cur = last.getNext();
            for (int i=0; i<size; i++) {
               str += cur.getValue();
               if (cur != last) str += ",";
               cur = cur.getNext();
            }
         }         
         str += "}";
         return str;
      }
   }
   

   ---

   Exemplo de utilização (TestCircularLinkedList.java)

   // -----------------------------------------------------------
   // Estruturas de Dados 2023/2024 (CC1007) - DCC/FCUP
   // https://www.dcc.fc.up.pt/~miguel-areias/teaching/2324/ed/
   // -----------------------------------------------------------
   // Exemplo de utilizacao da lista circular
   // (Pedro Ribeiro @ DCC-FCUP)
   // -----------------------------------------------------------
   
   public class TestCircularLinkedList {
      public static void main(String[] args) {
   
         // Simulando processos (A,B,C,D) e escalonamento round-robin      
         // Criacao de lista de caracteres
         CircularLinkedList<Character> list = new CircularLinkedList<Character>();
   
         // Adicionando letras de 'A' a 'E'
         list.addLast('A');
         list.addLast('B');
         list.addLast('C');
         list.addLast('D');
   
         // Mostrando rotacao a funcionar
         System.out.println("8 rondas round-robin");
         for (int i=1; i<=8; i++) {
            System.out.println(i + ": " + list);
            list.rotate();
         }
   
         // Inserir e retirar elemento no final
         list.addLast('E');
         System.out.println("addLast('E'): " + list);
         list.removeLast();
         System.out.println("removeLast(): " + list);
   
         // Inserir retirar elemento no inicio
         list.addFirst('F');
         System.out.println("addFirst('F'): " + list);
         list.removeFirst();
         System.out.println("removeFirst(): " + list);
   
      }
   }
   

2. Execute o código anterior.
   

   Compile o código e execute a classe TestCircularLinkedList para ver as listas circulares em funcionamento. Procure acompanhar cada uma das linhas de código e o seu efeito. Note em particular o que faz o método rotate() que "roda" os elementos, colocando o primeiro elemento no final da lista e avançado o segundo elemento para o início da fila:

3. Resolver um problema.
   Resolva o exercício [ED006] Pim, Pam, Pum e também submeter no Mooshak para testar a sua resolução.
   Mostrar/Esconder Dicas
   • Comece por ler a linha com a frase de contagem para uma String (use o método nextLine() da classe Scanner e não se esqueça de "escapar" o resto da linha anterior).
   • Para saber o tamanho da frase basta por exemplo usar o método split da classe String. Se a linha estiver guardada numa string chamada line, então line.split(" ") devolve um array contendo as palavras e line.split(" ").length devolve a quantidade de elementos nesse array).
   • Agora é só simular o jogo a acontecer. De cada vez chame rotate() o número de vezes necessário (o tamanho da frase menos um, porque já está no primeiro elemento da contagem) e remova o primeiro elemento (método removeFirst()). No final é só ver qual a criança que sobrou na lista circular (método getFirst()).

Exercício 2) Listas Duplamente Ligadas

1. Verifique o seguinte código que implementa em Java um conjunto de operações sobre listas duplamente ligadas
   

   DNode.java

   // -----------------------------------------------------------
   // Estruturas de Dados 2023/2024 (CC1007) - DCC/FCUP
   // https://www.dcc.fc.up.pt/~miguel-areias/teaching/2324/ed/
   // -----------------------------------------------------------
   // Classe com um no generico com dupla ligacao
   // (Pedro Ribeiro @ DCC-FCUP)
   // -----------------------------------------------------------
   
   public class DNode<T> {
      private T value;       // Valor guardado no no
      private DNode<T> prev; // Referencia para o no anterior da lista
      private DNode<T> next; // Referencia para o proximo no da lista
   
      // Construtor
      DNode(T v, DNode<T> p, DNode<T> n) {
         value = v;
         prev = p;
         next = n;
      }
   
      // Getters e Setters
      public T getValue() { return value; }
      public DNode<T> getPrev()  { return prev; }
      public DNode<T> getNext()  { return next; }
      public void setValue(T v) { value=v; }
      public void setPrev(DNode<T> p) { prev = p; }
      public void setNext(DNode<T> n) { next = n; }
   }
   

   ---

   DoublyLinkedList.java

   // -----------------------------------------------------------
   // Estruturas de Dados 2023/2024 (CC1007) - DCC/FCUP
   // https://www.dcc.fc.up.pt/~miguel-areias/teaching/2324/ed/
   // -----------------------------------------------------------
   // Lista duplamente ligada (Pedro Ribeiro @ DCC-FCUP)
   // (implementada com sentinelas - nos "dummy" no inicio e no fim
   //  que facilitam a implementacao e evitam casos excepcionais)
   // -----------------------------------------------------------
   
   public class DoublyLinkedList<T> {
      private DNode<T> first; // Primeiro no da lista
      private DNode<T> last;  // Ultimo no da lista
      private int size;       // Tamanho da lista
   
      // Construtor (cria lista vazia com dois nos sentinelas)
      DoublyLinkedList() {
         first = new DNode<T>(null, null, null);
         last  = new DNode<T>(null, first, null); // Antes do ultimo vem o primeiro
         first.setNext(last); // A seguir ao primeiro vem o ultimo
         size = 0;
      }
   
      // Retorna o tamanho da lista
      public int size() {
         return size;
      }
   
      // Devolve true se a lista estiver vazia ou falso caso contrario
      public boolean isEmpty() {
         return (size == 0);
      }
      
      // Retorna o primeiro valor da lista (ou null se a lista for vazia)
      public T getFirst() {
         if (isEmpty()) return null;
         return first.getNext().getValue();
      }
   
      // Retorna o ultimo valor da lista (ou null se a lista for vazia)
      public T getLast() {
         if (isEmpty()) return null;
         return last.getPrev().getValue();
      }
      
      // Adiciona v ao inicio da lista
      public void addFirst(T v) {
         addBetween(v, first, first.getNext());
      }
   
      // Adiciona v ao final da lista
      public void addLast(T v) {
         addBetween(v, last.getPrev(), last);
      }
   
      // Adiciona elemento entre dois nos n1 e n2
      private void addBetween(T v, DNode<T> n1, DNode<T> n2) {
         DNode<T> newNode = new DNode<T>(v, n1, n2);
         n1.setNext(newNode);
         n2.setPrev(newNode);
         size++;
      }
   
      // Remove o primeiro elemento da lista (se for vazia nao faz nada)
      public void removeFirst() {
         if (isEmpty()) return;
         remove(first.getNext());
      }
   
      // Remove o ultimo elemento da lista (se for vazia nao faz nada)
      public void removeLast() {
         if (isEmpty()) return;
         remove(last.getPrev());            
      }
   
      // Remove um no da lista
      private void remove(DNode<T> n) {
         DNode<T> prev = n.getPrev();
         DNode<T> next = n.getNext();
         prev.setNext(next);
         next.setPrev(prev);
         size--;
      }
            
      // Converte a lista para uma String
      public String toString() {
         String str = "{";      
         DNode<T> cur = first.getNext();
         for (int i=0; i<size; i++) {
            str += cur.getValue();
            cur = cur.getNext();
            if (cur != last) str += ",";
         }      
         str += "}";
         return str;
      }
   }
   

   ---

   Exemplo de utilização (TestDoublyLinkedList.java)

   // -----------------------------------------------------------
   // Estruturas de Dados 2023/2024 (CC1007) - DCC/FCUP
   // https://www.dcc.fc.up.pt/~miguel-areias/teaching/2324/ed/
   // -----------------------------------------------------------
   // Exemplo de utilizacao da lista duplamente ligada
   // Pedro Ribeiro @ DCC-FCUP
   // -----------------------------------------------------------
   
   public class TestDoublyLinkedList {
      public static void main(String[] args) {
   
         // Criacao de lista de inteiros
         DoublyLinkedList<Integer> list = new DoublyLinkedList<Integer>();
   
         // Escrevendo lista (no inicio esta vazia)
         System.out.println(list);
   
         // Verificando se esta vazia
         System.out.println("isEmpty? " + list.isEmpty());     
         
         // Adicionando numeros de 1 a 5 ao final da lista
         for (int i=1; i<=5; i++)
            list.addLast(i);
         System.out.println(list);
   
         // Adicionando numeros de 6 a 10 ao inicio da lista
         for (int i=6; i<=10; i++)
            list.addFirst(i);
         System.out.println(list);
   
         // Verificando o tamanho da lista
         System.out.println("size = " + list.size());
   
         // Retirando o primeiro elemento
         list.removeFirst();
         System.out.println(list);
   
         // Retirando o ultimo elemento
         list.removeLast();
         System.out.println(list);
   
         // Verificando se esta vazia
         System.out.println("isEmpty? " + list.isEmpty());
   
         // Escreve o primeiro e ultimo elementos
         System.out.println("getFirst() = " + list.getFirst());
         System.out.println("getLast() = " + list.getLast());
   
      }
   }
   

2. Execute o código anterior.
   

   Compile o código e execute a classe TestDoublyLinkedList para ver as listas duplamente ligadas em funcionamento. Procure acompanhar cada uma das linhas de código e o seu efeito.

Exercício 3) Pilhas

Um TAD Pilha é uma sequência de elementos LIFO (Last-In-First-Out) onde temos duas operações para modificar o conteúdo:

• podemos adicionar um elemento x chamando push(x)
• podemos remover e obter o elemento que adicionamos mais recentemente usando pop()

1. Verifique o seguinte código que implementa em Java um conjunto de operações sobre Pilhas
   

   Interface (MyStack.java)

   // -----------------------------------------------------------
   // Estruturas de Dados 2023/2024 (CC1007) - DCC/FCUP
   // https://www.dcc.fc.up.pt/~miguel-areias/teaching/2324/ed/
   // -----------------------------------------------------------
   // Interface para o TAD Pilha
   // (Pedro Ribeiro @ DCC-FCUP)
   // -----------------------------------------------------------
   
   public interface MyStack<T> {
   
      // Metodos que modificam a pilha
      public void push(T v); // Coloca um valor no topo da pilha
      public T pop();        // Retira e retorna o valor no topo da pilha
   
      // Metodos que acedem a informacao (sem modificar)
      public T top();           // Retorna valor no topo da pilha
      public int size();        // Retorna quantidade de elementos na pilha
      public boolean isEmpty(); // Indica se a pilha esta vazia
   }
   

   ---

   Exemplo de utilização (TestMyStack.java)

   // -----------------------------------------------------------
   // Estruturas de Dados 2023/2024 (CC1007) - DCC/FCUP
   // https://www.dcc.fc.up.pt/~miguel-areias/teaching/2324/ed/
   // -----------------------------------------------------------
   // Exemplo de utilizacao do TAD Pilha
   // (Pedro Ribeiro @ DCC-FCUP)
   // -----------------------------------------------------------
   
   public class TestMyStack {
      public static void main(String[] args) {
   
         // Criacao da pilha
         MyStack<Integer> s = new LinkedListStack<Integer>();
         //MyStack<Integer> s = new ArrayStack<Integer>();
   
         // Exemplo de insercao de elementos na pilha
         for (int i=1; i<=8; i++)
            s.push(i); // insere i no topo da pilha
         System.out.println(s);
   
         // Exemplo de remocao de elementos na pilha
         for (int i=0; i<4; i++) {
            int aux = s.pop(); // retira o elemento no topo da pilha
            System.out.println("s.pop() = " + aux);
         }
         System.out.println(s);
   
         // Exemplo de utilizacao dos outros metodos
         System.out.println("s.size() = " + s.size());
         System.out.println("s.isEmpty() = " + s.isEmpty());
         System.out.println("s.top() = " + s.top());
      }
   }
   

   ---

   Implementação com Listas Ligadas (LinkedListStack.java)

   // -----------------------------------------------------------
   // Estruturas de Dados 2023/2024 (CC1007) - DCC/FCUP
   // https://www.dcc.fc.up.pt/~miguel-areias/teaching/2324/ed/
   // -----------------------------------------------------------
   // Implementacao do TAD Pilha usando lista duplamente ligada
   // (Pedro Ribeiro @ DCC-FCUP)
   // -----------------------------------------------------------
   
   public class LinkedListStack<T> implements MyStack<T> {
      private DoublyLinkedList<T> list;
   
      LinkedListStack() { list = new DoublyLinkedList<T>();}
      
      public void push(T v) { list.addFirst(v); }   
      public T pop() {
         T ans = list.getFirst();
         list.removeFirst();
         return ans;
      }
      public T top() { return list.getFirst();}
      public int size() {return list.size();}
      public boolean isEmpty() {return list.isEmpty();}
   
      public String toString() {return list.toString();}
   }
   

   ---

   Implementação com Arrays (ArrayStack.java)

   // -----------------------------------------------------------
   // Estruturas de Dados 2023/2024 (CC1007) - DCC/FCUP
   // https://www.dcc.fc.up.pt/~miguel-areias/teaching/2324/ed/
   // -----------------------------------------------------------
   // Implementacao de Pilha usando array
   // (Pedro Ribeiro @ DCC-FCUP)
   //
   // Nota: o Java proibe a criacao de arrays genericos. Para efeitos
   // de demonstracao, usamos aqui um array de Objects e um cast
   // (que prova um aviso de compilacao que e "evitado" com a linha do
   // Supress Warning). De um modo geral, para genericos, o ideal seria
   // nao usar um array "nativo", mas sim algo como um ArrayList, mas
   // aqui queremos demonstrar como pode ser feito.
   // -----------------------------------------------------------
   
   import java.util.Arrays;
   
   public class ArrayStack<T> implements MyStack<T> {
      public static final int CAPACITY = 1000; // Capacidade padrao   
      private T[] data;  // Array para conter elementos
      private int size;  // Quantidade de elementos
   
      ArrayStack() {
         this(CAPACITY);
      }
   
      @SuppressWarnings("unchecked")
      ArrayStack(int capacity) {
         data = (T[]) new Object[capacity];
         size = 0;
      }
      
      public void push(T v) {
         if (size >= data.length) throw new RuntimeException("Stack is full");
         data[size++] = v;
      }
      
      public T pop() {
         if (isEmpty()) return null;
         return data[--size];
      }
      
      public T top() { return data[size-1];}
      public int size() {return size;}
      public boolean isEmpty() {return (size==0);}
   
      public String toString() {
         String str = "[";
         for (int i=size-1; i>=0; i--) {
            str += data[i];
            if (i>0) str += ",";
         }
         str += "]";
         return str;
      }
   }
   

   Compile o código e execute a classe TestMyStack para ver a pilha em funcionamento.
   Procure acompanhar cada uma das linhas de código e o seu efeito. Note em particular os métodos do TAD (basta ver o interface) e como criar a Pilha (a variável do tipo do interface atribuída a uma implementação desse mesmo interface).

2. Como inverter uma Pilha
   Resolva o problema [ED194] Invertendo uma Pilha e poderá também submeter a sua solução no Mooshak.
   Mostrar/Esconder Dicas
   • Basta retirar n elementos da pilha (usando a operação pop) e depois voltar a inserir pela ordem correcta (usando a operação push). À medida que vai retirando os elementos pode por exemplo guardá-los... num array.

   Nota: se quiser testar o método pode optar por adicionar um main à sua classe ED194 (não será chamado no Mooshak) ou criar uma classe adicional no seu computador para fazer chamadas a ED194.
   Mostrar/Esconder Exemplo de programa para testar problema [ED194]

   // Pode submeter uma classe como esta.
   // - No seu computador pode testar com "java ED195"
   // - O mooshak apenas irá chamar o seu método reverse
   public class ED194 {
      
      // Método que deve implementar
      public static void reverse(MyStack<Integer> s, int n) {
         // Deve colocar aqui o código para resolver o problema
      }
   
      // Main apenas para testar no seu computador
      public static void main(String[] args) {
         MyStack<Integer> s = new LinkedListStack<Integer>();
   
         for (int i=5; i>0; i--)
            s.push(i);
         System.out.println(s); // Antes da chamada a reverse
         reverse(s, 3);
         System.out.println(s); // Depois da chamada a reverse
      }
   }
   

3. Expressões bem balanceadas
   Resolva o problema [ED195] Expressões bem balanceadas e poderá também submeter a sua solução no Mooshak.
   Mostrar/Esconder Dicas
   • Para iterar sobre todos os caracteres da string s pode usar o método charAt(int index) da classe String. Por exemplo, s.charAt(i) devolve o i-ésimo caracter da string s. Note que as posições válidas vão desde 0 até s.length()-1.
   • Use uma pilha de caracteres (MyStack<Character>) para ir guardando os parenteses de abertura: '(' e '['. Cada vez que apanhar um parenteses de fecho, verifique se corresponde ao tipo do último parenteses aberto (que está no topo da pilha).
   • Qual o estado final da pilha numa expressão bem formada? Como pode determinar que ficaram parenteses por fechar?

Exercício 4) Filas

Um TAD Fila é uma sequência de elementos FIFO (First-In-First-Out) onde temos duas operações para modificar o conteúdo:

• podemos adicionar um elemento x chamando enqueue(x)
• podemos remover e obter o elemento que adicionamos há mais tempo usando dequeue()

1. Verifique o seguinte código que implementa em Java um conjunto de operações sobre filas
   

   Interface (MyQueue.java)

   // -----------------------------------------------------------
   // Estruturas de Dados 2023/2024 (CC1007) - DCC/FCUP
   // https://www.dcc.fc.up.pt/~miguel-areias/teaching/2324/ed/
   // -----------------------------------------------------------
   // Interface para o TAD Fila
   // (Pedro Ribeiro @ DCC-FCUP)
   // -----------------------------------------------------------
   
   public interface MyQueue<T> {
   
      // Metodos que modificam a fila
      public void enqueue(T v); // Coloca um valor no final da fila
      public T dequeue();       // Retira e retorna o valor no inicio da fila
   
      // Metodos que acedem a informacao (sem modificar)
      public T first();         // Retorna valor no inicio da fila
      public int size();        // Retorna quantidade de elementos na fila
      public boolean isEmpty(); // Indica se a fila esta vazia
   }
   

   ---

   Exemplo de utilização (TestMyQueue.java)

   // -----------------------------------------------------------
   // Estruturas de Dados 2023/2024 (CC1007) - DCC/FCUP
   // https://www.dcc.fc.up.pt/~miguel-areias/teaching/2324/ed/
   // -----------------------------------------------------------
   // Exemplo de utilizacao do TAD Fila
   // (Pedro Ribeiro @ DCC-FCUP)
   // -----------------------------------------------------------
   
   public class TestMyQueue {
      public static void main(String[] args) {
   
         // Criacao da fila
         MyQueue<Integer> q = new LinkedListQueue<Integer>();
   
         // Exemplo de insercao de elementos na fila
         for (int i=1; i<=8; i++)
            q.enqueue(i); // insere i no final da fila
         System.out.println(q);
   
         // Exemplo de remocao de elementos da fila
         for (int i=0; i<4; i++) {
            int aux = q.dequeue(); // retira o elemento no inicio da fila
            System.out.println("q.dequeue() = " + aux);
         }
         System.out.println(q);
   
         // Exemplo de utilizacao dos outros metodos
         System.out.println("q.size() = " + q.size());
         System.out.println("q.isEmpty() = " + q.isEmpty());
         System.out.println("q.first() = " + q.first());
      }
   }
   

   ---

   Implementação com Listas Ligadas (LinkedListQueue.java)

   // -----------------------------------------------------------
   // Estruturas de Dados 2023/2024 (CC1007) - DCC/FCUP
   // https://www.dcc.fc.up.pt/~miguel-areias/teaching/2324/ed/
   // -----------------------------------------------------------
   // Implementacao do TAD Fila usando lista duplamente ligada
   // (Pedro Ribeiro @ DCC-FCUP)
   // -----------------------------------------------------------
   
   public class LinkedListQueue<T> implements MyQueue<T> {
      private DoublyLinkedList<T> list;
   
      LinkedListQueue() { list = new DoublyLinkedList<T>();}
      
      public void enqueue(T v) { list.addLast(v); }   
      public T dequeue() {
         T ans = list.getFirst();
         list.removeFirst();
         return ans;
      }
      public T first() { return list.getFirst();}
      public int size() {return list.size();}
      public boolean isEmpty() {return list.isEmpty();}
   
      public String toString() {return list.toString();}
   }
   

   Compile o código e execute a classe TestMyQueue para ver a Fila em funcionamento.
   Procure acompanhar cada uma das linhas de código e o seu efeito. Note em particular os métodos do TAD (basta ver o interface) e como criar a Fila (a variável do tipo do interface atribuída a uma implementação desse mesmo interface).

2. Como usar Filas
   Resolva o problema [ED196] Duas filas e poderá também submeter a sua solução no Mooshak.
   Mostrar/Esconder Dicas
   • A ideia é ir retirando elementos à fila (dois a dois) enquanto a fila não estiver vazia. Que método da fila serve para verificar se a fila ainda tem elementos?
   • Consoante a operação, devemos colocar logo numa certa lista, ou comparar os tamanhos. Que método da fila serve para ver o tamanhos de uma fila?
3. União ordenada
   Resolva o problema [ED197] União Ordenada e poderá também submeter a sua solução no Mooshak.
   Mostrar/Esconder Dicas
   • Comece por criar uma nova fila de inteiros que irá conter a união (MyQueue<Integer> q = new LinkedListQueue<Integer>();)
   • Depois, a ideia é "espreitar" o primeiro elemento de cada fila e escolher o que for menor. Que método da fila serve para ver o primeiro elemento?
   • Se uma das filas ficar vazia, o que falta fazer?

Baseado em material didático de Pedro Ribeiro (DCC-FCUP)