ShiYu

# 第3节 一些基础的数据结构

# 单向链表

单向链表节点结构（可以实现成范型）

public class Node {
    public int value;
    public Node next;
    public Node(int data) {
        value = data;
    }
}
1
2
3
4
5
6
7

# 双向链表

双向链表节点结构

public class DoubleNode {
    public int value;
    public DoubleNode last;
    public DoubleNode next;

    public DoubleNode(int data) {
        value = data;
    }
}
1
2
3
4
5
6
7
8
9

# 单向链表和双向链表最简单的练习

链表相关的问题几乎都是coding问题

  • 单链表和双链表如何反转

    package class03;

import java.util.ArrayList;
import java.util.List;

/**
 * 	单链表和双链表反转
 * @author yangyanchao
 *
 */
public class Code01_ReverseList {

	public static class Node {
		public int value;
		public Node next;

		public Node(int data) {
			value = data;
		}
	}

	public static class DoubleNode {
		public int value;
		public DoubleNode last;
		public DoubleNode next;

		public DoubleNode(int data) {
			value = data;
		}
	}
    
    //  head
	//   a    ->   b    ->  c  ->  null
	//   c    ->   b    ->  a  ->  null
	/**
	 * 	传入头节点 反转单向链表结构并返回新的头节点
	 * @param head
	 * @return
	 */
	public static Node<Integer> reverseLinkedList2(Node<Integer> head) {
		// 记录反转后节点的下一个节点
		Node<Integer> pre = null;
		// 记录现在的节点的下一个节点
		Node<Integer> next = null;
		while(head != null) {
			next = head.next;
			head.next = pre;
			pre = head;
			head = next;
		}
		
		return pre;
	}
	
	/**
	 * 	传入头节点 反转双向链表结构并返回新的头节点
	 * @param head
	 * @return
	 */
	public static DoubleNode<Integer> reverseDoubleList2(DoubleNode<Integer> head) {
		// 记录反转后节点的下一个节点
		DoubleNode<Integer> pre = null;
		// 记录现在的节点的下一个节点
		DoubleNode<Integer> next = null;
		while(head != null) {
			next = head.next;
			head.next = pre;
			head.last = next;
			pre = head;
			head = next;
		}
		return pre;
	}

	//  head
	//   a    ->   b    ->  c  ->  null
	//   c    ->   b    ->  a  ->  null
	public static Node reverseLinkedList(Node head) {
		Node pre = null;
		Node next = null;
		while (head != null) {
			next = head.next;
			head.next = pre;
			pre = head;
			head = next;
		}
		return pre;
	}

	public static DoubleNode reverseDoubleList(DoubleNode head) {
		DoubleNode pre = null;
		DoubleNode next = null;
		while (head != null) {
			next = head.next;
			head.next = pre;
			head.last = next;
			pre = head;
			head = next;
		}
		return pre;
	}

	public static Node testReverseLinkedList(Node head) {
		if (head == null) {
			return null;
		}
		ArrayList<Node> list = new ArrayList<>();
		while (head != null) {
			list.add(head);
			head = head.next;
		}
		list.get(0).next = null;
		int N = list.size();
		for (int i = 1; i < N; i++) {
			list.get(i).next = list.get(i - 1);
		}
		return list.get(N - 1);
	}

	public static DoubleNode testReverseDoubleList(DoubleNode head) {
		if (head == null) {
			return null;
		}
		ArrayList<DoubleNode> list = new ArrayList<>();
		while (head != null) {
			list.add(head);
			head = head.next;
		}
		list.get(0).next = null;
		DoubleNode pre = list.get(0);
		int N = list.size();
		for (int i = 1; i < N; i++) {
			DoubleNode cur = list.get(i);
			cur.last = null;
			cur.next = pre;
			pre.last = cur;
			pre = cur;
		}
		return list.get(N - 1);
	}

	// for test
	public static Node generateRandomLinkedList(int len, int value) {
		int size = (int) (Math.random() * (len + 1));
		if (size == 0) {
			return null;
		}
		size--;
		Node head = new Node((int) (Math.random() * (value + 1)));
		Node pre = head;
		while (size != 0) {
			Node cur = new Node((int) (Math.random() * (value + 1)));
			pre.next = cur;
			pre = cur;
			size--;
		}
		return head;
	}

	// for test
	public static DoubleNode generateRandomDoubleList(int len, int value) {
		int size = (int) (Math.random() * (len + 1));
		if (size == 0) {
			return null;
		}
		size--;
		DoubleNode head = new DoubleNode((int) (Math.random() * (value + 1)));
		DoubleNode pre = head;
		while (size != 0) {
			DoubleNode cur = new DoubleNode((int) (Math.random() * (value + 1)));
			pre.next = cur;
			cur.last = pre;
			pre = cur;
			size--;
		}
		return head;
	}

