#include <iostream>

template <typename T>
struct Node {
	T data;
	struct Node *front;
	struct Node *rear;
};

template <typename T>
class Queue {
private:
	Node<T> *head;
	Node<T> *tail;
	int size;
	
public:
	Queue() : head(nullptr), tail(nullptr) , size(0) {}
	~Queue() {
		if (this->head == nullptr)
			return;
		
		Node<T> *cur = this->tail;
		
		while (cur != nullptr) {
			cur = cur->front;
			delete this->tail;
			this->tail = cur;
		}
		
		this->head = this->tail;
	}
	
	int get_size() {
		return this->size;
	}
	
	bool is_empty() {
		return this->head == nullptr ? true : false;
	}
	
	void en_queue(T value) {
		Node<T> *node = new Node<T>;
		node->data = value;
		node->front = nullptr;
		node->rear = nullptr;
		
		if (is_empty()) // first push.
			this->head = node;
		else {
			node->front = this->tail;
			this->tail->rear = node;
		}
		
		this->tail = node;
		++size;
	}
	
	T de_queue() {
		if (is_empty()) // empty queue
			return -1; // T type에 맞는 error code return.
		else {
			int pop_val = this->head->data;
			
			if (this->head == this->tail) { // queue with 1 element.
				delete this->head;
				this->head = this->tail = nullptr;
			}
			else { // queue with more than 2 elements.
				Node<T> *node = new Node<T>;
				
				node = this->head->rear;
				
				delete this->head;
				
				this->head = node;
				this->head->front = nullptr;
			}
			
			--size;
			return pop_val;
		}
	}
	
	T get_head() {
		if (is_empty()) // empty queue
			return -1; // T type에 맞는 error code return.
		else
			return this->head->data;
	}
	
	T get_tail() {
		if (is_empty()) // empty queue
			return -1; // T type에 맞는 error code return.
		else
			return this->tail->data;
	}
	
	friend std::ostream& operator <<(std::ostream &out, Queue<T> &queue){
		Node<T> *temp = queue.head;
		
		for (int i = 0; i < queue.get_size(); ++i)
			out << "──";
		std::cout << std::endl;
		
		while(temp != nullptr) {
			out << temp->data << " ";
			temp = temp->rear;
		}
		std::cout << std::endl;
		
		for (int i = 0; i < queue.get_size(); ++i)
			out << "──";
		std::cout << std::endl;
		
		return out;
	}	
};
int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(NULL); 
	std::cout.tie(NULL);
	
	Queue<int> queue;
	
	std::cout << "Queue en_queue(push) : " << 1 << std::endl;
	queue.en_queue(1);
	std::cout << queue;
	
	std::cout << "Queue en_queue(push) : " << 2 << std::endl;
	queue.en_queue(2);
	std::cout << queue;
	
	std::cout << "Queue en_queue(push) : " << 4 << std::endl;
	queue.en_queue(4);
	std::cout << queue;
	
	std::cout << "Queue length(size) : " << queue.get_size() << std::endl;
	std::cout << "Queue front(head) : " << queue.get_head() << std::endl;
	std::cout << "Queue rear(tail) : " << queue.get_tail() << std::endl;
	
	
	std::cout << "Queue de_queue(pop) : " << queue.de_queue() << std::endl;
	std::cout << queue;
	
	std::cout << "Queue de_queue(pop) : " << queue.de_queue() << std::endl;
	std::cout << queue;
	
	std::cout << "Queue de_queue(pop) : " << queue.de_queue() << std::endl;
	std::cout << queue;
	
	std::cout << "Queue de_queue(pop) : " << queue.de_queue() << std::endl;
	std::cout << queue;
	
	return 0;
}