// fifo.h  -- A queue of integers (dynamic storage)

struct node{
	node *next;
	int value;
};

struct fifo{
	node * head;	// whence we dequeue
	node * tail;	// where we enqueue
};

// create and initialize a fifo
void createFifo(fifo& queue);

// enqueue a new value into an existing fifo
void enqueue(fifo& queue, int who);

// dequeue a value from a fifo
int dequeue(fifo& queue);

// check if a fifo is empty
int isempty(fifo& queue);


// fifo.cpp  -- A queue of integers (dynamic storage)

#include "fifo.h"

#define NULL 0

// Create and initialize a fifo
// It returns a fifo whose head and tal are null
void createFifo(fifo& queue)
{
	queue.head = NULL;
	queue.tail = NULL;
}

// enqueue a new value into an existing fifo
void enqueue(fifo& queue, int who)
{
	node *a = new node;

	a->next = NULL;
	a->value = who;
	if (queue.head == NULL)
		queue.head = a;
	else
		queue.tail->next = a;
	queue.tail = a;
}

// dequeue a value from a fifo
int dequeue(fifo& queue)
{
	node *headNode;
	int who;

	if (queue.head != NULL) {
		headNode = queue.head;
		queue.head = queue.head->next;
		who = headNode->value;
		if (queue.head == NULL)
			queue.tail = NULL;
		delete headNode;
		return who;
	}
	return 0; // You should never execute this
	          // statement (i.e. do not dequeue
	          // from an empty queue)
}

// check if a fifo is empty
int isempty(fifo& queue)
{
	return (queue.head == NULL);
}


// main.cpp  -- Driver for fifo class. Read a sequence of positive integers, 
//              store them in a fifo, then print them out

#include <iostream.h>
#include "fifo.h"

void main(void)
{
	int who;
	fifo queue;

	createFifo(queue);
	while(1) {
		cout << "Enter a positive integer [0 to terminate]: ";
		cin >> who;
		if (who <= 0) break;
		enqueue(queue, who);
	};
	while (!isempty(queue)) {
		who = dequeue(queue);
		cout << who << endl;
	}
}