	// for test
	public static List<Integer> getLinkedListOriginOrder(Node head) {
		List<Integer> ans = new ArrayList<>();
		while (head != null) {
			ans.add(head.value);
			head = head.next;
		}
		return ans;
	}

	// for test
	public static boolean checkLinkedListReverse(List<Integer> origin, Node head) {
		for (int i = origin.size() - 1; i >= 0; i--) {
			if (!origin.get(i).equals(head.value)) {
				return false;
			}
			head = head.next;
		}
		return true;
	}

	// for test
	public static List<Integer> getDoubleListOriginOrder(DoubleNode head) {
		List<Integer> ans = new ArrayList<>();
		while (head != null) {
			ans.add(head.value);
			head = head.next;
		}
		return ans;
	}

	// for test
	public static boolean checkDoubleListReverse(List<Integer> origin, DoubleNode head) {
		DoubleNode end = null;
		for (int i = origin.size() - 1; i >= 0; i--) {
			if (!origin.get(i).equals(head.value)) {
				return false;
			}
			end = head;
			head = head.next;
		}
		for (int i = 0; i < origin.size(); i++) {
			if (!origin.get(i).equals(end.value)) {
				return false;
			}
			end = end.last;
		}
		return true;
	}

	// for test
	public static void main(String[] args) {
		int len = 50;
		int value = 100;
		int testTime = 100000;
		System.out.println("test begin!");
		for (int i = 0; i < testTime; i++) {
			Node node1 = generateRandomLinkedList(len, value);
			List<Integer> list1 = getLinkedListOriginOrder(node1);
			node1 = reverseLinkedList(node1);
			if (!checkLinkedListReverse(list1, node1)) {
				System.out.println("Oops1!");
			}

			Node node2 = generateRandomLinkedList(len, value);
			List<Integer> list2 = getLinkedListOriginOrder(node2);
			node2 = testReverseLinkedList(node2);
			if (!checkLinkedListReverse(list2, node2)) {
				System.out.println("Oops2!");
			}

			DoubleNode node3 = generateRandomDoubleList(len, value);
			List<Integer> list3 = getDoubleListOriginOrder(node3);
			node3 = reverseDoubleList(node3);
			if (!checkDoubleListReverse(list3, node3)) {
				System.out.println("Oops3!");
			}

			DoubleNode node4 = generateRandomDoubleList(len, value);
			List<Integer> list4 = getDoubleListOriginOrder(node4);
			node4 = reverseDoubleList(node4);
			if (!checkDoubleListReverse(list4, node4)) {
				System.out.println("Oops4!");
			}

		}
		System.out.println("test finish!");

	}

}
    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
    261
    262
    263
    264
    265
    266
    267
    268
    269

  • 把给定值都删除

    package class03;

/**
 * 	删除给定的值
 * @author yangyanchao
 *
 */
public class Test02_DeleteGivenValue {
	/**
	 * 	单向链表结构
	 * @author yangyanchao
	 *
	 * @param <T>
	 */
	public static class Node<T> {
		public T value;
		public Node<T> next;
		public Node(T value) {
			this.value = value;
		}
	}
	
	/**
	 * 	双向链表结构
	 * @author yangyanchao
	 *
	 * @param <T>
	 */
	public static class DoubleNode<T> {
		public T value;
		public DoubleNode<T> last;
		public DoubleNode<T> next;
		public DoubleNode(T value) {
			this.value = value;
		}
	}
	
	/**
	 * 	单向链表删除给定的值
	 * @param head
	 * @return
	 */
	public static Node<Integer> removeValue(Node<Integer> head, Integer num) {
		// 找到第一个不是num值的节点作为head节点
		while(head != null) {
			if(head.value != num) {
				break;
			}
			head = head.next;
		}
		// 定义俩个指针 
		// cur当前节点 pre是预处理节点 卡住头节点 
		// 若是cur当前节点的值与num相等则pre是预处理节点的下一个节点是cur的下一个节点
		// 若是cur当前节点的值与num不相等则pre是预处理节点指向cur当前节点
		Node<Integer> pre = head;
		Node<Integer> cur = head;
		while(cur != null) {
			if(cur.value == num) {
				pre.next = cur.next;
			} else {
				pre = cur;
			}
			cur = cur.next;
		}
		return head;
	}
	
