一、栈(Stack)
1、概念
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据在栈顶。
2、栈的使用
public static void main(String[] args) {
Stack<Integer> s = new Stack();
s.push(1);
s.push(2);
s.push(3);
s.push(4);
System.out.println(s.size()); // 获取栈中有效元素个数---> 4
System.out.println(s.peek()); // 获取栈顶元素---> 4
s.pop(); // 4出栈，栈中剩余1 2 3，栈顶元素为3
System.out.println(s.pop()); // 3出栈，栈中剩余1 2 栈顶元素为3
if(s.empty()){
System.out.println("栈空");
}else{
System.out.println(s.size());
}
}
3、栈的模拟实现
public class MyStack {
int[] array;
int size;
public MyStack(){
array = new int[3];
}
public int push(int e){
ensureCapacity();
array[size++] = e;
return e;
}
public int pop(){
int e = peek();
size--;
return e;
}
public int peek(){
if(empty()){
throw new RuntimeException("栈为空，无法获取栈顶元素");
}
return array[size-1];
}
public int size(){
return size;
}
public boolean empty(){
return 0 == size;
}
private void ensureCapacity(){
if(size == array.length){
array = Arrays.copyOf(array, size*2);
}
}
}
二、队列(Queue)
1、概念
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾（Tail/Rear） 出队列：进行删除操作的一端称为队头（Head/Front）
2、队列的使用
在Java中，Queue是个接口，底层是通过链表实现的。
注意：Queue是个接口，在实例化时必须实例化LinkedList的对象，因为LinkedList实现了Queue接口。
public static void main(String[] args) {
Queue<Integer> q = new LinkedList<>();
q.offer(1);
q.offer(2);
q.offer(3);
q.offer(4);
q.offer(5); // 从队尾入队列
System.out.println(q.size());
System.out.println(q.peek()); // 获取队头元素
q.poll();
System.out.println(q.poll()); // 从队头出队列，并将删除的元素返回
if(q.isEmpty()){
System.out.println("队列空");
}else{
System.out.println(q.size());
}
}
