Interfaces:

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)

Treap(): cria e devolve uma treap vazia
Insert(r,x): insere x na treap com raiz r
Delete(r,x): remove x da treap com raiz r
Search(r,x): true se x está na treap com raiz r e false caso contrário
Min(r): menor chave presente na treap com raiz r
Print(r): imprime todos os elementos na treap com raiz r.
          para a impressão ser mais visual, acione uma rotina recursiva printRec(u, i)
          que aciona printRec(u.esq, i+3), imprime numa linha o valor (e a prio) da raiz
          depois de i espaços em branco, e depois aciona printRec(u.dir, i+3). 
          Se não entendeu a descrição e o objetivo, pergunte na aula ou no fórum. 

Stack(): cria e devolve uma pilha vazia
Push(p,x): empilha x na pilha p
Pop(p): desempilha um elemento de p
Size(p): número de elemento em p
Top(p): elemento do topo de p
Kth(p,k): k-ésimo elemento de p, onde o topo é o primeiro elemento de p
Print(p): imprime todos os elementos da pilha p

retroStack(): cria e devolve uma pilha retroativa vazia
insert(t, "Push", x): insere um "empilha x" na sequência de modificações no instante t
insert(t, "Pop"): insere um "pop" na sequência de modificações no instante t
delete(t): remove da sequência de modificações a operação do instante t
size(t): número de elemento na pilha retroativa no instante t
top(t): elemento do topo da pilha retroativa no instante t
kth(t,k): k-ésimo elemento da pilha retroativa no instante t

AS(S): cria uma árvore de segmentos para o conjunto S de intervalos
Segments(r,x): devolve uma lista com os segmentos na AS r que contém x
Print(r): imprime a AS r, com a lista de segmentos para cada nó

ASD(): cria e devolve uma AS dinâmica vazia
Segments(r,x): devolve uma lista com os segmentos na AS dinâmica r que contém x
Insert(r,s): insere na AS dinâmica r o intervalo s
PrintADS(r): aciona o Print para cada AS da ASD r

ST(): cria e devolve uma splay tree vazia
Insert(r,x): insere x na ST com raiz r
Delete(r,x): remove x da ST com raiz r
Search(r,x): true se x está na ST com raiz r e false caso contrário
Min(r): menor chave presente na ST com raiz r
Print(r): imprime todos os elementos na ST com raiz r
Split(r,x): divide a splay tree de raiz r em duas, uma com as chaves ≤ x e outra com as chaves > x; devolve as raízes das duas splay trees resultantes.
Join(r1,r2): junta as splay trees enraizadas em r1 e r2, assumindo que todas as chaves na árvore r1 são menores ou iguais às de r2. 

Treap(): cria e devolve uma treap vazia
Insert(r,x): insere x na treap com raiz r
Delete(r,x): remove x da treap com raiz r
Search(r,x): true se x está na treap com raiz r e false caso contrário
Min(r): menor chave presente na treap com raiz r
Print(r): imprime todos os elementos na treap com raiz r.
Split(r,x): divide a treap de raiz r em duas, uma com as chaves ≤ x e outra com as chaves > x; devolve as raízes das duas treaps resultantes.
Join(r1,r2): junta as treaps enraizadas em r1 e r2, assumindo que todas as chaves na árvore r1 são menores ou iguais às de r2.

As implementações das rotinas Insert e Delete devem usar as rotinas Split e Join.

GulosoASS(n,m,X): recebe inteiros n e m, e um vetor x[1..m] com inteiros entre 1 e n representando a sequência de pontos (1,x[1]),...,(m,x[m]), e imprime o conjunto arboreamente satisfeito contendo estes pontos, obtido do algoritmo guloso visto em aula. Os pontos devem ser impressos em ordem crescente de y-coordenada.