在 java 中实施队列

Question

在 Java 中实现队列是很常见的面试问题。我在网上冲浪并看到许多实现，他们在其中做一些花哨的事情，比如实现队列接口和编写自己的 addLast() 和 removeFirst() 方法。我的问题是我不能只使用 LinkedList() class 并使用它的预定义方法 addLast 和 removeFirst 方法来做同样的事情吗？例如

LinkedList<Student> qu=new LinkedList<Student>();
qu.add(new Student("anadkat1"));
qu.add(new Student("anadkat2"));
qu.add(new Student("anadkat5"));
System.err.println(qu);
qu.removeFirst();
System.err.println(qu);

这给了我完美的结果。这还不够吗？

Answer 1

我最近经历了这些面试问题。

使用 set 方法从列表中添加、删除、chekForEmpty 等是实现队列的通用方法。

例如：

   public void enqueue(E item) {
     list.addLast(item);
     }

   public E dequeue() {
      return list.poll();
      }

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

   public int size() {
      return list.size();
      }

   public void addItems(GenQueue<? extends E> l) {
      while (l.hasItems())
        list.addLast(l.dequeue());
        }

Answer 2

一种方法是维护一个项目数组 q 和队列头部和尾部的两个索引（初始设置为 0）。伪代码如下：

enqueue(x)
{   q[tail++] = x;
}

dequeue()
{   return q[head++];
}

如果数组溢出，将大小加倍并重新插入项目。这会产生每个操作的 O(1) 摊销时间。另一种方法是使用链表（您应该实现）并再次存储指向头部的指针和指向尾部的指针。

Answer 3

public class Queue<T>{
private LinkedList<T> list=new LinkedList<>();

public void insert(T element){
     list.addLast(element);
}

public void remove(){
    list.removeFirst();
}

public int size(){
    return list.size();
}

public T element(){
     return list.getFirst();
}
}

在 java 中实施队列

Implementing queue in java

java

queue