Estrutura de dados: Filas(Queues e Deques)-Conceitos, Princípios Fundamentais e Resolução de problemas.

O que é uma Fila?

Uma Fila (Queue em inglês) é uma estrutura de dados fundamental na ciência da computação. Ela segue o princípio FIFO (First-In-First-Out), que significa que o primeiro elemento inserido na fila será o primeiro a ser removido, também conhecido como "First Come, First Served" (FCFS), ou, "Primeiro a Chegar, Primeiro a ser Servido" em português.

Mas para que serve uma Fila?

Filas são usadas quando precisamos processar elementos em uma ordem específica, geralmente na ordem em que foram recebidos. Alguns motivos para usar Filas incluem:

1. Processamento de Tarefas: Quando temos várias tarefas a serem executadas, podemos colocá-las em uma fila e processá-las na ordem de chegada.

2. Gerenciamento de Recursos: Filas podem ser usadas para gerenciar recursos compartilhados, como impressoras ou conexões de rede. As solicitações são enfileiradas e atendidas na ordem em que foram recebidas.

3. Buffer de Dados: Filas podem atuar como um buffer entre produtores e consumidores de dados. O produtor insere elementos na fila, enquanto o consumidor os retira e processa.

Onde as Filas são Usadas

Filas têm várias aplicações no mundo real e na computação. Alguns exemplos incluem:

1. Atendimento ao Cliente: Em call centers ou suporte ao cliente, as chamadas são colocadas em uma fila e atendidas pelos atendentes na ordem em que foram recebidas.

2. Processamento de Pedidos: Em sistemas de comércio eletrônico, os pedidos dos clientes são enfileirados e processados na ordem de chegada.

3. Impressão de Documentos: Quando vários usuários enviam documentos para impressão, eles são enfileirados e impressos na ordem em que foram submetidos.

4. Agendamento de Tarefas: Em sistemas operacionais, as tarefas são colocadas em uma fila de prioridade e executadas com base na sua prioridade e ordem de chegada.

Operações e princípios

Os principais princípios envolvidos no funcionamento de uma Fila são:

1. FIFO (First-In-First-Out): O primeiro elemento inserido é o primeiro a ser removido.

2. Enqueue: A operação de inserir um elemento no final da fila.

3. Dequeue: A operação de remover o elemento do início da fila.

4. Front: O elemento no início da fila, pronto para ser removido.

5. Rear ou Back: O último elemento inserido na fila.

Exemplos da Vida Real

Antes de pensarmos em programação, vamos ver alguns exemplos de Filas na vida real:

1. Fila de Banco: Quando você vai ao banco, pega uma senha e aguarda sua vez na fila. A pessoa com a senha chamada é atendida, e novas pessoas se juntam ao final da fila.

2. Fila de Cinema: Quando você compra ingressos para um filme, entra na fila para entrar na sala. A primeira pessoa a chegar é a primeira a entrar, e novos espectadores se juntam ao final da fila.

3. Fila de Supermercado: No caixa do supermercado, os clientes formam uma fila para pagar suas compras. O primeiro cliente a chegar é o primeiro a ser atendido, e novos clientes se juntam ao final da fila.

Esses são apenas alguns exemplos de como as Filas estão presentes em nosso dia a dia. Na programação, as Filas são implementadas usando arrays ou listas encadeadas e oferecem operações eficientes para inserção e remoção de elementos.

Agora que entendemos os conceitos e princípios vamos iniciar os estudo de filas usando Javascript. Vamos lá!

Criando nossa classe Queue

Vamos criar uma classe que irá representar uma Fila.

class Queue {
  constructor() {
    this.items = {};
    this.count = 0;
    this.lowestCount = 0;
  }

  // Implementação dos métodos...
}

Agora, vamos implementar alguns métodos que farão parte da classe, pelos quais poderemos manipular e controlar a entrada e saída de elementos da nossa fila.

Enfileirar (Enqueue)

enqueue(element) {
  this.items[this.count] = element;
  this.count++;
}

O método enqueue recebe um parâmetro element, que representa o elemento a ser adicionado à fila.

Utilizamos o atributo count como chave para adicionar o elemento ao objeto items. Isso garante que cada elemento tenha uma chave única baseada na ordem em que foi adicionado.

Incrementamos o valor de count em 1 para manter o controle do número total de elementos que foram adicionados à fila.

Desenfileirar (Dequeue)

