Java：用一個隊列實現堆棧，有什麼問題？

所以我試圖用一個隊列實現一個堆棧，它看起來可以工作，但我不確定它是否有問題，因爲我在網上看到的大多數解決方案都使用兩個隊列。任何人都可以告訴我，如果我的執行有問題嗎？Java：用一個隊列實現堆棧，有什麼問題？

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

輸出：
空

來源

2013-08-04 user2017502

如果你想代碼審查這不是網站，你有一個意想不到的行爲？ – nachokk

沒有意外的行爲。我只是想知道爲什麼大多數在線解決方案使用兩個隊列時，似乎工作得很好。 – user2017502

從來沒有見過用2個隊列實現的堆棧，你見過的解決方案是什麼？此外，爲什麼'Queue'因爲是FIFO而Stack是LIFO。 – zapl

是絕對沒有理由的堆疊應該使用兩個隊列。事實上，它只需要跟蹤一個引用它下面的節點的頂級節點。

該代碼似乎工作，但正如nachokk所說，這不是代碼審查的網站。如果您遇到錯誤並需要幫助，此站點更新。

來源

2013-08-04 21:23:07 bas

您應該使用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; 
    } 
}

注意：這可能不是線程安全的。

來源

2013-08-04 21:23:41 OldCurmudgeon

如果您正在學習Java中的數據結構課程，請不要使用它。我從來沒有想過要知道這些結構是如何工作的，以及如何有效地實施這些結構。 – bas

謝謝，我不知道Deque是否存在。但無論如何，我只是試圖這樣做，因爲我在接受採訪時被問到。如果我自己做，我只會使用Java自己的實現，而不是試圖重新發明輪子。 – user2017502

@ user2017502 - 我添加了一個簡單的可能性。 – OldCurmudgeon

您的解決方案效率低下，因爲每次從中彈出某些內容時都必須遍歷整個堆棧。（實際上，在移除最後一個元素之前，必須遍歷整個鏈表。）編輯：Java的鏈接列表無論如何都是雙向鏈接的，所以這完全沒有意義。

來源

2013-08-04 21:28:05 user234461

如果你只有基本隊列。你將如何更有效地實現它？ – user2017502

只有在有基本的隊列操作時才能使用兩個隊列，如入隊和出隊。當你可以使用其他方法時，尤其是迭代隊列時，你可以只用一個隊列來完成，就像你一樣。

來源

2013-08-04 22:01:48 MGorgon

Java：用一個隊列實現堆棧，有什麼問題？

回答

相關問題