Saturday, December 27, 2014

Manage multiple stacks using an ArrayList of Stack objects.

Q. Imagine a (literal) stack of plates. If the stack gets too high, it might topple. Therefore, in real life, we would likely start a new stack when the previous tack exceeds some threshold. Implement a data structure that minics this. This Data Structure should be composed of several stacks and should create a new stack once the previous one exceeds capacity. It's push() and pop() should behave identically to a single stack (that is, pop() should return the same values as it would if there were just a single stack).

Implement a function popAt(int index) which performs a pop operation on a specific sub-stack.

Approach:

1. Use an ArrayList to manage individual stacks.
2. When a stack gets full, create another one and push the value on to the new stack.
3. If a stack gets empty, remove it from the ArrayList.

Source:

import java.util.ArrayList;

class Stacks<T>{
    int s;
    ArrayList<Stack<T>> stackList;
    
    Stacks(int s){ 
        this.s = s;
        stackList = new ArrayList<>(); 
    }
    
    public void push(T value){
        if(stackList.isEmpty()){stackList.add(new Stack<>(s));}
        if(stackList.get(stackList.size()-1).top == s-1){
            stackList.add(new Stack<>(s)); 
        }
        stackList.get(stackList.size()-1).push(value);
    }
    
    public T pop(){
        if(stackList.isEmpty())return null; 
        T val = stackList.get(stackList.size()-1).pop();
        if(stackList.get(stackList.size()-1).isEmpty()){
            stackList.remove(stackList.size()-1); 
        }
        return val;
    }
    
    public boolean isEmpty(){
        return stackList.isEmpty();
    }  
    
    //FOLLOW UP
    T popAt(int index){
        if(index<0 || index>=stackList.size() || stackList.isEmpty())return null; 
        Stack<T> st = stackList.get(index); 
         
        T val = st.pop(); 
        
        if(index != stackList.size()-1){ 
            st.push(stackList.get(index+1).elements[0]);  
            int i=index+1;
            for(;i+1<stackList.size();++i){
                st = stackList.get(i);
                //Remove the bottom most element
                for(int j = 0;j<st.elements.length-1;++j)
                    st.elements[j] = st.elements[j+1];
                st.top--;
                st.push(stackList.get(i+1).elements[0]);
            }
            //Fix last stack
            st = stackList.get(i);
            if(st.top == 0)stackList.remove(stackList.size()-1);
            else{
                for(int j=0;j<st.top;++j)
                    st.elements[j] = st.elements[j+1];
                st.top = st.top - 1;
            } 
        }
        return val;
    }
}

public class Code {
    public static void main(String[] args){
        Stacks<Integer> stacks = new Stacks<>(3);
        for(int i=1;i<=9;++i)
            stacks.push(i); 
        
        for(int i=0;i<10;++i)System.out.println(stacks.popAt(0));
    }
}

Stack Class 

public class Stack <T>{
    int top = -1; 
    T[] elements;
    
    public Stack(int size){
        elements = (T[])new Object[size]; 
    }
    
    public void push(T element){ 
        if(top+1 == elements.length){
            System.out.println("Overflow.");
            return;
        }
        elements[++top] = element;
    }
    
    public T pop(){
        if(top<0){
            System.out.println("Underflow.");
            return null;
        }
        return elements[top--];
    }
        
    public T peek(){
        if(top < 0){
            System.out.println("Stack is empty!");
            return null;
        }
        return elements[top];
    }
    
    public boolean isEmpty(){
        return top==-1;
    } 
}

Output:

3
4
5
6
7
8
9
2
1
Underflow.
null

No comments:

Post a Comment