	/**
	 * 	双向链表删除给定的值
	 * @param head
	 * @return
	 */
	public static DoubleNode<Integer> removeValue2(DoubleNode<Integer> head, Integer num) {
		// 找到第一个不是num值的节点作为head节点
		while(head != null) {
			if(head.value != num) {
				break;
			}
			head = head.next;
		}
		// 定义俩个指针 
		// cur当前节点 pre是预处理节点 卡住头节点 
		// 若是cur当前节点的值与num相等则pre是预处理节点的下一个节点是cur的下一个节点
		// 若是cur当前节点的值与num不相等则pre是预处理节点指向cur当前节点
		DoubleNode<Integer> pre = head;
		DoubleNode<Integer> cur = head;
		while(cur != null) {
			if(cur.value == num) {
				pre.next = cur.next;
				pre.next.last = pre;
			} else {
				pre = cur;
			}
			cur = cur.next;
		}
		return head;
	}
}
    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

# 栈和队列

逻辑概念

栈：数据先进后出，犹如弹匣

队列：数据先进先出，好似排队

# 栈和队列的实际实现

双向链表实现栈与队列

package class03;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * 	双向链表实现栈与队列
 * 	先实现双端队列 再使用双端队列实现栈结构
 * @author yangyanchao
 *
 */
public class Test03_DoubleEndsQueueToStackAndQueue {
	/**
	 * 	双向链表结构
	 * @author yangyanchao
	 *
	 * @param <T>
	 */
	public static class DoubleNode<T> {
		public T value;
		public DoubleNode<T> last;
		public DoubleNode<T> next;
		public DoubleNode(T value) {
			this.value = value;
		}
	}
	/**
	 * 	双向链表结构实现双端队列
	 * @author yangyanchao
	 *
	 * @param <T>
	 */
	public static class DoubleEndsQueue<T> {
		/**
		 * 	头节点
		 */
		public DoubleNode<T> head;
		/**
		 * 	尾节点
		 */
		public DoubleNode<T> tail;
		
		/**
		 * 	从头部节点添加
		 * @param value
		 */
		public void addFromHead(T value) {
			DoubleNode<T> cur = new DoubleNode<T>(value);
			if(head == null) {
				// 若头节点为空则说明队列中并没有数据则头尾节点都指向cur
				head = cur;
				tail = cur;
			} else {
				// 若头节点不为空则说明队列中有数据
				// cur节点的下一个节点指向头部节点
				// 头部节点的上一个节点指向cur节点
				// 头部节点指向cur节点
				cur.next = head;
				head.last = cur;
				head = cur;
			}
		}
		/**
		 * 	从尾部部节点添加
		 * @param value
		 */
		public void addFromBottom(T value) {
			DoubleNode<T> cur = new DoubleNode<T>(value);
			if(tail == null) {
				// 若尾节点为空则说明队列中并没有数据则头尾节点都指向cur
				head = cur;
				tail = cur;
			} else {
				// 若尾节点不为空则说明队列中有数据
				// cur节点的上一个节点指向尾部节点
				// 尾部节点的下一个节点指向cur节点
				// 尾部节点指向cur节点
				cur.last = tail;
				tail.next = cur;
				tail = cur;
			}
		}
		/**
		 * 	从头部部节点弹出
		 * @param value
		 */
		public T popFromHead() {
			if(head == null) {
				return null;
			} 
			DoubleNode<T> cur = head;
			if (head == tail) {
				head = null;
				tail = null;
			} else {
				head = head.next; 
				cur.next = null;
				cur.last = null;
			}
			return cur.value;
		}
		/**
		 * 	从尾部部节点弹出
		 * @param value
		 */
		public T popFromBottom() {
			if(tail == null) {
				return null;
			}
			DoubleNode<T> cur = tail;
			if (head == tail) {
				head = null;
				tail = null;
			} else {
				tail = tail.last;
				cur.last = null;
				cur.next = null;
			}
			return cur.value;
		}
		/**
		 * 	是否为空
		 * @return
		 */
		public boolean isEmpty() {
			return head == null;
		}
	}
	
	/**
	 * 	双端队列实现栈
	 * @author yangyanchao
	 *
	 * @param <T>
	 */
	public static class MyStack<T> {
		private DoubleEndsQueue<T> queue = null;
		public MyStack() {
			queue = new DoubleEndsQueue<T>();
		}
		/**
		 * 	向栈中压入数据 从尾部进入
		 * @param value
		 */
		public void push(T value) {
			queue.addFromBottom(value);
		}
		/**
		 * 	栈里弹出数据 从尾部弹出
		 * @return
		 */
		public T pop() {
			return queue.popFromBottom();
		}
		
