Created
February 4, 2015 16:51
-
-
Save samueltcsantos/3b96c30009d290d54d3a to your computer and use it in GitHub Desktop.
ArrayDeque my own Implementation in Java
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package adt.deque; | |
/** | |
* Implementing a Deque with a Circular Array. | |
* | |
* @author Samuel T. C. Santos | |
* @version 1.0 | |
* @param <E> | |
*/ | |
public class ArrayDeque<E> implements Deque<E> { | |
private E[] data; | |
private static final int CAPACITY = 5; | |
private int front = 0; | |
private int back = 0; | |
private int size = 0; | |
/** | |
* Constructs a ArrayDeque with default capacity. | |
*/ | |
public ArrayDeque(){ | |
this(CAPACITY); | |
} | |
/** | |
* Constructs a ArrayDeque with a given capacity. | |
* | |
* @param capacity | |
*/ | |
@SuppressWarnings("unchecked") | |
public ArrayDeque(int capacity){ | |
if (capacity <= 0 ){ | |
throw new IllegalArgumentException("Invalid Capacity!"); | |
} | |
data = (E[]) new Object[capacity]; | |
} | |
@Override | |
public int size() { | |
return size; | |
} | |
@Override | |
public boolean isEmpty() { | |
return size == 0; | |
} | |
@Override | |
public E first() { | |
return isEmpty() ? null : data[front]; | |
} | |
@Override | |
public E last() { | |
return isEmpty() ? null : data[back]; | |
} | |
@Override | |
public void addFirst(E element) throws DequeOverflowException { | |
if (size == data.length) | |
throw new DequeOverflowException(); | |
if (isEmpty()){ | |
data[front] = element; | |
} | |
else{ | |
front = (front - 1 + data.length) % data.length; | |
data[front] = element; | |
} | |
size++; | |
} | |
@Override | |
public void addLast(E element) throws DequeOverflowException { | |
if (size == data.length) | |
throw new DequeOverflowException(); | |
back = back % data.length; | |
data[back] = element; | |
size++; | |
} | |
@Override | |
public E removeFirst() throws DequeUnderflowException { | |
if (isEmpty()) | |
throw new DequeUnderflowException(); | |
E answer = data[front]; | |
front = (front + 1) % data.length; | |
size--; | |
return answer; | |
} | |
@Override | |
public E removeLast() throws DequeUnderflowException { | |
if (isEmpty()) | |
throw new DequeUnderflowException(); | |
E answer = data[back]; | |
back = (back - 1 + data.length) % data.length; | |
size--; | |
return answer; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Hi! I think there is a mistake in this code. If you do:
You get the following result:
While the correct answer is: