java学习笔记-集合之栈和队列

栈Stack

栈是Vector的一个子类，它实现了一个标准的后进先出的栈。堆栈只定义了默认构造函数，用来创建一个空栈。 堆栈除了包括由Vector定义的所有方法，也定义了自己的一些方法。

boolean empty()  //判断栈是否为空
Object peek()    //查看堆栈顶部的对象，但不从堆栈中移除它。
Object pop()     //移除堆栈顶部的对象，并作为此函数的值返回该对象。
Object push(E element) //把项压入堆栈顶部。
int search(Object element)  //返回对象在堆栈中的位置，以 1 为基数。

下面的代码演示了栈的基本用法

   public static void main(String[] args)
   {
        Stack<String> stack = new Stack<String>();

        stack.push("a");
        stack.push("b");
        stack.push("c");
        stack.push("d");
        System.out.println("stack中栈顶的元素: "+ stack.peek());
        System.out.println("stack中b的元素索引: "+ stack.search("b")); 
        while(!stack.empty()){
            System.out.print( stack.pop() + " " );
        }
    }

输出结果为

stack中栈顶的元素: d
stack中b的元素索引: 3
d   c   b   a   

队列 Queue

队列是一种特殊的线性表，它只允许在表的前端进行删除操作，而在表的后端进行插入操作。LinkedList类实现了Queue接口，因此我们可以把LinkedList当成Queue来用。
Queue的主要方法如下

boolean add(Object element)    //向队的末尾添加元素，如果队列已满，会抛出异常
boolean offer(Object element)  //相队的末尾添加元素，如果队列已满，返回false，推荐使用

Object remove()                //删除并返回队列头部的元素，如果队列为空抛出异常 
Object poll()                  //删除并返回队列头部的元素，如果队列为空返回null，推荐使用

Object element()               //返回队列头部的元素，如果队列为空抛出异常
Object peek()                  //返回队列头部的元素，如果队列为空返回null，推荐使用

一般队列 Queue

一般队列的示例代码如下

    public static void main(String[] args)
    {
        Queue<String> queueList = new LinkedList<>();
        //使用offer方法
        queueList.offer("a");
        queueList.offer("b");
        queueList.offer("c");
        queueList.offer("d");
        System.out.println("queueList peek 栈顶元素: " + queueList.peek());
        while(!queueList.isEmpty())
        {
            System.out.print( queueList.poll() + " " );
        }
        System.out.println( "\n队列为空 poll " + queueList.poll());
        System.out.println( "队列为空 peek " + queueList.peek());
        //使用add方法
        queueList.add("a");
        queueList.add("b");
        queueList.add("c");
        queueList.add("d");
        System.out.println("queueList element 栈顶元素: " + queueList.element());
        while(!queueList.isEmpty())
        {
            System.out.print( queueList.remove() + " " );
        }
        try {
            System.out.println( "\n队列为空 remove " + queueList.remove());
        }catch(NoSuchElementException e){
            System.out.print("\n队列为空 remove 捕获异常 " );
        }
        try {
            System.out.println( "\n队列为空 element " + queueList.element());
        }catch(NoSuchElementException e){
            System.out.print("\n队列为空 element 捕获异常 " );
        }
    }

输出结果为

queueList peek 栈顶元素: a
a   b   c   d   
队列为空 poll null
队列为空 peek null
queueList element 栈顶元素: a
a   b   c   d   
队列为空 remove  捕获异常   
队列为空 element 捕获异常

双向队列 Deque

Queue接口是单向队列，它有一个子接口Deque，表示双向队列。双向队列的特点是在队列的头部和尾部都可以添加或删除元素。它可以使用new ArrayDeque<>()来初始化，同时LinkedList实现了它的接口，也可使用new LinkedList<>()来初始化。
主要方法如下

//向队列的头部或者尾部添加元素，如果队列已满会抛出异常
void addFirst(Object element)        
void addLast(Object element)    

//向队列的头部或者尾部添加元素，如果队列已满返回false
boolean offerFirst(Object element)   
boolean offerLast(Object element)   

//从头部或尾部删除元素，如果队列为空抛出异常
Object removeFirst()
Object removeLast()

//从头部或尾部删除元素，如果队列为空返回nul
Object pollFirst()
Object pollLast()

//从队列头部或者尾部获取元素，如果队列为空抛出异常
Object getFirst()
Object getLast()

//从队列头部或者尾部获取元素，如果队列为空返回null
Object peekFirst()
Object peekLast()

示例代码

    public static void main(String[] args)
    {
        Deque<String> deque = new ArrayDeque<String>();

        deque.offer("b");
        deque.offerFirst("a");
        deque.offerLast("c");
        deque.offer("d");

        System.out.println("遍历双向队列 " );
        for(String atr : deque)
        {
            System.out.print(atr + " " );
        }
    }

输出结果

遍历双向队列 
a   b   c   d   

优先级队列 PriorityQueue

优先级队列会按照排序的方式对队列中的元素进行排序和检索。因此加入到PriorityQueue中的对象必须实现Comparable接口，提供对元素排序时两个元素之间的比较规则。
示例代码

    public static void main(String[] args)
    {
        Queue<String> priorityQueue = new PriorityQueue<String>();
        priorityQueue.add("c");
        priorityQueue.add("a");
        priorityQueue.add("d");
        priorityQueue.add("b");

        System.out.println("遍历优先级队列 " );
        for(String atr : priorityQueue)
        {
            System.out.print(atr + " " );
        }
        System.out.println("\n依次删除优先级队列中的元素");
        while(!priorityQueue.isEmpty())
        {
            System.out.print(priorityQueue.poll() + " " );
        }
    }

注意的是，用foreach语句遍历优先级队列时，获得元素并没有排序，而在通过poll()或者remove()方法删除元素时，该方法总会删除当前队列中最小的元素。
以上代码输出结果为

遍历优先级队列 
a   b   d   c   
依次删除优先级队列中的元素
a   b   c   d

LinkedList

LinkedList在实现中采用了链表的数据结构，对顺序访问进行了优化，向Lsit中插入和删除元素的速度较快，随机访问则相对较慢。而且LinkedList实现了实现了较多的接口，它可以作为栈、队列和双向队列使用。
示例代码如下

    public static void main(String[] args)
    {
        LinkedList<String> linkList = new LinkedList<>();
        System.out.println("linkList stack: ");

        linkList.push("a");
        linkList.push("b");
        linkList.push("c");
        linkList.push("d");
        while(!linkList.isEmpty())
        {
            System.out.print( linkList.pop() + " " );
        }

        System.out.println();
        System.out.println("linkList queue offer方法: ");
        linkList.offer("a");
        linkList.offer("b");
        linkList.offer("c");
        linkList.offer("d");
        while(!linkList.isEmpty())
        {
            System.out.print( linkList.poll() + " " );
        }

        System.out.println();
        System.out.println("linkList queue add方法: ");
        linkList.add("a");
        linkList.add("b");
        linkList.add("c");
        linkList.add("d");
        while(!linkList.isEmpty())
        {
            System.out.print( linkList.remove() + " " );
        }
    }

输出结果如下

linkList stack: 
d   c   b   a   
linkList queue offer方法: 
a   b   c   d   
linkList queue add方法: 
a   b   c   d