队列-线性表-数据结构和算法(Java)

1 队列简介

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。

队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队。因为队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出（FIFO—first in first out）线性表。 [1]

2 队列实现

这么我使用基于链表的方式实现最基础的队列，如果想要看基于数组的实现方式，可自行查阅相关文档或者留言。

2.1 API

• 队列接口：public interface Queue extends Iterable

• 基于链表的队列实现：public class LinkQueue implements Queue

  • 成员变量

  • 访问控制和类型	名称	描述
    private Node	first	队头
    private Node	last	队尾
    private int	size	队列元素个数

  • 成员方法API其他方法和Queue接口相同

2.2 代码实现

public class LinkQueue<E> implements Queue<E>, Serializable {

    /**
     * 队头
     */
    private Node<E> first;

    /**
     * 队尾
     */
    private Node<E> last;

    /**
     * 队列元素个数
     */
    private int size;

    public LinkQueue() {
    }

    /**
     * 元素入队(队尾）
     * @param e 元素
     */
    @Override
    public void offer(E e) {
        Node<E> l = last;
        last = new Node<>(e, null);
        if (first == null) {
            first = last;
        } else {
            l.next = last;
        }
        size++;
    }

    /**
     * 查看队头元素
     * @return  队头元素
     */
    @Override
    public E peek() {
        if (first == null) {
            throw new NoSuchElementException("Queue underflow");
        }
        return first.item;
    }

    /**
     * 队头元素出队
     * @return  队头元素
     */
    @Override
    public E poll() {
        if (first == null) {
            throw new NoSuchElementException("Queue underflow");
        }
        Node<E> f = first;
        E item = f.item;
        first = f.next;
        f.item = null;
        if (first == null) {
            last = null;
        } else {
            f.next = null;
        }
        size--;
        return item;
    }

    /**
     * 判断队列是否为空
     * @return {@code true} 队列为空时，否则
     *         {@code false}
     */
    @Override
    public boolean isEmpty() {
        return first == null;
    }

    /**
     * 返回队列元素个数
     * @return  队列元素个数
     */
    @Override
    public int size() {
        return size;
    }

    /**
     * 节点类
     * @param    泛型
     */
    private static class Node<E> {
        E item;
        Node<E> next;

        public Node(E item, Node<E> next) {
            this.item = item;
            this.next = next;
        }
    }

    @Override
    public Iterator<E> iterator()  {
        return new LinkedIterator(first);
    }

    @Override
    public String toString() {
        Iterator<E> it = iterator();
        if (! it.hasNext()) {
            return "[]";
        }

        StringBuilder sb = new StringBuilder();
        sb.append('[');
        for (;;) {
            E e = it.next();
            sb.append(e);
            if (! it.hasNext()) {
                return sb.append(']').toString();
            }
            sb.append(',').append(' ');
        }
    }

    /**
     * 迭代器
     */
    private class LinkedIterator implements Iterator<E> {
        private Node<E> current;

        public LinkedIterator(Node<E> first) {
            current = first;
        }

        @Override
        public boolean hasNext()  { return current != null;                     }

        /**
         * 基于队列只在队头删除元素的特点，这里不实现
         */
        @Override
        public void remove()      { throw new UnsupportedOperationException();  }

        @Override
        public E next() {
            if (!hasNext()) {
                throw new NoSuchElementException();
            }
            E item = current.item;
            current = current.next;
            return item;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157

3 后记

​ 如果小伙伴什么问题或者指教，欢迎交流。

❓QQ:806797785

⭐️源代码仓库地址：https://gitee.com/gaogzhen/algorithm

参考：

[1]百度百科.队列[EB/OL].2018-08-15/2022-11-02.

[2][美]Robert Sedgewich,[美]Kevin Wayne著;谢路云译.算法：第4版[M].北京：人民邮电出版社，2012.10