0%

数据结构之队列

定义:

队列(queue)是一种线性集合,其元素从一端进入,从另一端删除。队列元素是按照先进先出(First In First Out, FIFO)方式处理的。从队列删除元素的次序,与往队列放置元素的次序是一样的。

队列抽象数据类型

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

/**
* @author iisheng
* @date 2019/07/30 23:11:21
*/
public interface QueueADT<T> {

/**
* 向队列末端添加一个元素
*
* @param element
*/
void enqueue(T element);

/**
* 从队列前端删除一个元素
*
* @param element
*/
T dequeue(T element);

/**
* 返回队列最前端的元素,但不移出
*
* @return
*/
T first();

/**
* 如果队列为空返回true
*
* @return
*/
boolean isEmpty();

/**
* 返回队列中元素的数量
*
* @return
*/
int size();

/**
* 返回队列字符串表示
*
* @return
*/
String toString();
}

用链表实现队列

LinearNode<T>是链表一个节点的实现,点击查看源码

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

import cn.iisheng.common.LinearNode;

/**
* @author iisheng
* @date 2019/07/31 08:07:21
*/
public class LinkedQueue<T> implements QueueADT<T> {


private int count;

private LinearNode<T> head, tail;


public LinkedQueue() {
count = 0;
head = tail = null;
}

@Override
public void enqueue(T element) {
LinearNode<T> node = new LinearNode(element);
if (isEmpty()) {
head = node;
} else {
tail.setNext(node);
}
tail = node;
count++;
}

@Override
public T dequeue(T element) {
if (isEmpty()) {
throw new RuntimeException("Queue is empty.");
}
T result = head.getElement();
head = head.getNext();
count--;

if (isEmpty()) {
tail = null;
}

return result;
}

@Override
public T first() {
if (isEmpty()) {
throw new RuntimeException("Queue is empty.");
}
return head.getElement();
}

@Override
public boolean isEmpty() {
return count == 0;
}

@Override
public int size() {
return count;
}

@Override
public String toString() {
return "";
}
}

用数组实现队列

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 cn.iisheng.queue;

/**
* @author iisheng
* @date 2019/09/02 21:39:31
*/
public class CircularArrayQueue<T> implements QueueADT<T> {

private static final int DEFAULT_CAPACITY = 100;
private int front, rear, count;
private T[] queue;

public CircularArrayQueue(int capacity) {
front = rear = count = 0;
queue = (T[]) new Object[capacity];
}

public CircularArrayQueue() {
this(DEFAULT_CAPACITY);
}

@Override
public void enqueue(T element) {
if (size() == queue.length) {
expandCapacity();
}

queue[rear] = element;
rear = (rear + 1) % queue.length;

count++;
}

@Override
public T dequeue(T element) {
if (isEmpty()) {
throw new RuntimeException("Queue is empty.");
}

T result = queue[front];
front = (front + 1) % queue.length;

count--;
return result;
}

@Override
public T first() {
if (isEmpty()) {
throw new RuntimeException("Queue is empty.");
}
return queue[front];
}

@Override
public boolean isEmpty() {
return count == 0;
}

@Override
public int size() {
return count;
}

public void expandCapacity() {
T[] larger = (T[]) new Object[queue.length * 2];
for (int i = 0; i < count; i++) {
larger[i] = queue[front];
front = (front + 1) % queue.length;
}
front = 0;
rear = count;
queue = larger;
}
}

二叉树的层序遍历(level-order travelsal)

从根节点开始,访问每一层的所有节点,一次一层。

leetcode 102. Binary Tree Level Order Traversal

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
public static List<List<Integer>> levelOrder(TreeNode root) {

List<List<Integer>> res = new LinkedList<>();
if (root == null) {
return res;
}

LinkedList<TreeNode> queue = new LinkedList<>();
queue.add(root);

while (!queue.isEmpty()) {
int size = queue.size();
List<Integer> currentRes = new LinkedList<>();
// 当前队列的大小就是上一层节点个数,依次出队
while (size > 0) {
TreeNode current = queue.poll();
if (current == null) {
continue;
}
currentRes.add(current.val);
// 左子树和右子树入队
if (current.left != null) {
queue.add(current.left);
}
if (current.right != null) {
queue.add(current.right);
}
size--;
}
res.add(currentRes);
}
return res;
}
iisheng wechat
微信扫码关注 Coder阿胜