数据结构与算法 -- 队列

简介

  1. 栈支持两个基本操作:入栈(push)、出栈(pop)
  2. 队列支持两个基本操作:入队(enqueue)、出队(dequeue)
  3. 队列和栈都是操作受限的线性表
  4. 数组实现的队列叫作顺序队列,用链表实现的队列叫作链式队列

顺序队列

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
public class ArrayQueue<T> {
private Object[] items;
private int n;
private int head = 0;
private int tail = 0;

public ArrayQueue(int capacity) {
items = new Object[capacity];
n = capacity;
}

// 入队
public boolean enqueue(T t) {
if (tail == n) {
// 队列已满
return false;
}
items[tail++] = t;
return true;
}

// 出队
public T dequeue() {
if (head == tail) {
// 队列为空
return null;
}
return (T) items[head++];
}
}

存在的问题:随着不停地入队,tail会到达n,即使数组中还有空闲空间,也无法往队列中添加数据,可以优化enqueue

优化enqueue

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 入队
public boolean enqueue(T t) {
if (tail == n) {
if (head == 0) {
// 整个队列已满,只能扩容
return false;
}
// 数据搬移
System.arraycopy(items, head, items, 0, tail - head);
tail -= head;
head = 0;
}
items[tail++] = t;
return true;
}

依然有数据搬移的动作,可以采用循环队列

循环队列

循环队列体现出取模的思想

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
public class CircularQueue<T> {
private Object[] items;
private int n;
private int head;
private int tail;

public CircularQueue(int capacity) {
// 预留一个位置给tail
int realSize = capacity + 1;
items = new Object[realSize];
this.n = realSize;
}

// 入队
public boolean enqueue(T t) {
if ((tail + 1) % n == head) {
// 队列已满
return false;
}
items[tail] = t;
tail = (tail + 1) % n;
return true;
}

// 出队
public T dequeue() {
if (head == tail) {
// 队列为空
return null;
}
T t = (T) items[head];
head = (head + 1) % n;
return t;
}
}

链式队列

1
2
3
4
5
@Data
public class Node<T> {
private T data;
private Node<T> next;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class LinkedQueue<T> {
private Node<T> head = new Node<>();
private Node<T> tail = head;

// 入队
private boolean enqueue(T t) {
Node<T> node = new Node<>();
tail.setData(t);
tail.setNext(node);
tail = node;
return true;
}

// 出队
public T dequeue() {
if (head == tail) {
// 队列为空
return null;
}
T data = head.getData();
head = head.getNext();
return data;
}
}

阻塞队列

  1. 阻塞队列
    • 在队列为时,从队头取数据会被阻塞,直到队列中有数据
    • 在队列已时,往队尾插入数据会被阻塞,直到队列中有空闲位置
  2. 使用阻塞队列,可以很容易地实现生产者-消费者模型,有效地协调生产和消费的速度

并发队列

  1. 并发队列:线程安全的队列
  2. 最简单的实现方式是直接在enqueue和dequeue方法上加锁,但锁粒度太大会是降低并发度
  3. 基于数组的循环队列,利用CAS原子操作,可以非常高效地实现并发队列,例如Disruptor
0%