Pilhas e filas no Verse | Unreal Editor para Fortnite Documentação

Visão geral

Pilhas e filas são estruturas de dados comuns na ciência da computação que especificam a ordem na qual você pode adicionar e remover elementos. Você pode usá-las para controlar a ordem em que interage com os dados:

Pilha: um contêiner no qual você insere e remove elementos na ordem FILO (o primeiro a entrar é o último a sair), por exemplo, escolhendo um livro no topo de uma pilha de livros para ler.
Fila: um contêiner no qual você insere e remove elementos na ordem FIFO (o primeiro a entrar é o primeiro a sair), por exemplo, processando uma fila de clientes à espera por uma refeição.

Embora o código subjacente para pilhas e filas seja semelhante, cada um deles tem diferenças e pontos fortes importantes que você pode aproveitar para tornar sua experiência rápida, eficiente e intuitiva.

Pilhas

É possível pensar em uma pilha como uma pilha de panquecas. Suponha que você esteja em um restaurante que serve café da manhã, e o garçom oferece uma pilha interminável de panquecas. Como você quer seguir as regras de etiqueta, só vai pegar uma panqueca de cada vez, e apenas do topo da pilha. Você pode pedir ao garçom para enviar uma nova panqueca para o topo da pilha e, quando estiver com fome, pode retirar uma panqueca do topo da pilha e colocá-la no prato para comê-la. Se quiser comer uma panqueca específica no meio da pilha, terá que continuar comendo as panquecas em cima até chegar à que deseja. A primeira panqueca adicionada será a última a ser removida. Isso faz de uma pilha uma estrutura de dados FILO, ou seja, o primeiro a entrar é o último a sair.

Quando usar

Pilhas são úteis quando você precisa voltar atrás ou quando precisa da capacidade de lembrar em que ordem executou os eventos. Pode ser uma função de desfazer, uma cadeia de eventos ou uma série de escolhas. Por exemplo, talvez você tenha um robô que precisa resolver um labirinto com caminhos ramificados. Quando o robô atinge uma bifurcação no labirinto, ele escolhe um caminho e coloca essa escolha na pilha. Ao chegar a um beco sem saída, ele retrocede na pilha, selecionando opções até encontrar um novo caminho que possa seguir.

Implementação no Verse

A API Verse não tem uma implementação integrada de pilhas, mas você mesmo pode criar uma.

Os elementos em uma pilha podem ser representados usando qualquer estrutura de dados ordenada, como uma matriz ou uma lista vinculada. Neste exemplo, você usará uma matriz, pois ela oferece acesso fácil ao topo da pilha.

stack<public>(t:type) := class:
    Elements<internal>:[]t = array{}

A matriz Elements armazena os objetos na pilha, que são do tipo t. Isso significa que você pode inicializar uma pilha com qualquer tipo de elemento, como int, float, stack etc. Usar type como argumento para a classe stack é um exemplo de tipo paramétrico](parametric-types-in-verse).

Vamos definir algumas funções auxiliares primeiro. Você precisa saber onde está o topo da pilha para poder aplicar Push() e Pop() aos elementos dela. Para isso, precisará de três funções, Size(), IsEmpty() e Peek().

# Retorna o tamanho da pilha.
    Size<public>()<transacts>:int=
        Elements.Length

    # Tem êxito quando a pilha está vazia.
    IsEmpty<public>()<decides><transacts>:void=
        Size() = 0

    # Retorna o elemento superior da pilha.
    Peek<public>()<decides><transacts>:t=
        Elements[Elements.Length - 1]

A função Size() simplesmente retorna o valor Length da matriz Elements. A função IsEmpty() chama a função Size() e tem o especificador <transacts>, o que significa que falhará se Size() não for igual a 0.

A função Peek() retorna o elemento no índice superior (Comprimento - 1) da matriz de elementos. Essa função possui os especificadores <decides><transacts>, já que o acesso à matriz pode falhar se ela estiver vazia.

Para instanciar uma pilha, você pode usar uma função de construtor. O construtor é uma função especial que cria uma instância da classe à qual ele está associado. Ele define valores iniciais para um objeto, permite acessar o valor de Elements e atribuí-lo a uma matriz inicial de elementos.

# Cria e retorna uma pilha a partir de uma matriz inicial de elementos InitialElements.
CreateStack<public><constructor>(InitialElements:[]t where t:type) := stack(t):
    Elements := InitialElements

Enviar e retirar

Para adicionar e remover elementos da pilha, você precisa usar push para enviar o novo elemento ao topo da pilha ou usar pop para retirá-lo do topo.

# Adiciona NewElement ao topo da pilha retornando uma nova
# pilha com NewElement no topo
Push<public>(NewElement:t):stack(t)=
    stack(t){Elements := Elements + array{NewElement}}

# Remove o elemento no topo da pilha e retorna uma tupla de uma nova
# pilha com o elemento superior removido e o elemento removido.
Pop<public>()<decides><transacts>:tuple(stack(t),t)=
    FirstElement := Peek[]
    (stack(t){Elements := Elements.RemoveElement[Elements.Length - 1]}, FirstElement)

