线性表2：栈和队列

数组与链表在数据结构上是十分基础的，我们的一些其他的数据结构也使用到了这样的基础结构。

栈

从栈的操作特性上来看，栈是一种“操作受限”的线性表，只允许在一端插入和删除数据。 当某个数据集合只涉及在一端插入和删除数据，并且满足后进先出、先进后出的特性，这时我们就应该首选“栈”这种数据结构。

栈既可以用数组来实现，也可以用链表来实现。用数组实现的栈，我们叫作顺序栈，用链表实现的栈，我们叫作链式栈。

为了更好的规范栈实现，我们定义栈接口如下：

package cn.lishiyuan.algorithm.stack;  
  
public interface LeeStack<T> {  
    // 当前栈有多少元素
    int count();  
    // 是否为空
    boolean isEmpty();  
    // 压栈
    void push(T data);  
    // 查看不弹出（瞟一眼）
    T peek();  
    // 弹出栈顶元素
    T pop();  
}

通常栈只有push（压栈），和pop（弹栈）两种操作。由于操作有限，所以其实现起来是十分方便。

下面是顺序栈的实现：

package cn.lishiyuan.algorithm.stack;  
  
import java.util.Arrays;  
  
/**  
 * 使用数组结构实现的栈，自动扩容（其实是不合理的），不会缩容  
 * @param <T>  
 */  
public class ArrayStack<T> implements LeeStack<T>{  
  
    private Object[] array;  
  
    /**  
     * 当前位置  
     */  
    private int count = 0;  
  
    public ArrayStack(int size){  
        if (size <= 0) {  
            throw new IllegalArgumentException();  
        }  
        array = new Object[size];  
    }  
  
    public int count(){  
        return count;  
    }  
  
    @Override  
    public boolean isEmpty() {  
        return count == 0;  
    }  
  
    @Override  
    public void push(T data) {  
        // 达到最大值  
        if(count == array.length){  
            // 扩容  
            Object[] newArray = new Object[array.length * 2];  
            System.arraycopy(array, 0, newArray, 0, array.length);  
            array = newArray;  
        }  
        array[count] = data;  
        count++;  
    }  
  
    @Override  
    public T pop() {  
        if(count == 0){  
            return null;  
        }  
        count--;  
        T result = (T) array[count];  
        array[count] = null;  
        return result;  
    }  
  
    @Override  
    public T peek() {  
        if(count == 0){  
            return null;  
        }  
        T result = (T) array[count-1];  
        return result;  
    }  
  
    @Override  
    public String toString() {  
        return Arrays.toString( Arrays.copyOf(array, count));  
    }  
}

jdk自身的Stack类实现就是基于Vector也就是数组实现的。

下面是链式栈的实现：

package cn.lishiyuan.algorithm.stack;  
  
import cn.lishiyuan.algorithm.list.LinkedList;  
  
/**  
 * 使用链表结构实现的栈  
 * @param <T>  
 */  
public class LinkedStack<T> implements LeeStack<T>{  
  
    private final LinkedList<T> linkedList;  
  
    public LinkedStack(){  
        linkedList = new LinkedList<>();  
    }  
  
    public int count(){  
        return linkedList.size();  
    }  
  
    @Override  
    public boolean isEmpty() {  
        return linkedList.isEmpty();  
    }  
  
    @Override  
    public void push(T data) {  
       linkedList.addFirst(data);  
    }  
  
    @Override  
    public T pop() {  
        if(linkedList.isEmpty()){  
            return null;  
        }  
        T t = linkedList.get(0);  
        linkedList.removeFirst();  
        return t;  
    }  
  
    public T peek() {  
        if(linkedList.isEmpty()){  
            return null;  
        }  
        T t = linkedList.get(0);  
        return t;  
    }  
  
    @Override  
    public String toString() {  
        return linkedList.toString();  
    }  
}

这里的实现使用到了线性表1：数组与链表里面双向链表实现。

栈，由于其只操作栈顶元素，因此它是一种极其高效的数据结构。不论式push还是pop，他们的时间复杂度都是O(1)。在某些动态扩容的栈实现中可能会周期性需要扩容，而copy数组数据，该次操作的时间复杂度式O(n)，但是均摊到push操作上面，其时间复杂度依然是O(1)。

栈在实践中也是得到了广泛的应用。比如方法调用（函数调用）的实现基本上都是栈结构
我们的程序运行的表达式，操作数也是基于栈结构实现的。
一些语言的协程（虚拟线程）的实现也是使用栈结构实现的。

队列

