Java学习-Day9

链队列

一、描述

链队列比较容易写. 只要之前的链表增删改查没问题, 那么这个链队列也不在话下.

二、思路

为方便操作, 空队列也需要一个节点. 这和以前的链表同理. 头节点的引用 (指针) 称为 header. 也被称为带有头节点的链队列. 所谓链队列入队仅操作尾部, 出队仅操作头部. 换句话说就是只在头进行删除操作, 只在尾进行插入操作.

节点的结构如下: 

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
/**
 * An inner class.
 */
class Node {
	/**
	 * The data.
	 */
	int data;

	/**
	 * The reference to the next node.
	 */
	Node next;

	/**
	 ******************* 
	 * The constructor.
	 * 
	 * @param paraValue The data.
	 ******************* 
	 */
	public Node(int paraValue) {
		data = paraValue;
		next = null;
	}// Of the constructor
}// Of class Node

三、入队操作

输入

一个整数

输出

无

具体代码

1
2
3
4
5
6
7
8
9
10
11
12
/**
 *********************
 * Enqueue.
 * 
 * @param paraValue The value of the new node.
 *********************
 */
public void enqueue(int paraValue) {
	Node tempNode = new Node(paraValue);
	tail.next = tempNode;
	tail = tempNode;
}// Of enqueue

四、出队操作

输入

无

输出

若队列不为空则输出一个数值

若队列为空先打印字符串 "No element in the queue" 再返回 -1

具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 *********************
 * Dequeue.
 * 
 * @return The value at the header.
 *********************
 */
public int dequeue() {
	if (header == tail) {
		System.out.println("No element in the queue");
		return -1;
	} // Of if

	int resultValue = header.next.data;

	header.next = header.next.next;

	// The queue becomes empty.
	if (header.next == null) {
		tail = header;
	} // Of if

	return resultValue;
}// Of dequeue

五、完整代码

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
package datastructure.queue;

/**
 * Linked queue.
 * 
 * @author Shihuai Wen Email:wshysxcc@outlook.com
 */
public class LinkedQueue {

	/**
	 * An inner class.
	 */
	class Node {
		/**
		 * The data.
		 */
		int data;

		/**
		 * The reference to the next node.
		 */
		Node next;

		/**
		 ******************* 
		 * The constructor.
		 * 
		 * @param paraValue The data.
		 ******************* 
		 */
		public Node(int paraValue) {
			data = paraValue;
			next = null;
		}// Of the constructor
	}// Of class Node

	/**
	 * The header of the queue.
	 */
	Node header;

	/**
	 * The tail of the queue.
	 */
	Node tail;

	/**
	 *********************
	 * Construct an empty sequential list.
	 *********************
	 */
	public LinkedQueue() {
		header = new Node(-1);
		tail = header;
	}// Of the first constructor

	/**
	 *********************
	 * Enqueue.
	 * 
	 * @param paraValue The value of the new node.
	 *********************
	 */
	public void enqueue(int paraValue) {
		Node tempNode = new Node(paraValue);
		tail.next = tempNode;
		tail = tempNode;
	}// Of enqueue

	/**
	 *********************
	 * Dequeue.
	 * 
	 * @return The value at the header.
	 *********************
	 */
	public int dequeue() {
		if (header == tail) {
			System.out.println("No element in the queue");
			return -1;
		} // Of if

		int resultValue = header.next.data;

		header.next = header.next.next;

		// The queue becomes empty.
		if (header.next == null) {
			tail = header;
		} // Of if

		return resultValue;
	}// Of dequeue

	/**
	 *********************
	 * Overrides the method claimed in Object, the superclass of any class.
	 *********************
	 */
	public String toString() {
		String resultString = "";

		if (header.next == null) {
			return "empty";
		} // Of if

		Node tempNode = header.next;
		while (tempNode != null) {
			resultString += tempNode.data + ", ";
			tempNode = tempNode.next;
		} // Of while

		return resultString;
	}// Of toString

	/**
	 *********************
	 * The entrance of the program.
	 * 
	 * @param args Not used now.
	 *********************
	 */
	public static void main(String args[]) {
		LinkedQueue tempQueue = new LinkedQueue();
		System.out.println("Initialized, the list is: " + tempQueue.toString());

		for (int i = 0; i < 5; i++) {
			tempQueue.enqueue(i + 1);
		} // Of for i
		System.out.println("Enqueue, the queue is: " + tempQueue.toString());

		tempQueue.dequeue();
		System.out.println("Dequeue, the queue is: " + tempQueue.toString());

		int tempValue;
		for (int i = 0; i < 5; i++) {
			tempValue = tempQueue.dequeue();
			System.out.println("Looped delete " + tempValue + ", the new queue is: " + tempQueue.toString());
		} // Of for i

		for (int i = 0; i < 3; i++) {
			tempQueue.enqueue(i + 10);
		} // Of for i
		System.out.println("Enqueue, the queue is: " + tempQueue.toString());
	}// Of main
}// Of class LinkedQueue

六、运行截图

循环队列

一、描述

乌洛波洛斯是传说中头衔自己尾巴的一条蛇, 象征着 "无限" "循环". 由此来引出循环队列是再好不过的了.

想像操场跑道里放一队人, 循环的感觉就出来了.

跑道可能占满, 也有可能一部分学生在跑步, 自然这些学生不同时间就会出现在不同位置. 像极了循环队列中元素的移动.

