ArrayDeque.java

package edu.caltech.cs2.datastructures;


import edu.caltech.cs2.interfaces.IDeque;
import edu.caltech.cs2.interfaces.IQueue;
import edu.caltech.cs2.interfaces.IStack;

import java.util.Iterator;

public class ArrayDeque<E> implements IDeque<E>, IQueue<E>, IStack<E> {
    private E[] data;
    private int size;
    private static final int DEFAULT_CAPACITY = 10;
    private static final int DEFAULT_GROWTH = 2;

    public ArrayDeque() {
        this(DEFAULT_CAPACITY);
    }

    public ArrayDeque(int initialCapacity) {
        this.data = (E[]) new Object[initialCapacity];
        this.size = 0;
    }

    @Override
    public void addFront(E e) {
        resize();
        if (this.size > 0) {
            System.arraycopy(this.data, 0, this.data, 1, this.size);
        }
        this.data[0] = e;
        this.size++;
    }

    @Override
    public void addBack(E e) {
        resize();
        this.data[this.size] = e;
        this.size++;
    }

    @Override
    public E removeFront() {
        resize();
        if (this.size == 0){
            return null;
        }
        E e = this.data[0];
        System.arraycopy(this.data, 1, this.data, 0, this.size - 1);
        this.size--;
        return e;
    }

    @Override
    public E removeBack() {
        resize();
        if (this.size == 0){
            return null;
        }
        E e = this.data[this.size - 1];
        this.size--;
        return e;
    }

    @Override
    public boolean enqueue(E e) {
        addFront(e);
        return true;
    }

    @Override
    public E dequeue() {
        if (this.data[0] == null){
            return null;
        } else {
            return removeBack();
        }
    }

    @Override
    public boolean push(E e) {
        addBack(e);
        return true;
    }

    @Override
    public E pop() {
        if (this.data[0] == null){
            return null;
        } else {
            return removeBack();
        }
    }

    @Override
    public E peekFront() {
        if (this.size == 0){
            return null;
        }
        return this.data[0];
    }

    @Override
    public E peekBack() {
        if (this.size == 0){
            return null;
        }
        return this.data[this.size - 1];
    }

    @Override
    public E peek() {
        return peekBack();
    }

    @Override
    public Iterator<E> iterator() {
        return new ArrayDequeIterator();
    }

    @Override
    public int size() {
        return this.size;
    }

    private class ArrayDequeIterator implements Iterator<E> {
        private int idx = 0;

        @Override
        public boolean hasNext() {
            return this.idx < ArrayDeque.this.size;
        }

        @Override
        public E next() {
            E element = ArrayDeque.this.data[this.idx];
            this.idx++;
            return element;
        }
    }

    // from lecture notes
    private void resize() {
        if (this.size == this.data.length) {
            E[] newData = (E[])new Object[this.data.length * DEFAULT_GROWTH];
            System.arraycopy(this.data, 0, newData, 0, this.size);
            this.data = newData;
        }
    }

    @Override
    public String toString() {
        if (this.size == 0) {
            return "[]";
        }
        else {
            StringBuilder resultSB = new StringBuilder();
            resultSB.append("[");
            for (int i = 0; i < this.size; i++) {
                resultSB.append(this.data[i]).append(", ");
            }
            String result = resultSB.toString();
            result = result.substring(0, result.length() - 2);
            return result + "]";
        }

    }
}