dequeue() {
  if (this.isEmpty()) {
    return "A fila está vazia.";
  }
  const result = this.items[this.lowestCount];
  delete this.items[this.lowestCount];
  this.lowestCount++;
  return result;
}

O método dequeue remove e retorna o elemento mais antigo da fila (o primeiro elemento que foi adicionado).

Primeiro, verificamos se a fila está vazia usando o método isEmpty(). Se estiver vazia, retornamos a mensagem "A fila está vazia.". Se a fila não estiver vazia, obtemos o elemento mais antigo usando this.items[this.lowestCount]. O atributo lowestCount sempre aponta para o índice do elemento mais antigo na fila.

Removemos o elemento mais antigo do objeto items usando o operador delete e incrementamos o valor de lowestCount em 1 para atualizar o índice do próximo elemento mais antigo, depois retornamos o elemento desenfileirado.

Está Vazia (IsEmpty)

isEmpty() {
  return this.size() === 0;
}

O método isEmpty verifica se a fila está vazia. Utilizamos o método size() para obter o tamanho atual da fila e comparamos com zero. Se o tamanho for igual a zero, significa que a fila está vazia e retornamos true. Caso contrário, retornamos false.

Frente (Front)

front() {
  if (this.isEmpty()) {
    return "A fila está vazia.";
  }
  return this.items[this.lowestCount];
}

O método front retorna o elemento mais antigo da fila (o primeiro elemento que foi adicionado) sem removê-lo.

Primeiro, verificamos se a fila está vazia usando o método isEmpty(). Se estiver vazia, retornamos a mensagem "A fila está vazia.".

Se a fila não estiver vazia, retornamos o elemento mais antigo usando this.items[this.lowestCount]. O atributo lowestCount sempre aponta para o índice do elemento mais antigo na fila.

Tamanho (Size)

size() {
  return this.count - this.lowestCount;
}

O método size retorna o número de elementos atualmente na fila.

Calculamos o tamanho da fila subtraindo lowestCount de count. Isso nos dá a diferença entre o número total de elementos adicionados (count) e o índice do elemento mais antigo (lowestCount).

Imprimir Fila (PrintQueue)

printQueue() {
  if (this.isEmpty()) {
    console.log("A fila está vazia.");
  } else {
    let elements = [];
    for (let i = this.lowestCount; i < this.count; i++) {
      elements.push(this.items[i]);
    }
    console.log("Elementos da fila:", elements.join(", "));
  }
}

O método printQueue imprime os elementos da fila, para isso primeiro, verificamos se a fila está vazia usando o método isEmpty(), se estiver vazia, imprimimos a mensagem "A fila está vazia.". Caso a fila não esteja vazia, criamos um array vazio chamado elements para armazenar os elementos da fila.

Em seguida utilizamos um loop for para percorrer os elementos desde lowestCount até count - 1. Isso garante que percorremos apenas os índices válidos dos elementos na fila e adicionamos cada elemento ao array elements usando o método push().

Por fim, imprimimos a mensagem "Elementos da fila:" seguida dos elementos separados por vírgula, usando o método join(", ") para unir os elementos do array em uma string.

Entendendo um pouco mais

Na nossa implementação da classe Queue, o primeiro índice da fila pode não ser necessariamente zero, e é por isso que usamos o atributo lowestCount.

Quando criamos uma instância da classe Queue, inicializamos o atributo lowestCount com o valor zero. Isso significa que, inicialmente, o primeiro elemento da fila será adicionado na posição zero do objeto items.

No entanto, à medida que enfileiramos e desenfileiramos elementos, o valor de lowestCount pode mudar. Vejamos um exemplo:

const queue = new Queue();

queue.enqueue("A");
queue.enqueue("B");
queue.enqueue("C");

console.log(queue.items); // Output: { 0: "A", 1: "B", 2: "C" }

queue.dequeue();

console.log(queue.items); // Output: { 1: "B", 2: "C" }
console.log(queue.lowestCount); // Output: 1

Nesse exemplo:

1. Enfileiramos os elementos "A", "B" e "C" na fila. Nesse momento, o objeto items contém os elementos nos índices 0, 1 e 2, respectivamente.

2. Quando desenfileiramos um elemento usando dequeue(), removemos o elemento no índice lowestCount, que inicialmente é zero. Portanto, o elemento "A" é removido.

