什么是队列
队列也是一种操作受限制的线性表,只允许在表的前端进行删除,也就是出队,而在表的后端进行插入,即入队。
举一个生活中常见的例子,我们经常会遇到排队办事,先来的排在前边先办理,后来的排在后边,不允许插队。先进先出,这就是典型的队列。
队列的实现
队列的概念很容易理解,操作也比较简单,很容易掌握。
跟栈一样,队列也能用数组和链表来实现,用数组实现的队列叫顺序队列,用链表实现的队列叫链式队列。
下面我们先来看一下用数组的实现方式。
public class ArrayQueue {
private String[] items;
private int n = 0;
private int head = 0;
private int tail = 0;
public ArrayQueue(int n){
items = new String[n];
this.n = n;
}
public boolean Enqueue(String item){
if(tail == n){
return false;
}
items[tail++] = item;
return true;
}
public String Dequeue(){
if(head == tail){
return null;
}
String item = items[head++];
return item;
}
}
队列的数组实现比栈的实现稍微复杂一点点,队列需要两个指针,一个指向队头的 head 指针,一个指向队尾的 tail 指针。同样老办法,我们用画图来更清楚的了解一下这个过程。
image.png
如果这个时候我们调用一次出队,那么 head 指针就指向 1 的位置,并把 0 的位置的元素移除出队。如图。
image.png如果这个时候插入一个新的元素,那么 tail 指针就指向 5 的位置,然后把新的元素放到 4 的位置。
image.png我们通过图可以看到,这种实现方法有一个缺点,那就是随着我们不断的入队操作,等到 tail 指向最后一位的时候就没有办法接受新的元素入队了,即使前边有空闲的空间没有元素。所以我们来优化一下我们的代码,当 tail 等于数组的长度 n 的时候,这个时候如果再有新的元素入队,我们就看数组前边是不是有空闲的空间,如果有我们就把队列的元素整体向前移动几个单位。
public class ArrayQueue {
private String[] items;
private int n = 0;
private int head = 0;
private int tail = 0;
public ArrayQueue(int n){
items = new String[n];
this.n = n;
}
public boolean Enqueue(String item){
if(tail == n){
if(head == 0){
return false;
}
for (int i = head; i<tail;i++){
items[i-head] = items[I];
}
tail -= head;
head = 0;
}
items[tail++] = item;
return true;
}
public String Dequeue(){
if(head == tail){
return null;
}
String item = items[head++];
return item;
}
}
老办法,画图来展示这一过程。
image.png这样就不会有空间的浪费了,但是还有个问题就是数组不能动态扩展,数组满了之后就不能再入队新的元素了,我们来再来修改一下让数组支持动态扩展。当数组满了的时候我们重新申请一个新的数组,长度为原数组的两倍,然后把原数组的元素移到新数组里,然后再进行入队操作。
public class ArrayQueue {
private String[] items;
private int n = 0;
private int head = 0;
private int tail = 0;
private String[] newItems;
public ArrayQueue(int n){
items = new String[n];
this.n = n;
}
public boolean Enqueue(String item){
if(tail == n){
if(head == 0){
newItems = new String[2*n];
for (int i=0;i<tail;i++){
newItems[i] = items[I];
}
items = newItems;
}else {
for (int i = head; i < tail; i++) {
items[i - head] = items[I];
}
tail -= head;
head = 0;
}
}
items[tail++] = item;
return true;
}
public String Dequeue(){
if(head == tail){
return null;
}
String item = items[head++];
return item;
}
}
同样,上图。
image.png还有一种特殊的数组实现是循环队列,当 tail == n 的时候我们不迁移数组的元素,而是去看数组下标为 0 的位置为不为空,如果为空的话我们直接入队新的元素,tail 就等于 1 。我们来看一下代码实现。
public class CycleArrayQueue {
private String[] items;
private int n;
private int head = 0;
private int tail = 0;
public CycleArrayQueue(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 null;
String str = items[head];
head = (head+1)%n;
return str;
}
}
下边我们来看一下队列的链表实现,同样我们需要两个指针,head 指向链表第一个结点,tail 指向链表最后一个结点。入队时 tail->next=new_node,tail=tail->next。出队时 head=head->next。
public class ListNodeQueue {
private ListNode head;
private ListNode tail;
public void Enqueue(String val){
ListNode node = new ListNode(val, null);
if(tail == null){
head = node;
tail = node;
}else {
tail.next = node;
tail = tail.next;
}
}
public String Dequeue(){
if(head == null){
return null;
}
String string = head.val;
head = head.next;
if(head == null){
tail = null;
}
return string;
}
class ListNode{
private String val;
private ListNode next;
public ListNode(String x, ListNode next) {
val = x;
this.next = next;
}
public String GetValue() {
return val;
}
}
}
队列的应用
前边将的都是一些基本的理论知识,那队列在实际的项目中都在什么情况下使用呢?阻塞队列和并发队列应用的比较广泛。
- 阻塞队列
阻塞队列实际就是在队列的基础上加上了阻塞操作,当队列为空时,出队操作就会被阻塞,因为队列里没有数据,直到队列里有数据之后才能返回;当队列满的时候,入队操作就会被阻塞,直到队列中有空闲的空间时再执行入队操作。
我们可以用阻塞队列很容易的实现一个”生产者-消费者“模型,这样我们可以有效的控制生产和消费的速度。当生产者生产的过快时,队列很快就满了,这个时候生产者就阻塞等待,直到消费者消费了,生产者才会被唤醒继续生产。反之消费者消费过快时也同样被阻塞。不仅如此,我们还可以通过调整生产者和消费者的个数,来实现生产和消费的供需平衡。 - 并发队列
在多线程应用中,多个线程同时操作队列,就会存在线程安全问题,处理这个问题的队列我们称为并发队列。最简答的方法就是在入队和出队的时候加锁,保证同时只有一个线程执行队列的入队或出队,但是这样以来就会大大降低线程的并发度。
我们可以用上边提到的数组实现的循环队列来解决这个问题,利用 CAS 的原子操作,可以实现非常高效的并发队列。因此,循环队列比链式队列应用的更为广泛。
欢迎关注公众号:「努力给自己看」
公众号200x200
网友评论