我如何在 Java 中使这些数据结构实现通用？

Question

我编写了自己的 Stack 和 队列，但我让它们专门用于整数。我很了解 Java 实现，java.util.Stack 和 java.util.Queue，但我这样做是作为一种学习经验......只是想要学习新东西。我将如何实现这些通用实现，以便我可以在堆栈/队列中存储任何对象，而不仅仅是整数？

下面是代码，但我也欢迎所有关于改进的批评和建议。我想知道我哪些做得好，哪些做得不好。

堆栈节点实现

public class StackNode {

    public Integer value;

    public StackNode() {
        this.value = null;
    }

    public StackNode(StackNode node) {
        this.value = node.value;
    }

    public StackNode(Integer data) {
        this.value = data;
    }
}

堆栈实现

/**
 * Stack Data Structure.
 * 
 * A Stack is a last in, first out (LIFO) data structure. A Stack can have any abstract data type as an element, but is
 * characterized by two fundamental operations: push() and pop(). The push() operation adds an element to the top of the Stack,
 * hiding any elements already on the Stack, or initializing the Stack if it is empty. The pop() operation removes an element
 * from the top of the Stack, and returns this element's value to the caller. Elements are removed from the Stack in the reverse
 * order to the order of their addition to the Stack; therefore, lower elements are those that have been on the Stack the
 * longest, thus, the first element added to the Stack will be the last one to be removed.
 * 
 * @author Hristo
 */
public class Stack {

    private int size;
    private int capacity;
    private int topNodeIndex;

    private Object[] theStack;

    /**
     * Default Constructor. Initalizes this Stack with initial size = 0 and capacity = 1.
     */
    public Stack() {

        this.size = 0;
        this.capacity = 1;
        this.topNodeIndex = -1;
        this.theStack = new Object[capacity];
    }

    /**
     * Constructor. Initializes a Stack to have the given capacity.
     * 
     * @param capacity - the capacity of the Stack-to-be
     */
    public Stack(int capacity) {

        this.size = 0;
        this.capacity = capacity;
        this.topNodeIndex = -1;
        this.theStack = new Object[capacity];
    }

    /**
     * Returns the size of this Stack, i.e., how many elements are in this Stack.
     * 
     * @return int - the size of this Stack
     */
    public int size() {

        return this.size;
    }

    /**
     * Returns the capacity of this Stack, i.e., the maximum number of elements this Stack can hold.
     * 
     * @return int - the capacity of this Stack
     */
    public int capacity() {

        return this.capacity;
    }

    /**
     * Returns whether or not this Stack is empty, i.e., size == 0.
     * 
     * @return boolean - true if this Stack is empty, false otherwise
     */
    public boolean isEmpty() {

        return ((this.topNodeIndex == -1) && (this.size == 0)) ? true : false;
    }

    /**
     * Returns whether or not this Stack is full, i.e., size == capacity.
     * 
     * @return boolean - true if this Stack is full, false otherwise
     */
    public boolean isFull() {

        return (this.size == this.capacity) ? true : false;
    }

    /**
     * Pushes the given value onto the top of this Stack.
     * 
     * @param value - the data to push
     */
    public void push(Integer value) {

        if (value == null) {

            return;

        } else {

            if (isFull()) {

                resize();
            }
            insert(value);
            return;
        }
    }

    /**
     * Removes the top element of this Stack and returns the corresponding value.
     * 
     * @return Integer - the value of the top element of this Stack
     */
    public Integer pop() {

        if (isEmpty()) {

            return null;

        } else {

            return remove();
        }
    }

    /**
     * Returns the top element of this Stack without removing it.
     * 
     * @return Integer - the top element of this Stack
     */
    public Integer peek() {

        return (isEmpty()) ? null : (((StackNode) theStack[this.topNodeIndex]).value);
    }

    /**
     * Inserts the given value onto this Stack.
     * 
     * @param value - the value to insert
     */
    private void insert(Integer value) {

        theStack[this.topNodeIndex + 1] = new StackNode(value);
        this.topNodeIndex++;
        this.size++;

        return;
    }

    /**
     * Removes the top element of this Stack and returns the corresponding value.
     */
    private Integer remove() {

        StackNode topNode = (StackNode) theStack[this.topNodeIndex];
        theStack[this.topNodeIndex] = null;
        this.topNodeIndex--;
        this.size--;

        return topNode.value;
    }

    /**
     * Creates an array with double the size of the original and copies over the contents from the original.
     */
    private void resize() {

        Object[] doubleStack = new Object[this.capacity * 2];

        for (int index = 0; index < this.size; index++) {
            doubleStack[index] = theStack[index];
        }

        theStack = doubleStack;
        capacity *= 2;
        return;
    }
}

队列节点实现

public class QueueNode {

    public Integer value;

    public QueueNode() {
        this.value = null;
    }

    public QueueNode(QueueNode node) {
        this.value = node.value;
    }

    public QueueNode(Integer data) {
        this.value = data;
    }
}

队列实现