3. Após a remoção, o objeto items agora contém os elementos "B" e "C" nos índices 1 e 2, respectivamente.

4. O valor de lowestCount é incrementado para 1, indicando que o próximo elemento a ser desenfileirado está no índice 1.

Agora, se continuarmos a desenfileirar elementos sem enfileirar novos elementos, o valor de lowestCount continuará aumentando:

queue.dequeue();

console.log(queue.items); // Output: { 2: "C" }
console.log(queue.lowestCount); // Output: 2

queue.dequeue();

console.log(queue.items); // Output: {}
console.log(queue.lowestCount); // Output: 3

Nesse caso:

1. Desenfileiramos o elemento "B", que estava no índice 1. Agora, o objeto items contém apenas o elemento "C" no índice 2.

2. O valor de lowestCount é incrementado para 2, indicando que o próximo elemento a ser desenfileirado (se houver) estará no índice 2.

3. Desenfileiramos o último elemento, "C". O objeto items fica vazio.

4. O valor de lowestCount é incrementado para 3, mesmo que não haja mais elementos na fila.

Portanto, o uso do atributo lowestCount nos permite rastrear o índice do elemento mais antigo na fila, independentemente de onde ele esteja no objeto items. Isso é especialmente útil quando desenfileiramos elementos e os índices no objeto items não começam mais em zero.

Ao usar lowestCount, podemos sempre acessar o elemento mais antigo usando this.items[this.lowestCount], garantindo que estamos obtendo o elemento correto, mesmo que o primeiro índice da fila não seja zero.

Testando a classe com mais um exemplo

Vamos mexer em uma lista de nomes de animais para ficar mais divertido. Vamos tirar e inserir elementos, além de poder usar os outros métodos que escrevemos acima.

class Queue {
  constructor() {
    this.items = {};
    this.count = 0;
    this.lowestCount = 0;
  }

  enqueue(element) {
    this.items[this.count] = element;
    this.count++;
  }

  dequeue() {
    if (this.isEmpty()) {
      return "A fila está vazia.";
    }
    const result = this.items[this.lowestCount];
    delete this.items[this.lowestCount];
    this.lowestCount++;
    return result;
  }

  front() {
    if (this.isEmpty()) {
      return "A fila está vazia.";
    }
    return this.items[this.lowestCount];
  }

  size() {
    return this.count - this.lowestCount;
  }

  isEmpty() {
    return this.size() === 0;
  }

  printQueue() {
    if (this.isEmpty()) {
      console.log("A fila está vazia.");
    } else {
      let elements = [];
      for (let i = this.lowestCount; i < this.count; i++) {
        elements.push(this.items[i]);
      }
      console.log("Elementos da fila:", elements.join(", "));
    }
  }
}

// Criando uma instância da fila
const animalQueue = new Queue();

// Verificando se a fila está vazia
console.log("A fila está vazia?", animalQueue.isEmpty()); // Output: true

// Adicionando elementos à fila
animalQueue.enqueue("Cachorro");
animalQueue.enqueue("Gato");
animalQueue.enqueue("Coelho");

// Imprimindo os elementos da fila
animalQueue.printQueue(); // Output: Elementos da fila: Cachorro, Gato, Coelho

// Verificando o tamanho da fila
console.log("Tamanho da fila:", animalQueue.size()); // Output: 3

// Verificando o elemento da frente da fila
console.log("Elemento da frente:", animalQueue.front()); // Output: Cachorro

// Removendo elementos da fila
console.log("Elemento removido:", animalQueue.dequeue()); // Output: Cachorro
console.log("Elemento removido:", animalQueue.dequeue()); // Output: Gato

// Imprimindo os elementos da fila após a remoção
animalQueue.printQueue(); // Output: Elementos da fila: Coelho

// Adicionando mais elementos à fila
animalQueue.enqueue("Elefante");
animalQueue.enqueue("Leão");

// Imprimindo os elementos da fila após a adição
animalQueue.printQueue(); // Output: Elementos da fila: Coelho, Elefante, Leão

// Verificando o tamanho da fila
console.log("Tamanho da fila:", animalQueue.size()); // Output: 3

// Removendo todos os elementos da fila
console.log("Elemento removido:", animalQueue.dequeue()); // Output: Coelho
console.log("Elemento removido:", animalQueue.dequeue()); // Output: Elefante
console.log("Elemento removido:", animalQueue.dequeue()); // Output: Leão

