数据结构之链表，使用链表实现栈以及使用链表实现队列
1、结合之前实现的链表这个数据结构，如果只对链表的头部进行增加和删除，时间复杂度是O(1)的，只对链表的头部进行查询的话，时间复杂度是O(1)的。那么，满足这样的数据结构是什么呢，就是栈，栈这种数据结构是后入先出的，或者先进后出的，只对栈的一端，就是栈顶进行操作，无论是添加元素、删除元素、查询元素，都是在栈顶进行的。所以对于链表来说，可以将链表的头部当作栈顶，用链表做为栈的底层实现来实现一个栈。
创建一个栈的接口，可以使用数组的方式或者链表的方式进行实现栈的功能哦！
1 package com.stack;
2
3 /**
4 * @param <E> 使用泛型，可以接受任何数据类型的
5 */
6 public interface Stack<E> {
7
8 /**
9 * 获取到栈里面的大小
10 *
11 * @return
12 */
13 public int getSize();
14
15 /**
16 * 判断栈是否为空
17 *
18 * @return
19 */
20 public boolean isEmpty();
21
22 /**
23 * 向栈中添加一个元素，即入栈
24 *
25 * @param e
26 */
27 public void push(E e);
28
29 /**
30 * 从栈中取出栈顶的元素，即出栈
31 *
32 * @return
33 */
34 public E pop();
35
36 /**
37 * 查看栈顶的元素
38 *
39 * @return
40 */
41 public E peek();
42
43 }由于之前已经使用过数组实现栈，所以这里使用的是链表实现栈的功能，具体代码，如下所示：
1 package com.linkedlist;
2
3 import com.stack.Stack;
4
5 /**
6 *
7 */
8 public class LinkedListStack<E> implements Stack<E> {
9
10 // 自己实现的LinkedList链表这种数据结构，私有的链表类对象。
11 private LinkedList<E> linkedList;
12
13 /**
14 * 构造函数，创建一个LinkedList对象
15 */
16 public LinkedListStack() {
17 linkedList = new LinkedList<>();
18 }
19
20 /**
21 * 返回链表实现的栈的大小
22 *
23 * @return
24 */
25 @Override
26 public int getSize() {
27 return linkedList.getSize();
28 }
29
30 /**
31 * 返回链表实现的栈是否为空
32 *
33 * @return
34 */
35 @Override
36 public boolean isEmpty() {
37 return linkedList.isEmpty();
38 }
39
40 /**
41 * 向链表实现的栈中添加元素，即入栈操作，将元素添加到栈的栈顶
42 *
43 * @param e
44 */
45 @Override
46 public void push(E e) {
47 // 对链表的头部进行操作，时间复杂度是O(1)
48 linkedList.addFirst(e);
49 }
50
51 /**
52 * 从链表实现的栈中删除元素，即出栈操作
53 *
54 * @return
55 */
56 @Override
57 public E pop() {
58 // 对链表的头部取出元素操作，时间复杂度是O(1)
59 return linkedList.removeFirst();
60 }
61
62 /**
63 * 查看栈顶的元素
64 *
65 * @return
66 */
67 @Override
68 public E peek() {
69 // 对链表的头部查看元素操作，时间复杂度是O(1)
70 return linkedList.getFirst();
71 }
72
73 @Override
74 public String toString() {
75 StringBuilder stringBuilder = new StringBuilder();
76 // 链表的左侧是栈顶哦！
77 stringBuilder.append("Stack：top ");
78 stringBuilder.append(linkedList);
79 return stringBuilder.toString();
80 }
81
82 public static void main(String[] args) {
83 LinkedListStack<Integer> linkedListStack = new LinkedListStack<>();
84 for (int i = 0; i < 10; i++) {
85 // 入栈操作
86 linkedListStack.push(i);
87 System.out.println(linkedListStack.toString());
88 }
89
90 // 出栈操作
91 linkedListStack.pop();
92 System.out.println("出栈操作: " + linkedListStack.toString());
93
94 // 获取到栈的大小
95 int size = linkedListStack.getSize();
96 System.out.println("获取到栈的大小: " + size);
97
98 // 获取到栈顶的元素内容
99 Integer peek = linkedListStack.peek();
100 System.out.println("获取到栈顶的元素内容: " + peek);
101 }
102
103 }2、数组栈和链表栈的复杂度都是一致的，都是O(1)的。即使运行时间略有区别。对数组栈的性能和链表栈的性能进行对比分析。
1 package com.main;
2
3 import com.linkedlist.LinkedListStack;
4 import com.queue.ArrayQueue;
5 import com.queue.LoopQueue;
6 import com.queue.Queue;
7 import com.stack.ArrayStack;
8 import com.stack.Stack;
9
10 import java.util.Random;
11
12 /**
13 *
14 */
15 public class Main {
16
17 /**
18 * 测试使用stack运行opCount个push和pop操作所需要的时间，单位：秒
19 * <p>
20 * 数组栈和链表栈的复杂度都是一致的，都是O(1)的。即使运行时间略有区别。
21 *
22 * @param queue
23 * @param opCount
24 * @return
25 */
26 public static double queuePerforms(Stack<Integer> queue, int opCount) {
27 // 开始时间
28 long startTime = System.nanoTime();
29
30 Random random = new Random();
31 // 入队操作
32 for (int i = 0; i < opCount; i++) {
33 queue.push(random.nextInt(Integer.MAX_VALUE));
34 }
35
36 // 出队操作
37 for (int i = 0; i < opCount; i++) {
38 queue.pop();
39 }
40
41 // 结束时间
42 long endTime = System.nanoTime();
43
44 // 秒与纳秒之前差九位数
45 return (endTime - startTime) / 1000000000.0;
46 }
47
48 public static void main(String[] args) {
49 int opCount = 100000;// 十万次
50
51 // 数组栈的性能
52 // 对于数组栈来说，需要重新分配静态数组，将原来的数组拷贝到新的数组中，即扩容操作。
53 ArrayStack<Integer> arrayStack = new ArrayStack<>();
54 double time1 = queuePerforms(arrayStack, opCount);
55 System.out.println("ArrayStack, time: " + time1 + " s");
56
57
58 // 链表栈的性能
59 // 其实这个时间比较复杂，因为LinkedListStack中包含更多的new操作。
60 LinkedListStack<Integer> linkedListStack = new LinkedListStack<>();
61 double time2 = queuePerforms(linkedListStack, opCount);
62 System.out.println("LinkedListStack, time: " + time2 + " s");
63 }
64
65 }3、带有尾指针的链表，使用链表实现队列。
1）、结合之前实现的链表这个数据结构，如果只对链表的头部进行增加和删除，时间复杂度是O(1)的，只对链表的头部进行查询的话，时间复杂度是O(1)的。如果对链表的尾部进行操作的话，无论是添加元素还是删除元素，时间复杂度都是O(n)的。对于队列这种数据结构来说，需要在这种线性结构中的一端插入元素，在另外一端删除元素，所以我们势必会在这种线性结构的两端同时操作，那么此时就会有一端的操作，它的复杂度是O(n)级别的。 2）、对于使用数组来实现队列的时候，也遇到类似问题，需要改进数组实现队列的方式，所以产生了循环队列，对于链表也存在同样的问题，我们不能直接使用之前的链表结构，需要引入改进该链表，由此引入了尾指针。改进思路，对于链表来说，在链表的头部的位置，不管插入元素还是删除元素，都十分容易，因为对于链表来说，有head这个变量来帮助我们标记链表的头部在哪里，拥有了这个标记以后，在链表的头部进行添加元素还是删除元素都是容易的。 3）、所以在链表的尾部，再创建一个Node类型的变量tail，来标记链表的尾部在哪里，所以，如果知道了链表的尾部，再添加一个元素会是非常容易的。这就相当于给链表添加元素，在链表索引为size的位置添加一个元素，换句话说，tail这个位置的节点就是我们待添加元素的位置，也就是最后一个位置之前的那个节点，相应的，我们在tail这个节点的后面添加一个节点是非常容易的。 4）、所以，对于链表来说，在head端和tail端添加节点都是非常容易的。
3.1、考虑，如何在tail端删除一个节点。链表新增尾指针，使用链表实现队列。
1）、如何在tail端删除一个节点，注意的是，链表的结构不是对称的，之前的链表结构中，想要删除一个元素，需要找到待删除元素的前一个位置的节点，如果现在想要删除tail这个位置所指向的节点，就要找到tail这个位置它前一个位置的节点，如何找到tail这个节点之前的那个位置节点呢，对于此时的链表来说，只有一个next指向后一个节点，所以此时是无法使用O(1)的复杂度直接找到tail这个节点它之前那个位置的节点的，此时，还是需要从head头部节点循环遍历，这样时间复杂度变成了O(n)，所以，即使在链表的尾部标记了tail，我们还是无法使用O(1)的复杂度直接删除tail这个位置的节点的。即从tail删除元素不容易的。 2）、但是，对于，在链表的头部head这个节点删除或者新增一个节点非常容易的，所以根据此分析，改进链表，即在链表的尾部添加一个Node节点tail，来标记整个链表中尾节点处在什么位置，然后在在链表的头部head这个节点删除或者新增一个节点非常容易的，对于tail端，我们只是添加元素容易，删除元素不容易。 3）、对于队列中，队首和队尾的选择，由于tail端删除元素不容易，只能从tail端插入元素，从head端删除元素，所以，删除元素的这一端在队列中称为队首，负责出队，添加元素的这一端称为队尾，负责入队。 4）、注意，由于对这个链表的操作全都在链表的一侧完成，也就是head端或者tail端完成，就不使用虚拟头节点了，因为不牵扯到对链表的中间的一个元素进行插入或者删除这样的操作，所以也就没有必要统一对链表的中间元素进行操作和对链表两侧的元素进行操作，他们之间可能带来的逻辑不统一的问题。 如果添加了tail这个Node节点以后，还需要注意一个情况，就是此时，当我们的链表为空的时候。head和tail都将指向空，由于没有虚拟头节点，要注意链表为空的情况。
链表新增tail节点，结合head头部节点的链表实现队列的功能。
1 package com.queue;
2
3 /**
4 * 使用链表创建队列
5 *
6 * @param <E>
7 */
8 public class LinkedListQueue<E> implements Queue<E> {
9
10 // 由于LinkedListQueue也是一个链表，所以需要链表的节点Node
11 // 链表是由一个一个节点组成
12 private class Node {
13 // 设置公有的，可以让外部类进行修改和设置值
14 public E e;// 成员变量e存放元素
15 public Node next;// 成员变量next指向下一个节点，指向Node的一个引用
16
17 /**
18 * 含参构造函数
19 *
20 * @param e
21 * @param next
22 */
23 public Node(E e, Node next) {
24 this.e = e;
25 this.next = next;
26 }
27
28 /**
29 * 无参构造函数
30 */
31 public Node() {
32 this(null, null);
33 }
34
35 /**
36 * 如果用户只传了e，那么可以调用含参构造函数，将next指定为null
37 *
38 * @param e
39 */
40 public Node(E e) {
41 this(e, null);
42 }
43
44 @Override
45 public String toString() {
46 return e.toString();
47 }
48 }
49
50
51 // 创建头节点和尾节点
52 private Node head;// 链表的头节点
53 private Node tail;// 链表的尾节点
54 private int size;// 链表的长度大小
55
56 /**
57 * 无参构造函数，和默认的构造函数做的是一样的。
58 * 链表初始化的时候head、tail都是空
59 */
60 public LinkedListQueue() {
61 head = null;
62 tail = null;
63 size = 0;
64 }
65
66 /**
67 * 使用链表实现的队列的，入队操作。
68 * <p>
69 * 链表实现的入队操作，是从链表的尾部进行。
70 * <p>
71 * 此方法是O(1)级别的复杂度。
72 *
73 * @param e
74 */
75 @Override
76 public void enqueue(E e) {
77 // 首先判断链表的尾部是否为空，如果tail为空，说明head也是空的，此时链表是空的
78 // 但凡链表包含元素，tail指向的是尾节点位置，就不会是空的。
79 if (tail == null) {
80 // 如果尾部节点是空，就直接在尾部插入一个系节点，此节点存储e元素
81 tail = new Node(e);
82 // 此时，莫要忘记维护head，此时head==tail
83 head = tail;
84 } else {
85 // 如果tail指向的位置不为空，那么在tail的next位置，创建新节点，存储元素e
86 tail.next = new Node(e);
87 // 然后维护tail的位置即可，让tail指向链表的最后一个位置的元素。
88 // 新的tail等于刚刚创建的tail的next。此时就不用维护head头部节点的位置了。
89 tail = tail.next;
90 }
91
92 // 最后，维护size的大小即可
93 size++;
94 }
95
96 /**
97 * 使用链表实现的队列的，出队操作。
98 * <p>
99 * 此方法是O(1)级别的复杂度。不需要遍历队列所以元素
100 *
101 * @return
102 */
103 @Override
104 public E dequeue() {
105 // 出队过程，首先，需要判断队列能否可以出队一个元素。
106 // 换句话说，如果此时队列为空的时候，就无法出队，抛出异常即可。
107 if (isEmpty()) {
108 throw new IllegalArgumentException("Cannot dequeue from an empty queue.");
109 }
110
111 // 如果有元素，就进行出队操作。
112 // 此操作类似于从链表的头部删除一个元素。
113 // 首先，returnNode出队元素所在的节点应该就是head这个位置所指向的节点。
114 Node returnNode = head;
115 // 让head指向原来head的next下一个位置节点。新的head跳过returnNode，直接指向head.next。
116 head = head.next;
117
118 // 这样一来returnNode的next其实相当于指向了head这个节点。
119 // 此时让returnNode从链表中断开，需要操作的是returnNode.next = null;
120 returnNode.next = null;
121
122 // 此时，需要注意，当指向了head = head.next的时候，也就是我们的那个head这个节点指向了原来
123 // 我们头节点的下一个节点，但是这个下一个节点可能是空的，也即是说，我们的链表只有一个元素。
124 // 我们把returnNode出队之后，我们的链表就为空了。此时需要判断head是否为空，然后维护tail这个节点。
125 if (head == null) {
126 // 此时需要判断head是否为空，然后维护tail这个节点。让tail节点为空。
127 // 例如，只有一个元素，head和tail都指向这个元素，如果经过上面的出队操作之后，
128 // 如果此时tail还指向此元素，就错了，所以需要维护tail的节点为空即可。
129 tail = null;
130 }
131
132 // 维护size的大小
133 size--;
134
135 // 返回出队的节点元素
136 return returnNode.e;
137 }
138
139 /**
140 * 使用链表实现的队列的，获取到队首元素。
141 *
142 * @return
143 */
144 @Override
145 public E getFront() {
146 // 获取队首元素
147 if (isEmpty()) {
148 throw new IllegalArgumentException("Queue is empty.");
149 }
150
151 // 否则返回队首的元素即可
152 return head.e;
153 }
154
155 /**
156 * 返回链表的大小
157 *
158 * @return
159 */
160 @Override
161 public int getSize() {
162 return size;
163 }
164
165 /**
166 * 判断链表是否为空
167 *
168 * @return
169 */
170 @Override
171 public boolean isEmpty() {
172 return size == 0;
173 }
174
175 @Override
176 public String toString() {
177 StringBuilder stringBuilder = new StringBuilder();
178 // 队首，负责出队
179 stringBuilder.append("Queue ： front ");
180 // 使用while循环进行循环
181 Node current = head;
182 while (current != null) {
183 stringBuilder.append(current + "->");
184 current = current.next;
185 }
186 // 队尾，负责入队
187 stringBuilder.append("NULL tail ");
188 return stringBuilder.toString();
189 }
190
191 public static void main(String[] args) {
192 // 基于链表实现的队列
193 LinkedListQueue<Integer> linkedListQueue = new LinkedListQueue<>();
194 // 队列的入队操作
195 for (int i = 0; i < 10; i++) {
196 linkedListQueue.enqueue(i);
197 // System.out.println("队列的入队操作: " + linkedListQueue);
198 System.out.println(linkedListQueue);
199
200 // if (i % 3 == 2) {
201 // linkedListQueue.dequeue();
202 // System.out.println(linkedListQueue);
203 // }
204 }
205
206 // 队列的出队操作
207 linkedListQueue.dequeue();
208 System.out.println("队列的出队操作: " + linkedListQueue.toString());
209
210 // 获取到队首的元素
211 Integer front = linkedListQueue.getFront();
212 System.out.println("获取到队首的元素: " + front);
213 }
214
215 }4、数组队列，循环数组队列，链表队列的性能测试比较。如下所示：
1 package com.queue;
2
3 import java.util.Random;
4
5 /**
6 *
7 */
8 public class Main {
9
10 /**
11 * 测试使用queue运行opCount个enqueue和dequeue操作所需要的时间，单位：秒
12 *
13 * @param queue
14 * @param opCount
15 * @return
16 */
17 public static double queuePerforms(Queue<Integer> queue, int opCount) {
18 // 开始时间
19 long startTime = System.nanoTime();
20
21 Random random = new Random();
22 // 入队操作
23 for (int i = 0; i < opCount; i++) {
24 queue.enqueue(random.nextInt(Integer.MAX_VALUE));
25 }
26
27 // 出队操作
28 for (int i = 0; i < opCount; i++) {
29 queue.dequeue();
30 }
31
32 // 结束时间
33 long endTime = System.nanoTime();
34
35 // 秒与纳秒之前差九位数
36 return (endTime - startTime) / 1000000000.0;
37 }
38
39 public static void main(String[] args) {
40 int opCount = 100000;// 十万次
41
42 // 数组队列的性能
43 // 影响数组队列性能的是出队操作，因为每一个元素都要进行前移操作
44 // 时间复杂度是O(n*n)。
45 ArrayQueue<Integer> arrayQueue = new ArrayQueue<>();
46 double time1 = queuePerforms(arrayQueue, opCount);
47 System.out.println("ArrayQueue, time: " + time1 + " s");
48
49
50 // 循环队列的性能
51 // 时间复杂度是O(1)。
52 LoopQueue<Integer> loopQueue = new LoopQueue<>();
53 double time2 = queuePerforms(loopQueue, opCount);
54 System.out.println("LoopQueue, time: " + time2 + " s");
55
56
57 // 链表队列的性能。循环队列和链表队列的时间复杂度是一样的。
58 // 时间复杂度是O(1)。
59 LinkedListQueue<Integer> linkedListQueue = new LinkedListQueue<>();
60 double time3 = queuePerforms(linkedListQueue, opCount);
61 System.out.println("LinkedListQueue, time: " + time3 + " s");
62 }
63
64 }本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2020-03-07 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读