Deque

Interface: 
  Deque(): cria e devolve uma deque vazia
  PushFront(d,x): insere x no extremo front de d
  PushBack(d,x): insere x no extremo back de d
  PopFront(d): remove o elemento no extremo front de d
  PopBack(d): remove o elemento no extremo back de d
  Front(d): devolve o elemento no extremo front de d
  Back(d): devolve o elemento no extremo back de d
  Kth(d,k): k-ésimo elemento de d, onde o front é o primeiro elemento de d
  Print(d): imprime todos os elementos da deque d na mesma linha, separados por um branco
            (não precisa se preocupar com eventual espaço em branco no fim da linha)
Descrição da entrada de testes: Seu programa deve criar uma deque d0 vazia antes de começar a processar a entrada.

Codificação das operações: 

1 <t> <x> significa d_ultima+1 = PushFront(d_t, x) 
2 <t> <x> significa d_ultima+1 = PushBack(d_t, x) 
3 <t>     significa d_ultima+1 = PopFront(d_t) 
4 <t>     significa d_ultima+1 = Popback(d_t) 
5 <t>     significa println(Front(d_t))
6 <t>     significa println(Back(d_t))
7 <t> <k> significa println(Kth(d_t, k))
8 <t>     significa Print(d_t)
Exemplo de entrada para o programa de testes: 
1 0 1
1 1 2
2 2 3
8 3
2 3 4
1 4 5
8 5
5 5
6 5
7 5 2
7 5 4
3 3
8 5
8 3
8 6
4 5
8 7
1 4 6
8 8
Saída esperada para este teste: 
2 1 3
5 2 1 3 4
5
4
2
3
5 2 1 3 4
2 1 3
1 3
5 2 1 3
6 2 1 3 4