		public boolean isEmpty() {
			return queue.isEmpty();
		}
	}
	
	/**
	 * 	使用双端队列实现队列
	 * @author yangyanchao
	 *
	 * @param <T>
	 */
	public static class MyQueue<T> {
		private DoubleEndsQueue<T> queue = null;
		public MyQueue() {
			queue = new DoubleEndsQueue<T>();
		}
		/**
		 * 	从头部进入
		 * @param value
		 */
		public void push(T value) {
			queue.addFromHead(value);
		}

		/**
		 * 	从尾部弹出
		 * @return
		 */
		public T poll() {
			return queue.popFromBottom();
		}

		public boolean isEmpty() {
			return queue.isEmpty();
		}
	}
	
	public static boolean isEqual(Integer o1, Integer o2) {
		if (o1 == null && o2 != null) {
			return false;
		}
		if (o1 != null && o2 == null) {
			return false;
		}
		if (o1 == null && o2 == null) {
			return true;
		}
		return o1.equals(o2);
	}
	
	public static void main(String[] args) {
		int oneTestDataNum = 100;
		int value = 10000;
		int testTimes = 100000;
		for (int i = 0; i < testTimes; i++) {
			MyStack<Integer> myStack = new MyStack<>();
			MyQueue<Integer> myQueue = new MyQueue<>();
			Stack<Integer> stack = new Stack<>();
			Queue<Integer> queue = new LinkedList<>();
			for (int j = 0; j < oneTestDataNum; j++) {
				int nums = (int) (Math.random() * value);
				if (stack.isEmpty()) {	
					myStack.push(nums);
					stack.push(nums);
				} else {
					if (Math.random() < 0.5) {
						myStack.push(nums);
						stack.push(nums);
					} else {
						if (!isEqual(myStack.pop(), stack.pop())) {
							System.out.println("oops!");
						}
					}
				}
				int numq = (int) (Math.random() * value);
				if (stack.isEmpty()) {
					myQueue.push(numq);
					queue.offer(numq);
				} else {
					if (Math.random() < 0.5) {
						myQueue.push(numq);
						queue.offer(numq);
					} else {
						if (!isEqual(myQueue.poll(), queue.poll())) {
							System.out.println("oops!");
						}
					}
				}
			}
		}
		System.out.println("finish!");
	}
}
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

# 既然语言都有这些结构和api，为什么还需要手撸练习？

  • 算法问题无关语言
  • 语言提供的api是有限的，当有新的功能是api不提供的，就需要改写
  • 任何软件工具的底层都是最基本的算法和数据结构，这是绕不过去的

# 栈和队列的常见面试题

怎么用数组实现不超过固定大小的队列和栈？

使用固定大小的数组实现栈结构

package class03;

/**
 * 	使用固定大小的数组实现栈结构
 * @author yangyanchao
 *
 */
public class Test04_ArrayImplementStack {
	/**
	 * 	数组实现栈
	 * @author yangyanchao
	 *
	 */
	public static class MyStack {
		/**
		 * 	数组
		 */
		private int[] arr;
		
		/**
		 * 	真实数据的长度
		 */
		private int size;
		
		/**
		 * 	数组容量
		 */
		private int limit;
		
		public MyStack(int limit) {
			arr = new int[limit];
			this.limit = limit;
			this.size = 0;
		}
		
		/**
		 * 	向栈中压入数据
		 * @param value
		 */
		public void push(int value) {
			if(size == limit) {
				throw new RuntimeException("栈满了，不能再push了");
			}
			arr[size++] = value;
		}
		
		/**
		 * 	栈里弹出栈顶数据
		 * @return
		 */
		public int pop() {
			if(size == 0) {
				throw new RuntimeException("栈空了，不能再pop了");
			}
			return arr[size--];
		}
		
		/**
		 * 	获取看一下栈顶数据 不弹出
		 * @return
		 */
		public int peek() {
			if(size == 0) {
				throw new RuntimeException("栈空了，不能再peek了");
			}
			return arr[size];
		}
		
		public boolean isEmpty() {
			return size == 0;
		}
		
	}
}
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

使用固定大小的数组实现队列结构

package class03;

/**
 * 	使用固定大小的数组实现队列结构
 * @author yangyanchao
 *
 */
public class Test05_ArrayImplementQueue {
	/**
	 * 	环数组实现队列
	 * @author yangyanchao
	 *
	 */
	public static class MyQueue {
		/**
		 * 	数组
		 */
		private int[] arr;
		