// Verificando se a fila está vazia após a remoção de todos os elementos
console.log("A fila está vazia?", animalQueue.isEmpty()); // Output: true

Agora vamos olhar o nosso exemplo passo a passo:

1. Criamos uma instância da classe Queue chamada animalQueue para manipular a fila de nomes de animais.

2. Verificamos se a fila está vazia usando o método isEmpty(). Como acabamos de criar a fila, ela está vazia e o resultado é true.

3. Adicionamos três elementos à fila usando o método enqueue(): "Cachorro", "Gato" e "Coelho". Esses elementos são inseridos na fila na ordem em que foram adicionados.

4. Imprimimos os elementos da fila usando o método printQueue(). Isso nos mostra os elementos atualmente na fila: "Cachorro", "Gato" e "Coelho".

5. Verificamos o tamanho da fila usando o método size(). O tamanho atual da fila é 3, pois adicionamos três elementos.

6. Verificamos o elemento da frente da fila usando o método front(). O elemento da frente é "Cachorro", que foi o primeiro elemento adicionado à fila.

7. Removemos dois elementos da fila usando o método dequeue(). O primeiro elemento removido é "Cachorro" e o segundo é "Gato". Esses elementos são removidos na ordem em que foram adicionados (primeiro a entrar, primeiro a sair - FIFO).

8. Imprimimos os elementos da fila após a remoção usando o método printQueue(). Agora, a fila contém apenas o elemento "Coelho".

9. Adicionamos mais dois elementos à fila usando o método enqueue(): "Elefante" e "Leão". Esses elementos são inseridos na fila após o elemento "Coelho".

10. Imprimimos os elementos da fila após a adição usando o método printQueue(). Agora, a fila contém os elementos "Coelho", "Elefante" e "Leão".

11. Verificamos o tamanho da fila usando o método size(). O tamanho atual da fila é 3, pois temos três elementos na fila.

12. Removemos todos os elementos da fila usando o método dequeue() três vezes. Os elementos são removidos na ordem em que foram adicionados: "Coelho", "Elefante" e "Leão".

13. Verificamos se a fila está vazia após a remoção de todos os elementos usando o método isEmpty(). Como removemos todos os elementos, a fila está vazia e o resultado é true.

Como vimos nesse exemplo podemos usar a classe Queue para manipular uma fila de nomes de animais, adicionando elementos com enqueue(), removendo elementos com dequeue(), verificando o tamanho da fila com size(), obtendo o elemento da frente com front(), imprimindo os elementos da fila com printQueue() e verificando se a fila está vazia com isEmpty()..

Estrutura de dados Deque

Vamos aprender sobre a estrutura de dados Deque, também conhecida como fila de duas pontas.

Um Deque (Double-Ended Queue) é uma estrutura de dados linear que permite inserções e remoções em ambas as extremidades da fila. Diferentemente de uma fila convencional (Queue), onde os elementos são inseridos em uma extremidade (rear) e removidos da outra extremidade (front), um Deque oferece maior flexibilidade, permitindo inserções e remoções tanto no início quanto no final da estrutura.

Características do Deque:

1. Estrutura de dados linear: Um Deque é uma estrutura de dados linear, o que significa que os elementos são armazenados e acessados em uma ordem sequencial.

2. Inserção e remoção em ambas as extremidades: Um Deque permite a inserção e remoção de elementos tanto no início quanto no final da estrutura. Isso proporciona maior flexibilidade em comparação com uma fila convencional.

3. FIFO e LIFO: Um Deque pode ser usado tanto como uma fila (First-In-First-Out) quanto como uma pilha (Last-In-First-Out), dependendo de como os elementos são inseridos e removidos.

4. Eficiência: As operações de inserção e remoção em um Deque geralmente têm uma complexidade de tempo constante O(1), o que significa que essas operações são executadas de forma eficiente, independentemente do tamanho do Deque.

Operações básicas do Deque:

1. addFront(element): Insere um elemento no início do Deque.

2. addRear(element): Insere um elemento no final do Deque.

3. removeFront(): Remove e retorna o elemento do início do Deque.

4. removeRear(): Remove e retorna o elemento do final do Deque.

5. peekFront(): Retorna o elemento do início do Deque sem removê-lo.

6. peekRear(): Retorna o elemento do final do Deque sem removê-lo.

7. isEmpty(): Verifica se o Deque está vazio.

