java - 通过单链表实现栈

Question

关闭。此题需要 details or clarity 。目前不接受答案。

---

想要改进这个问题吗？通过 editing this post 添加详细信息并澄清问题.

已关闭 8 年前。

Improve this question

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

这是我正在实现的界面:

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;
}