A função Push() usa o elemento que você deseja colocar no topo da pilha e retorna uma nova pilha com esse elemento no topo. Retornar uma nova pilha em vez de modificar a pilha atual é um exemplo de programação funcional e reduz o risco de efeitos colaterais.

Para implementar a função Pop(), você precisa primeiro encontrar o elemento no topo da pilha usando Peek(). Em seguida, precisa remover o elemento do topo (usando a função RemoveElement[]) e também retornar uma nova pilha sem esse elemento. É possível usar uma tupla para retornar a nova pilha e o elemento removido simultaneamente. Por causa de expressões falíveis para o acesso da matriz e da chamada para Peek(), Pop() deve ter os especificadores <decides><transacts>.

Código completo

O código completo da classe stack é fornecido abaixo.

stack<public>(t:type) := class:
    Elements<internal>:[]t = array{}

    # Adiciona NewElement ao topo da pilha retornando uma nova
    # pilha com NewElement no topo
    Push<public>(NewElement:t):stack(t)=
        stack(t){Elements := Elements + array{NewElement}}

    # Remove o elemento no topo da pilha e retorna uma tupla de uma nova
    # pilha com o elemento superior removido e o elemento removido.
    Pop<public>()<decides><transacts>:tuple(stack(t),t)=
        FirstElement := Peek[]
        (stack(t){Elements := Elements.RemoveElement[Elements.Length - 1]}, FirstElement)

    # Retorna o tamanho da pilha.
    Size<public>()<transacts>:int=
        Elements.Length

    # Tem êxito quando a pilha está vazia.
    IsEmpty<public>()<decides><transacts>:void=
        Size() = 0

    # Retorna o elemento superior da pilha.
    Peek<public>()<decides><transacts>:t=
        Elements[Elements.Length - 1]

Filas

Você pode pensar em uma fila como uma esteira rolante de sushis. Suponha que você esteja em um restaurante de sushi que envia pratos de sushi, um de cada vez, por uma esteira rolante, e eles chegam na ordem em que foram pedidos. Você pode desenfileirar o prato na frente da fila para pegá-lo e comê-lo, mas só pode pegar um prato de cada vez. Quando quiser pedir um novo prato, você peça ao chef para enfileirar um prato no final da fila. Se a fila já tiver outros pratos de sushi, você terá que continuar comendo os pratos na frente da fila até chegar ao prato no final. O primeiro prato de sushi adicionado será o primeiro a ser removido. Isso cria uma fila FIFO, ou seja, uma estrutura de dados em que primeiro a entrar é o primeiro a sair.

Quando usar

Filas são úteis quando você precisa processar dados com base no momento em que eles chegam. Alguns exemplos incluem atender clientes em um drive-thru, alinhar ligações em uma central de atendimento ou fazer uma lista de perguntas ao jogador em uma entrevista. Por exemplo, se você precisa criar uma sala de espera para os jogadores enquanto eles fazem uma tarefa ou passam por uma experiência, um de cada vez, pode usar uma fila para ordená-los por ordem de chegada.

Implementação no Verse

A API Verse não tem uma implementação integrada de filas, mas você mesmo pode criar uma.

Assim como nas pilhas, você pode representar os elementos da fila usando qualquer estrutura de dados ordenada, como uma matriz ou uma lista vinculada. Neste exemplo, você usará uma matriz, pois ela oferece acesso fácil ao início e ao final da fila. Para obter uma implementação de fila usando uma lista vinculada, confira este trecho de código.

queue<public>(t:type) := class:
    Elements<internal>:[]t = array{}

A matriz Elements armazena os objetos na fila do tipo t. Isso significa que você pode inicializar uma fila com qualquer tipo de elemento, como int, float, queue etc. Usar type como argumento para a classe stack é um exemplo de tipo paramétrico](parametric-types-in-verse).

Como acontece nas pilhas, as filas precisam de algumas funções auxiliares. Você precisa saber onde estão o início e o final da fila para poder executar Enqueue() e Dequeue(). Também é útil saber o tamanho da fila e se ela está vazia. Você os definirá em quatro funções:Size(), IsEmpty(), Front() e Back().

# Retorna o tamanho da fila
Size<public>()<transacts>:int=
    Elements.Length

# Tem êxito quando a fila está vazia
IsEmpty<public>()<decides><transacts>:void=
    Size() = 0

# Retorna o elemento que está no início da fila.
Front<public>()<decides><transacts>:t=
    Elements[0]

# Retorna o elemento que está no final da fila.
Rear<public>()<decides><transacts>:t=
    Elements[Elements.Length - 1]

A função Size() retorna o valor Length da matriz Elements. A função IsEmpty() chama a função Size() e tem o especificador <transacts>, o que significa que falhará se Size() não for igual a 0.

As funções Front() e Rear() retornam o elemento nos índices frontal (índice 0) e traseiro (Comprimento - 1) da matriz de elementos. Ambas as funções possuem os especificadores <decides><transacts> já que o acesso à matriz pode falhar se ela estiver vazia.

