Java链表对Queue接口的支持

2015-07-11 10:43:49 暂无评论阳光倾城随笔杂文 860

Queue接口的操作：队列属于：先进先出；提供了一系列添加、清除元素的操作：
                Throws exception          Returns special value
Insert:                 add(e)                                 offer(e)
Remove :                remove()                         poll()
Examine :           element()                         peek()
// 添加元素到队列：入列
The offer method inserts an element if possible, otherwise returning false. This differs from the Collection.add method, which can fail to add an element only by throwing an unchecked exception. The offer method is designed for use when failure is a normal, rather than exceptional occurrence, for example, in fixed-capacity (or “bounded”) queues.
1.boolean add(E e)        // 没有空间时抛出异常
    Inserts the specified element into this queue if it is possible to do so immediately without violating capacity restrictions, returning true upon success and throwing an IllegalStateException if no space is currently available.
2.public boolean offer(E e) // 没有空间限制时自动添加到尾部，有长度限制时和add方法一样抛出异常；
    Inserts the specified element into this queue if it is possible to do so immediately without violating capacity restrictions. When using a capacity-restricted queue, this method is generally preferable to add(E), which can fail to insert an element only by throwing an exception.
// 从队列删除元素：出列
The remove() and poll() methods remove and return the head of the queue. Exactly which element is removed from the queue is a function of the queue's ordering policy, which differs from implementation to implementation. The remove() and poll() methods differ only in their behavior when the queue is empty: the remove() method throws an exception, while the poll() method returns null.
1.E remove()        // 队列头返回并删除
                                        // 为空时抛出异常
    Retrieves and removes the head of this queue. This method differs from poll only in that it throws an exception if this queue is empty.
2.E poll()        // 队列头返回并删除
                                         // 为空时返回null；
    Retrieves and removes the head of this queue, or returns null if this queue is empty.
The element() and peek() methods return, but do not remove, the head of the queue.
1.public E element() // 队列头返回但保留// 空队列抛出异常
    Retrieves, but does not remove, the head of this queue. This method differs from peek only in that it throws an exception if this queue is empty.
2.public E peek()        // 队列头返回保留        // 空队列返回null；
    Retrieves, but does not remove, the head of this queue, or returns null if this queue is empty.
