通過單鏈表實現棧

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