数据结构实现（二）队列

1、队列的顺序存储结构实现

package dataStructures;

public class QueueArray<E> {
    private Object[] data = null;
    private int maxSize; // 队列容量
    private int head; // 队列头，允许删除
    private int tail; // 队列尾，允许插入

    // 构造函数
    public QueueArray() {
        this(10);
    }

    public QueueArray(int initialSize) {
        if (initialSize >= 0) {
            this.maxSize = initialSize;
            data = new Object[initialSize];
            head = tail = 0;
        } else {
            throw new RuntimeException("初始化大小不能小于0：" + initialSize);
        }
    }

    // 判空
    public boolean empty() {
        return tail == head ? true : false;
    }

    // 插入
    public boolean add(E e) {
        if (tail == maxSize) {
            throw new RuntimeException("队列已满，无法插入新的元素！");
        } else {
            data[tail++] = e;
            return true;
        }
    }

    // 返回队首元素，但不删除
    public E peek() {
        if (empty()) {
            throw new RuntimeException("空队列异常！");
        } else {
            return (E) data[head];
        }
    }

    // 出队
    public E poll() {
        if (empty()) {
            throw new RuntimeException("空队列异常！");
        } else {
            E value = (E) data[head]; // 保留队列的head端的元素的值
            data[head++] = null; // 释放队列的head端的元素
            return value;
        }
    }

    // 队列长度
    public int length() {
        return tail - head;
    }
}

2、循环队列的顺序存储结构实现

 1 package dataStructures;
 2 
 3 import java.util.Arrays;
 4 
 5 public class QueueArray2<E> {
 6     public Object[] data = null;
 7     private int maxSize; // 队列容量
 8     private int tail;// 队列尾，允许插入
 9     private int head;// 队列头，允许删除
10     private int size = 0; // 队列当前长度
11 
12     public QueueArray2() {
13         this(10);
14     }
15 
16     public QueueArray2(int initialSize) {
17         if (initialSize >= 0) {
18             this.maxSize = initialSize;
19             data = new Object[initialSize];
20             head = tail = 0;
21         } else {
22             throw new RuntimeException("初始化大小不能小于0：" + initialSize);
23         }
24     }
25 
26     // 判空
27     public boolean empty() {
28         return size == 0;
29     }
30 
31     // 插入
32     public boolean add(E e) {
33         if (size == maxSize) {
34             throw new RuntimeException("队列已满，无法插入新的元素！");
35         } else {
36             data[tail] = e;
37             tail = (tail + 1) % maxSize;
38             size++;
39             return true;
40         }
41     }
42 
43     // 返回队首元素，但不删除
44     public E peek() {
45         if (empty()) {
46             throw new RuntimeException("空队列异常！");
47         } else {
48             return (E) data[head];
49         }
50     }
51 
52     // 出队
53     public E poll() {
54         if (empty()) {
55             throw new RuntimeException("空队列异常！");
56         } else {
57             E value = (E) data[head]; // 保留队列的head端的元素的值
58             data[head] = null; // 释放队列的head端的元素
59             head = (head + 1) % maxSize; // 队首指针加1
60             size--;
61             return value;
62         }
63     }
64 
65     // 队列长度
66     public int length() {
67         return size;
68     }
69 
70     // 清空循环队列
71     public void clear() {
72         Arrays.fill(data, null);
73         size = 0;
74         head = 0;
75         tail = 0;
76     }
77 }

3、队列的链式存储结构实现

 1 package dataStructures;
 2 
 3 public class QueueLink<E> {
 4     // 链栈的节点
 5     private class Node<E> {
 6         E e;
 7         Node<E> next;
 8 
 9         public Node() {
10         }
11 
12         public Node(E e, Node next) {
13             this.e = e;
14             this.next = next;
15         }
16     }
17 
18     private Node head;// 队列头，允许删除
19     private Node tail;// 队列尾，允许插入
20     private int size; // 队列当前长度
21 
22     public QueueLink() {
23         head = null;
24         tail = null;
25     }
26 
27     // 判空
28     public boolean empty() {
29         return size == 0;
30     }
31 
32     // 插入
33     public boolean add(E e) {
34         if (empty()) { // 如果队列为空
35             head = new Node(e, null);// 只有一个节点，head、tail都指向该节点
36             tail = head;
37         } else {
38             Node<E> newNode = new Node<E>(e, null);
39             tail.next = newNode; // 让尾节点的next指向新增的节点
40             tail = newNode; // 以新节点作为新的尾节点
41         }
42         size++;
43         return true;
44     }
45 
46     // 返回队首元素，但不删除
47     public Node<E> peek() {
48         if (empty()) {
49             throw new RuntimeException("空队列异常！");
50         } else {
51             return head;
52         }
53     }
54 
55     // 出队
56     public Node<E> poll() {
57         if (empty()) {
58             throw new RuntimeException("空队列异常！");
59         } else {
60             Node<E> temp = head; // 得到队列头元素
61             head = head.next;// 让head引用指向原队列头元素的下一个元素
62             temp.next = null; // 释放原队列头元素的next引用
63             size--;
64             return temp;
65         }
66     }
67 
68     // 队列长度
69     public int length() {
70         return size;
71     }
72 }

4、基于LinkedList实现队列结构

 1 package dataStructures;
 2 
 3 /**
 4  * 使用java.util.Queue接口,其底层关联到一个LinkedList（双端队列）实例.
 5  */
 6 import java.util.LinkedList;
 7 import java.util.Queue;
 8 
 9 public class QueueLinkedList<E> {
10     private Queue<E> queue = new LinkedList<E>();
11 
12     // 将指定的元素插入此队列（如果立即可行且不会违反容量限制），在成功时返回 true，
13     // 如果当前没有可用的空间，则抛出 IllegalStateException。
14     public boolean add(E e) {
15         return queue.add(e);
16     }
17 
18     // 获取，但是不移除此队列的头。
19     public E element() {
20         return queue.element();
21     }
22 
23     // 将指定的元素插入此队列（如果立即可行且不会违反容量限制），当使用有容量限制的队列时，
24     // 此方法通常要优于 add(E)，后者可能无法插入元素，而只是抛出一个异常。
25     public boolean offer(E e) {
26         return queue.offer(e);
27     }
28 
29     // 获取但不移除此队列的头；如果此队列为空，则返回 null
30     public E peek() {
31         return queue.peek();
32     }
33 
34     // 获取并移除此队列的头，如果此队列为空，则返回 null
35     public E poll() {
36         return queue.poll();
37     }
38 
39     // 获取并移除此队列的头
40     public E remove() {
41         return queue.remove();
42     }
43 
44     // 判空
45     public boolean empty() {
46         return queue.isEmpty();
47     }
48 }

转载：https://www.cnblogs.com/CherishFX/p/4608880.html