Stacks and Queue
一、基本概念
- 堆栈：检测最初退出的对象。后进先出，插入元素又叫入栈（push），去掉最近退出的元素又叫出栈（pop）。
- 队列：检测最先退出的对象。先进先出，插入元素又叫入队（enqueue），去掉最近退出的元素又叫出队（dequeue）。
二、stacks：基于链表实现
指针始终指向链表的第一个节点，在最后方进行插入和删除操作
以字符串为存储对象的 stacks 举例
stack 须要实现的API
外部类
private class Node { String item; Node next;}pop出栈操作
1、 保留头节点中存储的对象
String item = first.item;2、扭转指针指向下一个节点（本来的头结点会被垃圾回收器回收）
first = first.next;3、 返回1中保留下来的对象
return item;push 入栈操作
1、创立一个新指针指向以后的头结点
Node oldfirst = first2、创立一个新的头节点，并将first指针指向该节点
first = new Node();3、给新节点设置实例变量
first.item = "not"first.next = oldfirst三、stacks：基于链表实现的性能体现
- 工夫： 因为没有for循环，每个办法都只有个别指令，因而是常数项的复杂度
- 空间：节点数为N，则内存占用 ~40N 字节：
| 内存占用项 | 占用空间（bytes） |
|---|---|
| 对象头部 | 16 |
| 外部对象额定的开销 | 8 |
| 指向字符串的指针 | 8 |
| 指向下一个节点的指针 | 8 |
四、stacks：基于数组实现
基于数组实现的缺点
数组是有容量的，存储的数量可能超过容量，须要对其进行解决。
public class FixedCapacityStackOfStrings { private String[] s; private int N = 0; //这里假如提前设置好数组大小，之后会解决这个问题 public FixedCapacityStackOfStrings(int capacity) { s = new String[capacity]; } public boolean isEmpty() { return N == 0; } public void push(String item) // 应用以后索引插入数组，而后递增N { s[N++] = item; } public String pop() // 递加N，而后应用索引拜访数组元素 { return s[--N]; } }五、对于stacks数组实现更多的思考
数组的上溢和下溢
下溢(Underflow)：从空堆栈中进行pop操作会抛出异样
上溢(Overflow)：扩容数组容量（resizing array）
空值: 容许空值插入
对象游离(loitering)