重新认识LinkedList实现栈、队列或者双端队列

如果想进大厂免不了要leetcode，而leetcode时免不了很多题跟栈，队列有关，重新认识一下LinkedList也许能在不时之需时，助你进入大厂。LinkedList实现了Deque和Queue接口，可以按照队列、栈和双端队列的方式进行操作。

0x01：Queue接口

Queue里面的方法，Queue扩展了Collection，它的主要操作有三个功能操作。每个操作有2个方法，针对队列长度是否受限制，对应是否抛异常。有些队列的是有长度限制的，本例的LinkedList实现queue没长度限制。

• 在尾部添加元素 (add, offer)：add()会在长度不够时抛出IllegalStateException异常；offer()则不会，只返回false；
• 查看头部元素 (element, peek)：返回头部元素，但不改变队列。element()会在没元素时抛出NoSuchElementException异常，而peek()返回null;
• 删除头部元素 (remove, poll)：返回头部元素，并且从队列中删除。remove()会在没元素时抛出NoSuchElementException异常; 而poll()返回null;

LinkedList模拟队列

import java.util.LinkedList;
import java.util.Queue;
/**
* 用LinkedList模拟队列，因为链表擅长插入和删除
*/
public class QueueDemo{
    public static void main(String [] args) { 
        //做剑指offer遇见过这个数结
        Queue<String> queue = new LinkedList<String>();
        //追加元素
        queue.add("zero");
        queue.offer("one");
        queue.offer("two");
        queue.offer("three");
        queue.offer("four");
        System.out.println(queue);//[zero, one, two, three, four]
        //从队首取出元素并删除
        System.out.println(queue.poll()); // zero
        System.out.println(queue.remove()); // one
        System.out.println(queue); //[two, three, four]
        //从队首取出元素但是不删除
        String peek = queue.peek();
        System.out.println(peek); // two
        //遍历队列，这里要注意，每次取完元素后都会删除，整个
        //队列会变短，所以只需要判断队列的大小即可
        while(queue.size() > 0) {
            System.out.println(queue.poll());
        }//two three four
    }
}

0x02：Deque接口

Java中有一个类Stack，用于表示栈，但该类已经过时了。Java中没有单独的栈接口，栈相关方法包括在了表示双端队列的接口Deque中，主要有三个方法。

• push()表示入栈，在头部添加元素，栈的空间可能是有限的，如果栈满了，push会抛出异常IllegalStateException；
• pop()表示出栈，返回头部元素，并且从栈中删除，如果栈为空，会抛出NoSuchElementException异常；
• peek()查看栈头部元素，不修改栈，如果栈为空，返回null;

栈和队列只是双端队列的特殊情况，它们的方法都可以使用双端队列的方法替代，使用不同的名称和方法，概念上更为清晰。具体参考Deque接口里面的方法。

LinkedList模拟栈

import java.util.Deque;
import java.util.LinkedList;

public class StackDemo{
    public static void main(String[] args) {
        /*模拟栈，这是从头开始进来的*/
        Deque<String> deque = new LinkedList<String>();
        /*Pushes an element onto the stack at the head of this dequeue */
        deque.push("a");
        deque.push("b");
        deque.push("c");
        System.out.println(deque); //[c, b, a]
        //获取栈首元素后，元素不会出栈
        System.out.println(deque.peek());//c
        while(deque.size() > 0) {
            //获取栈首元素后，元素将会出栈
            System.out.println(deque.pop());//c b a
        }
        System.out.println(deque);//[]

        /*模拟栈*/
        deque.offerLast("a");
        deque.offerLast("b");
        deque.offerLast("c");// [a, b, c]
        while(!deque.isEmpty()){
            System.out.println(deque.pollLast());
        }
    }   // 先输出c再b最后a
}