public class MStack implements Stack{
 
	public Node top;
	public Node[] stack;
	public static int T[];
	public static int B[];
	public static int oldT[];
	public static int i;
	int size2;
	int noOfStack;
 
 
	class Node{
		Object info;
		Node link;
	}
 
	public MStack(){
 
	}
 
	public MStack(int size, int noOfStack){
		size2= size;
		stack = new Node[size];
		T = new int[noOfStack + 1];
		B = new int[noOfStack + 1];
		for (int i = 0; i < noOfStack+1; i++){
			B[i]= (int)Math.floor(size/noOfStack) * i -1;
			T[i] = B[i];
		}
	}
 
	public Object top(int i){
		if (isEmpty(i)){
			System.out.println("Stack empty.");
		}return top.info;
	}
 
	public void push(String item,int i ) {
		if (T[i]== B[i+1]){
				System.out.println("Stack"+ i + "is full.");
		}else{
			Node newNode = new Node();
			newNode.info = item;
			newNode.link = top;
			top = newNode;
			System.out.println("You have pushed an element into stack");
		}
	}
 
	public Object pop(int i ){
		Node temp[] = new Node[noOfStack];
		if (isEmpty(i)){
			System.out.println("Stack has nothing inside it");
		}
		temp[i] = top;
		top = top.link;
		return temp[i].info;
	}
 
	public boolean isEmpty(int i){
		return (T[i] == B[i]);
	}
 
	public int size(int i){
		int size = T[i] - B[i] ;
		return size;
	}
}

import java.io.*;
 
public class BookShelf extends MStack {
 
		public static InputStreamReader ir = new InputStreamReader(System.in);
		public static BufferedReader bf = new BufferedReader(ir);
		public static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		public static MStack bookShelf;
		public static int size;
		public static int shelf;
 
		public static void main (String []args) throws IOException{
			System.out.println("What size do you want your bookshelf to be?(integer):");
			size =	Integer.parseInt(in.readLine());
			System.out.println("How many shelves do you want your bookshelf to have?:");
			shelf = Integer.parseInt(in.readLine());
			bookShelf = new MStack(size, shelf);
 
			new BookShelf();
		}
 
		public BookShelf(){
			super();
			options();
		}
		public void options(){
			try{
				do{
					System.out.println("\nPlease choose from below. Use numbers to choose.");
					System.out.println("1. Place book on shelf");
					System.out.println("2. Retrieve book from shelf");
					System.out.println("3. View books on each shelf");
					System.out.println("4. Exit");
					int choice = Integer.parseInt(in.readLine());
					if  (choice == 1){
						System.out.println("Which shelf do you want to place a book?");
						System.out.println("Enter either 1, 2 or 3");
						int placement = Integer.parseInt(in.readLine());
						if(placement == 1){
							System.out.println("Enter element:");
							String item = bf.readLine();
							garwick(placement);
							bookShelf.push(item, placement);
						}if(placement == 2){
							System.out.println("Enter an element:");
							String item = bf.readLine();
							garwick(placement);
							bookShelf.push(item, placement);
						}if(placement == 3){
							System.out.println("Enter an element:");
							String item = bf.readLine();
							garwick(placement);
							bookShelf.push(item, placement);
						}
					}else if (choice == 2){
						System.out.println("Which shelf do you want to retrieve a book, 1, 2, or 3?");
						int choice2 = Integer.parseInt(in.readLine());
						switch (choice2){
							case 1 : if (bookShelf.isEmpty(choice2)) {
										System.out.println( " Shelf " + choice2 + " is empty!");
									}else {
										System.out.println("Item" + bookShelf.pop(choice2)+ " is retrieved.");
									}break;
							case 2 : if (bookShelf.isEmpty(choice2)) {
										System.out.println(" Shelf " + choice2 + " is empty!");
									}else {
										System.out.println("Item" + bookShelf.pop(choice2)+ " is retrieved.");
									}break;
							case 3 : if (bookShelf.isEmpty(choice2)) {
										System.out.println(" Shelf " + choice2 + " is empty!");
									}else {
										System.out.println("Item" + bookShelf.pop(choice2)+ " is retrieved.");
									}break;
							}
					}else if(choice == 3){
						System.out.println("Recent items");
						for (int i = 1; i <= shelf; ++i) {
							System.out.println("shelf #" + i + ": " + bookShelf.top(i));
							}
							System.out.println("shelf #" + i + ":  Empty");
					}else if (choice == 4){
						System.out.println("You have exited. Thank you!");
						break;
					}
			}while (true);
		}catch(IOException e){}
	}
 
		/*
		 * Method that implements garwick's algorithm for reallocating free space
		 * within a multiple stack
		 */
		public void garwick(int i) {
			int diff[] = new int[shelf + 1];
			int size[] = new int[shelf + 1];
			int totalSize = 0;
			double freecells, incr = 0;
			double alpha, beta, sigma = 0, tau = 0;
			/* Compute for the allocation factors */
			for (int j = 1; j <= bookShelf.noOfStack; j++) {
				size[j] = bookShelf.size(j);
				if ((bookShelf.T[j] - bookShelf.oldT[j]) > 0){
					diff[j] = bookShelf.T[j] - bookShelf.oldT[j];
				}else{
					diff[j] = 0;
					totalSize += size[j];
					incr += diff[j];
				}
			}
			diff[i]++;
			size[i]++;
			totalSize++;
			incr++;
			freecells = bookShelf.size2 - totalSize;
			alpha = 0.10 * freecells / bookShelf.noOfStack;
			beta = 0.90 * freecells / incr;
			/* If all stacks are full */
			if (freecells < 1)
				throw new StackException("Stack overflow: All Stacks are full");
			/* Compute for new bases */
			for (int j = 2; j <= bookShelf.noOfStack; j++) {
				tau = sigma + alpha + diff[j - 1] * beta;
				bookShelf.B[j] = bookShelf.B[j - 1] + size[j - 1] + (int) Math.floor(tau)- (int) Math.floor(sigma);
				sigma = tau;
			}
			/* Restore size of the overflowed stack to its old value */
			size[i]--;
			System.out.println("size[" + i + "] = " + size[i]);
			/* Compute for new top addresses */
			for (int j = 1; j <= bookShelf.noOfStack; j++) {
				bookShelf.T[j] = bookShelf.B[j] + size[j];
			}
			bookShelf.oldT = bookShelf.T;
		}
}