		/**
		 * 	添加数据的位置索引
		 */
		private int pushi;
		
		/**
		 * 	弹出数据的位置索引
		 */
		private int polli;
		
		/**
		 * 	真实数据的长度
		 */
		private int size;
		
		/**
		 * 	数组容量
		 */
		private int limit;

		public MyQueue(int limit) {
			arr = new int[limit];
			this.limit = limit;
			this.pushi = 0;
			this.polli = 0;
			this.size = 0;
		}
		
		/**
		 * 	向队列中加入数据
		 * @param value
		 */
		public void push(int value) {
			if(size == limit) {
				throw new RuntimeException("队列满了，不能再push了");
			}
			arr[pushi] = value;
			size++;
			pushi = nextIndex(pushi);
		}
		
		/**
		 * 	向队列中获取数据并弹出
		 * @param value
		 */
		public int poll() {
			if(size == 0) {
				throw new RuntimeException("队列空了，不能再poll了");
			}
			int ans = arr[polli];
			size--;
			polli = nextIndex(polli);
			return ans;
		}
		
		/**
		 * 	向队列中获取数据不弹出
		 * @param value
		 */
		public int peek() {
			if(size == 0) {
				throw new RuntimeException("队列空了，不能再peek了");
			}
			return arr[polli];
		}
		
		/**
		 * 	如果现在的下标是i，返回下一个位置
		 * @param value
		 */
		private int nextIndex(int i) {
			return i < limit - 1 ? i + 1 : 0;
		}
		
		public boolean isEmpty() {
			return size == 0;
		}
		
	}
}
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

实现一个特殊的栈，在基本功能的基础上，再实现返回栈中最小元素的功能

1）pop、push、getMin操作的时间复杂度都是 O(1)。

2）设计的栈类型可以使用现成的栈结构。

设计一个数据栈、一个最小栈、同步加入与弹出

package class03;

import java.util.Stack;

/**
 * 	实现一个特殊的栈，在基本功能的基础上，再实现返回栈中最小元素的功能  
 * 	1）pop、push、getMin操作的时间复杂度都是 O(1)。 
 * 	2）设计的栈类型可以使用现成的栈结构。
 * @author yangyanchao
 *
 */
public class Test06_GetMinStack {
	/**
	 * 	最小栈只记录 数据栈中比自己的栈顶元素小的值 不会记录大的值
	 * @author yangyanchao
	 *
	 */
	public static class MyStackNoRecordBig {
		
		/**
		 * 	数据栈
		 */
		private Stack<Integer> dataStack;
		
		/**
		 * 	最小栈
		 */
		private Stack<Integer> minStack;
		
		public MyStackNoRecordBig() {
			this.dataStack = new Stack<Integer>();
			this.minStack = new Stack<Integer>();
		}
		
		/**
		 * 	添加数据
		 * @param value
		 */
		public void push(Integer value) {
			dataStack.push(value);
			if(minStack.isEmpty()) {
				minStack.push(value);
			} else if(value <= getMin()) {
				minStack.push(value);
			}
		}
		/**
		 * 	弹出数据
		 * @param value
		 */
		public Integer pop() {
			if (dataStack.isEmpty()) {
				throw new RuntimeException("Your stack is empty.");
			}
			Integer ans = dataStack.pop();
			if(ans == getMin()) {
				minStack.pop();
			}
			return ans;
		}
		
		/**
		 * 	得到最小值
		 * @return
		 */
		public Integer getMin() {
			if (minStack.isEmpty()) {
				throw new RuntimeException("Your stack is empty.");
			}
			return minStack.peek();
		}
	}
	
	/**
	 * 	最小栈   记录数据栈中比自己的栈顶元素小的值 也会记录大的值
	 * @author yangyanchao
	 *
	 */
	public static class MyStackRecordBig {
		
		/**
		 * 	数据栈
		 */
		private Stack<Integer> dataStack;
		
		/**
		 * 	最小栈
		 */
		private Stack<Integer> minStack;
		
		public MyStackRecordBig() {
			this.dataStack = new Stack<Integer>();
			this.minStack = new Stack<Integer>();
		}
		
		/**
		 * 	添加数据
		 * @param value
		 */
		public void push(Integer value) {
			dataStack.push(value);
			if(minStack.isEmpty()) {
				minStack.push(value);
			} else if(value < getMin()) {
				minStack.push(value);
			} else {
				minStack.push(getMin());
			}
		}
		/**
		 * 	弹出数据
		 * @param value
		 */
		public Integer pop() {
			if (dataStack.isEmpty()) {
				throw new RuntimeException("Your stack is empty.");
			}
			minStack.pop();
			return dataStack.pop();
		}
		
