sejam bem-vindos a maus uma aula do curso

hoje falaremos sobre duas sequencias muito utilizadas no dia a a dia de um programador: stacks e queues.

a parte boa dessas sequencias é que podem ser facilmente implementadas, nao necessariamete da forma mais eficiente, com arrays.

em aulas futuras veremos outras estruturas que podem servir como base para stacks e queues, como linked lists - que para stacks é uma implementação mais eficiente garantindo que a operação de push e pop sejam O(1).

para queues podemos usar uma lista duplamente ligada com um augmentation mantendo tracking da head e da tail

Stacks

Stacks são uma strutura de sequência de elementos que segue a regra LIFO (Last In, First Out). Isso significa que o último elemento a ser inserido é o primeiro a ser removido.

ADT de uma Stack

• push - adiciona um elemento no topo da stack;
• pop - remove o elemento do topo da stack;
• peek - retorna o elemento do topo da stack;
• isEmpty - retorna se a stack está vazia ou não;

Casos de uso

• Chamar funções - quando você chama uma função, o endereço de retorno é colocado em uma stack. Quando a função termina, o endereço é retirado da stack;
• Implementação de máquinas virtuais - quando você executa um programa, as instruções são colocadas em uma stack. Quando uma instrução é executada, ela é retirada da stack (uma VM famose que aplica esse conceito é a máquina virtual do Java);
• Desfazer (undo) - quando você desfaz uma ação, a ação é colocada em uma stack. Quando você refaz, a ação é retirada da stack;
  • Navegação - quando você navega em um site, cada página visitada é colocada em uma stack. Quando você clica no botão de voltar, a página é retirada da stack;

Queues

Queues são uma estrutura de sequência de elementos que segue a regra FIFO (First In, First Out). Isso significa que o primeiro elemento a ser inserido é o primeiro a ser removido.

ADT de uma Queue

• enqueue - adiciona um elemento no final da queue;
• dequeue - remove o elemento do início da queue;
• peek - retorna o elemento do início da queue;
• isEmpty - retorna se a queue está vazia ou não;

Casos de uso

• Filas de impressão - quando você manda um documento para a impressora, ele é colocado em uma queue. A impressora então imprime o documento que está no início da queue;
• Sistemas de arquivos - quando você salva um arquivo, ele é colocado em uma queue. O sistema operacional então salva o arquivo que está no início da queue;
• Eventos - quando você clica em um botão, um evento é colocado em uma queue. O navegador então executa o evento que está no início da queue (React, por exemplo, usa essa técnica para atualizar o DOM);