Pilhas e filas

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 que envie 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 em 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 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).

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().

# Returns the size of the stack.
    Size<public>()<transacts>:int=
        Elements.Length

    # Succeeds if the stack is empty.
    IsEmpty<public>()<decides><transacts>:void=
        Size() = 0

    # Returns the top element of the stack.
    Peek<public>()<decides><transacts>:t=

A função Size() simplesmente retorna o valor Tamanho 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.

# Creates and returns a stack from an initial array of elements 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.

# Adds NewElement to the top of the stack by returning a new
# stack with NewElement as the top
Push<public>(NewElement:t):stack(t)=
    stack(t){Elements := Elements + array{NewElement}}

# Removes the element on top of the stack and returns a tuple of both a new
# stack with the top element removed and the removed element.
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 de 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{}

    # Adds NewElement to the top of the stack by returning a new
    # stack with NewElement as the top
    Push<public>(NewElement:t):stack(t)=
        stack(t){Elements := Elements + array{NewElement}}

    # Removes the element on top of the stack and returns a tuple of both a new
    # stack with the top element removed and the removed element.

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 remover o prato da 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ê pede ao chef que coloque 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 em 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 uma implementação de fila usando uma lista vinculada, confira esse 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().

# Returns the size of the queue
Size<public>()<transacts>:int=
    Elements.Length

# Succeeds if the queue is empty
IsEmpty<public>()<decides><transacts>:void=
    Size() = 0

# Returns the element at the front of the queue.
Front<public>()<decides><transacts>:t=

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 Elements. 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.

# Creates and returns a queue from an initial array of elements InitialElements.
CreateQueue<public><constructor>(InitialElements:[]t where t:type) := queue(t):
    Elements := InitialElements

Colocar e remover da fila

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

# Adds a new element to the back of the queue by returning a
# new queue with NewElement at the back.
Enqueue<public>(NewElement:t):queue(t)=
    queue(t){Elements := Elements + array{NewElement}}

# Removes the element at the front of the queue and returns a tuple of
# both a new queue with the element removed and the removed element.
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 de 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{}

    # Adds a new element to the back of the queue by returning a
    # new queue with NewElement at the back.
    Enqueue<public>(NewElement:t):queue(t)=
        queue(t){Elements := Elements + array{NewElement}}

    # Removes the element at the front of the queue and returns a tuple of
    # both a new queue with the element removed and the removed element.

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?