		/**
		 * 	得到最小值
		 * @return
		 */
		public Integer getMin() {
			if (minStack.isEmpty()) {
				throw new RuntimeException("Your stack is empty.");
			}
			return minStack.peek();
		}
	}
	
	public static void main(String[] args) {
		MyStackNoRecordBig stack1 = new MyStackNoRecordBig();
		stack1.push(3);
		System.out.println(stack1.getMin());
		stack1.push(4);
		System.out.println(stack1.getMin());
		stack1.push(1);
		System.out.println(stack1.getMin());
		System.out.println(stack1.pop());
		System.out.println(stack1.getMin());

		System.out.println("=============");

		MyStackRecordBig stack2 = new MyStackRecordBig();
		stack2.push(3);
		System.out.println(stack2.getMin());
		stack2.push(4);
		System.out.println(stack2.getMin());
		stack2.push(1);
		System.out.println(stack2.getMin());
		System.out.println(stack2.pop());
		System.out.println(stack2.getMin());
	}
}
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

如何用栈结构实现队列结构

package class03;

import java.util.Stack;

/**
 * 	双栈实现队列结构
 * @author yangyanchao
 *
 */
public class Test07_TwoStacksImplementQueue {
	/**
	 * 	push栈倒入pop栈的过程
	 * @author yangyanchao
	 */
	public static class TwoStacksQueue {
		/**
		 * 	添加数据栈
		 */
		private Stack<Integer> pushStack;
		/**
		 * 	弹出数据栈
		 */
		private Stack<Integer> popStack;
		
		public TwoStacksQueue() {
			this.pushStack = new Stack<Integer>();
			this.popStack =  new Stack<Integer>();
		}
		
		/**
		 * 	push栈倒入pop栈
		 * 	1、要到必须一次倒完
		 * 	2、倒入前验证pop栈是否为空 必须为空时才能倒数据
		 */
		public void pushToPop() {
			if(popStack.isEmpty()) {
				while (!pushStack.isEmpty()) {
					popStack.push(pushStack.pop());
				}
			}
		}
		
		/**
		 * 	添加数据
		 * @param value
		 */
		public void add(Integer value) {
			pushStack.push(value);
			pushToPop();
		}
		
		/**
		 * 	弹出数据
		 * @return
		 */
		public Integer poll() {
			if (isEmpty()) {
				throw new RuntimeException("Queue is empty!");
			}
			pushToPop();
			return popStack.pop();
		}
		
		/**
		 * 	查看数据
		 * @return
		 */
		public int peek() {
			if (isEmpty()) {
				throw new RuntimeException("Queue is empty!");
			}
			pushToPop();
			return popStack.peek();
		}
		
		public boolean isEmpty() {
			return pushStack.isEmpty() && popStack.isEmpty();
		}
	}
	public static void main(String[] args) {
		TwoStacksQueue test = new TwoStacksQueue();
		test.add(1);
		test.add(2);
		test.add(3);
		System.out.println(test.peek());
		System.out.println(test.poll());
		System.out.println(test.peek());
		System.out.println(test.poll());
		System.out.println(test.peek());
		System.out.println(test.poll());
	}
}
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

如何用队列结构实现栈结构

package class03;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * 	双队列实现栈结构
 * @author yangyanchao
 *
 */
public class Test08_TwoQueueImplementStack {

	/**
	 * 	队列与辅助队列来回倒数据
	 * @author yangyanchao
	 *
	 * @param <T>
	 */
	public static class TwoQueueStack<T> {
		/**
		 * 	数据队列
		 */
		public Queue<T> queue;
		/**
		 * 	辅助队列
		 */
		public Queue<T> help;
		public TwoQueueStack() {
			queue = new LinkedList<T>();
			help = new LinkedList<T>();
		}
		
		/**
		 * 	添加数据
		 * @param value
		 */
		public void push(T value) {
			queue.offer(value);
		}
		
		/**
		 * 	弹出数据
		 * @return
		 */
		public T poll() {
			while(queue.size() > 1) {
				help.offer(queue.poll());
			}
			T ans = queue.poll();
			Queue<T> temp = queue;
			queue = help;
			help = temp;
			return ans;
		}
		
