#include <iostream>
#include <fstream>
using namespace std;
//dinh nghia 1 node. trong c++ chung ta khong can tu struct nua
struct Node
{
	int x;
	Node *pNext;
};

//1 list Lifo hay Fifo thi ta deu co the quan ly bang 2 con tro co ban nay. Nhu vay thao tac se de hon so voi 1 con tro first
struct List
{
	Node *pHead;
	Node *pTail;
};

//Khoi tao 1 List trong, khong co phan tu nao
void CreateList(List &L)
{
	L.pHead = L.pTail = NULL;
}

//Khoi tao 1 node co gia tri x
Node *CreateNode(int x)
{
	Node *p = new Node;
	//Kiem tra neu khong du bo nho de cap phat thi thoat luon
	if (p == NULL)
		exit(1);
	p->pNext = NULL;
	p->x = x;
	return p;
}

//Them 1 Node vao dau danh sach. cai nay danh cho LIFO
void AddHead(List &L, Node *pAdd)
{
	if (L.pHead == NULL)
	{
		L.pHead = L.pTail = pAdd;
	}
	else
	{
		pAdd->pNext = L.pHead;
		L.pHead = pAdd;
	}
}

//Them 1 Node vao cuoi danh sach. cai nay danh cho FIFO
void AddTail(List &L, Node *pAdd)
{
	if (L.pHead == NULL)
	{
		L.pHead = L.pTail = pAdd;
	}
	else
	{
		L.pTail->pNext = pAdd;
		L.pTail = pAdd;
	}
}

//Duyet cac phan tu trong List ra de xem
void Output(List L)
{
	Node *p = L.pHead;
	while (p != NULL)
	{
		cout << " " << p->x;
		p = p->pNext;
	}
}

//Doc tep vao danh sach LIFO
void ReadFile(List &L)
{
	//thay vi dung ifstream de doc minh dung lop tong quat hon la fstream va dung mode la ca in va out
	fstream f;
	int x;
	f.open("D:\\input.txt", ios::in | ios::out);
	if (!f)
		cout << "tep khong ton tai\n";
	else
	{
		while (!f.eof())
		{
			f >> x;
			//Tao node co gia tri x va them vao dau danh sach fifo
			AddHead(L, CreateNode(x));
		}
	}
	f.close();
}

//Lay phan tu chan duong trong lifo chuyen sang fifo
void Lifo_Fifo(List Fifo, List &Lifo)
{
	Node *p = Fifo.pHead;
	while (p != NULL)
	{
		if (p->x > 0 && p->x % 2 == 0)
		{
			//Tao node co gia tri p->x va them vao danh sach lifo
			AddTail(Lifo, CreateNode(p->x));
		}
		p = p->pNext;
	}
}

void Input(List &L, int Max)
{
	int x;
	cout << "Viec nhap se ket thuc khi nhap gia tri x = 0\nNhap danh sach LIFO\n";
	while (Max > 0)
	{
		cout << "x = ";
		cin >> x;
		if (x == 0) break;
		AddHead(L, CreateNode(x));
		Max--;
	}
}


void main()
{
	List Fifo, Lifo;
	//Khoi tao 2 list
	CreateList(Fifo);
	CreateList(Lifo);

	//Nhap du lieu vao Lifo va xuat ra man hinh
	//Tam thoi khuc nay minh gioi han 5 phan tu. ban co the cin >> n va truyen n vao de nhap n phan tu
	Input(Lifo, 5);
	Output(Lifo);

	cout << endl;

	//Doc du lieu vao Fifo va xuat ra man hinh
	Lifo_Fifo(Lifo, Fifo);
	Output(Fifo);
}