如何将ArrayStack类改造为使用ArrayList和LinkedList的类？

Hey there! Let's break down how to convert your ArrayStack into versions using ArrayList and LinkedList—I'll walk you through each step so you can see exactly how these collection classes fit in place of the raw array.

First, let's define the custom exception your original code uses (since we'll need it for both versions):

class ArrayStackException extends RuntimeException {
    public ArrayStackException(String message) {
        super(message);
    }
}

ArrayList is a dynamic array implementation, which makes it a natural replacement for your fixed-size array stack. We can keep your original max-size logic while leveraging ArrayList's built-in methods to avoid managing a top pointer manually.

import java.util.ArrayList;

public class ArrayListStack {
    private final int maxSize;
    private final ArrayList<Integer> items;

    public ArrayListStack(int maxSize) {
        if (maxSize <= 0) {
            throw new ArrayStackException("Stack size must be positive");
        }
        this.maxSize = maxSize;
        // Initialize with maxSize as initial capacity to avoid unnecessary resizing
        this.items = new ArrayList<>(maxSize);
    }

    public void push(int item) {
        if (isFull()) {
            throw new ArrayStackException("Stack is full");
        }
        // Add to the end of the list—this acts as our stack top
        items.add(item);
    }

    public int pop() {
        if (isEmpty()) {
            throw new ArrayStackException("Stack is empty");
        }
        // Remove and return the last element (stack top)
        return items.remove(items.size() - 1);
    }

    public int peek() {
        if (isEmpty()) {
            throw new ArrayStackException("Stack is empty");
        }
        // Return the last element without removing it
        return items.get(items.size() - 1);
    }

    public boolean isEmpty() {
        return items.isEmpty();
    }

    public boolean isFull() {
        return items.size() == maxSize;
    }

    public int size() {
        return items.size();
    }
}

Key Notes: #

• We ditch the top variable entirely—items.size() tells us exactly how many elements are in the stack, and the stack top is always at index size() - 1.
• push() uses ArrayList.add() which appends to the end, perfectly matching stack behavior.
• We initialize the ArrayList with maxSize as the initial capacity to avoid auto-resizing overhead (though it will still resize if you bypass the isFull() check).

LinkedList implements the Deque interface, which comes with built-in stack methods (push(), pop(), peek()) that align perfectly with stack behavior. This version is even more concise.

import java.util.LinkedList;

public class LinkedListStack {
    private final int maxSize;
    private final LinkedList<Integer> items;

    public LinkedListStack(int maxSize) {
        if (maxSize <= 0) {
            throw new ArrayStackException("Stack size must be positive");
        }
        this.maxSize = maxSize;
        this.items = new LinkedList<>();
    }

    public void push(int item) {
        if (isFull()) {
            throw new ArrayStackException("Stack is full");
        }
        // LinkedList.push() adds elements to the HEAD (our stack top)
        items.push(item);
        // Equivalent to: items.addFirst(item);
    }

    public int pop() {
        if (isEmpty()) {
            throw new ArrayStackException("Stack is empty");
        }
        // LinkedList.pop() removes and returns the HEAD element (stack top)
        return items.pop();
        // Equivalent to: items.removeFirst();
    }

    public int peek() {
        if (isEmpty()) {
            throw new ArrayStackException("Stack is empty");
        }
        // LinkedList.peek() returns the HEAD element without removing it
        return items.peek();
        // Equivalent to: items.getFirst();
    }

    public boolean isEmpty() {
        return items.isEmpty();
    }

    public boolean isFull() {
        return items.size() == maxSize;
    }

    public int size() {
        return items.size();
    }
}

Key Notes: #

• LinkedList uses its head node as the stack top, so push()/pop() operations are O(1) time complexity (no element shifting needed).
• We use the built-in stack methods for clarity, but you could also use addFirst(), removeFirst(), and getFirst() if you prefer explicit calls.
• Like the ArrayList version, we keep the maxSize check to match your original stack's behavior—you can remove this if you want an unbounded stack.

Quick Comparison #

• ArrayList: Best if you need occasional random access to stack elements (though stacks rarely need this) and want efficient append/pop from the end.
• LinkedList: Best if you prioritize O(1) insert/remove from the top and don't need random access.

内容的提问来源于stack exchange，提问作者Moch. Chamdani M