数据结构与算法(5)_队列

发表于 | 分类于

如何理解队列

先进先出,这就是典型的”队列”.

最基本的操作: 入队, 放一个数据到对尾;出队,从队头取一个数据.队列跟栈一样也是一种受限的线性表数据结构

顺序队列和链式队列

用数组来实现的队列,叫顺序队列;用链表来实现的队列,叫链式队列.

顺序队列

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
//基于数组实现的队列
public class ArrayQueue{
	//String数组items,大小为n
	private String[] items; 
	private int n;
	//head 代表对头下标,tail代表对尾下标
	private int head = 0;
	private int tail = 0;

	//初始化一个大小为n的数组
	public ArrayQueue(int n){
		items = new String[n];
		this.n = n;
	}

	//入队操作
	public boolean enqueue(String item){
		//taill == n  表示队列已满
		if(tail == n) return false;
		items[tail] = item;
		tail++;
		return true;
	}
	//出队操作
	public String dequeue(){
		//head == tail 表示队列为空
		if(head == tail) return null;
		String tmp = items[head];
		head++;
		return tmp;
	}
}

//TODO
如图,上述代码中,随着不停地进行入队,出队操作,head和tail都会持续的向后移动,当tail等于n时,及时数组中还有空余空间(因为出队操作,head也会像n靠近),也无法添加数据.此时就需要数据搬移.但是,每次进行出队操作都相当于删除数组下标为0的数据,要搬移整个队列中的数据,这样的出队操作时间复杂对就会从O(1) 变成 O(n).怎么优化呢?

实际上,我们在入队的时候,集中出发一次数据搬移操作就可以了.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
...		

public boolean enqueue(String item){
	if(tail == n){
		//如果head==0 && tail==n,此时数组中就没有空闲数据
		if(head == 0) return false;
		//否则进行数据搬移
		for(int i=head; i<tail; ++i){
			items[i-head] = item[i];
		}
		//数据搬移后,更新head和tail
		tail -= head;
		head = 0;
	}
	items[tail] = item;
	tail++;
	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
36
37
38
public class QueueBasedOnLinkedList{
	Node head = null;
	Node tail = null;

	//入栈操作
	public void enqueue(String value){
		Node newNode = new Node(value,null);
		if(tail == null){
			head = newNode;
			tail = newNode;
		}else{
			tail.next = newNode;
			tail = tail.next;
		}
	}

	//出栈操作
	public String dequeue(){
		if(head == null) return null;
		String tmp = head.data;
		head = head.next;
		if(head == null){
			tail = null;	
		}
		return tmp;
	}

	public class Node(){
		public Node next;
		public String data;
		public Node(){
		}
		public Node(String data,Node next){
			this.data = data;
			this.next = next;
		}
	}
}

循环队列

在基于数组实现的队列中,当tail=n时,会有数据搬移操作,这样入队操作时就会受到影响.
循环队列可以避免数据搬移.

在一个大小为8的队列中.假如此时head=4,tail=7.当有一个新元素a入队时,我们放入下标为7的位置.但这个时候我们不把tail更新为8,而是移动到下标为0的位置.当再有一个新元素b入队时,我们将b放在下标为0的位置,然后tail加1更新为 1.

通过这样的方法避免了数据搬移的操作.其中代码实现的重点是确定好队空和队满的判断条件.

队空的判断条件仍然是head == tail,队满的条件是(tail+1)%n=head.另外在循环队列中,队满时,tail指向的位置是没有存储数据的,所以循环队列会浪费一个数组空间

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
public class CircularQueue{
	private String[] items;
	private int n;
	private int head = 0;
	private int tail = 0;
	public CircularQueue(int n){
		items = new String[n];
		this.n = n;
	}

	//入队操作
	public boolean enqueue(String item){
		if((tail + 1)%n == head) return false;
		items[tail] = item;
		tail = (tail + 1)%n;
		return true;
	}

	//出队操作
	public String dequeue(){
		if(head == tail) return "";
		String tmp = items[head];
		head = (head + 1) % n;
		return tmp;
	}
}

阻塞队列和并发队列

阻塞队列

阻塞队列其实就是在队列基础上增加了阻塞操作.简单来说就是在队列为空时,从队头取数据会被阻塞.直到队列中有数据了再返回.如果队列已满,那么插入数据的操作就会被阻塞,直到队列中有空闲位置后再插入数据,再返回.即生产者–消费者模型.

并发队列

线程安全的队列我们叫作并发队列。最简单的方式是在enqueue和dequeue方法上加锁.但是锁粒度大并发就会降低.利用CAS原子操作,可以实现非常高效的并发队列.