8. size(): Retorna o número de elementos presentes no Deque.

O Deque pode ser implementado usando uma variedade de estruturas de dados subjacentes, como arrays dinâmicos ou listas encadeadas. A escolha da estrutura de dados subjacente depende dos requisitos específicos do problema e das operações mais frequentes.

Vejamos uma implementação básica de um Deque usando um array dinâmico em JavaScript:

class Deque {
  constructor() {
    this.items = {};
    this.count = 0;
    this.lowestCount = 0;
  }

  addFront(element) {
    if (this.isEmpty()) {
      this.addRear(element);
    } else if (this.lowestCount > 0) {
      this.lowestCount--;
      this.items[this.lowestCount] = element;
    } else {
      for (let i = this.count; i > 0; i--) {
        this.items[i] = this.items[i - 1];
      }
      this.count++;
      this.lowestCount = 0;
      this.items[0] = element;
    }
  }

  addRear(element) {
    this.items[this.count] = element;
    this.count++;
  }

  removeFront() {
    if (this.isEmpty()) {
      return undefined;
    }
    const result = this.items[this.lowestCount];
    delete this.items[this.lowestCount];
    this.lowestCount++;
    return result;
  }

  removeRear() {
    if (this.isEmpty()) {
      return undefined;
    }
    this.count--;
    const result = this.items[this.count];
    delete this.items[this.count];
    return result;
  }

  peekFront() {
    if (this.isEmpty()) {
      return undefined;
    }
    return this.items[this.lowestCount];
  }

  peekRear() {
    if (this.isEmpty()) {
      return undefined;
    }
    return this.items[this.count - 1];
  }

  isEmpty() {
    return this.size() === 0;
  }

  size() {
    return this.count - this.lowestCount;
  }

  clear() {
    this.items = {};
    this.count = 0;
    this.lowestCount = 0;
  }

  toString() {
    if (this.isEmpty()) {
      return '';
    }
    let objString = `${this.items[this.lowestCount]}`;
    for (let i = this.lowestCount + 1; i < this.count; i++) {
      objString = `${objString},${this.items[i]}`;
    }
    return objString;
  }
}

Nesta implementação, usamos um objeto JavaScript (this.items) para armazenar os elementos do Deque. O atributo count mantém o controle do próximo índice disponível para inserção no final do Deque, enquanto o atributo lowestCount mantém o controle do índice do primeiro elemento no Deque.

Os métodos addFront e addRear são usados para inserir elementos no início e no final do Deque, respectivamente. Os métodos removeFront e removeRear são usados para remover e retornar elementos do início e do final do Deque, respectivamente. Os métodos peekFront e peekRear permitem visualizar os elementos do início e do final do Deque sem removê-los.

Além disso, temos os métodos isEmpty para verificar se o Deque está vazio, size para obter o número de elementos no Deque, clear para limpar o Deque e toString para obter uma representação de string dos elementos do Deque.

O Deque é uma estrutura de dados versátil e pode ser usado em várias situações, como:

1. Gerenciamento de histórico: Um Deque pode ser usado para manter um histórico de ações realizadas, permitindo desfazer (undo) e refazer (redo) operações.

2. Processamento de palíndromos: Um Deque pode ser usado para verificar se uma string é um palíndromo, comparando os caracteres das extremidades do Deque.

3. Simulação de filas e pilhas: Um Deque pode ser usado para simular o comportamento de uma fila ou pilha, dependendo de como os elementos são inseridos e removidos.

4. Algoritmos de busca e otimização: Alguns algoritmos, como a busca em largura (BFS) e a busca em profundidade (DFS), podem ser implementados usando um Deque para manter o controle dos elementos a serem visitados.

Adicionando um elemento na frente do Deque

A partir de agora exploraremos detalhadamente o que acontece quando um elemento é adicionado na frente de um Deque, considerando três situações distintas: quando o Deque está vazio, quando um elemento é removido da frente do Deque e quando o índice lowestCount é igual a zero. Compreender esses cenários é essencial para entender o funcionamento interno do Deque e como ele gerencia a inserção de elementos de maneira eficiente.

1. Adicionando um elemento na frente de um Deque vazio:

Quando o Deque está vazio e um elemento é adicionado na frente, o processo é simples. O elemento é inserido no início do Deque, ocupando a primeira posição. Nesse caso, tanto o lowestCount quanto o count são atualizados para 0, indicando que o Deque agora possui um único elemento.

