I have been working on a program called Deque. The program has four methods: given an arbitrary array, I can add an element to the front of the array(addFirst), to the back(addLast), remove the first element(removeFirst), and remove the last element(removeLast).

(StdIn, StdOut are API's that work the same way as in C)

Yes, the program compiles and I can add and remove items on a list. Everything works perfectly until I stop adding element and try to print out the elements on the list (I assign StdIn.isEmpty = True and break the loop; please refer to the main method.). For example, input 1 and 2 gives me the following error:

```
java Deque1.java
+
Type your input String addFirst: 1
++
Type your input String addLast: 2
deque[]: Exception in thread "main" java.lang.ClassCastException: [Ljava.lang.Object; cannot be cast to [Ljava.lang.String;
        at Deque1.main(Deque1.java:123)

```

and line 123 is:
`StdOut.print(dequeinstance.deque[(dequeinstance.first + i) % dequeinstance.deque.length] + " ");`

I have been working on this small error for several hours but all that returned was a frustration from a repeated run-time error. I believe I have declared Item to be the type String but I can't figure out why the code does not work. Help me please. This is the code that I wrote that continuously gives me classcastexception error:

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

public class Deque1<Item> implements Iterable<Item> {

    private Item[] deque;
    private int N = 0;
    private int last = 0;
    private int first = 0;

    public Deque1()                           // construct an empty deque
    {
        deque = (Item[]) new Object[2];
    }

    public boolean isEmpty()                 // is the deque empty?
    {
        return N == 0;
    }

    public int size()                        // return the number of items on the deque
    {
        return N;
    }

    public void addFirst(Item item)          // add the item to the front
    {
        if(item == null) throw new java.lang.NullPointerException();
        if(N == deque.length) resize(2 * deque.length);
        deque[first--] = item;
        if (first == -1) first = deque.length - 1;
        N++;
    }

    public void addLast(Item item)           // add the item to the end
    {
        if(item == null) throw new java.lang.NullPointerException();
        if(N == deque.length) resize(2*deque.length);
        if(last == deque.length - 1) last = -1;
        deque[++last] = item;
        N++;
    }

    public Item removeFirst()                // remove and return the item from the front
    {
        if (isEmpty()) throw new NoSuchElementException("Queue underflow");
        if(N > 0 && N == deque.length/4) resize(deque.length/2);
        if(first == deque.length - 1) first = -1;
        Item item = deque[++first];
        deque[first] = null;
        return item;
    }

    public Item removeLast()                 // remove and return the item from the end
    {
        if (isEmpty()) throw new NoSuchElementException("Queue underflow");
        if(N > 0 && N == deque.length/4) resize(deque.length/2);
        Item item = deque[last];
        deque[last--] = null;
        if(last == -1) last = deque.length -1;
        N--;
        return item;
    }

    private void resize(int capacity)
    {
        Item[] temp = (Item[]) new Object[capacity];
        for(int i = 0; i < N; i++)
        {
            temp[i] = deque[(first + i)%deque.length];
        }
        deque = temp;
        first = 0;
        last = N - 1;
    }

    public Iterator<Item> iterator() {return new ArrayIterator();}

    // an iterator, doesn't implement remove() since it's optional
    private class ArrayIterator implements Iterator<Item> {
        private int i = 1;
        public boolean hasNext()  {return i <= N;}
        public void remove()      {throw new java.lang.UnsupportedOperationException();}

        public Item next()
        {
            if (!hasNext()) throw new java.util.NoSuchElementException();
            Item item = deque[(i + first) % deque.length];
            i++;
            return item;
        }
    }

    public static void main(String[] args)
    {
        Deque1<String> dequeinstance = new Deque1();
        //String[] dq = dequeinstance.deque;
        //Iterator<String> itr = dq.iterator();
        while (!StdIn.isEmpty())
        {
            String item = StdIn.readString();
            if (item.equals("--")) dequeinstance.removeLast();
            else if (item.equals("-")) dequeinstance.removeFirst();
            else if (item.equals("++")) 
            {
                StdOut.print("Type your input String addLast: ");
                String item2 = StdIn.readString();
                dequeinstance.addLast(item2);
            }
            else if (item.equals("+")) 
            {
                StdOut.print("Type your input String addFirst: ");
                String item2 = StdIn.readString();
                dequeinstance.addFirst(item2);
            }
        }

        //for(String str : itr)
        StdOut.print("deque[]: ");
        for(int i = 1; i <= dequeinstance.size(); i++)
        {
            StdOut.print(dequeinstance.deque[(dequeinstance.first + i) % dequeinstance.deque.length] + " ");
        }

        System.out.println();
    }
}

```

ps. On a separate piece of note, how do I create an Iterator that iterates all elements in the list deque (String[] deque)?

When I try to create an iterator

```
Iterator<String> itr = dq.iterator();

```

I get a compile-error:

```
  Deque1.java:99: error: cannot find symbol
  Iterator<String> itr = dq.iterator();
                                 ^
  symbol:   method iterator()
  location: variable dq of type String[]

```

I tried to use an alternative by removing dq and directly referring deque in class Deque

```
Iterator<String> itr = dequeinstance.deque.iterator();

```

this time, I get a similar but different error:

```
Iterator<String> itr = dequeinstance.deque.iterator();
                                                  ^
symbol:   method iterator()
location: variable deque of type Item[]
where Item is a type-variable:
Item extends Object declared in class Deque1

```