/**
 * Queue Data Structure.
 * 
 * A Queue is a first in, first out (FIFO) data structure. A Queue can have any abstract data type as an element, but is
 * characterized by two fundamental operations: enqueue() and dequeue(). The enqueue() operation adds an element to the front of
 * the Queue, hiding any elements already in the Queue, or initializing the Queue if it is empty. The dequeue() operation
 * removes an element from the front of the Queue, and returns this element's value to the caller. Elements are removed from the
 * Queue in the same order to the order of their addition to the Queue; therefore, the first element added to the Queue will be
 * the first one to be removed.
 * 
 * @author Hristo
 */
public class Queue {

    private int size;
    private int capacity;
    private int theEndIndex;
    private int theFrontIndex;

    private Object[] theQueue;

    /**
     * Default Constructor. Initalizes this Queue with initial size = 0 and capacity = 1.
     */
    public Queue() {

        this.size = 0;
        this.capacity = 1;
        this.theEndIndex = -1;
        this.theFrontIndex = -1;
        this.theQueue = new Object[this.capacity];
    }

    /**
     * Constructor. Initializes a Queue to have the given capacity.
     * 
     * @param capacity - the capacity of the Queue-to-be
     */
    public Queue(int capacity) {

        this.size = 0;
        this.capacity = capacity;
        this.theEndIndex = -1;
        this.theFrontIndex = -1;
        this.theQueue = new Object[capacity];

    }

    /**
     * Returns the size of this Queue, i.e., how many elements are in this Queue.
     * 
     * @return int - the size of this Queue
     */
    public int size() {

        return this.size;
    }

    /**
     * Returns the capacity of this Queue, i.e., the maximum number of elements this Queue can hold.
     * 
     * @return int - the capacity of this Queue
     */
    public int capacity() {

        return this.capacity;
    }

    /**
     * Returns whether or not this Queue is empty, i.e., size == 0.
     * 
     * @return boolean - true if this Queue is empty, false otherwise
     */
    public boolean isEmpty() {

        return ((this.theEndIndex == this.theFrontIndex) && (this.size == 0)) ? true : false;
    }

    /**
     * Returns whether or not this Queue is full, i.e., size == capacity.
     * 
     * @return boolean - true if this Queue is full, false otherwise
     */
    public boolean isFull() {

        return (this.size == this.capacity && this.theEndIndex == this.theFrontIndex) ? true : false;
    }

    /**
     * Inserts the given value onto the end of this Queue.
     * 
     * @param value - the data to insert
     */
    public void enqueue(Integer value) {

        if (value == null) {

            return;

        } else {

            if (isEmpty()) {
                this.theEndIndex = 0;
                this.theFrontIndex = 0;
            }

            if (isFull()) {

                resize();
            }
            insert(value);
            return;
        }
    }

    /**
     * Removes the front element in this Queue and returns it.
     * 
     * @return Integer - the front element in this Queue
     */
    public Integer dequeue() {

        if (isEmpty()) {

            return null;

        } else {

            return remove();
        }
    }

    /**
     * Returns the front element of this Queue without removing it.
     * 
     * @return Integer - the front element of this Queue
     */
    public Integer peek() {

        return (isEmpty()) ? null : (((QueueNode) theQueue[this.theFrontIndex]).value);
    }

    /**
     * Inserts the given value into this Queue.
     * 
     * @param value - the value to insert
     */
    private void insert(Integer value) {

        this.theQueue[this.theEndIndex] = new QueueNode(value);

        /*
         * 'theEndIndex' pointer indicates where to insert new QueueNodes in 'theQueue' array. If incrementing this pointer goes
         * beyond the size of 'theQueue' array, then pointer needs to wrap around to the beggining of 'theQueue' array.
         */
        this.theEndIndex++;
        if (this.theEndIndex >= this.theQueue.length) {
            this.theEndIndex = 0; // wrap around
        }

        this.size++;
        return;
    }

    /**
     * Removes the front element in this Queue and returns the corresponding value.
     */
    private Integer remove() {

        QueueNode node = (QueueNode) this.theQueue[this.theFrontIndex];
        theQueue[this.theFrontIndex] = null;

        /*
         * 'theFrontIndex' pointer indicates where to remove QueueNodes from 'theQueue' array. If incrementing this pointer goes
         * beyond the size of 'theQueue' array, then pointer needs to wrap around to the beggining of 'theQueue' array.
         */
        this.theFrontIndex++;
        if (this.theFrontIndex >= this.theQueue.length) {
            this.theFrontIndex = 0; // wrap around
        }

        this.size--;
        return node.value;
    }

    /**
     * Creates an array with double the size of the original and copies over the contents from the original.
     */
    private void resize() {

        Object[] doubleQueue = new Object[this.capacity * 2];

        int count = 0;
        int iter = this.theFrontIndex;

        while (count < this.size) {

            doubleQueue[count] = (QueueNode) theQueue[iter];
            iter++;
            count++;

            if (iter >= this.size && this.size > 1) {
                iter = 0;
            }
        }

        this.theQueue = doubleQueue;
        this.capacity *= 2;

        this.theEndIndex = this.size;
        this.theFrontIndex = 0;
        return;
    }
}

Answer 1

像这样（您添加其余部分）：

public class StackNode<T> 
{

    public T value;
}

public class Stack<T> 
{
    private int size;
    private int capacity;
    private int topNodeIndex;

    private StackNode<T>[] theStack;
}

占位符 T 描述了节点类的值帮助的类型。因此，您可以创建 Stack 或 Stack 或您希望的任何其他类型。