Deque vazio: []
Adicionar elemento 'A' na frente: ['A']
lowestCount = 0, count = 1

2. Adicionando um elemento na frente quando um elemento é removido da frente do Deque:

Quando um elemento é removido da frente do Deque, o lowestCount é incrementado para indicar que a posição do primeiro elemento mudou. Ao adicionar um novo elemento na frente, podemos aproveitar o espaço vazio deixado pelo elemento removido.

Nesse cenário, o lowestCount é decrementado em 1 e o novo elemento é inserido na posição indicada por lowestCount. Isso evita a necessidade de deslocar todos os elementos existentes para abrir espaço para o novo elemento.

Deque: ['A', 'B', 'C']
lowestCount = 1, count = 3
Remover elemento da frente: ['B', 'C']
lowestCount = 2, count = 3
Adicionar elemento 'D' na frente: ['D', 'B', 'C']
lowestCount = 1, count = 3

1. Adicionando um elemento na frente quando o lowestCount é igual a zero:

Quando o lowestCount é igual a zero, significa que não há espaço vazio no início do Deque para inserir o novo elemento. Nesse caso, é necessário deslocar todos os elementos existentes uma posição para a direita, a fim de abrir espaço para o novo elemento na frente.

O processo envolve percorrer o Deque de trás para frente, movendo cada elemento uma posição para a direita. Em seguida, o novo elemento é inserido na posição 0 (lowestCount), e o count é incrementado para refletir o aumento no tamanho do Deque.

Deque: ['A', 'B', 'C']
lowestCount = 0, count = 3
Adicionar elemento 'D' na frente:
Deslocar elementos para a direita: ['A', 'B', 'C', vazio]
Inserir 'D' na posição 0: ['D', 'A', 'B', 'C']
lowestCount = 0, count = 4

Em resumo, ao adicionar um elemento na frente de um Deque, temos três cenários possíveis:

1. Quando o Deque está vazio, o elemento é simplesmente inserido na primeira posição.

2. Quando um elemento é removido da frente, o novo elemento pode aproveitar o espaço vazio deixado pelo elemento removido, evitando deslocamentos desnecessários.

3. Quando o lowestCount é igual a zero, é necessário deslocar todos os elementos para a direita para abrir espaço para o novo elemento na frente.

Esses cenários garantem que a adição de elementos na frente do Deque seja eficiente e utilize adequadamente o espaço disponível na estrutura de dados.

Exemplo de problema

No ensino de computação, é comum utilizarmos exemplos lúdicos e interativos para ilustrar conceitos e aplicações de estruturas de dados. Um desses exemplos é o jogo da "Batata Quente" (Hot Potato), que pode ser simulado usando as estruturas de dados Fila (Queue) e Deque (Double-Ended Queue). Essa atividade proporciona uma oportunidade de aprendizado prático para os alunos, permitindo que visualizem o funcionamento dessas estruturas de dados em um contexto mais familiar.

A "Batata Quente" é uma brincadeira em que os participantes formam um círculo e passam um objeto (geralmente uma batata imaginária) de mão em mão, enquanto uma música toca ou uma contagem é feita. Quando a música para ou a contagem chega a um determinado número, a pessoa que estiver segurando a batata é eliminada do jogo. O processo continua até que reste apenas um jogador, que é declarado o vencedor.

Essa brincadeira recebe o nome de "Batata Quente" porque a batata imaginária é considerada "quente", criando uma sensação de urgência para que os jogadores a passem rapidamente e evitem ser eliminados.

Para simular o jogo da "Batata Quente" usando as estruturas de dados Fila (Queue) e Deque, podemos seguir os seguintes passos:

1. Criar uma instância da classe Queue para representar o círculo de jogadores.

2. Adicionar os nomes dos jogadores à fila ou ao deque, utilizando os métodos enqueue (para Fila).

3. Definir um contador para controlar o número de passagens da batata antes da eliminação.

4. Enquanto houver mais de um jogador na fila ou no deque:

   • Percorrer a fila ou o deque e passar a batata de jogador para jogador até atingir o contador definido, utilizando os métodos dequeue e enqueue (para Fila) .

   • Eliminar o jogador que estiver segurando a batata quando o contador chegar a zero, utilizando o método dequeue (para Fila).

   • Reiniciar o contador para a próxima rodada.

5. O último jogador restante na fila ou no deque é declarado o vencedor.

