Q3_3.java

import java.util.ArrayList;
public class Q3_3{
	public static void main(String[] args ){
		
		int capacity_per_substack = 5;
		SetsOfStacks set = new SetsOfStacks(capacity_per_substack);
		for (int i = 0; i < 45; i++) {
			set.push(i+" ");
		}
		for (int i = 0; i < 6; i++) {
			System.out.println("Popped " + set.popAt(0));
			System.out.println("Popped " + set.popAt(3));
			System.out.println("Popped " + set.popAt(4));
		}	
		
		SetsOfStacks test = new SetsOfStacks(3);
		test.push("1");
		test.push("2");
		test.push("3");
		test.push("4");
		test.push("5");
		System.out.println(test.listSize);
		System.out.println(test.list.get(1).pop());
		System.out.println(test.popAt(0));		
		System.out.println(test.list.get(1).size);
		
	}
}

class SetsOfStacks{
	ArrayList<StackWithLL> list = new ArrayList<StackWithLL>();
	int listSize;;
	int size;
	int threashold;
	SetsOfStacks(int x){
		threashold =x;
		list.add(new StackWithLL(threashold));
		listSize = 1;
	    size=0;
	}
	void push(String value){
		StackWithLL lastStack = list.get(listSize-1);
		if(lastStack.isFull()){
			StackWithLL newStack = new StackWithLL(threashold);
			newStack.push(value);
			list.add(newStack);
			listSize ++;
		}
		else{
			lastStack.push(value);
		}
		size = size+1;
	}
	
	String pop(){
		StackWithLL lastStack = list.get(listSize-1);
		while (listSize > 0 && lastStack.isEmpty()){
			list.remove(listSize-1);
			listSize--;
			if(listSize > 0)
			     lastStack = list.get(listSize-1);
		}
		if(listSize == 0)
		      return null;
		size = size-1;
		return lastStack.pop();
	}
	
	String peek(){
		StackWithLL lastStack = list.get(listSize-1);
		while (listSize > 0 && lastStack.isEmpty()){
			list.remove(listSize-1);
			listSize--;
			if(listSize > 0)
			     lastStack = list.get(listSize-1);
		}
		if(listSize == 0)
		      return null;
		return lastStack.peek();
	}
	String popAt(int index){
		StackWithLL stack = list.get(index);
		if(stack == null  || stack.isEmpty())
		      return null;
		      
		String ret = stack.pop();
		shiftOne(index);
		return ret;		
	}
	
	void shiftOne(int index){
		while(index < listSize-1 && list.get(index+1)!=null && !list.get(index+1).isEmpty()){
			StackWithLL stack1 = list.get(index);
		        StackWithLL stack2 = list.get(index+1);
		        String s = stack2.popFirst();
			stack1.push(s);
			index= index+1;
		}
	}
	
	
}

class StackWithLL{
	DuNode head;
	DuNode tail;
	int size = 0;
	int capacity;
	
	StackWithLL(int c){
		head = new DuNode();
		tail = new DuNode();
		capacity = c;
	}
	
	void push(String s){
		DuNode n = new DuNode(s);
		if(size ==0){
			head = tail = n;
		}
		else{
			n.previous = tail;
			tail.next = n;
			tail = n;
		}
		size = size +1;
	}
	String pop(){
		size = size -1;
		String ret = tail.data;
		tail = tail.previous;
		if(tail != null)
			tail.next = null;
		return ret;
	}
	
	String popFirst(){
		if(head == null || size == 0){
			return null;
		}
		String ret = head.data;
		size = size -1;
		head = head.next;
		if(head != null)
			head.previous = null;
		return ret;
		
	}
	
	String peek(){
		return tail.data;
	}
	boolean isEmpty(){
		return size == 0;
	}
	boolean isFull(){
		return size == capacity;
	}	
	
}
class DuNode{
	String data = "";
	DuNode next = null;
	DuNode previous =null;
	
	DuNode(String s){
		data = s;
	}

	public DuNode() {
		// TODO Auto-generated constructor stub
	}
	
}