어떻게 링크 된 목록에서 스택을 만들 수 있습니까?

Question

문자열을 가져 와서 각 문자열 문자를 추가하는 스택을 만들려고 시도하고 있지만 LinkedList를 훨씬 더 효율적으로 사용한다고 들었습니다. LinkedList를 사용하여 스택을 만들고 조작하려면 어떻게해야합니까?

예를 들어 주시면 감사하겠습니다.

Answer 1

확인을 얻기는 문제입니다. 다음을 시도해보십시오

public class Example 
{ 
    private LinkedList aList = new LinkedList(); 

    public void push(char c) { 
     aList.addFirst(c); 
    } 
    public Object pop() { 
     return aList.removeFirst(); 
    } 
    public boolean empty() { 
     return aList.isEmpty(); 
    } 
    public static void main(String[] args) { 
     Stack exmpStack = new Stack(); 
     String ranString = "Dad"; 
     for (int i = 0; i < ranString.length(); i++) { 
      exmpStack.push(ranString.charAt(i)); 
     } 
     while (!exmpStack.empty()) { 
      System.out.print(exmpStack.pop()); 
     } 
    } 
} 

당신은 항상 null의 First를 사용하지 않을 때문에 - 그래서 당신의 루프가 결코 전혀 실행하지 않습니다! 그것을 전혀 사용하지 않고 단지 isEmpty() 함수를 사용하십시오.

편집 : 물론, 당신은 정말 전혀 그 기능이 필요하지 않습니다 - 다음은 잘 작동합니다 :

public class Example 
{ 
    private LinkedList aList = new LinkedList(); 

    public static void main(String[] args) { 
     String ranString = "Dad"; 
     for (int i = 0; i < ranString.length(); i++) { 
      aList.push(ranString.charAt(i)); 
     } 
     while (!aList.isEmpty()) { 
      System.out.print(aList.pop()); 
     } 
    } 
} 

을 지금이 여전히 약간 위험한 - 당신은에 의해 한 단계를 갈 수 있습니다 사용하여 다음 :

private LinkedList<Character> aList = new LinkedList<>(); 

가 조금 더 안전하고 Character의 대신 Objects 반환 방법 - 그리고 Characters 암시 char에 캐스트 할 수 있습니다 :)

Answer 2

Java의 LinkedList는 목록의 끝과 머리 부분에서 요소를 가져오고 추가하고 제거하는 효율적인 접근자를 사용하여 이중 연결된 목록이므로 이러한 메서드를 사용하여 스택을 에뮬레이트 할 수 있습니다.

Answer 3

LinkedList은 Vector에 의존하여 동기화 된 방법이 제공되므로 실제로 더 효율적입니다. 단일 스레드 응용 프로그램에서는 후자를 사용하면 아무런 이익이없는 동기화 가격을 지불해야합니다. 멀티 스레드 응용 프로그램에서도 동기화에 대해보다 많은 제어가 필요할 수 있습니다.

다음은 가능한 LinkedList 기반 솔루션입니다. 상속 대신 컴포지션을 사용합니다. 이렇게하면 List 관련 메서드를 사용하여 악용 될 수없는 제대로 작동하는 Stack이 제공됩니다. 귀하의 질문에서 알 수 있듯이 당신의 스택이 문자열의 문자만을 의미하는 경우

class MyStack<T> { 
    private List<T> list = new LinkedList<T>(); 

    public void push(T object) { list.add(0, object); } 

    public T pop(T object) { 
     if (isEmpty()) throw new NoSuchElementException(); 
     return list.remove(0); 
    } 

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

그럼에도 불구하고, 당신은 동적 문자 배열에 직접 스택을 에뮬레이트 할 수 있습니다. 나는 그것을 독자에게 연습으로 남겨 두거나 미래의 편집에서 제공 할 것입니다.

Answer 4

LinkedList는 스택의 작업보다 많은 작업을 제공합니다.

문자열의 문자를 푸시하고 터뜨리기 위해 스택을 사용합니다. 그러나 문자열을 삽입하는 것과 반대 방향으로 만 문자를 검색 할 수 있습니다. 이 행동을 원하면 확실합니까?

linkedlist를 사용하면 head/tail에서 데이터를 추가/검색 할 수 있습니다.

Answer 5

여기 샘플은 Stack implementation입니다. 희망이 도움이됩니다. 전혀 First를 사용하지 않을 것을

그것은 C#을 함께 이루어집니다하지만 당신은 아이디어