Assim como stack, a classe queue também precisa usar uma função de construtor para atribuir a matriz Elements. A função de construtor permite acessar o valor de Elements e atribuí-lo a uma matriz inicial de elementos.

# Cria e retorna uma fila a partir de uma matriz inicial de elementos InitialElements.
CreateQueue<public><constructor>(InitialElements:[]t where t:type) := queue(t):
    Elements := InitialElements

Enfileirar e desenfileirar

Para adicionar e remover elementos da fila, você precisa enfileirar o novo elemento no final da fila ou desenfileirar um elemento do início.

# Adiciona um novo elemento ao final da fila, retornando uma
# nova fila com NewElement no final.
Enqueue<public>(NewElement:t):queue(t)=
    queue(t){Elements := Elements + array{NewElement}}

# Remove o elemento do início da fila e retorna uma tupla de
# uma nova fila com o elemento removido e o elemento removido.
Dequeue<public>()<decides><transacts>:tuple(queue(t),t)=
    FirstElement := Front[]
    (queue(t){Elements := Elements.RemoveElement[0]}, FirstElement)

A função Enqueue() usa o elemento que você deseja inserir na fila e retorna uma nova fila com o novo elemento no final. Retornar uma nova fila em vez de modificar a fila atual é um exemplo de programação funcional e reduz o risco de efeitos colaterais.

Para a função Dequeue(), você precisa remover e retornar o elemento no início da fila, além de também retornar uma nova fila com o primeiro elemento removido (usando a função RemoveElement[]). Por causa de expressões falíveis para o acesso da matriz e da chamada para Front(), Dequeue() deve ter os especificadores <decides><transacts>.

Código completo

O código completo da classe Queue é fornecido abaixo.

queue<public>(t:type) := class:
    Elements<internal>:[]t = array{}

    # Adiciona um novo elemento ao final da fila, retornando uma
    # nova fila com NewElement no final.
    Enqueue<public>(NewElement:t):queue(t)=
        queue(t){Elements := Elements + array{NewElement}}

    # Remove o elemento do início da fila e retorna uma tupla de
    # uma nova fila com o elemento removido e o elemento removido.
    Dequeue<public>()<decides><transacts>:tuple(queue(t),t)=
        FirstElement := Front[]
        (queue(t){Elements := Elements.RemoveElement[0]}, FirstElement)

    # Retorna o tamanho da fila
    Size<public>()<transacts>:int=
        Elements.Length

    # Tem êxito quando a fila está vazia
    IsEmpty<public>()<decides><transacts>:void=
        Size() = 0

    # Retorna o elemento que está no início da fila.
    Front<public>()<decides><transacts>:t=
        Elements[0]

    # Retorna o elemento que está no final da fila.
    Rear<public>()<decides><transacts>:t=
        Elements[Elements.Length - 1]
       
# Cria e retorna uma fila a partir de uma matriz inicial de elementos InitialElements.
CreateQueue<public><constructor>(InitialElements:[]t where t:type) := queue(t):
    Elements := InitialElements

queue<public>(t:type) := class:
    Elements<internal>:[]t = array{}

# Adiciona um novo elemento ao final da fila, retornando uma
    # nova fila com NewElement no final.
    Enqueue<public>(NewElement:t):queue(t)=
        queue(t){Elements := Elements + array{NewElement}}

# Remove o elemento do início da fila e retorna uma tupla de
    # uma nova fila com o elemento removido e o elemento removido.
    Dequeue<public>()<decides><transacts>:tuple(queue(t),t)=
        FirstElement := Front[]
        (queue(t){Elements := Elements.RemoveElement[0]}, FirstElement)

# Retorna o tamanho da fila
    Size<public>()<transacts>:int=
        Elements.Length

# Tem êxito quando a fila está vazia
    IsEmpty<public>()<decides><transacts>:void=
        Size() = 0

# Retorna o elemento que está no início da fila.
    Front<public>()<decides><transacts>:t=
        Elements[0]

# Retorna o elemento que está no final da fila.
    Rear<public>()<decides><transacts>:t=
        Elements[Elements.Length - 1]
       
# Cria e retorna uma fila a partir de uma matriz inicial de elementos InitialElements.
CreateQueue<public><constructor>(InitialElements:[]t where t:type) := queue(t):
    Elements := InitialElements

Por conta própria

Há muitas maneiras de iterar e aprimorar pilhas e filas, e você deve explorar diferentes maneiras de adicionar funcionalidades. Aqui estão algumas ideias para você começar:

Você pode transformar uma fila em uma fila circular, em que o último elemento está conectado ao primeiro elemento, e a fila continua em loop?
Que tal uma fila de prioridades, em que os objetos são ordenados com base no momento em que entram na fila E em algum outro valor?
Você pode criar jogos usando uma pilha, como o Tower of Hanoi? E que tal um jogo de restaurante, em que os clientes têm que esperar em uma fila?