Java数据结构之线性表、栈和队列
线性表
线性表详解：数据结构线性表10分钟入门（建议笔记结合这个教程一起看）
线性表，全名为线性存储结构。将具有一对一关系的数据线性地存储到物理空间中，这种存储结构就称为线性存储结构（简称线性表）。
线性表常用术语：
数据结构中，一组数据中的每个个体被称为“数据元素”（简称“元素”）。
另外，对于具有“一对一”逻辑关系的数据，我们一直在用“某一元素的左侧（前边）或右侧（后边）”这样不专业的词，其实线性表中有更准确的术语：
- 某一元素的左侧相邻元素称为“直接前驱”，位于此元素左侧的所有元素都统称为“前驱元素”
- 某一元素的右侧相邻元素称为“直接后继”，位于此元素右侧的所有元素都统称为“后继元素”
线性表又分为顺序表和链表：
- 将数据依次存储在连续的整块物理空间中，这种存储结构称为顺序存储结构（简称顺序表）
- 数据分散的存储在物理空间中，通过一根线保存着它们之间的逻辑关系，这种存储结构称为链式存储结构（简称链表）
Java Collection API中的表
在类库中，Java 语言包含有一些普通数据结构的实现，该语言的这一部分通常叫作Collections API。表ADT是在Collections API中实现的数据结构之一。我们会在后面的笔记中看到其他一些数据结构。
Collection接口：
Collections API位于java.util包中。集合( collection)的概念在Collection接口中得到抽象，它存储一组类型相同的对象。在Collection接口中的许多方法所做的工作由它们的英文名称可以看出：如size()返回集合中的项数； isEmpty()返回true当且仅当集合的大小为0。如果x在集合中，则contains()返回true。注意，这个接口并不规定集合如何决定x是否属于该集合一，这要由实现该Collection接口的具体的类来确定。add和remove从集合中添加和删除x,如果操作成功则返回true,如果因某个看似有理(非异常)的原因失败则返false。例如，如果要删除的项不在集合中，则remove可能失败，而如果特定的集合不允许重复，那么当企图插人一项重复项时，add操作就可能失败。（具体可查看jdk1.8文档）
Collection接口扩展了Iterable接口。实现Iterable接口的那些类可以拥有增强的for循环，该循环施于这些类之上以观察它们所有的项。
Iterator接口：
实现Iterable接口的集合必须提供一个称为iterator的方法，该方法返回一个Iterator类型的对象。该Iterator是一个在java.util包中定义的接口。（next() 返回迭代中的下一个元素，hasNext() 返回 true如果迭代具有更多的元素，即可以继续迭代）
重要的一个基本法则：当直接使用Iterator(而不是通过一个增强的for循环间接使用)时，如果对正在被迭代的集合进行结构上的改变(即对该集合使用add、remove或clear方法)，那么迭代器就不再合法(并且在其后使用该迭代器时将会有ConcurrentModi ficat ionException异常被抛出)。
List接口、ArrayList类和LinkedList类
List接口一共有三个实现类，分别是ArrayList、Vector和LinkedList。List用于存放多个元素，能够维护元素的次序，并且允许元素的重复。3个具体实现类的相关区别如下：
- ArrayList是最常用的List实现类，内部是通过数组实现的（顺序表），它允许对元素进行快速随机访问。数组的缺点是每个元素之间不能有间隔，当数组大小不满足时需要增加存储能力，就要将已经有数组的数据复制到新的存储空间中。当从ArrayList的中间位置插入或者删除元素时，需要对数组进行复制、移动、代价比较高。因此，它适合随机查找和遍历，不适合插入和删除。
- Vector与ArrayList一样，也是通过数组实现的，不同的是它支持线程的同步，即某一时刻只有一个线程能够写Vector，避免多线程同时写而引起的不一致性，但实现同步需要很高的花费，因此，访问它比访问ArrayList慢。
- LinkedList是用链表结构存储数据的（链表），很适合数据的动态插入和删除，随机访问和遍历速度比较慢。另外，它还提供了List接口中没有定义的方法，专门用于操作表头和表尾元素，可以当作堆栈、队列和双向队列使用。
List接口继承了Collection接口，具体的一些方法可查看jdk1.8文档。
List ADT有两种流行的实现方式。ArrayList类提供了List ADT的一种可增长数组的实现（顺序表）。使用ArrayList的优点在于，对get和set的调用花费常数时间。其缺点是新项的插人和现有项的删除代价昂贵，除非变动是在ArrayList的末端进行。LinkedList类则提供了List ADT的双链表实现（链表）。使用LinkedList的优点在于，新项的插人和现有项的删除均开销很小，这里假设变动项的位置是已知的。这意味着，在表的前端进行添加和删除都是常数时间的操作，由此LinkedList 更提供了方法addFirst和removeFirst、 addLast 和removeLast、以及getFirst和getLast等以有效地添加、删除和访问表两端的项。使用LinkedList的缺点是它不容易作索引，因此对get的调用是昂贵的，除非调用非常接近表的端点(如果对get的调用是对接近表后部的项进行，那么搜索的进行可以从表的后部开始)。
ArrayList的实现
ArrayList的实现，即顺序表的实现。这里我们将类命名为MyArrayList，用于区分ArrayList。
直接上代码：
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
| public class MyArrayList<E>{
private static final int DEFAULT_CAPACITY = 10;
private int theSize;
private E [ ] theItems;
public MyArrayList() {
doClear();
}
public void clear( )
{
doClear( );
}
public int size(){
return theSize;
}
public boolean isEmpty(){
return size()==0;
}
public E get(int index){
if( index < 0 || index >= size( ) )
throw new ArrayIndexOutOfBoundsException( "Index " + index + "; size " + size( ) );
return theItems[index];
}
public E set(int index, E newValue){
if( index < 0 || index >= size( ) )
throw new ArrayIndexOutOfBoundsException( "Index " + index + "; size " + size( ) );
E oldValue = theItems[index];
theItems[index] = newValue;
return oldValue;
}
public void add(int index, E value) {
if (theItems.length==size()){
ensureCapacity(size()*2+1);
}
for (int i = theSize; i > index; i--) {
theItems[i] = theItems[i-1];
}
theItems[index] = value;
theSize++;
}
public boolean add(E value){
add(size(), value);
return true;
}
public E remove(int index){
E removedValue = theItems[index];
for (int i = index; i < size() - 1; i++) {
theItems[i] = theItems[i+1];
}
theSize--;
return removedValue;
}
@SuppressWarnings("unchecked")
public void ensureCapacity(int newCapacity) {
if( newCapacity < theSize )
return;
E[] old = theItems;
theItems = (E[]) new Object[newCapacity];
for (int i = 0; i < size(); i++) {
theItems[i] = old[i];
}
}
@Override
public String toString() {
StringBuilder stringBuilder = new StringBuilder("[ ");
for (int i = 0; i < size(); i++) {
stringBuilder.append(theItems[i]+" ");
}
stringBuilder.append("]");
return new String(stringBuilder);
}
private void doClear() {
theSize = 0;
ensureCapacity(DEFAULT_CAPACITY);
}
}
|
LinkedList的实现
链表（链式存储结构）及创建
Java实现单向链表基本功能
LinkedList的实现，即链表的实现。这里我们将类命名为MyLinkedList，用于区分LinkedList。这里我们先写一个单链表。
链表又分为几类：
- 单向链表：一个节点指向下一个节点
- 双向链表：一个节点有两个指针域（指向前一个和下一个）
- 循环链表：能通过任何一个节点找到其他所有的节点，将两种（单/双）链表的最后一个节点指向第一个节点从而实现循环。
操作链表时要时刻记住：节点中指针域指向的就是下一个节点
链表中的节点又细分为：头节点，首元节点和其他节点
- 头节点：其实就是一个不存任何数据的空节点，通常作为链表的第一个节点。对于链表来说，头节点不是必须的，它的作用只是为了方便解决某些实际问题
- 首元节点：由于头节点（也就是空节点）的缘故，链表中称第一个存有数据的节点为首元节点。首元节点只是对链表中第一个存有数据节点的一个称谓，没有实际意义
- 其他节点：链表中其他的节点
相关算法都在代码注释中，直接上代码：
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
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
| import java.util.HashSet;
import java.util.Set;
public class MyLinkedList<E> {
private Node head = new Node();
private class Node {
public E data;
public Node next;
public Node() {
this.data = null;
this.next = null;
}
public Node(E data) {
this.data = data;
}
public Node(E data, Node next) {
this.data = data;
this.next = next;
}
}
public void addData(E value){
Node addNode = new Node(value);
Node temp = head;
while (temp.next != null){
temp = temp.next;
}
temp.next = addNode;
}
public void insertData(int index, E value){
if (index<1 || index>length()+1){
System.out.println("插入位置不合法！");
return;
}
Node temp = head.next;
int current = 1;
Node insertNode = new Node(value);
while (temp.next != null){
if (current == index){
insertNode.next = temp.next;
temp.next = insertNode;
return;
}
current++;
temp = temp.next;
}
}
public int length(){
int length = 0;
Node temp = head.next;
while (temp!=null){
temp = temp.next;
length++;
}
return length;
}
public void deleteByIndex(int index){
if (index<1 || index>length()+1){
System.out.println("插入位置不合法！");
return;
}
Node temp = head;
int current = 1;
while (temp.next!=null){
if (current == index){
Node deleteNode = temp.next;
temp.next = deleteNode.next;
return;
}
current++;
temp = temp.next;
}
}
public E findData(int k){
if (k<1 || k>length()){
return null;
}
Node p1 = head.next;
Node p2 = head.next;
for (int i = 0; i < k-1; i++) {
p2 = p2.next;
}
while (p2.next != null){
p1 = p1.next;
p2 = p2.next;
}
return p1.data;
}
public void deleteDuplicates(){
Set<E> hashSet = new HashSet<>();
Node temp = head.next;
if (temp==null){
return;
}
hashSet.add(temp.data);
while (temp != null){
while (temp.next!=null && hashSet.contains(temp.next.data)){
temp.next = temp.next.next;
}
if (temp.next != null){
hashSet.add(temp.next.data);
}
temp = temp.next;
}
}
public E searchMid(){
Node p1 = head.next;
Node p2 = head.next;
while (p2!=null && p2.next!=null && p2.next.next!=null){
p1 = p1.next;
p2 = p2.next.next;
}
return p1.data;
}
public void printListReversely(){
printListReversely(head);
}
public void printListReversely(Node node){
if (node!=null){
printListReversely(node.next);
if (node.data!=null){
System.out.print(node.data+" ");
}
}
}
public void reverseList(){
head.next = reverseList(head.next);
}
public Node reverseList(Node node){
Node pre = null;
Node cur = node;
while (cur!=null){
Node next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}
@Override
public String toString() {
StringBuilder stringBuilder = new StringBuilder("[ ");
Node temp = head.next;
while (temp!=null){
if (temp.data!=null){
stringBuilder.append(temp.data+" ");
}
temp = temp.next;
}
stringBuilder.append("]");
return new String(stringBuilder);
}
}
|
反转整个链表的实现逻辑光看代码可能有点麻烦，这里贴一下比较潦草的草稿：
循环链表实现约瑟夫环
约瑟夫环问题，是一个经典的循环链表问题，题意是：已知 n 个人（分别用编号 1，2，3，…，n 表示）围坐在一张圆桌周围，从编号为 k 的人开始顺时针报数，数到 m 的那个人出列；他的下一个人又从 1 开始，还是顺时针开始报数，数到 m 的那个人又出列；依次重复下去，直到圆桌上剩余一个人。
代码如下：
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
| import java.util.Scanner;
public class Main {
private static class Node{
int value;
Node next;
public Node(int value) {
this.value = value;
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.print("请输入 n 个人围坐在一张圆桌周围的n值：");
int n = scanner.nextInt();
System.out.print("请输入数到m的那个人出列的m值：");
int m = scanner.nextInt();
System.out.print("请输入从编号为k的人开始顺时针报数的k值：");
int k = scanner.nextInt();
Node head = new Node(1);
Node temp = head;
for (int i = 2; i <= n; i++) {
temp.next = new Node(i);
temp = temp.next;
}
temp.next = head;
for (int i = 1; i < k; i++) {
temp = temp.next;
}
while (temp != temp.next){
for (int i = 1; i < m; i++) {
temp = temp.next;
}
System.out.println("出列人的编号为："+temp.next.value);
temp.next = temp.next.next;
}
System.out.println("最后胜利的编号为："+temp.value);
}
}
|
栈
什么是栈，栈及其特点和应用详解
栈是重要的数据结构，从数据结构角度看，栈也是线性表，其特殊性在栈的基本操作是线性表的子集。Stack作为最基本的数据结构，在JDK代码中，也有它的实现，java.util.Stack类是继承了Vector类，来实现了栈的基本功能。
栈的特点：
- 栈只能从表的一端存取数据，另一端是封闭的
- 在栈中，无论是存数据还是取数据，都必须遵循"先进后出"的原则，即最先进栈的元素最后出栈。
基于栈结构的特点，在实际应用中，通常只会对栈执行以下两种操作：
- 向栈中添加元素，此过程被称为"进栈"（入栈或压栈）
- 从栈中提取出指定元素，此过程被称为"出栈"（或弹栈）
栈的实现
由于栈是一个表，因此任何实现表的方法都能实现栈。显然，ArrayList和LinkedList都支持操作。这里我们就只给出用ArrayList实现栈的代码了，很简单的
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
| import java.util.ArrayList;
import java.util.EmptyStackException;
public class MyStack<E> {
private ArrayList<E> myStack;
public MyStack() {
myStack = new ArrayList<E>();
}
public void push(E value){
myStack.add(value);
}
public E pop(){
if (isEmpty()){
throw new EmptyStackException();
}
return myStack.remove(myStack.size()-1);
}
private boolean isEmpty() {
return myStack.isEmpty();
}
public E peek(){
if (isEmpty()){
throw new EmptyStackException();
}
return myStack.get(myStack.size()-1);
}
public int size(){
return myStack.size();
}
}
|
Java Stack类
在JDK代码中，java.util.Stack类是继承了Vector类，来实现了栈的基本功能。
Stack常用方法如下：
- boolean empty() ：测试此堆栈是否为空
- E peek() ：查看此栈顶部的对象，而不将它从栈中删除
- E pop() ：在这个栈的顶部删除对象，并返回该对象的值作为该函数的值
- E push(E item) ：将一个项目推到这个堆栈的顶部
- int search(Object o) ：返回理想对象o距离栈顶的距离（距离栈顶最近的距离记为1），若对象o在栈中不存在，则返回-1（可以自己运行一下就很好理解了）
单调栈
在后面的刷题中遇到需要用单调栈来解决的题目，这里补充一下。
OI-WiKi单调栈
单调栈解题模板秒杀八道题
单调栈技巧总结
深入浅出搞通单调队列单调栈
顾名思义，单调栈即满足单调性的栈结构。与单调队列相比，其只在一端进行进出。
单调栈的重点分为单调和栈：
单调栈和单调队列这两种数据结构理解起来挺清楚的，主要还是要结合题目来做，看看具体是怎么用代码来实现单调栈和单调队列的。
队列
什么是队列，队列及其应用（超详细）
队列，和栈一样，也是一种对数据的"存"和"取"有严格要求的线性存储结构。与栈结构不同的是，队列的两端都"开口"，要求数据只能从一端进，从另一端出。不仅如此，队列中数据的进出要遵循 “先进先出” 的原则，即最先进队列的数据元素，同样要最先出队列。
Queue作为最基本的数据结构，在JDK代码中，也有它的实现，java.util.Queue类来实现了队列的基本功能。
队列的实现
队列存储结构的实现有以下两种方式：顺序队列（在顺序表的基础上实现的队列结构）和链队列（在链表的基础上实现的队列结构）
这里我们用链表实现队列，代码如下：
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
| import java.util.NoSuchElementException;
public class MyQueen<E> {
private Node front;
private Node rear;
private int size;
class Node{
E data;
Node next;
public Node() {
}
public Node(E data) {
this.data = data;
}
public Node(E data, Node next) {
this.data = data;
this.next = next;
}
}
public MyQueen() {
front = rear = new Node();
}
public boolean add(E data){
Node addNode = new Node(data);
rear.next = addNode;
rear = rear.next;
size++;
return true;
}
public E remove(){
if (isEmpty()){
throw new NoSuchElementException("队列为空！");
}
Node removeNode = front.next;
E removeData = removeNode.data;
front.next = removeNode.next;
removeNode = null;
size--;
if (isEmpty()){
front = rear;
}
return removeData;
}
public E peekFront(){
if (isEmpty()){
throw new NoSuchElementException("队列为空！");
}
return front.next.data;
}
public E peekRear(){
if (isEmpty()){
throw new NoSuchElementException("队列为空！");
}
return rear.data;
}
public int size(){
return size;
}
private boolean isEmpty() {
return size == 0;
}
@Override
public String toString() {
if (isEmpty()) {
return "[]";
}
StringBuilder builder = new StringBuilder();
Node cur = front.next;
builder.append("[");
while (cur != null) {
builder.append(cur.data).append(", ");
cur = cur.next;
}
builder.replace(builder.length() - 2, builder.length(), "]");
return builder.toString();
}
}
|
Java Queue接口
在JDK代码中，也有它的实现，java.util.Queue类来实现了队列的基本功能。
Queue接口常用方法如下：
- boolean add(E e) ：向队列中插入元素，若队列已满，则返回false并抛出异常IllegalStateException
- E remove() ：删除此队列的头并返回被删除的值
- E peek() ：检索但不删除这个队列头，如果队列为空则返回null
JDK QUEUE队列
Queue接口的所有已知实现类有： AbstractQueue， ArrayBlockingQueue， ArrayDeque， ConcurrentLinkedDeque， ConcurrentLinkedQueue， DelayQueue， LinkedBlockingDeque， LinkedBlockingQueue， LinkedList（LinkedList就可以作为队列使用）， LinkedTransferQueue， PriorityBlockingQueue， PriorityQueue， SynchronousQueue 。
其中比较常用的非阻塞队列有：ArrayDeque（数组双端队列），PriorityQueue（优先队列）
比较常用的阻塞队列有：
- ArrayBlockingQueue, （基于数组的并发阻塞队列） 底层是数组，有界队列，如果我们要使用生产者-消费者模式，这是非常好的选择
- LinkedBlockingQueue, （基于链表的FIFO阻塞队列） 底层是链表，可以当做无界和有界队列来使用，所以大家不要以为它就是无界队列
- PriorityBlockingQueue, （带优先级的无界阻塞队列） 是无界队列，基于数组，数据结构为二叉堆，数组第一个也是树的根节点总是最小值
单调队列
在后面的刷题中遇到需要用单调队列来解决的题目，这里补充一下。
认识单调队列
深入浅出搞通单调队列单调栈
OI-Wiki 单调队列
顾名思义，单调队列的重点分为单调和队列：
关于单调队列概念的介绍就到这里，具体的可以去结合题目看看。比如说LeetCode 239. 滑动窗口最大值
在Java中，由于单调队列支持两端的删除操作，所以用Deque实现。Deque不考虑并发性问题，有两种实现方式(ArrayDeque和LinkedList)。
