package mt.util;
import java.util.Enumeration;
// Copyright 2000 Jonathan White 
// Use/modify this however you want, just keep this and the previous line

/*
  Version 1.0 - converted from c++ Feb 02 2000
*/

public class Deque extends Object{
    class DataCapsule{
	Object     data;
	DataCapsule next = null;
	DataCapsule prev = null;
    }
    private DataCapsule front;
    private DataCapsule back;
    public Deque(){
	/*Purpose:Creates the Deque
	  Input  : None
	  Output : None
	*/
	front = back = new DataCapsule();
    }

    public boolean isEmpty(){
	/*Purpose: Check to see if deque is empty
	  Input : None
	  Output: Truth value for empty status
	  Pre   : None
	*/
	return ((front.next == null) && (front.prev == null));
    }  
  
    public void push(Object data){
	/*Purpose: Add an element to the front
	  Input : Object
	  Output: None
	  Pre   : A deque has been created && Not full
	*/
	front.data = data;    
	front.prev = new DataCapsule();
	front.prev.next = front;
	front = front.prev;
	front.prev = null;
    }
    /* Added 2000/09/30  Treats deque as a stack but it make no
       modification to it.
    */
    public Enumeration enumerateStack(){
	return new Enumeration(){
		DataCapsule cur = Deque.this.front;
		public boolean hasMoreElements(){
		    return cur.next != null;
		}
		public Object nextElement(){
		    cur = cur.next;
		    return cur.data;
		}
	    };
    }
    public Object pop(){
	/*Purpose: Remove an element from front
	  Input : None
	  Output: Object
	  Pre   : A deque has been created && Not empty
	*/
	Object temp;
	temp = front.next.data;
	front = front.next;
	front.prev = null;
	return temp;
    }
  
    public void enqueue(Object data){
	/*Purpose: Add an element to the Front
	  Input : Object
	  Output: None
	  Pre   : A deque has been created && Not full
	*/
	push(data);
    }
    public Object dequeue(){
	/*Purpose: Remove an element from Back
	  Input : None
	  Output: Object
	  Pre   : A deque has been created && Not empty
	*/
	Object temp;
	temp = back.data;
	back = back.prev;
	back.next = null;
	return temp;
    }
    //Example method
    public static void main(String[] args){
	Deque q = new Deque();
	for(int i=0; i< 20; i++){
	    q.enqueue(i + " ");
	}
	while(!q.isEmpty())
	    System.out.println(q.dequeue());
	for(int i=0; i< 20; i++){
	    q.enqueue(i + " ");
	}
	while(!q.isEmpty())
	    System.out.println(q.pop());
    }
}