栈&队列

栈

后进先出，先进后出，这就是典型的“栈”结构。

当一个数据集合只涉及在一段插入和删除数据，并且满足后进先出、先进后出的特点，我们就应该首选“栈”这种数据结构。

用数组实现的栈，叫做顺序栈，用链表实现的栈。叫做链式栈。

// 基于数组实现的顺序栈
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 原子操作。