java - 如何在Stack数据结构中使用泛型？

Question

我已经用 Java 实现了一个简单的堆栈并且它可以工作。它使用Node类来保存堆栈int值。现在，我正在计划另一个类 NodeWithMin ，它应该包含相关的节点以及从节点到底部的最小值。这意味着当我获得堆栈的顶部节点时，我将获得节点和堆栈的最小值。

我想使用泛型与 Stack 类来切换我想要插入的任何类(Node/NodeWithMin) 。所以，最终它会是一些东西 -

public class myStack extends Stack< Node or NodeWithMin >{

}

堆栈需要在哪里

class Stack<T>{

}

如果您需要进一步澄清该问题，请告诉我。我了解 Stack 类中的一些方法需要更改。关于我该怎么做有什么建议吗？谢谢。

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

在我看来好像 NodeWithMin与 Node 执行相同的基本操作，加上它还有 Min 的东西。所以我会做 NodeWithMin延长Node 。然后你可以将 MyStack 声明为:

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

MyStack现在可以使用 Node或NodeWithMin .

至于Stack ，最值得注意的问题是它被编写为显式依赖 Node 的实例。这是一个问题，因为你说你想要 Stack是通用的，能够接受任何 T 。因此，您必须保留所有 T以正确的顺序排列实例，而不期望它们记住谁在前面或在后面，这与您尝试对 NodeWithMin 执行的操作不一致.

所以我认为你需要重新考虑你希望这些东西有多通用。如果Stack应该是完全通用的，即它应该能够按 LIFO 顺序保留任何类型的对象，然后 MyStack必须重写 Stack 中的大部分方法为了利用它所知道的Node 。 OTOH，如果你真正想做的就是保留一堆Node (或其子类型)按 LIFO 顺序排列的对象，然后放弃 Stack完全直接进入MyStack .

哦顺便说一句，你使用 HashSet很麻烦。由于您实例化它一次，因此您面临着保留 Stack 中不再存在的内容的风险。 ，即您可以弹出当前最小值，但 min()方法会不断返回它。最好将其设为 min() 中的局部变量方法，因为这是唯一使用它的地方。

此外，为了使用Collections.min()方法， Stack 中的所有对象必须实现Comparable ，这反对使用通用 T 。您可能想要移动 min()方法MyStack (假设您更改 Node 来实现 Comparable )。