一. 栈
- 介绍
栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅能在表尾进行插入和删除操作。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。
栈是一种后进先出（Last In First Out LIFO）的数据结构。
栈
栈在计算机中有着不可思议的作用，比如撤销（Undo）操作、java程序调用的虚拟机栈、临时存储运算数据的操作数栈等等。
- 实现
public interface Stack<E> {
//将元素入栈
public void push(E item) ;
//将元素出栈
public E pop() ;
// 获取栈顶元素
public E peek() ;
// 栈是否为空
public boolean isEmpty();
}
//我们可以使用之前自定义的数组方式实现，只需要每次都从尾部添加和移除元素即可。
public class ArrayStack<E> implements Stack<E> {
private Array<E> array = new Array<>();
@Override
public void push(E item) {
array.addLast(item);
}
@Override
public E pop() {
return array.removeLast();
}
......
}
二. 队列
- 定义
队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。
入队和出队操作
队列是一种先进先出（First In First Out）的线性结构。
- 实现
public interface Queue<E> {
//获得 队列中的元素个数
int getSize();
// 队列是否为空
boolean isEmpty();
//入队
void enqueue(E e);
//出队
E dequeue();
//获得队首元素
E getFront();
}
//同样，我们可以使用之前自定义的动态数组完成队列的实现，只需要向数组尾部添加元素，从数组头部获取即可
public class ArrayQueue<E> implements Queue<E> {
private Array<E> array = new Array<>();
@Override
public void enqueue(E e) {
array.addLast(e);
}
@Override
public E dequeue() {
return array.removeFirst();
}
......
}
- 扩展
我们使用数组实现队列时，在出队时，由于移除的是数组中第一个位置的元素，所以会导致数组的其他元素往左移，使得出队的时间复杂度变为 O(n)。
所以我们可以将数组看做成一个环，在元素出队时不进行元素的移动，而是修改队首的指针；而在入队时，当数组的右侧已经无法容纳元素时，在扩容之前会首先寻找数组的左侧是否有空闲的位置，如果有出队的操作，则表示有空闲的位置，我们直接将入队的元素放置到数组的左侧，如果没有空闲的位置，则进行扩容。具体流程如下：
入队和出队操作
public class LoopQueue<T> implements Queue<T>{
private T[] data;
private int font;
private int tail;
private int size;
public LoopQueue(int cap){
data = (T[])new Object[cap + 1];
}
@Override
public void enqueue(T t) {
//按照图中描述, 当 (tail + 1) % n = font 进行扩容
if((tail + 1) % data.length == font) resize(data.length * 2);
// 放置元素， 修改 tail 指向
data[tail] = t;
tail = (tail + 1)% data.length;
size ++;
}
@Override
public T dequeue() {
if(size == 0) return null;
//出队，修改 font 指针指向
T ret = data[font];
font = (font + 1)% data.length;
size -- ;
return ret;
}
private void resize(int newcap){
T[] newArr =(T[]) new Object[newcap];
int len = data.length;
for (int i = 0; i <= size; i++) {
newArr[i] = data[(font + i) % len];
}
this.data = newArr;
font = 0;
tail = size;
}
}