与栈结构先进后出的规则不同，队列是一种先进先出的结构。我们知道，栈只支持两个基本操作：入栈 push()和出栈 pop()。队列跟栈非常相似，支持的操作也很有限，最基本的操作也是两个：入队 enqueue()，放一个数据到队列尾部；出队 dequeue()，从队列头部取一个元素。所以，队列跟栈一样，也是一种操作受限的线性表数据结构。

队列在实际生产中被广泛应用，由于队列的特性极其适合生产消费模式，所以所有消息队列，阻塞队列，公平锁等等都使用到了队列。实际上，对于大部分资源有限的场景，当没有空闲资源时，基本上都可以通过“队列”这种数据结构来实现请求排队，我们在实际使用中也是经常通过队列来协调资源。

和栈一样，队列的实现可以基于链表，也可以基于数组。基于链表实现的队列叫做链式队列，基于数组实现的队列叫做顺序队列。数组大小始终是有限的，有限的队列称为有界队列，链式队列可以无线延伸，无限大小的队列称为无界队列。

我们可以想象到，链式队列实现该数据结构有着天然的优势，基于数组实现时，如果由于指针移动

队列首指针       队列尾指针
|↓|               |↓|
[a][b][c][d][e][f][ ]

队列的首指针和index=0之间必然存在空隙，如果每次dequeue都进行数据移动操作，那么必然使得性能低下。一个优化思路是，在队列尾指针到达数组index上限的时候再做数据移动操作，我们只记录队列首指针当前的位置。另一个优化思路是，再队列尾指针到达数组上限的时候，重新回到index=0，使得数据结构在逻辑上成环，那么该队列便成了循环队列。 这样在任何时候都不需要进行数据移动操作。

为了更好的实现队列，我定义接口如下：

package cn.lishiyuan.algorithm.queue;  
  
public interface LeeQueue<T> {  
    // 当前队列有多少元素  
    int count();  
    // 是否为空  
    boolean isEmpty();  
    // 入队  
    void enqueue(T data);  
    // 出队  
    T dequeue();  
}

顺序循环队列的实现：

package cn.lishiyuan.algorithm.queue;  
  
import java.util.Arrays;  
  
/**  
 * 顺序队列  
 * @param <T>  
 */  
public class ArrayQueue<T> implements LeeQueue<T>{  
    private Object[] array;  
    // 队列首位置，取数据位置  
    private int front = 0;  
  
    // 队列尾位置，插入数据位置  
    private int rear = 0;  
  
    private int count = 0;  
  
    public ArrayQueue(int size) {  
        array = new Object[size];  
    }  
  
  
    @Override  
    public int count() {  
        return count;  
    }  
  
    @Override  
    public boolean isEmpty() {  
        return count == 0;  
    }  
  
    @Override  
    public void enqueue(T data) {  
        if (count == array.length) {  
            throw new IllegalStateException("队列已满");  
        }  
        array[rear] = data;  
        // 更新插入位置  
        rear = (rear + 1) % array.length;  
        count ++;  
  
    }  
  
    @Override  
    public T dequeue() {  
        if (count == 0) {  
            return null;  
        }  
        T data = (T) array[front];  
        array[front] = null;  
        front = (front + 1) % array.length;  
        count--;  
        return data;  
    }  
  
    @Override  
    public String toString() {  
        return Arrays.toString(array);  
    }  
}

通过index = (index + 1) % array.length保证队列的循环。一种更加极致的优化方式是保证数组长度是2的n次幂，通过index = (index + 1) & (array.length - 1)更加高效的计算移动后的index。

链式队列的实现

package cn.lishiyuan.algorithm.queue;  
  
import cn.lishiyuan.algorithm.list.LinkedList;  
  
/**  
 * 链式队列  
 * @param <T>  
 */  
public class LinkedQueue<T> implements LeeQueue<T>{  
  
    LinkedList<T> list ;  
  
    public LinkedQueue() {  
        list = new LinkedList<>();  
    }  
  
    @Override  
    public int count() {  
        return list.size();  
    }  
  
    @Override  
    public boolean isEmpty() {  
        return list.isEmpty();  
    }  
  
    @Override  
    public void enqueue(T data) {  
        list.addLast(data);  
    }  
  
    @Override  
    public T dequeue() {  
        if (list.isEmpty()){  
            return null;  
        }  
        T t = list.get(0);  
        list.removeFirst();  
        return t;  
    }  
  
    @Override  
    public String toString() {  
        return list.toString();  
    }  
}

链式队列的实现使用到了线性表1：数组与链表中链表的实现。

在上文队列的实现中，顺序队列由于是循环队列，没有数据移动操作，所以在其之上的队列操作都是O(1)实践复杂度的，而链式队列的操作只涉及head和tail节点的操作，在我的实现中这些操作本质上都是直接操作双端链表中保存的head和tail节点，所以其时间复杂度也是O(1)。