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：用一个队列实现堆栈，有什么问题？

回答

相关问题