Skip to content

Instantly share code, notes, and snippets.

@samueltcsantos
Created February 4, 2015 16:51
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 2 You must be signed in to fork a gist
  • Save samueltcsantos/3b96c30009d290d54d3a to your computer and use it in GitHub Desktop.
Save samueltcsantos/3b96c30009d290d54d3a to your computer and use it in GitHub Desktop.
ArrayDeque my own Implementation in Java
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;
}
}
@ivanrusanov
Copy link

Hi! I think there is a mistake in this code. If you do:

add first -479
delete last
add last -119
delete first

You get the following result:

-479
-479

While the correct answer is:

-479
-119

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment