SetOfStacksの実装

・Stackにサイズがあり，サイズを超えてpushしようとすると次のStackにpushされる．
・SetOfStacksクラスからは通常のStackのようにpop()，push()が実行できる．

世界で戦うプログラミング力を鍛える150問の中の一つの問題．
答えは，SetOfStacksクラスにArrayListを持つこと．

とあったのですが，ここでリストを使ってしまうの!? O(n/stackSize)のメモリが必要だし，何よりStackの実装にリスト用いていないのに(本のお手本でだけどね)，ここでリストというのが一貫性に欠けるきがする．

ということで自分が考えたのは，
LinkedListNodeでメンバーにLinkedListNodeをもってリンクを表現して，Stackを実装したように，Stackでメンバ−にStackを持ってリンクを表現すればSetOfStacksを表現する．使用メモリも減りそう．バグないかな．

LinkedListNode.java

public class LinkedListNode {
	public LinkedListNode next;
	public Object data;
	public int idx;
	public LinkedListNode(Object data){
		this.data = data;
	}
}

Stack.java

public class Stack {
	LinkedListNode top;
	int maxSize = 2;
	Stack next;
	
	public void push(Object data) throws Exception{
		if(isFull())
			throw new Exception();
		
		LinkedListNode node = new LinkedListNode(data);
		if(top==null)
			node.idx = 1;
		else
		{
			node.next = top;
			node.idx = top.idx + 1;
		}
		top = node;
	}
	public Object pop() throws Exception{
		if(top==null)
			throw new Exception();
		Object data = top.data;
		top = top.next;
		return data;
	}
	public boolean isFull(){
		if(this.top == null)
			return false;
		if(this.top.idx == this.maxSize)
			return true;
		return false;
	}
}

SetOfStacks.java

public class SetOfStacks {
	Stack top;
	
	public void push(Object data) {
		if(top != null){
			if(!top.isFull())
			{
				try{
				top.push(data);
				}catch(Exception e){}
			}
			else {
				Stack next = new Stack();
				try{
					next.push(data);
				}catch(Exception e){}
				
				next.next = top;
				this.top = next;
				System.out.println("StackSize has expanded!");
			}
		}else{
			Stack top = new Stack();
			try{
				top.push(data);
			}catch(Exception e){}
			this.top = top;
		}
	}
	
	public Object pop() throws Exception{
		if(top == null)
			throw new Exception();
		
		Object data = null;
		try{
			data = top.pop();
		}catch(Exception topEmpty){
			if(top.next == null)
				throw new Exception();
			else {
				System.out.println("StackSize has shrinked!");
				top = top.next;
				try{
					data = top.pop();
				}catch(Exception ee){}
			}
		}
		return data;
	}
	
	public int countStacks(){
		int count = 0;
		Stack now = top;
		while(now!=null)
		{
			count++;
			now = now.next;
		}
		return count;
	}
}