通过单链表实现栈

Question

我在通过 single linked list 实现 stack 时遇到问题：

这是我正在实现的界面：

public interface Stack<E> {

    /**
     * element at the top without removing it
     */
    public E peek();

    /**
     * pop from the stack
     */
    public void pop();

    /**
     * insert into the stack
     */
    public void push( E e );

    /**
     * isEmpty
     */
    public boolean isEmpty();

    /**
     * size
     */
    public int size();

    /**
     * reverse
     */
    public Stack<E> reverse();

}

这是我的实现：

public class ListStack<E> implements Stack<E> {

    private static class Node<T> {
        private T item;
        private Node<T> next;

        private Node(T item, Node<T> next) {
            this.item = item;
            this.next = next;
        }
    }

    private Node<E> first;
    private int size;


    public ListStack() {
        this.size = 0;
        this.first = null;
    }

    @Override
    public E peek() {
        return first.item;
    }

    @Override
    public void pop() {
        first = first.next;
        size--;
    }

    @Override
    public void push(E e) {

        Node<E> node = new Node<E>(e, first);
        first = node;
        size++;
    }

    @Override
    public boolean isEmpty() {

        return (first == null);
    }

    @Override
    public int size() {

        return size;
    }

    @Override
    public Stack<E> reverse() {

    }

}

我正在努力使用 reverse 方法，我不确定我的编程是否正确。

如有任何帮助，我们将不胜感激！

Answer 1

要反转现有堆栈，您只需遵循现有堆栈的 Node.next 引用，并沿途将项目推入新堆栈。

@Override
public Stack<E> reverse()
{
    ListStack<E> reversed = new ListStack<E>();

    Node<E> node = first;
    while(node != null)
    {
        reversed.push(node.item);
        node = node.next;
    }

    return reversed;
}

通过单链表实现栈

Implementing a stack through a single linked list

java

stack