		/**
		 * 	查看数据
		 * @return
		 */
		public T peek() {
			while(queue.size() > 1) {
				help.offer(queue.poll());
			}
			T ans = queue.poll();
			help.offer(ans);
			Queue<T> temp = queue;
			queue = help;
			help = temp;
			return ans;
		}
		public boolean isEmpty() {
			return queue.isEmpty();
		}
	}
	public static void main(String[] args) {
		System.out.println("test begin");
		TwoQueueStack<Integer> myStack = new TwoQueueStack<>();
		Stack<Integer> test = new Stack<>();
		int testTime = 1000000;
		int max = 1000000;
		for (int i = 0; i < testTime; i++) {
			if (myStack.isEmpty()) {
				if (!test.isEmpty()) {
					System.out.println("Oops");
				}
				int num = (int) (Math.random() * max);
				myStack.push(num);
				test.push(num);
			} else {
				if (Math.random() < 0.25) {
					int num = (int) (Math.random() * max);
					myStack.push(num);
					test.push(num);
				} else if (Math.random() < 0.5) {
					if (!myStack.peek().equals(test.peek())) {
						System.out.println("Oops");
					}
				} else if (Math.random() < 0.75) {
					if (!myStack.poll().equals(test.pop())) {
						System.out.println("Oops");
					}
				} else {
					if (myStack.isEmpty() != test.isEmpty()) {
						System.out.println("Oops");
					}
				}
			}
		}

		System.out.println("test finish!");

	}
}
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

# 递归？这东西是什么啊？

  • 怎么从思想上理解递归

  • 怎么从实际实现的角度出发理解递归

    实际递归就是利用系统栈暂存实现的

示例

求数组arr[L..R]中的最大值，怎么用递归方法实现。

1）将[L..R]范围分成左右两半。左：[L..Mid] 右[Mid+1..R] 2）左部分求最大值，右部分求最大值 3） [L..R]范围上的最大值，是max{左部分最大值，右部分最大值}

注意：2）是个递归过程，当范围上只有一个数，就可以不用再递归了

package class03;

/**
 * 	最简单的递归
 * 	求arr中的最大值
 * @author yangyanchao
 *
 */
public class Test09_GetMax {
	
	/**
	 * 	求arr中的最大值
	 * @param arr
	 * @return
	 */
	public static int getMaxByArray(int arr[]) {
		return process(arr, 0, arr.length - 1);
	}
	
	/**
	 * 	arr[L..R]范围上求最大值  L ... R   N
	 * @param arr
	 * @param L
	 * @param R
	 * @return
	 */
	public static int process(int[] arr, int L, int R) {
		// arr[L..R]范围上只有一个数，直接返回，base case
		if (L == R) { 
			return arr[L];
		}
		// L...R 不只一个数
		// mid = (L + R) / 2
		int mid = L + ((R - L) >> 1); // 中点   	1
		int leftMax = process(arr, L, mid);
		int rightMax = process(arr, mid + 1, R);
		return Math.max(leftMax, rightMax);
	}
}
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

# 递归的脑图和实际实现

  • 对于新手来说，把调用的过程画出结构图是必须的，这有利于分析递归
  • 递归并不是玄学，递归底层是利用系统栈来实现的
  • 任何递归函数都一定可以改成非递归

# Master公式

递归函数的时间复杂度 子问题的规模是一致的才能使用Master公式

形如 T(N) = a * T(N/b) + O(N^d)(其中的a、b、d都是常数) 的递归函数，可以直接通过Master公式来确定时间复杂度 如果 log(b,a) < d，复杂度为O(N^d) 如果 log(b,a) > d，复杂度为O(N^log(b,a)) 如果 log(b,a) == d，复杂度为O(N^d * logN)

# 哈希表

  • 哈希表在使用层面上可以理解为一种集合结构
  • 如果只有key，没有伴随数据value，可以使用HashSet结构
  • 如果既有key，又有伴随数据value，可以使用HashMap结构
  • 有无伴随数据，是HashMap和HashSet唯一的区别，实际结构是一回事
  • 使用哈希表增(put)、删(remove)、改(put)和查(get)的操作，可以认为时间复杂度为 O(1)，但是常数时间比较大
  • 放入哈希表的东西，如果是基础类型，内部按值传递，内存占用是这个东西的大小
  • 放入哈希表的东西，如果不是基础类型，内部按引用传递，内存占用是8字节

# 有序表

  • 有序表在使用层面上可以理解为一种集合结构
  • 如果只有key，没有伴随数据value，可以使用TreeSet结构
  • 如果既有key，又有伴随数据value，可以使用TreeMap结构
  • 有无伴随数据，是TreeSet和TreeMap唯一的区别，底层的实际结构是一回事
  • 有序表把key按照顺序组织起来，而哈希表完全不组织
  • 红黑树、AVL树、size-balance-tree和跳表等都属于有序表结构，只是底层具体实现不同
  • 放入如果是基础类型，内部按值传递，内存占用就是这个东西的大小
  • 放入如果不是基础类型，内部按引用传递，内存占用是8字节
  • 不管是什么底层具体实现，只要是有序表，都有以下固定的基本功能和固定的时间复杂度

