Java : 하나의 대기열에 스택을 구현하면 문제가 발생합니까?

Question

그래서 하나의 대기열로 스택을 구현하려고 시도했지만 제대로 작동하는 것처럼 보였습니다. 그러나 온라인에서 두 가지 대기열을 사용하는 솔루션의 대부분이 2 개의 대기열을 사용하기 때문에 문제가 있는지 확실하지 않습니다. 내 구현에 문제가 있다면 아무에게 말해 줄 수 있습니까?

public class MyStack<T> { 

/** 
* @param args 
*/ 
private Queue<T> q = new LinkedList<T>(); 
public MyStack(){ 
} 
public static void main(String[] args) { 
    // TODO Auto-generated method stub 
    MyStack<String> s = new MyStack<String>(); 
    s.push("1"); 
    s.push("2"); 
    s.push("3"); 
    s.push("4"); 
    System.out.println(s.pop()); 
    System.out.println(s.pop()); 
    System.out.println(s.pop()); 
    System.out.println(s.pop()); 
    System.out.println(s.pop()); 
} 

public void push(T s){ 
    q.offer(s);   
} 

public T pop(){ 
    int n = q.size(); 
    for(int i = 0; i < n-1; i++){ 
     q.offer(q.poll());    
    } 
    return q.poll(); 
} 
} 

출력 :
4
3
2
1
널

Answer 1

스택 두 개의 큐를 사용해야하는 이유가 전혀 없다. 사실, 노드 아래에있는 노드를 참조하는 최상위 노드 하나만 추적하면됩니다.

코드가 작동하는 것처럼 보이지만 nachokk이 말한 것처럼 코드 검토 사이트가 아닙니다. 이 사이트는 오류가 발생하여 도움이 필요하면 도움이됩니다.

Answer 2

Stack 또는 Deque 또는 LinkedList 중 하나를 사용해야합니다.

자신 만의 구현은 의미가 없습니다. 물론 (@bas가 제시 한대로) 데이터 구조에 대한 코스를 수행하지 않는 한, Commando로 이동하여 처음부터 직접 구조를 구현해야합니다. 그것이 당신이 만들고자하는 것과 거의 비슷하기 때문에 다른 구조를 사용하는 것은 망치로 나사를 사용하는 것과 같습니다. 당신이 정말로 뭔가를 구현해야하는 경우

자신은 다음과 같이 작동합니다 :

public class Stack<T> { 
    private Entry top = null; 

    private class Entry { 
    final Entry up; 
    final T it; 

    public Entry(Entry up, T it) { 
     this.up = up; 
     this.it = it; 
    } 
    } 

    public void push (T it) { 
    top = new Entry(top, it); 
    } 

    public T pop() { 
    if (top == null) { 
     throw new EmptyStackException(); 
    } 
    T it = top.it; 
    top = top.up; 
    return it; 
    } 
} 

NB :이 스레드로부터 안전하지 않을 수 있습니다.

Answer 3

당신이 뭔가를 뽑을 때마다 전체 스택을 반복해야하기 때문에 솔루션이 비효율적입니다. (실제로는 끝나는 요소를 제거하기 전에 링크 된 전체 목록을 트래버스해야합니다.) 편집 : Java의 연결된 목록은 어쨌든 이중으로 링크되어 있기 때문에 완전히 무의미합니다.

Answer 4

기본 대기열 작업 (예 : 대기열에 넣기 및 대기열에서 제외)이있을 때만 두 개의 대기열을 사용해야합니다. 다른 메소드를 사용할 수있을 때, 특히 큐를 반복 할 때와 마찬가지로, 하나의 큐로 처리 할 수 ​​있습니다.