Set of stacks with capacity

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 stack exceeds some threshold. Implement a data structure SetOfStacks that mimics this. SetOfStacks should be composed of several stacks, and should create a new stack once the previous one exceeds capacity. SetOfStacks.push() and SetOfStacks.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).
FOLLOW UP
Implement a function popAt(int index) which performs a pop operation on a specific sub-stack.

My initial thoughts:
Use stack of stacks. Push to the top sub-stack. Pop from the top sub-stack. If the top sub-stack becomes empty, remove it. Keep a array list of all the sub-stacks.

My initial codes:

	public class MyStackOfStack<T> {

		private MyStack<MyStack<T>> buffer = new MyStack<MyStack<T>>();
		private static final int THRESHOLD = 10;
		private int size = 0;
		private List<MyStack<T>> indices = new ArrayList<MyStack<T>>();

		public void push(T data) {
			if (size < THRESHOLD && size > 1) {
				buffer.peek().push(data);
				size++;
			} else { // size == 0 || size == THRESHOLD
				MyStack<T> newStack = new MyStack<T>();
				newStack.push(data);
				size = 1;
				buffer.push(newStack);
				indices.add(newStack);
			}
		}

		public T pop() {
			MyStack<T> topStack = buffer.peek();
			if (size > 1) {
				return topStack.pop();
			} else { // size == 1
				T data = topStack.pop();
				buffer.pop();
				indices.remove(indices.size() - 1);
				size = THRESHOLD;
				return data;
			}
		}

		public T popAt(int index) {
			return indices.get(index).pop();
		}
	}

Comments after running:

  • popAt(int index) removes the bottom element of the sub-stack.
  • If one of the middle sub-stack is poped, its above sub=stack is supposed to pad down one element. This behavior is not supported.

Solution:

public class StackNode2<T> {
	private T data = null;
	private StackNode2<T> below = null;
	private StackNode2<T> above = null;
        // getters and setters are omitted.
}

public class MyStack2<T> {

	private StackNode2<T> top = null;
	private final int CAPACITY;
	private StackNode2<T> bottom = null;
	private int size = 0;

	public MyStack2(int capacity) {
		this.CAPACITY = capacity;
	}

	public void push(T data) {
		StackNode2<T> item = new StackNode2<T>(data);
		if (size == 0) {
			top = item;
			bottom = top;
			size++;
		} else if (size < CAPACITY) {
			top.setAbove(item);
			item.setBelow(top);
			top = item;
			size++;
		}
	}

	public T pop() {
		if (size > 0) {
			size--;
			StackNode2<T> item = top;
			top = item.getBelow();
			// top.setAbove(null);
			return item.getData();
		}
		return null;
	}

	public T peek() {
		if (size > 0) {
			return top.getData();
		}
		return null;
	}

	public int size() {
		return size;
	}

	public boolean isEmpty() {
		return size == 0;
	}

	public boolean isFull() {
		return size == CAPACITY;
	}

	public T getBottom() {
		if (size > 0)
			return bottom.getData();
		else
			return null;
	}

	public T removeFromBottom() {
		if (size > 0) {
			size--;
			StackNode2<T> item = bottom;
			bottom = item.getAbove();
			bottom.setBelow(null);
			return item.getData();
		} else {
			return null;
		}
	}
}

public class SetOfStack<T> {

	private ArrayList<MyStack2<T>> buffer = 
			new ArrayList<MyStack2<T>>();
	private final int CAPACITY;

	public SetOfStack(int capacity) {
		this.CAPACITY = capacity;
	}

	public void push(T data) {
		if (buffer.isEmpty()) {
			MyStack2<T> stack = new MyStack2<T>(CAPACITY);
			stack.push(data);
			buffer.add(stack);
		} else {
			MyStack2<T> stack = buffer.get(buffer.size() - 1);
			if (stack.isFull()) {
				MyStack2<T> newStack = new MyStack2<T>(CAPACITY);
				newStack.push(data);
				buffer.add(newStack);
			} else {
				stack.push(data);
			}
		}
	}

	public T pop() {
		if (buffer.isEmpty()) {
			return null;
		} else {
			MyStack2<T> stack = buffer.get(buffer.size() - 1);
			T data = stack.pop();
			if (stack.isEmpty())
				buffer.remove(buffer.size() - 1);
			return data;
		}
	}

	public T popAt(int index) {
		return leftShift(index, true);
	}

	public T leftShift(int index, boolean removeTop) {
		MyStack2<T> stack = buffer.get(index);
		T removedItem = null;
		if (removeTop)
			removedItem = stack.pop();
		else
			removedItem = stack.removeFromBottom();
		if (stack.isEmpty())
			buffer.remove(index);
		else if (buffer.size() > index + 1) {
			stack.push(leftShift(index + 1, false));
		}
		return removedItem;
	}
}
Advertisements

1 Comment (+add yours?)

  1. gaurang
    Jan 21, 2013 @ 00:35:54

    C++ implementation ::

    #include
    #include
    #include
    using namespace std;

    vector<stack*>vec;
    int index=0;
    int size=5;

    void init()
    {
    stack*s=new stack;
    vec.push_back(s);
    }

    bool top(int &v)
    {
    stack*s=new stack;
    s=vec.at(index);
    if(s->size()==0 && index==0)
    return false;
    if(s->size()==0)
    {
    delete s;
    index–;
    s=vec.at(index);
    }

    v=s->top();
    return true;
    }

    void pop(int b)
    {
    stack*s=new stack;
    s=vec.at(index);

    if(s->size()==0 && index==0)
    {
    cout<size()==0 && index>0)
    {
    delete(s);
    index–;
    s=vec.at(index);
    s->pop();
    }
    else if(s->size()>0 && index>=0)
    {
    s->pop();
    }

    }
    void push(int x)
    {
    stack*s=vec.at(index);
    cout<size();
    if(s->size()==5)
    {
    s=new stack;
    vec.push_back(s);
    index++;
    }
    s->push(x);
    }

    void pop_at(int in)
    {
    stack*s=new stack;
    s=vec.at(in);
    int a[5],i=0;
    int x=s->top();
    s->pop();
    if(s->size()<5&& in!=index)
    {
    while(in!=index)
    {
    stack*q=new stack;
    in=in+1;
    q=vec.at(in);
    while(q->size()!=0 && i!=5)
    {
    a[i]=q->top();

    i++;
    q->pop();

    }
    i–;
    s->push(a[i]);
    while(i!=0)
    { i–;
    q->push(a[i]);
    }
    s=q;
    }
    }
    }

    int main()
    {
    init();
    for(int i=0;i<15;i++)
    {
    push(i);
    cout << "Push: Stack index " << index << " — " << i << endl;

    }

    for(int i=0;i<1;i++)
    {
    int b,v;
    b=top(v);
    pop(b);
    if(b){
    cout << "Stack index " << index << " — " << v << endl;
    }
    else{
    cout << "No more elements in stack !" <>in;
    pop_at(in);
    for(int i=0;i<14;i++)
    {
    int b,v;
    b=top(v);
    pop(b);
    if(b){
    cout << "Stack index " << index << " — " << v << endl;
    }
    else{
    cout << "No more elements in stack !" << endl;
    }
    }

    return 0;
    }

    Reply

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s