栈
后进先出,先进后出,这就是典型的“栈”结构。
当一个数据集合只涉及在一段插入和删除数据,并且满足后进先出、先进后出的特点,我们就应该首选“栈”这种数据结构。
用数组实现的栈,叫做顺序栈,用链表实现的栈。叫做链式栈。
// 基于数组实现的顺序栈
public class ArrayStack {
private String[] items; // 数组
private int count; // 栈中元素个数
private int n; // 栈的大小
// 初始化数组,申请一个大小为 n 的数组空间
public ArrayStack(int n) {
this.items = new String[n];
this.n = n;
this.count = 0;
}
// 入栈操作
public boolean push(String item) {
// 数组空间不够了,直接返回 false,入栈失败。
if (count == n) return false;
// 将 item 放到下标为 count 的位置,并且 count 加一
items[count] = item;
++count;
return true;
}
// 出栈操作
public String pop() {
// 栈为空,则直接返回 null
if (count == 0) return null;
// 返回下标为 count-1 的数组元素,并且栈中元素个数 count 减一
String tmp = items[count-1];
--count;
return tmp;
}
}
栈的经典应用场景就是函数调用栈。操作系统给每个线程分配了一块独立的内存空间,这块内存被组织成“栈”这种结构,用来存储函数调用时的临时变量。
为什么函数调用要用“栈”来保存临时变量呢?用其他数据结构不行吗?
其实,我们不一定非要用栈来保存临时变量,只不过如果这个函数调用符合后进先出的特性,用栈这种数据结构来实现,是最顺理成章的选择。
从调用函数进入被调用函数,对于数据来说,变化的是什么呢?是作用域。所以根本上,只要能保证每进入一个新的函数,都是一个新的作用域就可以。而要实现这个,用栈就非常方便。在进入被调用函数的时候,分配一段栈空间给这个函数的变量,在函数结束的时候,将栈顶复位,正好回到调用函数的作用域内。
栗子:A调用B,B又调用C,那么就需要先把C执行完,结果赋值给B中的临时变量,B的执行结果再赋值给A的临时变量,嵌套越深的函数越需要被先执行,这样刚好符合栈的特点,因此每次遇到函数调用,只需要压栈,最后依次从栈顶弹出依次执行即可。
队列
先进先出,就是典型的“队列”。
用数组实现的队列叫做顺序队列,用链表实现的队列叫做链式队列。
队列作为一种非常基础的数据结构,应用非常广泛,特别是一些具有某些额外特性的队列,比如循环队列、阻塞队列、并发队列。他们在很多偏底层系统、框架、中间件的开发中,起着关键作用。比如高性能队列 Disruptor、Linux 环形缓存,都用到了循环并发队列;Java concurrent 并发包利.用 ArrayBlockingQueue 来实现公平锁等。
- 顺序队列
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 String dequeue() {
// 如果 head == tail 表示队列为空
if (head == tail) return null;
String ret = items[head];
++head;
return ret;
}
}
// 入队(存在问题:当tail移动到最右边的时候,即使数组中有空闲空间,也无法继续添加数据)
public boolean enqueue(String item) {
// 如果 tail == n 表示队列已经满了
if (tail == n) return false;
items[tail] = item;
++tail;
return true;
}
//入队 (当tail在最右边,且数组中有空闲空间,通过数据搬移来解决上面的问题)
// 入队操作,将 item 放入队尾
public boolean 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;
}
-
循环队列
顺序队列中,当 tail 移动到数组的最右端的时候,会有数据搬移操作,这样入队操作性能会受到影响。循环队列可以解决这个问题。
当tail等于7的时候,再向里面添加元素,tail会变成0.png
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 boolean 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;
}
}
-
阻塞队列其实就是在队列的基础上增加了阻塞操作。简单来说,就是在队列为空的时候,从队头取数据会被阻塞,直到队列中有了数据才能返回;如果队列已经满了,那么插入数据的操作就会阻塞,直到队列中有空的位置后再插入数据,然后再返回。其实就是一个“生产者-消费者模型”。
-
并发队列就是线程安全的队列。对简单的实现方式是直接在入队和出队的方法上加锁,但是锁粒度大并发度会比较低,同一时刻仅允许一个存或者说取操作。基于数组的循环队列,利用 CAS 原子操作,可以实现非常高效的并发队列。
在入队前,获取tail位置,入队时比较tail是否发生变化,如果否,则允许入队,反之,本次入队失败。出队则是获取head位置,进行 CAS 原子操作。
网友评论