How to use generic in Stack data structure?

Question

I have implemented a simple Stack in Java and it works. It uses Node class for holding the stack int values. Now, I'm planning another class NodeWithMin that should contain the node in concern and the minimum values from the node to bottom. That means when I will get the top node of the stack I will have node and the minimum value of the stack.

I want to use generic with the Stack class to switch whichever class ( Node / NodeWithMin) that I would like to plug with it. So, finally it will be something -

public class myStack extends Stack< Node or NodeWithMin >{

}

Where Stack needs to be

class Stack<T>{

}

Let me know if you need further clarification of the question. I understand inside of some methods in the Stack class needs to changed. Any advice on how can I do that ? THANK YOU.

import java.util.*;

class Node {

    public Node above;
    public Node below;
    public int data;

    public Node(int data) {

        this.data = data;
    }

}

class NodeWithMin {

    public NodeWithMin above;
    public NodeWithMin below;

    public int data;
    public int min;

    public NodeWithMin(int data , int min){

        this.data = data;
        this.min = min;
    }

}


class Stack {

    private int capacity;
    public Node top;
    public Node bottom;
    public int size;

    HashSet<Integer> hashSet = new HashSet<Integer>();

    public Stack ( int cap ){

        this.top = null;
        this.bottom = null;
        this.capacity = cap;
        this.size = 0;
    }

    public static int randomInt(int n) {

        return (int) (Math.random() * n);
    }

    public static int randomIntInRange(int min, int max) {

        return randomInt(max + 1 - min) + min;
    }

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

    public void join (Node newNode, Node stackTop) {

        // not empty stack 
        if ( stackTop != null ){

            stackTop.above = newNode;
        }

        // if the new node is not null
        // previous top is now below of the inserted node which is the current top 
        if ( newNode != null){

            newNode.below = stackTop;
        }
    }

    public boolean push(int v) {

        if (size >= capacity) 
            return false;

        size++;
        Node n = new Node(v);
        if (size == 1) bottom = n;
        join(n, top);

        // define the new top 
        top = n;

        // pushing is sucessful 
        return true;
    }

    public int min(){

        if ( top == null) return -1;

        Node curr = this.top;
        int min =-1 ; 

        System.out.println("\n\n");
        while( curr != null){

            hashSet.add(curr.data);
            curr = curr.below;
        }

        System.out.println();
        min = Collections.min(hashSet);

        return min; 
    }

    public int pop() {

        Node t = top;
        top = top.below;
        size--;
        return t.data;
    }

    public int peek (){

        Stack myStack = this; 
        return myStack.top.data ;

    }

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

    public int removeBottom() {

        Node b = bottom;
        bottom = bottom.above;
        if (bottom != null) bottom.below = null;
        size--;
        return b.data;
    }

    public void display(){

        if ( top == null) return;

        Node curr = this.top;
        int min =-1 ; 

        System.out.println("\n\n");
        while( curr != null){

            System.out.println( curr.data);

            curr = curr.below;

            if ( curr != null){

                System.out.println("↑");
            }
        }

        System.out.println();
    }

    public static void main ( String[] args ){

        // System.out.println("\nMy stack is here \n");
        Stack s = new Stack(5);

        for (int j = 0; j < 5; j ++){
            s.push( randomIntInRange(0, 100) );
        }

        s.display();
        System.out.println("the min of the stack is =  "+ s.min());

    }

}

Answer 1

It looks to me as if NodeWithMin does the same basic thing as Node, plus it has the Min stuff. So I'd make NodeWithMin extend Node. Then you could declare MyStack as:

public class myStack extends Stack< ? extends Node > {
...
}

MyStack will now work with either Node or NodeWithMin.

As for Stack, the most notable problem is that it is written to explicitly depend on instances of Node. That's an issue because you say you want Stack to be generic, able to take any T. So you'll have to keep all of the T instances in the correct order without expecting them to remember who comes before or after, and that's inconsistent with what you're trying to do with NodeWithMin.

So I think you need to rethink just how generic you want this stuff to be. If Stack should really be completely generic, i.e. it should be able to keep any kind of object in LIFO order, then MyStack will have to override large portions of the methods in Stack in order to make use of what it knows about Node. OTOH, if all you really want to do is keep a bunch of Node (or subtypes thereof) objects in LIFO order, then ditch Stack completely and just go straight to MyStack.

Oh BTW, your use of HashSet is troublesome. Since you instantiate it once, you run the risk of it keeping stuff around that no longer exists in the Stack, i.e. you could pop the current min, but the min() method would keep returning it. Better to make it a local variable in the min() method since that's the only place it's used.

Further, in order to use the Collections.min() method, all of the objects in the Stack must implement Comparable, and that argues against using a generic T. You will probably want to move the min() method to MyStack (assuming that you change Node to implement Comparable).