TAD MyDeque

// -----------------------------------------------------------
// Estruturas de Dados 2024/2025 (CC1007) - DCC/FCUP
// http://www.dcc.fc.up.pt/~fds/aulas/EDados/2425/
// -----------------------------------------------------------
// Interface para o TAD Deque
// Ultima alteracao: 06/04/2018
// -----------------------------------------------------------

public interface MyDeque<T> {

   // Metodos que modificam o deque
   public void addFirst(T v); // Coloca um valor no inicio da fila
   public void addLast(T v);  // Coloca um valor no final da fila
   public T removeFirst();    // Retira e retorna o valor no inicio da fila
   public T removeLast();     // Retira e retorna o valor no final da fila

   // Metodos que acedem a informacao (sem modificar)
   public T first();          // Retorna valor no inicio da fila
   public T last();           // Retorna valor no final da fila
   public int size();         // Retorna quantidade de elementos na fila
   public boolean isEmpty();  // Indica se a fila esta vazia
}

// -----------------------------------------------------------
// Estruturas de Dados 2024/2025 (CC1007) - DCC/FCUP
// http://www.dcc.fc.up.pt/~fds/aulas/EDados/2425/
// -----------------------------------------------------------
// Exemplo de utilizacao do TAD Deque
// Ultima alteracao: 06/04/2018
// -----------------------------------------------------------

public class TestMyDeque {
   public static void main(String[] args) {

      // Criacao do Deque
      MyDeque<Integer> q = new LinkedListDeque<Integer>();

      // Exemplo de insercao de elementos no inicio e no fim da fila
      for (int i=1; i<=4; i++) q.addFirst(i);
      for (int i=5; i<=8; i++) q.addLast(i); 
      System.out.println(q);

      // Exemplo de remocao de elementos no inicio e fim fila
      System.out.println("q.removeFirst() = " + q.removeFirst());
      System.out.println("q.removeLast() = " + q.removeLast());
      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());
      System.out.println("q.last() = " + q.last());
   }
}

// -----------------------------------------------------------
// Estruturas de Dados 2024/2025 (CC1007) - DCC/FCUP
// http://www.dcc.fc.up.pt/~fds/aulas/EDados/2425/
// -----------------------------------------------------------
// Implementacao do TAD Deque usando lista duplamente ligada
// Ultima alteracao: 06/04/2018
// -----------------------------------------------------------

public class LinkedListDeque<T> implements MyDeque<T> {
   private DoublyLinkedList<T> list;

   LinkedListDeque() { list = new DoublyLinkedList<T>();}
   
   public void addLast(T v)  { list.addLast(v); }
   public void addFirst(T v) { list.addFirst(v); }
   public T removeFirst() {
      T ans = list.getFirst();
      list.removeFirst();
      return ans;
   }
   public T removeLast() {
      T ans = list.getLast();
      list.removeLast();
      return ans;
   }
   public T first() { return list.getFirst();}
   public T last() { return list.getLast();}
   public int size() {return list.size();}
   public boolean isEmpty() {return list.isEmpty();}

   public String toString() {return list.toString();}
}