—-LinkedList对队列支持实例：
package com.mldn;
import java.util.LinkedList;
import java.util.ArrayList;
import java.util.List;
public class LinkedListDemo
{
        public static void main(String[] args)
        {
                LinkedList link = null;        // 声明一个空链表,元素是String类型
                List al = new ArrayList(1); // 实例化初始长度为1的数组向量
                link = new LinkedList(al);        // 实例化初始长度为1的链表
                try
                {        // 判断链表是否有边界
                        System.out.println(link.add(“a”));
                        System.out.println(link.add(“b”));
                }
                catch (Exception e)
                {
                        e.printStackTrace();
                }
                try
                {        // 判断List是否有边界
                        System.out.println(al.add(“a”));
                        System.out.println(al.add(“b”));
                }
                catch (Exception e)
                {
                        e.printStackTrace();
                }
                try
                {        // 用offer方法
                        System.out.println(link.offer(“b”));
                        System.out.println(link.offer(“c”));
                        System.out.println(link.peek());
                }
                catch (Exception e)
                {
                        e.printStackTrace();
                }
                link = new LinkedList(); // 实例化
                // 以追加的形式添加元素
                link.add(“a”);        // 添加元素
                link.add(“b”);
                link.add(“c”);        // 空间不足抛出异常
                link.offer(“d”); // 以队列形式添加元素，空间不足时，返回false，
                System.out.println(“检查链表头：” + link.element());        // 检查队列头，存在返回，为空抛出异常
                System.out.println(“检查链表头：” + link.peek());        // 检查队列头，存在返回，否则返回null
                System.out.println(“链表头出列：” + link.remove());        // 删除链表头，并返回，不存在抛出异常
                System.out.println(“链表头出列：” + link.poll());        // 删除链表头，并返回，不存在返回null
                System.out.println(“链表头出列：” + link.remove());        // 删除链表头，并返回，不存在抛出异常
                System.out.println(“链表头出列：” + link.poll());        // 删除链表头，并返回，不存在返回null
                System.out.println(“检查链表头1.peek()：” + link.peek());        // 检查队列头，存在返回，否则返回null
                System.out.print(“检查链表头2.element()：”);
                try
                {
                        System.out.print(link.element());        // 检查队列头，存在返回，为空抛出异常
                }
                catch (Exception e)
                {
                        e.printStackTrace();
                }
                System.out.println(“\n链表头出列1.remove()：”);
                try
                {
                        System.out.println(link.remove());        // 删除链表头，并返回，不存在抛出异常
                }
                catch (Exception e)
                {
                        e.printStackTrace();
                }
                System.out.println(“\n链表头出列2.poll()：”);
                try
                {
                        System.out.println(link.poll());        // 删除链表头，并返回，不存在抛出异常
                }
                catch (Exception e)
                {
                        e.printStackTrace();
                }
        }
}
/*
administrator@xu-desktop:~$ java com.mldn.LinkedListDemo
true
true
true
true
true
true // 全为真，说明List类型是无边界的，可以添加任意多的元素；
a
检查链表头：a
检查链表头：a
链表头出列：a
链表头出列：b
链表头出列：c
链表头出列：d
检查链表头1.peek()：null // 不抛出异常，继续执行程序
检查链表头2.element()：java.util.NoSuchElementException // 抛出异常，若不捕获将终止程序
        at java.util.LinkedList.getFirst(LinkedList.java:109)
        at java.util.LinkedList.element(LinkedList.java:459)
        at com.mldn.LinkedListDemo.main(LinkedListDemo.java:66)
链表头出列1.remove()： // 抛出异常，若不捕获将终止程序
java.util.NoSuchElementException
        at java.util.LinkedList.remove(LinkedList.java:788)
        at java.util.LinkedList.removeFirst(LinkedList.java:134)
        at java.util.LinkedList.remove(LinkedList.java:481)
        at com.mldn.LinkedListDemo.main(LinkedListDemo.java:75)
链表头出列2.poll()： // 不抛出异常，继续执行程序
null
*/
———–按队列FIFO输出链表：
package com.mldn;
import java.util.LinkedList;
import java.util.Collections;
public class LinkedListDemo
{
        public static void main(String[] args)
        {
                LinkedList link = null;        // 声明一个空链表,元素是String类型
                link = new LinkedList(); // 实例化
                // 以追加的形式添加元素
                link.add(“a”);        // 添加元素
                link.add(“b”);
                link.add(“c”);        // 空间不足抛出异常
                link.offer(“d”); // 以队列形式添加元素，空间不足时，返回false，
                System.out.println(“以FIFO方式输出：”);        // 先进先出
                /*int length = link.size();        // 链表的长度在poll操作中是个变数，所以要首先确定下来循环的次数！
                for (int x = 0, temp = 0, t = 0; x                 {
                        temp = link.size();
                        System.out.println(“链表头：” + link.get(0));
                        System.out.println(“循环执行” + (++t) + “次, 弹出 ” + link.poll() + ” 当前链表长度temp = ” + temp);
                }*/
                int t = 0, temp = 0;
                System.out.println(“链表元素：”);
                for (int x = 0; x                 {
                        System.out.print(link.get(x) + ” “);        // 输出链表
                }
                System.out.println();        // 换行
                while (link.peek() != null)                // 更安全的操作是使用while
                {
                        temp = link.size();
                        System.out.println(“链表头：” + link.get(0));
                        System.out.println(“循环执行” + (++t) + “次, 弹出 ” + link.poll() + ” 当前链表长度temp = ” + temp);
                }
        }
}
/*
administrator@xu-desktop:~$ java com.mldn.LinkedListDemo
以FIFO方式输出：
链表元素：
a b c d
链表头：a
循环执行1次, 弹出 a 当前链表长度temp = 4
链表头：b
循环执行2次, 弹出 b 当前链表长度temp = 3
链表头：c
循环执行3次, 弹出 c 当前链表长度temp = 2
链表头：d
循环执行4次, 弹出 d 当前链表长度temp = 1
*/
// List,Queue都属于顺序集合的接口，可以存放重复的元素；
// Set不可以存放重复元素：