Vamos ao pensamento em torno da fila, se trata de um exemplo de implementação da simulação usando a classe Queue, dos nossos exemploas anteriores, escrita em JavaScript:

function hotPotato(nameList, num) {
  const queue = new Queue();

  // Adiciona os nomes dos jogadores à fila
  for (let i = 0; i < nameList.length; i++) {
    queue.enqueue(nameList[i]);
  }

  let eliminated = '';

  // Enquanto houver mais de um jogador na fila
  while (queue.size() > 1) {
    // Passa a batata de jogador para jogador
    for (let i = 0; i < num; i++) {
      queue.enqueue(queue.dequeue());
    }

    // Elimina o jogador que está segurando a batata
    eliminated = queue.dequeue();
    console.log(`${eliminated} foi eliminado(a) do jogo.`);
  }

  // Retorna o vencedor
  return queue.dequeue();
}

// Exemplo de uso
const names = ['João', 'Maria', 'Pedro', 'Ana', 'Lucas'];
const numPassagens = 7;
const vencedor = hotPotato(names, numPassagens);
console.log(`O vencedor é: ${vencedor}`);

A saida será a seguinte:

Maria foi eliminado(a) do jogo.
Lucas foi eliminado(a) do jogo.
João foi eliminado(a) do jogo.
Ana foi eliminado(a) do jogo.
O vencedor é: Pedro

• Na primeira rodada, após 7 passagens da batata, Maria é eliminada do jogo.

• Na segunda rodada, após 7 passagens da batata, Lucas é eliminado do jogo.

• Na terceira rodada, após 7 passagens da batata, João é eliminado do jogo.

• Na quarta rodada, após 7 passagens da batata, Ana é eliminada do jogo.

• Como Pedro é o último jogador restante na fila, ele é declarado o vencedor.

A saída mostra a sequência de eliminações dos jogadores a cada rodada, até que reste apenas um jogador, que é o vencedor do jogo.

Verificando se uma palavra é ou não um palíndromo.

Um palíndromo é uma palavra, frase ou sequência de caracteres que pode ser lida da mesma forma tanto da esquerda para a direita quanto da direita para a esquerda, desconsiderando espaços, pontuações e diferenças entre letras maiúsculas e minúsculas. Alguns exemplos de palíndromos são: "radar", "A base do teto desaba", "Socorram-me, subi no ônibus em Marrocos".

Existem várias formas de resolver o problema de verificar se uma palavra ou frase é um palíndromo. Algumas abordagens comuns incluem:

1. Usando loops: Comparar os caracteres correspondentes do início e do fim da sequência, avançando em direção ao centro até que todos os caracteres sejam verificados.

2. Usando pilhas: Empilhar os caracteres da sequência em uma pilha e, em seguida, desempilhar e comparar com a sequência original.

3. Usando deques: Adicionar os caracteres da sequência em um deque e, em seguida, remover os caracteres das extremidades e compará-los.

4. Usando recursão: Comparar os caracteres correspondentes do início e do fim da sequência recursivamente até que todos os caracteres sejam verificados.

Hoje por ocasião da matéria veremos um exemplo de verificador de palíndromo usando a classe Deque do exemplo anterior:

function isPalindrome(str) {
  // Remover espaços e pontuações e converter para minúsculas
  str = str.toLowerCase().replace(/[^a-z0-9]/g, '');

  const deque = new Deque();

  // Adicionar os caracteres ao deque
  for (let i = 0; i < str.length; i++) {
    deque.addBack(str[i]);
  }

  // Verificar se é um palíndromo
  while (deque.size() > 1) {
    if (deque.removeFront() !== deque.removeBack()) {
      return false;
    }
  }

  return true;
}

// Exemplos de uso
console.log(isPalindrome('radar')); // true
console.log(isPalindrome('A base do teto desaba')); // true
console.log(isPalindrome('Socorram-me, subi no ônibus em Marrocos')); // true
console.log(isPalindrome('Hello')); // false

1. A função isPalindrome recebe uma string str como parâmetro.

2. Primeiro, a string é convertida para minúsculas usando o método toLowerCase() e, em seguida, todos os caracteres que não são letras ou números são removidos usando o método replace() com uma expressão regular. Isso garante que apenas os caracteres relevantes sejam considerados na verificação do palíndromo.

3. É criada uma instância da classe Deque chamada deque para armazenar os caracteres da string.

