简述
栈和队列结构是表结构基础上针对特定操作行为的数据结构。
特性：
- 栈：先进后出。放入栈中的元素具有先进后出的特性。就像一队人走进了死胡同，后面的人必须先出去，这样前面的人才可以出来；
- 队列：先进先出。队列中的元素先进先出的性质。与我们日常排队一样，先排队的人先出队。
栈和队列说明
栈
我们使用数组来实现栈结构，从坐标0开始依次插入数据(入栈)，从最后元素的坐标向0依次取出队列(出栈)。列出关键的两个操作入栈和出栈。
重点：
- 扩容
- size指向数组中最有一个元素的下一个位置
- 利用数组实现，栈底的元素索引一定为0
public class MyStack<E> {
private Object[] elements;//数组实现栈结构
private int size = 0;//当前栈中元素个数，也是最后一个元素坐标的下一个位置
public MyStack(){//构造函数初始化容量为5的栈
elements = new Object[5];
}
public MyStack(int initCapacity){//自定容量的栈
elements = new Object[initCapacity];
}
public E push(E item) {//入栈
if (size >= elements.length){//如果元素个数为数组容量，则需要扩容
grow();//扩容操作
}
elements[size++] = item;//入栈，size自增1
return item;
}
public E pop() {//出栈
if (size > 0){//如果栈有元素出栈
return (E)elements[--size];//size先减1，返回最有一个元素
}
return null;
}
private void grow(){//扩容操作
int len = elements.length;//保持原有数组长度
Object[] tmp = elements;//复制原有数组
elements = new Object[len * 2];//扩容为当前容量的2倍
System.arraycopy(tmp, 0, elements, 0, len);//复制数组
}
public static void main(String[] args){//测试用例
MyStack<String> stack = new MyStack<String>();
stack.push("1");
stack.push("2");
stack.push("3");
stack.push("4");
stack.push("5");
String res = stack.push("6");
String o1 = stack.pop();
String o2 = stack.pop();
String o3 = stack.pop();
String o4 = stack.pop();
String o5 = stack.pop();
String o6 = stack.pop();
stack.push("7");
String o7 = stack.pop();
}
}
队列
队列数组实现比起栈实现要相对复杂，这是由于队列先进先出导致的出队之后数组的头部位置元素无用却仍旧在内存中，而尾部位置仍需要不断入队，如果使用普通数组会导致数组占用内存越来越多，但数组的前部空间浪费。我们使用循环数组实现，循环数组就是数组的首尾相连，形成一个环，读取尾部元素之后再读取头部元素。循环数组的实现定义一个数组，我们利用指针遍历时按模取余，循环遍历数组元素。
重点：
- 循环数组实现队列，会损失一个元素空间。如果数组大小是5，则实际存储的元素个数为4，这是由需要定义两个索引分别表示队列的头和尾，为了区分队列满和空的情况导致。
- 空队列条件(也是初始化的条件)：front == rear，头索引等于尾索引，两者在数组上重合表示没有元素。
- 满队列条件：(rear + 1) % elements.length == front，尾索引加1取模等于头索引，在循环数组中也就是尾指针刚好在头指针前一位。此时队列索引rear处不能放置元素，如果放置，rear加1取模之后就满足了空队列条件，而实际上此时是满队列的情况。
- 循环数组，定义一个数组，指针遍历时按模取余，循环遍历数组元素来实现。
public class MyQueue<E> {
private Object[] elements;//数组实现队列
private int front = 0;//头索引位置
private int rear = 0;//尾索引位置
public MyQueue(){//初始化数组容量为5
elements = new Object[5];
}
public MyQueue(int initCapacity){//初始化设定的容量数组
elements = new Object[initCapacity];
}
public boolean add(E item){//添加元素到队尾
if ((rear + 1) % elements.length == front){//判断队列是满了
return false;
}
elements[rear] = item;//插入元素在rear位置
rear = (rear + 1) % elements.length;//rear自增1取模指向下一个位置索引
return true;
}
public E remove(){//删除队头元素
if (front == rear){//判断队列是否为空
return null;
}
E ele = (E)elements[front];//返回front处元素
front = (front + 1) % elements.length;//front自增1取模指向下一个索引位置
return ele;
}
public static void main(String[] args){//测试用例
MyQueue<String> queue = new MyQueue<String>();
queue.add("1");
queue.add("2");
queue.add("3");
queue.add("4");
boolean r1 = queue.add("5");
String s1 = queue.remove();
String s2 = queue.remove();
String s3 = queue.remove();
String s4 = queue.remove();
String s5 = queue.remove();
queue.add("6");
String s6 = queue.remove();
}
}
补充说明
上面的栈实现代码存在着一个内存的泄露问题。如果栈先是快速增长到一个很大容量，然后在收缩，那么从栈中弹出来的对象将不会被当作垃圾回收，仍旧会一直驻留在内存中，这部分引用称为过期引用（obsolete reference）。只有当栈对象被回收时，过期引用才会得到回收，这类内存泄露问题很难被发现，因为实际上很难会表现出明显的失败导致系统崩溃。解决方法就是元素一旦出栈，清空其引用即可。有兴趣可以参考《Effective Java》第三版第7条，消除过期的对象引用。
代码如下：
public E pop() {//出栈
if (size > 0){//如果栈有元素出栈
E result = (E)elements[--size];//size先减1，返回最有一个元素
elements[size] = null;
return result;
}
return null;
}
总结
栈和队列实现简单，操作简单，但在实际中用途非常广泛，例如括号匹配问题前括号入栈，遇到后括号执行出栈操作，后括号与弹出的括号判断是否匹配；弹出异常时使用栈存储异常信息；系统不能全部马上响应时，把请求入队按照先到先执行原则从队列中依次执行请求；多个线程请求互斥资源，设置等待队列让线程依次等待，每次资源释放都从队列中取出最早排队的线程赋予资源。栈和队列在实际开发中占重要作用，是计算机数据结构学科的基础。