# 有序表相关函数

  • void put(K key, V value) 将一个(key，value)记录加入到表中，或者将key的记录 更新成value。
  • V get(K key) 根据给定的key，查询value并返回。
  • void remove(K key) 移除key的记录。
  • boolean containsKey(K key) 询问是否有关于key的记录。
  • K firstKey() 返回所有键值的排序结果中，最小的那个。
  • K lastKey() 返回所有键值的排序结果中，最大的那个。
  • K floorKey(K key) 返回<= key 离key最近的那个
  • K ceilingKey(K key) 返回>= key 离key最近的那个

# 哈希表和有序表的原理

以后讲！现在的你可能会听不懂，只需要记住： 哈希表在使用时，增删改查时间复杂度都是O(1)

有序表在使用时，比哈希表功能多，时间复杂度都是O(logN)

代码

package class03;

import java.util.HashMap;
import java.util.HashSet;
import java.util.TreeMap;

/**
 * 	简单介绍HashMap与TreeMap
 * @author yangyanchao
 *
 */
public class HashMapAndSortedMap {

	public static class Node {
		public int value;

		public Node(int v) {
			value = v;
		}
	}

	public static class Zuo {
		public int value;

		public Zuo(int v) {
			value = v;
		}
	}

	public static void main(String[] args) {

		HashMap<Integer, String> test = new HashMap<>();
		Integer a = 19000000;
		Integer b = 19000000;
		System.out.println(a == b);

		test.put(a, "我是3");
		System.out.println(test.containsKey(b));

		Zuo z1 = new Zuo(1);
		Zuo z2 = new Zuo(1);
		HashMap<Zuo, String> test2 = new HashMap<>();
		test2.put(z1, "我是z1");
		System.out.println(test2.containsKey(z2));

		// UnSortedMap
		HashMap<Integer, String> map = new HashMap<>();
		map.put(1000000, "我是1000000");
		map.put(2, "我是2");
		map.put(3, "我是3");
		map.put(4, "我是4");
		map.put(5, "我是5");
		map.put(6, "我是6");
		map.put(1000000, "我是1000001");

		System.out.println(map.containsKey(1));
		System.out.println(map.containsKey(10));

		System.out.println(map.get(4));
		System.out.println(map.get(10));

		map.put(4, "他是4");
		System.out.println(map.get(4));

		map.remove(4);
		System.out.println(map.get(4));

		// key
		HashSet<String> set = new HashSet<>();
		set.add("abc");
		set.contains("abc");
		set.remove("abc");

		// 哈希表，增、删、改、查，在使用时，O（1）

		System.out.println("=====================");

		Integer c = 100000;
		Integer d = 100000;
		System.out.println(c.equals(d));

		Integer e = 127; // - 128 ~ 127
		Integer f = 127;
		System.out.println(e == f);

		HashMap<Node, String> map2 = new HashMap<>();
		Node node1 = new Node(1);
		Node node2 = node1;
		map2.put(node1, "我是node1");
		map2.put(node2, "我是node1");
		System.out.println(map2.size());

		System.out.println("======================");

		// TreeMap 有序表：接口名
		// 红黑树、avl、sb树、跳表
		// O(logN)
		System.out.println("有序表测试开始");
		TreeMap<Integer, String> treeMap = new TreeMap<>();

		treeMap.put(3, "我是3");
		treeMap.put(4, "我是4");
		treeMap.put(8, "我是8");
		treeMap.put(5, "我是5");
		treeMap.put(7, "我是7");
		treeMap.put(1, "我是1");
		treeMap.put(2, "我是2");

		System.out.println(treeMap.containsKey(1));
		System.out.println(treeMap.containsKey(10));

		System.out.println(treeMap.get(4));
		System.out.println(treeMap.get(10));

		treeMap.put(4, "他是4");
		System.out.println(treeMap.get(4));

		// treeMap.remove(4);
		System.out.println(treeMap.get(4));

		System.out.println("新鲜：");

		System.out.println(treeMap.firstKey());
		System.out.println(treeMap.lastKey());
		// <= 4
		System.out.println(treeMap.floorKey(4));
		// >= 4
		System.out.println(treeMap.ceilingKey(4));
		// O(logN)

	}

}
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

← 第4节 归并排序及其相关面试题 →