// Arup Guha
// 6/20/06
// 2006 BHCSI Implemented in class: A QueueLL class using a linked list.
import java.util.*;

public class QueueLL {
	
	// Need a reference to both the front and back for efficiency.
	private Node front;
	private Node back;
	
	// Creates an empty QueueLL.
	public QueueLL() {
		front = null;
		back = null;
	}
	
	// EnQueueLLs the element x.
	public void enQueueLL(int x) {
		
		// This is if the QueueLL is empty.
		if (front == null) {
			Node temp = new Node(x);
			front = temp;
			back = temp;
		}
		
		// This creates the new node and attaches it to the end.
		else {
			Node temp = new Node(x);
			back.next = temp;
			back = temp;
		}
	}
	
	// Pops an element off the stack and returns it.
	// Returns -1 if there's no element to pop.
	public int deQueue() {
		// Default case.
		if (empty())
			return -1;
			
		// Grab the first element and advance the front reference.
		else {
			int retval = front.data;
			front = front.next;
			return retval;
		}
	}
	
	// Returns the element at the front of the QueueLL.
	// Returns -1 if no such element exists.
	public int front() {
		if (empty())
			return -1;
		else
			return front.data;
	}
	
	// Returns true if the QueueLL is empty.
	public boolean empty() {
		return (front==null);
	}
	
	
	// Prints out each element in the QueueLL in order. Should be for
	// debugging only.
	private void print() {
		Node temp = front;
		while (temp != null) {
			System.out.print(temp.data+" ");
			temp = temp.next;
		}
		System.out.println();
	}
	
	public static void main(String[] args) {
		
		// Allows for testing of a single QueueLL object.
		Scanner stdin = new Scanner(System.in);
		System.out.println("Enter choice, 1=enq, 2=deq, 3.print");
		int choice = stdin.nextInt();
		
		QueueLL test = new QueueLL();
		while (choice != 4) {
			if (choice == 1) {
				System.out.println("Elem to push.");
				int item = stdin.nextInt();
				test.enQueueLL(item);
			}
			else if (choice == 2) {
				int val = test.deQueue();
				System.out.println("dequeued "+val);
			}
			else if (choice == 3) {
				test.print();
			}
			System.out.println("Enter choice, 1=enq, 2=deq, 3.print");
			
			choice = stdin.nextInt();
		}
		
	}
}