数据结构-3-栈&队列

注意：本篇文章基本为转载。

栈简介

栈的特点时先进后出。
栈既可以用数组来实现，也可以用链表来实现。用数组实现的栈，我们叫作顺序栈，用链表实现的栈，我们叫作链式栈。

顺序栈的JAVA实现

顺序栈的JAVA实现：

// 基于数组实现的顺序栈
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;
    }
}

栈在编程中的应用

一个类加载到内存中是使用的栈的模型，依次加载到内存中，比如调用一个方法，调用就是加载到方法栈中，调用完成就弹栈，继续执行调用方法后面的代码。

栈在括号匹配中的应用

我们假设表达式中只包含三种括号，圆括号 () 、方括号 [] 和花括号 {} ，并且它们可以任意嵌套。比如， {[{}]} 或 [{()}([])] 等都为合法格式，
而 {[}()] 或 [({)] 为不合法的格式。那我现在给你一个包含三种括号的表达式字符串，如何检查它是否合法呢？

这里也可以用栈来解决。我们用栈来保存未匹配的左括号，从左到右依次扫描字符串。当扫描到左括号时，则将其压入栈中；当扫描到右括号时，从栈顶取出一
个左括号。如果能够匹配，比如 “(” 跟 “)” 匹配， “[” 跟 “]” 匹配， “{” 跟 “}” 匹配，则继续扫描剩下的字符串。如果扫描的过程中，遇到不能配对的右括号，或者栈中没
有数据，则说明为非法格式。
当所有的括号都扫描完成之后，如果栈为空，则说明字符串为合法格式；否则，说明有未匹配的左括号，为非法格式。

队列简介

队列就是为了实现先来后到问题的排队效果。队列跟栈一样，也是一种操作受限的线性表数据结构。

栈只支持两个基本操作：入栈push()和出栈pop()。队列跟栈非常相似，支持的操作也很有限，最基本的操作也是两个：入队enqueue()，放一个数据到队列尾部；出队dequeue()，从队列头部取一个元素。

队列的概念很好理解，基本操作也很容易掌握。作为一种非常基础的数据结构，队列的应用也非常广泛，特别是一些具有某些额外特性的队列，比如循环队列、
阻塞队列、并发队列。它们在很多偏底层系统、框架、中间件的开发中，起着关键性的作用。比如高性能队列 Disruptor 、 Linux 环形缓存，都用到了循环并发队
列； Java concurrent 并发包利用 ArrayBlockingQueue 来实现公平锁等。

用数组实现的队列叫作顺序队列，用链表实现的队列叫作链式队列。

顺序队列的JAVA实现

// 用数组实现的队列
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 boolean enqueue(String item) {
        // 如果tail == n 表示队列已经满了
        if (tail == n) return false;
        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 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;
}

效果如下：

循环队列

循环队列的数据组首位相连，使得在队列尾部添加元素时不需要进行上述的搬移工作，直接在数组环上进行移动首尾指针即可。

代码实现会更加的复杂：

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;
    }
}

阻塞队列和并发队列

阻塞队列其实就是在队列基础上增加了阻塞操作。简单来说，就是在队列为空的时候，从队头取数据会被阻塞。因为此时还没有数据可取，直到队列中有了数据
才能返回；如果队列已经满了，那么插入数据的操作就会被阻塞，直到队列中有空闲位置后再插入数据，然后再返回。

类似于 生产者-消费者模型。