#include <iostream>
#include <set>

using namespace std;

template <typename T>
class Queue {

private:
  struct Item {
    T value;
    Item *next;
  };

  Item *first;
  Item *last;
  int _size;

  void copyItems(const Item *item, Item *(&first), Item *(&last), int &_size);

  void deleteItems(Item *item);

public:

  Queue();

  Queue(Queue &q);

  ~Queue();

  Queue& operator=(const Queue &q);

  Queue(istream &is);

  T front() const;

  void pop();

  void push(T value);

  int size() const;

  void print(ostream &os) const;

  void read(istream &is);

  void duplicate(const set<T>& s);

};

template <typename T>
void Queue<T>::copyItems(const Item *item, Item *(&first), Item *(&last), int &_size) {
  if (item == nullptr) {
    first = nullptr;
    last = nullptr;
    _size = 0;
  }
  else {
    first = new Item();
    first->value = item->value;
    last = first;
    _size = 1;
    while (item->next != nullptr) {
      last->next = new Item();
      last = last->next;
      item = item->next;
      last->value = item->value;
      _size++;
    }
    last->next = nullptr;
  }
}

template <typename T>
void Queue<T>::deleteItems(Item *item) {
  while (item != nullptr) {
    Item *aux = item;
    item = item->next;
    delete aux;
  }
}


template <typename T>
Queue<T>::Queue() {
  first = last = nullptr;
  _size = 0;
}

template <typename T>
Queue<T>::Queue(Queue &q) {
  copyItems(q.first, first, last, _size);
}

template <typename T>
Queue<T>::~Queue() {
  deleteItems(first);
}

template <typename T>
Queue<T>& Queue<T>::operator=(const Queue &q) {
  if (this != &q) {
    deleteItems(first);
    copyItems(q.first, first, last, _size);
  }
  return *this;
}

template <typename T>
T Queue<T>::front() const {
  if (first == nullptr) {
    cerr << "Error: front on empty queue" << endl;
    exit(0);
  }
  return first->value;
}

template <typename T>
void Queue<T>::pop() {
  if (first == nullptr) {
    cerr << "Error: pop on empty queue" << endl;
    exit(0);
  }
  Item *aux = first;
  first = first-> next;
  delete aux;
  _size--;
  if (first == nullptr) last = nullptr;
}

template <typename T>
void Queue<T>::push(T value) {
  Item *pitem = new Item();
  pitem->value = value;
  pitem->next = nullptr;
  if (first == nullptr) {
    first = last = pitem;
    _size = 1;
  }
  else {
    last->next = pitem;
    last = pitem;
    _size++;
  }
}

template <typename T>
int Queue<T>::size() const {
  return _size;
}

template <typename T>
void Queue<T>::print(ostream &os) const {
  os << _size;
  for (typename Queue<T>::Item *item = first; item != nullptr; item = item->next) {
    os << " " << item->value;
  }
}

template <typename T>
void Queue<T>::read(istream &is) {
  deleteItems(first);
  first = last = nullptr;
  _size = 0;

  int size;
  is >> size;
  for (int i = 0; i < size; ++i) {
    T x;
    is >> x;
    push(x);
  }
}

template<typename T>
ostream &operator<<(ostream &os, const Queue<T> &q) {
  q.print(os);
  return os;
}

template<typename T>
istream &operator>>(istream &is, Queue<T> &q) {
  q.read(is);
  return is;
}

template <typename T>
void Queue<T>::duplicate(const set<T>& s) {
}
