public class Main {
/**
* @param args
*/
public static void main(String[] args) {
Deque<Integer> Q = new Deque<Integer>(6);
try {
Q.addFirst(3);
System.out.println(Q);
Q.addFirst(5);
System.out.println(Q);
Q.removeFirst();
System.out.println(Q);
Q.addLast(7);
System.out.println(Q);
Q.removeFirst();
System.out.println(Q);
Q.removeLast();
System.out.println(Q);
System.out.println(Q.isEmpty());
Q.removeFirst();
} catch (FullStackException e) {
// TODO Auto-generated catch block
System.out.println(e.getMessage());
}catch (EmptyStackException e) {
// TODO Auto-generated catch block
System.out.println(e.getMessage());
}
}
}
/**
* Double queue class
*/
class Deque<E>
{
//f is front index
//r is rear index
//N is the size of the queue
//A is the queue
//E is a generic type
private int f,r,N;
private E[] A;
public Deque(int s)
{
A = (E[]) new Object[s];
f = 0;
r = 0;
N = s;
}
public void addFirst(E e) throws FullStackException
{
if (size() == N - 1) throw new FullStackException();
/**
* Would work in Python
* f = (f - 1 ) % N;
*/
f = (f == 0) ? N - 1 : (f - 1 ) % N;
A[f] = e;
}
public void addLast(E e) throws FullStackException
{
if (size() == N - 1) throw new FullStackException();
A[r] = e;
r = (r + 1 ) % N;
}
public E removeFirst() throws EmptyStackException
{
if (isEmpty()) throw new EmptyStackException();
E temp = A[f];
A[f] = null;
f = (f + 1 ) % N;
return temp;
}
public E removeLast() throws EmptyStackException
{
if (isEmpty()) throw new EmptyStackException();
/**
* Would work in Python
* r = (r - 1 ) % N;
*/
r = (r == 0) ? N - 1 : (r - 1 ) % N;
E temp = A[r];
A[r] = null;
return temp;
}
public E getFirst() throws EmptyStackException
{
if (isEmpty()) throw new EmptyStackException();
return A[f];
}
public E getLast() throws EmptyStackException
{
if (isEmpty()) throw new EmptyStackException();
int temp = (r - 1 ) % N;
return A[temp];
}
public int size()
{
return (N - f + r) % N;
}
public boolean isEmpty()
{
return f == r;
}
public String toString()
{
String str = "(";
for(E e:A) str += e + ",";
str += ")";
return str;
}
}
class FullStackException extends Exception
{
public FullStackException()
{
super("Stack is full!");
}
}
class EmptyStackException extends Exception
{
public EmptyStackException()
{
super("Stack is empty!");
}
}