//Majewski Raffael, 1121099; Nikolaus Sterzinger, 1121162


   import java.lang.*;

   public class Dequeue<T>   {
   
    //--- Instanzvariablen
   
    
      private Node start,ende;
      private int laenge;
    
    
    //--- Konstruktoren
    
   
      public Dequeue() {
      
         laenge = 0;
         start  = null;
         ende   = null;
      }
   
   
      public Dequeue(Node n) {
      
         start  = n;
         ende   = n;
      }
    
     
     
     //--- Fügt Element an erster Stelle ein
   
   
      public void push_front( T element){
      
         Node newNode       = new Node (element, null, null);
      
         if (isEmpty()) {
            newNode.linkVor = newNode;
            newNode.linkZur = newNode;
         }
         
         else {
            newNode.linkVor = ende.linkVor;
            newNode.linkZur = start.linkZur;
            start.linkZur   = newNode;
            ende.linkVor    = newNode;
         }
      
         start  = newNode;
      
         laenge = laenge + 1;
      
      
      
      }
   
    
    
    //--- Fügt Element an letzter Stelle ein
   
    
   
      public void push_back( T element){
      
         Node newNode       = new Node (element, null, null);
      
         if (isEmpty()){
            newNode.linkVor = newNode;
            newNode.linkZur = newNode;
            ende = newNode;
         }
         
         else{
            newNode.linkVor = ende.linkVor;
            newNode.linkZur = start.linkZur;
            start.linkZur   = newNode;
            ende.linkVor    = newNode;
         }
      
         start   = newNode;
         laenge  = laenge + 1;
      }
   
   
   
    //--- Entfernt Element an erster Stelle ein
   
      public T pop_front(){
      
      if (isEmpty())
      return null;
      
      else{
         T ergebnis    = start.data;
         //T ergebnis = start;
       //start.linkZur = ergebnis.linkZur;
       //return ergebnis.data;
      
         Node helfer   = new Node(null, null, start.linkZur);
         ende.linkVor  = start.linkVor;
         start         = start.linkVor;
         start.linkZur = helfer.linkZur;
      
         laenge = laenge - 1;
         return ergebnis;
      }
      }
   
   
   //--- Entfernt Element an letzter Stelle 
   
      public T pop_back(){
      
       if (isEmpty())
      return null;
      
      else{
         T ergebnis    = start.data;
         //T ergebnis = start;
       //ende.linkZur = ergebnis.linkZur;
       //return ergebnis.data;
         Node helfer   = new Node(null, ende.linkVor, null);
         start.linkZur = ende.linkZur;
         ende          = ende.linkZur;
         ende.linkVor  = helfer.linkVor;
      
         laenge = laenge - 1;
         return ergebnis;
         }
      }
   
   
   
   //--- Zeigt Element an erster Stelle 
   
   
      public T peek_front(){
      
       if (isEmpty())
      return null;
      
      else{
      
         T ergebnis = start.data;
         return ergebnis;
         }
      }
    
   
   //--- Zeigt Element an letzter Stelle 
   
      public T peek_back(){
      
       if (isEmpty())
      return null;
      
      else {
         T ergebnis = ende.data;
         return ergebnis;
         }
      }
    
     
   
   
   
   
      public String toString(){
      
         MyIterator inhalt = new MyIterator(); 
      
         StringBuffer sb = new StringBuffer();
      
         for (int a = 0; a <= laenge; a++) {
            sb = sb.append(inhalt.getNext() + " ");
         }
      
         return sb.toString(); 
      }   
   
    
   
   
   //--- Überprüfung ob Queue leer
   
      public boolean isEmpty(){
      
       return laenge == 0;
         //return start == null;
      }
   
   
   
   //--- Innere Klasse für Knoten
   
      private class Node{
      
         T data;
         Node linkVor, linkZur;
      
      
         Node() {}
      
         Node(T e, Node v, Node z){
         
            data    = e;
            linkZur = v;
            linkVor = z;
         
         }
      }
       
       
              
      //--- Ausgabe des gesammten Inhalts

       
      //--- innere Klasse für Iterator
      
      
      private class MyIterator {
         
         Node current;
         
         MyIterator() {
            current = start;
            
         }
         
         
         public T getNext(){
            
            T ergebnis = current.data;
            current = current.linkVor;
            
            return ergebnis;
            
         }
         
         
         public boolean hasNext(){
            return current != null ;
            
         }
            
          
         
      }
       
       
      
   }