4. Os caracteres da string são adicionados ao deque usando o método addBack em um loop for.

5. É iniciado um loop while que continua enquanto houver mais de um caractere no deque, verificado pelo método size().

6. Dentro do loop while, o primeiro caractere é removido do deque usando o método removeFront() e o último caractere é removido usando o método removeBack(). Esses caracteres são comparados. Se forem diferentes, significa que a string não é um palíndromo e a função retorna false.

7. Se o loop while terminar sem encontrar caracteres diferentes, significa que a string é um palíndromo e a função retorna true.

8. No exemplo de uso, são testadas algumas strings para verificar se são palíndromos. Os resultados são impressos no console.

Saída do exemplo:

true
true
true
false

A saída mostra que as strings "radar", "A base do teto desaba" e "Socorram-me, subi no ônibus em Marrocos" são palíndromos, enquanto a string "Hello" não é um palíndromo.

Curiosidade

O laço de eventos (event loop) do navegador é um mecanismo fundamental do JavaScript que permite o processamento assíncrono de eventos e a execução de código de forma não bloqueante. Ele é responsável por coordenar a execução do código JavaScript, o processamento de eventos e a atualização da interface do usuário.

O JavaScript usa duas filas principais para controlar os eventos: a fila de mensagens (message queue) e a fila de tarefas (task queue).

1. Fila de Mensagens (Message Queue):

   • A fila de mensagens é uma fila de eventos que são gerados por fontes externas, como eventos do usuário (cliques, pressionamentos de teclas), temporizadores (setTimeout, setInterval) e requisições de rede (XMLHttpRequest, fetch).

   • Quando um evento ocorre, ele é adicionado à fila de mensagens para ser processado posteriormente.

   • O laço de eventos verifica constantemente se há eventos na fila de mensagens. Se houver, ele remove o evento da fila e o processa, executando o código associado a esse evento.

2. Fila de Tarefas (Task Queue):

   • A fila de tarefas é uma fila separada que contém as tarefas assíncronas que foram concluídas e estão prontas para serem executadas.

   • Quando uma tarefa assíncrona, como uma requisição de rede ou um temporizador, é concluída, ela é movida da fila de mensagens para a fila de tarefas.

   • O laço de eventos verifica a fila de tarefas somente após processar todos os eventos da fila de mensagens e após a conclusão da execução do código síncrono atual.

   • Se houver tarefas na fila de tarefas, o laço de eventos as executa uma por uma, na ordem em que foram adicionadas.

O funcionamento do laço de eventos pode ser resumido da seguinte maneira:

1. O código JavaScript é executado de forma síncrona, linha por linha.

2. Quando um evento ocorre (por exemplo, um clique do usuário), ele é adicionado à fila de mensagens.

3. Após a conclusão da execução do código síncrono atual, o laço de eventos verifica a fila de mensagens.

4. Se houver eventos na fila de mensagens, o laço de eventos remove o primeiro evento da fila e executa o código associado a esse evento.

5. Após processar todos os eventos da fila de mensagens, o laço de eventos verifica a fila de tarefas.

6. Se houver tarefas na fila de tarefas, o laço de eventos as executa uma por uma, na ordem em que foram adicionadas.

7. Após processar todas as tarefas da fila de tarefas, o laço de eventos aguarda por novos eventos na fila de mensagens.

8. O processo se repete continuamente, permitindo que o JavaScript lide com eventos assíncronos de forma eficiente.

Esse mecanismo de filas e o laço de eventos permitem que o JavaScript execute código de forma não bloqueante, evitando que a interface do usuário fique congelada enquanto tarefas demoradas são processadas. Ele garante que o código síncrono seja executado primeiro e, em seguida, lida com os eventos assíncronos à medida que eles ocorrem, mantendo a responsividade da aplicação.

É importante ressaltar que o JavaScript é single-threaded, o que significa que ele executa uma tarefa de cada vez. No entanto, graças ao laço de eventos e às filas, ele é capaz de lidar com múltiplas tarefas de forma assíncrona, dando a impressão de concorrência.

Conclusão

Espero que esta conversa tenha sido esclarecedora e tenha contribuído para aprimorar o conhecimento do aluno em programação, especialmente no que diz respeito ao JavaScript. Que o aluno entenda e não se esqueça que a prática é essencial para solidificar esses conceitos e aplicá-los em projetos reais.