数据结构与算法之栈与队列

线性表包括数组，链表（单链表，双向链表，循环链表，双向循环链表，静态链表），栈（顺序栈，链式栈），队列（普通队列，双端队列，阻塞队列，并发队列，阻塞并发队列）。

栈

栈是限定仅在表位进行插入和删除操作的线性表，栈只有两种操作：入栈和出栈，LIFO (后进先出)。
栈可以用数组来实现（顺序栈）， 也可以用链表实现（链式栈）。
入栈和出栈的代码演示

package dataStructures;

public class Stack {
    private String[] items;
    private int size;
    private int count;

    public Stack(int size) {
        this.size = size;
        this.count = 0;
        items = new String[size];
    }

    public boolean push(String item) {
        if (count == size) return false;
        items[count] = item;
        ++count;
        return true;
    }

    public String pop() {
        if (count > 0) {
            String item = items[count];
            --count;
            return item;
        }
        return null;
    }
}

队列

队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。队列是一种先进先出（FIFO）的线性表，允许插入的一端称为队尾，允许删除的一端称为队头。队列也只有两种操作入队（enqueue）和出队（dequeue）。队列跟栈一样，也可以由数组或链表实现，分别称为顺序队列和链式队列

package dataStructures;

public class ArrayQueue {
    private String[] items;
    private int size = 0;
    private int head = 0;
    private int tail = 0;

    public ArrayQueue(int size) {
        this.size = size;
        items = new String[size];
    }

    public boolean enqueue(String item) {
        if (tail == size) {//tail已经超出数组空间了
            if (head == 0) return false;//队列已满
            for (int i = head; i < tail; ++i) {
                items[i - head] = items[i];
            }
            tail -= head;
            head = 0;
        }
        items[tail] = item;
        ++tail;
        return true;
    }

    public String dequeue() {
        if (head == tail) return null;
        String item = items[head];
        ++head;
        return item;
    }
}

上述队列会发生数据搬移操作，所以多少会影响性能。
下面介绍循环队列，所谓循环队列，顾名思义，就是首尾相接的队列。
当 head = tail 的时候说明队列是空的，当 head 与 tail 相差为1是说明队列已满，但对于循环队列来说 head 有时候会比 tail 大，有时会比 tail 小，所以我们用取模的形式（tail+1）%QueueSize = head 这是说明队列已满，由于此时tail还没有插入值，所有对于循环队列来说，总有一个是空的

package dataStructures;
//循环队列
public class CircularQueue {
    private String items[];
    private int head = 0;
    private int tail = 0;
    private int queueSize = 0;

    public CircularQueue(int size) {
        this.queueSize = size;
        items = new String[size];
    }

    private boolean enqueue(String item) {
        //队列已满
        if ((tail + 1) % queueSize == head) return false;
        items[tail] = item;
        tail = (tail + 1) % queueSize;
        return true;
    }

    private String dequeue() {
        //队列为空
        if (head == tail) return null;
        String value = items[head];
        head = (head + 1) % queueSize;
        return value;
    }
}