#include <iostream>
#include <vector>

/*******************************************************************************
 * ATENÇÃO:
 * 1. Se precisar uma fila, use std::queue, ao invés de implementar a sua.
 * 2. Esta não é a melhor forma de resolver o problema. Use unique_ptr!
 *    (veja arquivo queue_list.cpp)
 */

// Representa uma Fila ou FIFO (first in first out), com operações de inserção
// (push), leitura do valor na frente (front), retirada (pop) e verificação se
// está vazia (is_emty).
class Queue {
  struct Node {
    int value;
    Node *next;
  };

  Node *_front{nullptr};
  Node *_back{nullptr};

  // Alguns métodos auxiliares.
  // Copia os dados de uma outra fila.
  void _copy_from(Queue const &q);
  // Limpa toda a fila (liberando memória).
  void _clear();

public:
  // Insere v no fim da fila.
  void push(int v);
  // Descarta elemento da frente da fila.
  void pop();
  // Lê valor do elemento da frente da fila.
  int front() const;
  // Verifica se está vazia.
  bool is_empty() const;

  // Métodos da regra dos 5 para gerenciar recursos (neste caso, memória).
  Queue() = default; // Precisa porque acrescentamos construtores abaixo.
  Queue(Queue const &q);
  Queue(Queue &&q);
  Queue &operator=(Queue const &q);
  Queue &operator=(Queue &&q);
  ~Queue();
};

// Insere v na pilha.
void Queue::push(int v) {
  Node *new_node = new Node;
  new_node->value = v;
  new_node->next = nullptr;
  if (_back) {
    _back->next = new_node;
    _back = new_node;
  } else {
    _front = _back = new_node;
  }
}

// Descarta elemento no topo da pilha.
// Pré-condição: !is_empty()
void Queue::pop() {
  Node *tmp = _front;
  _front = _front->next;
  if (tmp == _back) {
    // Retirou o último elemento!
    _back = nullptr;
  }
  delete tmp;
}

// Retorna elemento do topo da pilha.
// Pré-condição: !is_empty()
int Queue::front() const { return _front->value; }

// Verifica se a pilha está vazia.
bool Queue::is_empty() const { return _front == nullptr; }

// Copia os dados de uma outra fila.
void Queue::_copy_from(Queue const &q) {
  // Copia a queue q para este objeto.
  // Precisa copiar todos os nós.
  _front = nullptr;
  Node *current = q._front;
  Node *previous = nullptr;
  while (current) {
    Node *new_node = new Node{current->value, nullptr};
    if (previous) {
      previous->next = new_node;
    } else {
      _front = new_node;
    }
    previous = new_node;
    current = current->next;
  }
  _back = previous;
}

// Limpa toda a fila (liberando memória).
void Queue::_clear() {
  Node *current = _front;
  while (current) {
    auto tmp{current};
    current = current->next;
    delete tmp;
  }
  _front = _back = nullptr;
}

Queue::Queue(Queue const &q) { _copy_from(q); }

Queue::Queue(Queue &&q) {
  // Precisamos mover os dados de q para esta fila.
  // Basta mover os ponteiros e limpar os ponteiros de q.
  _front = q._front;
  _back = q._back;
  q._front = q._back = nullptr;
}

Queue &Queue::operator=(Queue const &q) {
  // Similar ao construtor de cópia, mas precisamos cuidar do caso
  // a = a e limpar possíveis dados pré-existentes:
  if (&q != this) {
    _clear();
    _copy_from(q);
  }
  return *this;
}

Queue &Queue::operator=(Queue &&q) {
  // Similar a construtor de movimento, mas considerando possível
  // existência de dados prévios e operações a = a.
  if (&q != this) {
    _clear();
    _front = q._front;
    _back = q._back;
    q._front = q._back = nullptr;
  }
  return *this;
}

Queue::~Queue() { _clear(); }

// Alguns testes simples.
int main(int, char const *[]) {
  Queue my_queue;
  for (int i = 0; i < 4; ++i) {
    my_queue.push(i);
  }
  std::cout << "Primeiro na fila: " << my_queue.front() << std::endl;
  my_queue.pop();
  for (int i = 0; i < 3; ++i) {
    my_queue.push(3 * i);
  }

  std::cout << "Fila atual: ";
  while (!my_queue.is_empty()) {
    auto x = my_queue.front();
    my_queue.pop();
    std::cout << x << " ";
  }
  std::cout << std::endl;
}