# 【数据结构】链表实现队列

#include <iostream>
#include <string>
#include <cstring>
#include <queue>
using namespace std;
template<class T>
struct Node
{
T data;
Node<T> *next_pos;
};

template<class T>
class LinkedQueue
{
public:
LinkedQueue();
~LinkedQueue();
T getFront();
T popFront();
void Push(T x);
int getLength();
private:
Node<T> *first, *p, *s, *tail;
};

template<class T>
LinkedQueue<T>::LinkedQueue()//带头结点的队列
{
s = new Node<T>;
s->next_pos = NULL;
first = tail = s;
}

template<class T>
LinkedQueue<T>::~LinkedQueue()
{
while (first->next_pos)
{
p = first->next_pos;
s = p;
first->next_pos = p->next_pos;
delete s;
}
}

template<class T>
T LinkedQueue<T>::getFront()
{
p = first->next_pos;
return p == NULL ? -1 : p->data;
}

template<class T>
T LinkedQueue<T>::popFront()
{
p = first->next_pos;
T re = p->data;
s = p;
first->next_pos = p->next_pos;
delete s;
return re;
}

template<class T>
void LinkedQueue<T>::Push(T x)
{
s = new Node<T>;
s->data = x;
s->next_pos = NULL;
tail->next_pos = s;
tail = s;
}

template<class T>
int LinkedQueue<T>::getLength()
{
p = first->next_pos;
long long int count = 0;
while (p != NULL)
{
p = p->next_pos; count++;
}
return count;
}

int main()
{
int n = 0;
cin >> n;
LinkedQueue<int> que;
for (int i = 0; i < n; i++)
{
int temp = 0;
cin >> temp;
que.Push(temp);
}
for (int i = 0; i < n; i++)
{
cout << que.getFront() << endl;
que.popFront();
}
}