二、思路

存储结构

对于队列中元素的存储可以选择顺序表, 当然也可以选择链表的结构. 从示例代码来看这里选择的是顺序表, 简而言之就是数组.

循环队列首先应该考虑的就是循环的问题, 求余的作用就是超过限度之后回到数组开头.

要是循环队列采用的是链表的结构呢？ 想必可能就不需要这个求余过程了.

用链式结构, 空间的分配与回收由系统做, 用循环队列, 则是自己把控. 想像自己写的是操作系统, 从这个代码可以感受下内存的管理（内存管理绝不是如此简单的一个过程）.

关键操作

为了区分空队列与满队列, 需要留一个空间. 相当于不允许首尾相连.

当头和尾相同时队列为空, 那么此时判空表达式为

1
head == tail

当尾下一个位置为头时队列为满, 那么此时判空表达式为

1
(tail + 1) % TOTAL_SPACE == head

三、入队操作

输入

一个整数

输出

若队列满则打印 "Queue full.", 返回空值

若队列未满只返回空值

具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 *********************
 * Enqueue.
 * 
 * @param paraValue The value of the new node.
 *********************
 */
public void enqueue(int paraValue) {
	if ((tail + 1) % TOTAL_SPACE == head) {
		System.out.println("Queue full.");
		return;
	} // Of if

	data[tail % TOTAL_SPACE] = paraValue;
	tail++;
}// Of enqueue

四、出队操作

输入

无

输出

若队列不为空则输出一个数值

若队列为空先打印字符串 "No element in the queue." 再返回 -1

具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 *********************
 * Dequeue.
 * 
 * @return The value at the head.
 *********************
 */
public int dequeue() {
	if (head == tail) {
		System.out.println("No element in the queue.");
		return -1;
	} // Of if

	int resultValue = data[head % TOTAL_SPACE];

	head++;

	return resultValue;
}// Of dequeue

五、完整代码

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
package datastructure.queue;

/**
 * Circle char queue.
 * 
 * @author Shihuai Wen Email:wshysxcc@outlook.com
 */
public class CircleIntQueue {

	/**
	 * The total space. One space can never be used.
	 */
	public static final int TOTAL_SPACE = 10;

	/**
	 * The data.
	 */
	int[] data;

	/**
	 * The index for calculating the head. The actual head is head % TOTAL_SPACE.
	 */
	int head;

	/**
	 * The index for calculating the tail.
	 */
	int tail;

	/**
	 ******************* 
	 * The constructor
	 ******************* 
	 */
	public CircleIntQueue() {
		data = new int[TOTAL_SPACE];
		head = 0;
		tail = 0;
	}// Of the first constructor

	/**
	 *********************
	 * Enqueue.
	 * 
	 * @param paraValue The value of the new node.
	 *********************
	 */
	public void enqueue(int paraValue) {
		if ((tail + 1) % TOTAL_SPACE == head) {
			System.out.println("Queue full.");
			return;
		} // Of if

		data[tail % TOTAL_SPACE] = paraValue;
		tail++;
	}// Of enqueue

	/**
	 *********************
	 * Dequeue.
	 * 
	 * @return The value at the head.
	 *********************
	 */
	public int dequeue() {
		if (head == tail) {
			System.out.println("No element in the queue.");
			return -1;
		} // Of if

		int resultValue = data[head % TOTAL_SPACE];

		head++;

		return resultValue;
	}// Of dequeue

	/**
	 *********************
	 * Overrides the method claimed in Object, the superclass of any class.
	 *********************
	 */
	public String toString() {
		String resultString = "";

		if (head == tail) {
			return "empty";
		} // Of if

		for (int i = head; i < tail; i++) {
			resultString += data[i % TOTAL_SPACE] + ", ";
		} // Of for i

		return resultString;
	}// Of toString

	/**
	 *********************
	 * The entrance of the program.
	 * 
	 * @param args Not used now.
	 *********************
	 */
	public static void main(String args[]) {
		CircleIntQueue tempQueue = new CircleIntQueue();
		System.out.println("Initialized, the list is: " + tempQueue.toString());

		for (int i = 0; i < 5; i++) {
			tempQueue.enqueue(i + 1);
		} // Of for i
		System.out.println("Enqueue, the queue is: " + tempQueue.toString());

		int tempValue = tempQueue.dequeue();
		System.out.println("Dequeue " + tempValue + ", the queue is: " + tempQueue.toString());

		for (int i = 0; i < 6; i++) {
			tempQueue.enqueue(i + 10);
			System.out.println("Enqueue, the queue is: " + tempQueue.toString());
		} // Of for i

		for (int i = 0; i < 3; i++) {
			tempValue = tempQueue.dequeue();
			System.out.println("Dequeue " + tempValue + ", the queue is: " + tempQueue.toString());
		} // Of for i

		for (int i = 0; i < 6; i++) {
			tempQueue.enqueue(i + 100);
			System.out.println("Enqueue, the queue is: " + tempQueue.toString());
		} // Of for i
	}// Of main

} // Of class CircleIntQueue

六、运行截图

总结

队列呢在现实生活中真的比栈要常见得多了, 先来先到的概念深入人心. 而在计算机的世界中我只能想到操作系统进程调度的先来先服务和消息队列.

总之, 伟大的算法或者数据结构和现实世界是息息相关的. 毕竟计算机无非就是为了更好模拟现实世界, 然后尽可能地提高算力.