关于队列这个问题，为什么要在tail部分添加元素呢？

Question

在front部分添加删除元素都是o(1)的复杂度
在tail部分添加就是o(n)
我觉得在tail这端删除也是o(n)
那为什么老师选择在tail端添加在front端删除
我觉得在front端添加和在tail端删除也一样的啊
为什么加了尾部指针就可以了呢

Answer 1

liuyubobobo 2018-09-18 02:39:33

如果我们的链表没有tail指针的话：

在链表头添加：O(1)，在链表尾删除：O(n)；

在链表头删除：O(1)，在链表尾添加：O(n)；

所以，如果使用链表实现一个队列，在没有指针的情况下，不管选择从哪边删除哪边添加，总有一个操作是O(n)的。

当我们维护了一个尾指针以后。从链表头增删，和从链表尾增删，都是O(1)的。

是的。此时，从链表头添加，从链表尾删除也是ok的。这时只是一个选择而已，对性能没有影响。我选择从链表头删除，从链表尾添加，是因为和队列的“语意”保持一致，即链表头就是队头，用于出队；链表尾就是队尾，用于入队。

当然了，依然是，你选择从链表头添加，从链表尾删除，是完全ok的。建议有兴趣自己实现一下试试看：）

加油！：）

• 提问者 慕前端0929456 #1

  老师，对于您昨天的回答，我试了一下这样我做。

• 提问者 慕前端0929456 #2

  //入队 
  public void enqueue(E e) {
                Node node = new Node(e);
                if(size==0){
                     head = node;
                     tail = node;
                     size++;
                }else {
                    node.next = head;
                    head = node;
                    tail = head.next;
                     while(tail.next!=null){
                         tail = tail.next;
                     }
  
                    size++;
                }
  
  
              }
  
  
  
  
  
  
  
  
  //出队
   public E deQueue(){
                if(isEmpty()){
                    throw  new IllegalArgumentException("队列为空，不能出队!");
                }else{
                    Node e = head;
                    E til = tail.e;
                    while(e.next!=tail){
                        e = e.next;
                    }
                    tail = e;
                    tail.next=null;
                    size--;
                    return til;
  
  
  
                }
  
  
             }

• 提问者 慕前端0929456 #3

  这样可以实现出来，front这边入队，不过要对tail进行维护，我觉得还是要遍历整个链表。我认为时间时间复杂度是o(n),对于在tail这端出队，要找到tail之前的那个节点，我认为也是o(n)这样虽然实现了，但是我觉得还是发现您上课讲的方比较方便一点

点开查看后面1条评论