LinkedListy-Stack

Question

I came across this interesting question while reading 'Cracking the coding Interview' and came up with a simple implementation. Any suggestions are welcomed.

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 SetOf Stacks that mimics this. SetOf Stacks should be composed of several stacks and should create a new stack once the previous one exceeds capacity. SetOf Stacks. push() and SetOf Stacks. 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).

My take was to use a LinkedListy Stack which stores reference to Stack that is currently active, and once it exceeds it's capacity (i.e. stack full) it'll create another stack and change the pointer (like linkedlist)

Code:

static class Node{
    int data;
    Node next;

    Node(int data){
        this.data = data;
    }
}

interface Stack{
    public void push(int ... data);
    public Node pop();
}

//Normal Stack 
static class basicStack implements Stack{
    Node top;
    String name;
    int capacity;
    int size;
    basicStack nextStack;
    public int getSize(){
        return this.size;
    }

    public boolean isFull(){
        if(capacity == size){
            return true;
        }else{
            return false;
        }

    }

    public boolean isEmpty(){
        if(top==null){
            return true;
        }else{
            return false;
        }
    }

    //constructor
    basicStack(String name, int capacity){
        this.name = name;
        this.capacity = capacity;
        size = 0;
    }

    public void _push(int data){
        if(this.isFull()){
            System.out.println("Error : " + this.name + " is full!!");
            return;
        }
        size++;
        System.out.println("Pushing : " + data + " to " + this.name + " size : " + size);
        if(top==null){
            top = new Node(data);
        }else{
            Node temp = new Node(data);
            temp.next = top;
            top = temp;
        }

    }

    public void push(int... data){
        for(int i : data){
            this._push(i);
        }
    }

    public Node pop(){
        if(top==null){
            System.out.println("Error : Stack is empty!!");
            return new Node(-1);
        }
        System.out.println("Popping " + top.data + " from " + this.name);
        Node toRet = top;
        top = top.next;
        size--;
        return toRet;
    }   
}

//Special stack with extended functions
static class LinkedListyStack implements Stack{
    basicStack topStack;
    int stackCount;
    int stackCapacity;
    LinkedListyStack(int stackCapacity){
        stackCount = 0;
        this.stackCapacity = stackCapacity;
    }

    public void _push(int data){
        if(topStack==null){
            stackCount++;
            topStack = new basicStack(String.valueOf(stackCount), this.stackCapacity);

        }

        if(topStack.isFull()){
            stackCount++;
            basicStack tempStack = new basicStack(String.valueOf(stackCount), this.stackCapacity);
            tempStack.nextStack = topStack;
            topStack = tempStack;

        }

        topStack.push(data);

    }

    public Node pop(){
        if(topStack.isEmpty() && topStack.nextStack == null){
            System.out.println("All Stacks are empty");
            return new Node(-1);
        }

        if(topStack.isEmpty()){
            topStack = topStack.nextStack;
            stackCount--;
        }

        Node toRet = topStack.pop();
        //System.out.println("Popping : " + toRet.data + " from " + topStack.name);
        return toRet;
    }

    public void push(int ... data){
        for(int numbers : data){
            this._push(numbers);
        }
    }
}


//Main function
public static void main(String[] args) {
    LinkedListyStack myStack = new LinkedListyStack(5);
    myStack.push(12,4,2,4,5,5,6,7,5,12,78,45,12,43,457,6,823,2,3,1);
    myStack.pop();
    myStack.pop();
    myStack.pop();
    myStack.pop();
    myStack.pop();
    myStack.pop();
    myStack.pop();
    myStack.pop();
    myStack.pop();
}

Answer 1

Inconsistent API

This is an inconsistent API for a stack:

interface Stack{
    public void push(int ... data);
    public Node pop();
}

That is, pushing int values but popping Node values is strange.

Perhaps the problem originates from your trying to use the same interface for both stacks: the internal stack of stacks, and the user-facing stack of integers. One way to do that would be using a generic interface:

interface Stack<E> {
    void push(E data);
    E pop();
}

Encapsulate / hide implementation details

Node is an implementation detail of your stack. As far as this problem is concerned, the stack should appear as a regular stack. The fact that internally it's using multiple stacks, linked lists, nodes, should be hidden, as they are not the concern of the users.

As such, Node should be declared private:

private static class Node {
    // ...
}

The same goes for basicStack.

Use boolean expressions directly

Instead of this:

public boolean isFull(){
    if(capacity == size){
        return true;
    }else{
        return false;
    }
}

You can (and should) use boolean expressions directly:

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

Naming conventions in Java

In Java, the convention is that classes should be named with PascalCase, so BasicStack instead of Stack.

Linked list of linked lists?

Just for the record, the exercise is probably motivated by a problem concerning stack implementations backed by a single array. Growing or shrinking arrays are expensive operations (allocate new array, copy from old array), which can be greatly mitigated by using a stack of arrays, as described in the exercises.

Keep in mind that stack implementations backed by a linked list don't have the same issue, and growing and shrinking the storage are cheap operations. As such, stacking linked lists is quite pointless.