import java.util.EmptyStackException;

public class StackDeque implements Deque {
  	//Data
  	protected FancyArrayStack left;
  	protected FancyArrayStack right;
	
	//Constructor
  	public StackDeque() { 
		left = new FancyArrayStack();
		right = new FancyArrayStack();
	}
	
	public StackDeque(int n) { 
		left = new FancyArrayStack(n / 2 + 1);
		right = new FancyArrayStack(n / 2 + 1);
	}
	
 	public StackDeque(Object[] arg) {
 		int n = arg.length / 2;
		left = new FancyArrayStack(2 * n);
        right = new FancyArrayStack(2 * n);
		for(int i = n - 1; i >= 0; i--)
			left.push(arg[i]);
		for(int i = n; i < arg.length; i++)
			right.push(arg[i]);
 	}
	
	//Private method
	private void change() {
		StackDeque temp = new StackDeque(this.toArray());
		left = temp.left;
		right = temp.right;
	}
	
  	//Deque methods implementation
  	public  boolean isEmpty() {
		return  left.isEmpty() && right.isEmpty();
	}
	
	public void addFront(Object x) {
		try{
			left.push(x);
		}catch(FullStackException e) {
			change();
			left.push(x); }
	}
	
	public void addRear(Object x) {
		...
	}
	
	public Object removeFront() throws EmptyDequeException {
		if(isEmpty()) throw new EmptyDequeException("Deque is empty!"); 
		try {
			return left.pop();
		}catch(EmptyStackException e) {
			if(right.size() == 1) return right.pop();
			change();
			return left.pop(); }
	}
	
   	public Object removeRear() throws EmptyDequeException {
		...
	}
	
	public Object getFirst() throws EmptyDequeException {
		Object result = left.pop();
		left.push(result);
		return result;
	}
	
   	public Object getLast() throws EmptyDequeException {
   		...
   	}
	
	//Other method
   	public Object[] toArray() {
		Object[] result = new Object[left.size() + right.size()];

		Object[] w1 = left.toArray(); int n1 = w1.length;
		for(int i = 0; i < n1; i++)
			result[i] = w1[n1 - 1 - i];
		
		Object[] w2 = right.toArray(); int n2 = w2.length;
		for(int i = 0; i < n2; i++)
			result[n1 + i]=w2[i];

		return result;
	}
}