0

所以我尝试用一​​个队列实现一个堆栈，它似乎可以工作，但我不确定它是否有问题，因为我在网上看到的大多数解决方案都使用两个队列。谁能告诉我我的实施是否有问题？

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
空

4

4 回答 4

1

您的解决方案效率低下，因为每次从中弹出某些内容时都必须遍历整个堆栈。（实际上，您必须遍历整个链表，然后才能删除最后的元素。）编辑：Java 的链表无论如何都是双向链接的，所以这完全没有意义。

于 2013-08-04T21:28:05.837 回答
1

您应该使用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-04T21:23:41.793 回答
0

堆栈绝对没有理由使用两个队列。事实上，它只需要跟踪一个引用它下面的节点的顶级节点。

该代码似乎有效，但正如 nachokk 所说，这不是代码审查的站点。如果您遇到错误并需要帮助，本网站将提供帮助。

于 2013-08-04T21:23:07.330 回答
0

仅当您具有基本队列操作（例如入队和出队）时，才必须使用两个队列。当您可以使用其他方法时，尤其是迭代队列时，您可以只使用一个队列，就像您所做的那样。

于 2013-08-04T22:01:48.320 回答