概念
队列:先进者先出。与栈一样,也是一种受限的线性表,同样有两个基本操作:入队和出队。
队列实现
队列有两种实现方式:顺序队列和链式队列。
顺序队列
用数组实现的队列叫作顺序队列。
需要两个指针:head指针和tail指针,分别指向队头和队尾。
随着入队和出队操作,head和tail会移到最右边,即便还有空闲空间,也不通用再入队了。这时候要用数据搬移。在入队时,把数据数组前端移动。
队列的数据搬移// 用数组实现的队列
public class ArrayQueue
{
// 数组:items,数组大小:n
private string[] items;
private int n = 0;
// head表示队头下标,tail表示队尾下标
private int head = 0;
private int tail = 0;
// 申请一个大小为capacity的数组
public ArrayQueue(int capacity)
{
items = new string[capacity];
n = capacity;
}
// 入队
public bool Enqueue(string item)
{
// tail == n表示队列末尾没有空间了
if (tail == n)
{
// tail ==n && head==0,表示整个队列都占满了
if (head == 0) return false;
// 数据搬移
for (int i = head; i < tail; ++i)
{
items[i - head] = items[i];
}
// 搬移完之后重新更新head和tail
tail -= head;
head = 0;
}
items[tail] = item;
++tail;
return true;
}
// 出队
public string Dequeue()
{
// 如果head == tail 表示队列为空
if (head == tail) return null;
// 为了让其他语言的同学看的更加明确,把--操作放到单独一行来写了
string ret = items[head];
++head;
return ret;
}
}
链式队列
用链表实现的队列叫作链式队列。
需要两个指针:head指针和tail指针,分别指向链表第一个结点和最后一个结点。
链式队列的入队&出队// 用链表来实现的队列
public class LinkedListQueue
{
// 用来记录队列可用元素个数
private int n = 0;
// head表示第一个结点,tail表示最后一个结点
private MyLinkedListNode head = null;
private MyLinkedListNode tail = null;
// 申请一个大小为capacity的数组
public LinkedListQueue(int capacity)
{
n = capacity;
}
// 入队
public bool Enqueue(string item)
{
// n == 0表示队列末尾没有空间了
if (n == 0)
{
return false;
}
// 第一次入队
if (head == null || tail == null)
{
head = tail = new MyLinkedListNode(item);
}
else
{
tail.Next = new MyLinkedListNode(item);
tail = tail.Next;
}
--n;
return true;
}
// 出队
public string Dequeue()
{
// 如果head == null 表示队列为空
if (head == null) return null;
// 为了让其他语言的同学看的更加明确,把--操作放到单独一行来写了
string ret = head.Data;
head = head.Next;
++n;
return ret;
}
public class MyLinkedListNode
{
public MyLinkedListNode(string data)
{
Data = data;
}
public string Data { get; set; }
public MyLinkedListNode Next { get; set; }
}
}
循环队列
上面的数组实现,在tail==n时,会有数据搬移操作,这样入队操作性能就会受到影响。
循环队列是一种特殊的队列,长得像个环,原来数组是有头有尾的,是一条直线,现在把首尾相连,形成一个环,如下图:
循环队列队列空的条件:head==tail
队列满的条件:(tail+1)%n=head
public class CircularQueue
{
// 数组:items,数组大小:n
private string[] items;
private int n = 0;
// head表示队头下标,tail表示队尾下标
private int head = 0;
private int tail = 0;
// 申请一个大小为capacity的数组
public CircularQueue(int capacity)
{
items = new string[capacity];
n = capacity;
}
// 入队
public bool Enqueue(string item)
{
// 队列满了
if ((tail + 1) % n == head) return false;
items[tail] = item;
tail = (tail + 1) % n;
return true;
}
// 出队
public string Dequeue()
{
// 如果head == tail 表示队列为空
if (head == tail) return null;
string ret = items[head];
head = (head + 1) % n;
return ret;
}
}
循环队列的关键要确定好队空和队满的判定条件。
阻塞队列和并发队列
阻塞队列就是在队列基础上增加了阻塞操作。简单来说,就是在队列为空的时候,从队头取数据会被阻塞。
可以使用阻塞队列来实现“生产者-消费者模型”。
1对1阻塞队列通过协调“生产者”和“消费者”的个数,来提高数据的处理效率。
1对多阻塞队列并发队列就是要求线程安全的队列。通过在enqueue()和dequeue()方法上加锁。
线程池实现
有两种处理策略:
- 非阻塞的处理方式,直接拒绝任务请求。
- 阻塞的处理方式,将请求排除,等有空闲线程时,取出请求继续处理。
而队列有两种实现方式:基于数组和基于链表
- 基于链表,可以实现一个支持无限排除的无界队列,但可能会导致响应时间过长,对于响应时间比较敏感的系统,不适合采用这种方式。
- 基于数组实现的有界队列,队列的大小有限,超过队列大小时会拒绝请求,但设置一个合理的队列大小是非常讲究的,既不能太大,也不能太小而无法充分利用资源,发挥最大性能。
<font color=red>对于大部分资源有限的场景,当没有空闲资源时,基本上都可以通过“队列”这种数据结构来实现请求排除。</font>
课后思考
1.除了线程池这种池结构会用到队列排队请求,你还知道有哪些类似的池结构或者场景中会用到队列的排队请求呢?
比如数据库连续池、Web应该的请求队列等。
2.今天讲到并发队列,关于如何实现无锁并发队列,网上有非常多的讨论。对这个问题,你怎么看呢?
在多线程高并发编程的时候,最关键的问题就是保证共享对象的安全访问。通常是用synchronized 来处理,其实加锁本质上是将并发转变为串行来实现的,势必会影响吞吐量。
而最高效的做法就是不加锁,那就是CAS,Compare and Swap即比较并替换,设计并发算法时常用到的一种技术。
CAS实现原理:CAS有三个操作数:内存值V、旧的预期值A、要修改的值B,当且仅当预期值A和内存值V相同时,将内存值修改为B并返回true,否则什么都不做并返回false。
网友评论