Deque.java

import java.util.Iterator;
import java.util.NoSuchElementException;

public class Deque<Item> implements Iterable<Item>{
    private Item[] deck; // the array for the deck
    private int N; // the number of items in the deck
    private int head;
    private int tail;
    
    public Deque(){
        deck = (Item[]) new Object[2];
        N = 0;
        head = 0; //head is the index where the element will be inserted at the front
        tail = deck.length - 1; //tail is the index where the element will be inserted at the end
    }
    
    public boolean isEmpty(){
        return N == 0;
    }
    
    public int size(){
        return N;
    }
    
    // the wrapping around is just similar to addLast
    public void addFirst(Item item){
        if (N == deck.length) resize(2 * deck.length);
        deck[head--] = item;
        if (head == 0) head = deck.length - 1; // wrap around;
        N++;
    }
    
    public void addLast(Item item){
        if (N == deck.length) resize(2 * deck.length);
        deck[tail++] = item;
        if(tail == deck.length) tail = 0; // wrap around;
        N++;
    }
    
    public Item removeFirst(){
        if(isEmpty()) throw new NoSuchElementException("Deck is already empty!");
        if(head == tail.length - 1) head = -1;
        Item item = deck[++head];
        deck[head] = null;
        N--;
        if (N > 0 && N == deck.length / 4) resize(deck.length / 2);
        return item;
    }
    
    public Item removeLast(){
        if(isEmpty()) throw new NoSuchElementException("Deck is already empty!");
        if(tail == 0) tail = deck.length; // wrap around
        Item item = deck[--tail];
        deck[tail] = null;
        N--;
        if (N > 0 && N == deck.length / 4) resize(deck.length / 2);
        return item;
    }
    
    private void resize(int size){
        Item[] newDeck = (Item[]) new Object[size];
        for (int i = 0; i < N; i++){
            newDeck[i] = deck[(head + 1 + i) % deck.length];
        }
        deck = newDeck;
        head = deck.length - 1;
        tail = N;
    }
    
    public Iterator<Item> iterator(){
        return new ArrayIterator();
    }
    
    private class ArrayIterator implements Iterator<Item>{
        private int current = 0;
        public boolean hasNext(){return current < N;}
        public void remove(){ throw new UnsupportedOperationException();}
        public Item next(){ // test your iterator before submission! use the simplest example: add only two elements 0 and 1
                            // and try to iterate according to your code.
            if(!hasNext()) throw new NoSuchElementException();
            Item item = deck[(head + 1 + current) % deck.length];
            current++;
            return item;
        }
    }
    
    public static void main(String[] args){
        
    }
}