package Dequeue;
import java.util.Iterator;
public class ListDequeue<DequeueType> implements Iterable<DequeueType>{
    private Node first,last;  //голова и конец
    private int N;              //размер очереди
    public ListDequeue() {
        this.first = new Node(); //создание фиктивного узла
        this.last=first;}
    @Override
    public Iterator<DequeueType> iterator() {
        return new ListDeqIterator();
            
    }
    private class ListDeqIterator implements Iterator<DequeueType>{
        private Node current=first;
        @Override
        public boolean hasNext() {return current!=null;}

        @Override
        public DequeueType next() {
            DequeueType val=current.val;
            current=current.next;
            return val;
           }

        @Override
        public void remove() {
            throw new UnsupportedOperationException("Not supported yet."); 
        }
    }
    private class Node{
        DequeueType val;
        Node next,prev;        
    }
        
    public boolean isEmpty(){return first.prev==null &&first.next==null;}
    public int size(){return N;}
    public void pushLeft(DequeueType val){
        if(first.val==null){first.val=val;N++;return;} 
        Node oldfirst=first;
        first = new Node();
        first.val=val;
        first.next=oldfirst;
        first.prev=null;
        oldfirst.prev=first;
        N++;
    }
    public void pushRight(DequeueType val){
        if(last.val==null){last.val=val;N++;return;} 
        Node newlast=new Node();
        newlast.val=val;
        last.next=newlast;
        newlast.prev=last;
        last=newlast;
        N++;
    }
    public DequeueType popLeft(){   
    DequeueType val = first.val;
    if(isEmpty()){
        first=new Node();
        last=first;
        N--;
        return val;
    }
    first=first.next;
    first.prev=null;
    N--;
    return val;}
    public DequeueType popRight(){
    DequeueType val=last.val;
    if(isEmpty()){
        first=new Node();
        last=first;
        N--;
        return val;
    }
    last=last.prev;
    last.next=null;
    N--;
    return val;
    
    }
    
public static void main(String[] args) {
    ListDequeue<Character> s = new ListDequeue<>();
    s.pushLeft('A');




    }

}