import java.util.*;

public class DoubleStack<E> {
	private Object[] arr;
	private int topA, topB, bottomA, bottomB;
	
	public DoubleStack(){
		arr = new Object[64];
		bottomA = arr.length / 2;
		bottomB = arr.length / 2 + 1;
		topA = bottomA;
		topB = bottomB;
	}
	
	public boolean emptyA(){
		if(topA == bottomA)
			return true;
		else
			return false;
	}
	public boolean emptyB(){
		if(topB == bottomB)
			return true;
		else
			return false;
	}
	//push adds elements starting from the middle of the array and expands
	//either up (pushB) or down (pushA). will all so cycle if hitting the end.
	public void pushA(E o){
		if(topA<0){
			topA = arr.length;
		}
		if(arr[topA-1]!=null){
			throw new StackOverflowError("pushA has caused the stack to overflow");
		}else{
			topA--;
			arr[topA]=o;
		}
	}
	public void pushB(E o){
		if(topB>arr.length){
			topB = 0;
		}
		if(arr[topB+1]!=null){
			throw new StackOverflowError("pushB has caused the stack to overflow");
		}else{
			topA++;
			arr[topB]=o;
		}
	}
	
	//pop methods is pretty standard. if the stack is empty it throws an exception.
	//return the object at the top of the stack and replaces it with null. also change tops of the stacks
	//to their right values;
	public E popA(){
		if(this.emptyA()){
			Object o = arr[topA];
			arr[topA]=null;
			topA++;
			return (E)o;
		}else
			throw new StackOverflowError("stack A is empty. pop failed.");
				
	}
	public E popB(){
		if(this.emptyB()){
			Object o = arr[topB];
			arr[topB]=null;
			topB--;
			return (E)o;
		}else
			throw new StackOverflowError("stack B is empty. pop failed.");			
	}
	
	
	//top is very easy. throws an exception if the stack is empty else returns the
	//equivalent top of the stacks.
	public Object topA(){
		if(this.emptyA())
			throw new StackOverflowError("stack A is empty. top failed");
		return arr[topA];
	}
	public Object topB(){
		if(this.emptyB())
			throw new StackOverflowError("stack B is empty. top failed");
		return arr[topB];
	}
}