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

KinHeap(id, x0, speed, n): cria um maxheap cinético com n elementos,
  com identificador, valor inicial e velocidade nos vetores id, x0 e speed. 
Advance(t): avança o tempo para o instante t
Change(id, v): altera a velocidade do elemento id para v
Insert(id, xnow, v): insere o elemento id na posição xnow com velocidade v
Max(): identificador do elemento com o maior valor no instante atual
DeleteMax(): remove o elemento com o maior valor
Delete(id): remove o elemento id
Print(): imprime o heap no instante atual

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.

DynamicForest(n): cria e devolve uma floresta com n vértices e nenhuma aresta
Connected(F,u,v): true se u e v estão na mesma componente da floresta e false caso contrário
Link(F,u,v): insere a aresta uv na floresta
Cut(F,u,v): remove a aresta entre u e v
Print(): imprime todas as arestas da floresta.

VS(T): cria e devolve o vetor de sufixos e dos lcps para o texto T
Search(P): true se P ocorre no texto T e false caso contrário
Occurrences(P): lista de posição em que P aparece em T
NOccurrences(P): número de ocorrências de P em T
Print(): imprime o texto, o vetor de sufixos e o vetor dos lcps 

AS(T): cria e devolve a árvore de sufixos para o texto T
Search(P): true se P ocorre no texto T e false caso contrário
Occurrences(P): lista de posição em que P aparece em T
NOccurrences(P): número de ocorrências de P em T
Print(): imprime em posordem a árvore de sufixos, com os índices dos rótulos de cada aresta