링크 된 라이브러리에서의 스택 작업

Question

링크 된 목록을 사용하여 스택을 구현해야하는 클래스를 작성해야합니다. 그러나 머리 대신 목록의 꼬리 부분에서 푸시 및 팝 작업을 수행해야합니다. 또한 목록의 꼬리 노드에 대한 참조를 유지하면 안됩니다.

마지막 노드에 대한 참조를 유지하지 않고 어떻게 지구에서 이것을 할 수 있습니까 ??

Answer 1

이렇게 할 수 있지만 무언가를하고 싶을 때마다 전체 목록을 검토해야하기 때문에 꽤 비효율적입니다. 모든 작업이 꼬리에서 수행되는 동안 헤드에 대한 참조를 유지하려는 이유는 실제로 없습니다. 여기

그러나 나는 어쨌든 그것을 할 것입니다 방법은 다음과 같습니다

class Entry<E> { 
    E object; 
    Entry<E> next; 
    public Entry(E obj) { 
     object = obj; 
    } 
} 

class StackList<E> { 
    Entry<E> head; 
    public void push(E element) { 
     if (head == null) { 
      // first 
      head = new Entry<E>(element); 
      return; 
     } 
     Entry<E> node = head; 
     while (node != null && node.next != null) { 
      node = node.next; 
     } 
     // node is now the tail 
     Entry<E> newEntry = new Entry<E>(element); 
     node.next = newEntry; 
    } 
    public E pop() { 
     if (head == null) { 
      // empty 
      return null; 
     } 
     Entry<E> node = head, previousNode = null; 
     while (node.next != null) { 
      previousNode = node; 
      node = node.next; 
     } 
     // node is now the tail 
     // previousNode is the next-to-last 
     if (previousNode != null) { 
      previousNode.next = null; 
     } else { 
      // there was only one thing 
      head = null; 
     } 
     return node.object; 
    } 
}