Queue

template <typename T>
struct Queue {
  std::vector<T> head;
  std::vector<T> tail;

  [[nodiscard]] int size() const {
    return int(head.size()) + int(tail.size());
  }

  [[nodiscard]] bool empty() const {
    return size() == 0;
  }

  [[nodiscard]] const T& operator [] (int index) const {
    assert(0 <= index && index < size());
    return (index < int(head.size()) ? head[int(head.size()) - 1 - index] : tail[index - int(head.size())]);
  }

  [[nodiscard]] const T& front() const {
    assert(!empty());
    return head.empty() ? tail.front() : head.back();
  }

  [[nodiscard]] const T& back() const {
    assert(!empty());
    return tail.empty() ? head.front() : tail.back();
  }

  void transport() {
    std::swap(head, tail);
    std::reverse(head.begin(), head.end());
  }

  void push(const T& x) {
    tail.push_back(x);
  }

  void pop() {
    assert(!empty());
    if (head.empty()) {
      transport();
    }
    head.pop_back();
  }
};