知识点（5）——使用LinkedList实现栈和队列

前言

LinkedList是一个继承于AbstractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。

LinkedList 实现 List 接口，能对它进行队列操作。

LinkedList 实现 Deque 接口，即能将LinkedList当作双端队列使用。

LinkedList 实现了Cloneable接口，即覆盖了函数clone()，能克隆。

LinkedList 实现java.io.Serializable接口，这意味着LinkedList支持序列化，能通过序列化去传输。

LinkedList 是非同步的。

一、LinkedList可以作为LIFO(后进先出)的栈，作为LIFO的栈时，下表的方法等价：

栈方法        等效方法
push(e)      addFirst(e)
pop()        removeFirst()
peek()       peekFirst()

/**
  * 将LinkedList当作 LIFO(后进先出)的堆栈
  */
private void useLinkedListAsLIFO() {       
    // 新建一个LinkedList
    LinkedList stack = new LinkedList();

       // 将1,2,3,4添加到堆栈中
      stack.push("1");
      stack.push("2");
      stack.push("3");
      stack.push("4");

      // 打印“栈”
      System.out.println("stack:"+stack);

      // 删除“栈顶元素”
      System.out.println("stack.pop():"+stack.pop());
        
      // 取出“栈顶元素”
      System.out.println("stack.peek():"+stack.peek());

      // 打印“栈”
      System.out.println("stack:"+stack);
}

 

输出结果：

stack:[4, 3, 2, 1]
stack.pop():4
stack.peek():3
stack:[3, 2, 1]

 

二、LinkedList可以作为FIFO(先进先出)的队列，作为FIFO的队列时，下表的方法等价：

队列方法       等效方法
add(e)        addLast(e)
offer(e)      offerLast(e)
remove()      removeFirst()
poll()        pollFirst()
element()     getFirst()
peek()        peekFirst()

/**
  * 将LinkedList当作 FIFO(先进先出)的队列
  */
private void useLinkedListAsFIFO() {
      // 新建一个LinkedList
      LinkedList queue = new LinkedList();

      // 将10,20,30,40添加到队列。每次都是插入到末尾
      queue.add("10");
      queue.add("20");
      queue.add("30");
      queue.add("40");

      // 打印“队列”
      System.out.println("queue:"+queue);

      // 删除(队列的第一个元素)
      System.out.println("queue.remove():"+queue.remove());
  
      // 读取(队列的第一个元素)
      System.out.println("queue.element():"+queue.element());

      // 打印“队列”
      System.out.println("queue:"+queue);
 }

输出结果：

queue:[10, 20, 30, 40]
queue.remove():10
queue.element():20
queue:[20, 30, 40]