栈（Stack）和队列（Queue）
栈
栈（stack）是一种特殊的线性表，只允许在固定的一端进行插入和删除操作。
我们可以将栈近似看作一个桶，要取出桶底的元素，就要将桶顶的元素先取出，再将底部元素取出，也可以叫做后进先出。
这里所见的栈，本质上是一个顺序表/链表，但是，是在线性表/链表的基础上进行了一些限制。
对于栈而言，禁止了顺序表/链表的各种增删改查，只支持三个操作，入栈（push），出栈（poll），取栈顶元素（peek），可以认为栈是只能进行头删，尾删，取尾部元素的顺序表/链表。
栈存在的意义
既然栈可以用链表和顺序表/链表替代，那么为什么要将它单独存在。
编程中的一个基本原则，一个东西越灵活，越容易出错，越死板越不易出错，顺序表链表这样的结构功能太丰富，太灵活，所以栈/队列针对特定的场景，对顺序表和链表功能进行限制，大大减少出错的概率，栈虽然功能上做出限制，但是在特定场景下，解决特定问题的特定手段。
栈的实现
public static void main(String[] args) {Stack<Integer> k = new Stack<>();//元素入栈k.push(1);//元素出栈k.pop();//取栈顶元素k.peek();}
虽然栈是功能做出限制，让使用更简单，应该只提供三个方法，但是JAVA标准库中，Stack这个类的实现，其实是继承了Vector这样的类（Vactor是顺序表，与ArrayList差不多的，前者是上古时期的顺序表），但是Stack继承自Vactor，导致Vactor的各种操作，Stack也继承下来了。
模拟实现栈
栈可以用链表和顺序表实现。
public class MyStack {private int [] elem;private int size =0;public MyStack(){elem = new int [100];}public MyStack(int cope){if(cope<=100){cope=100;}elem = new int[cope];}public void push(int elems){elem[size] = elems;size++;}public int pop(){if(size==0){throw new RuntimeException();}int j = elem[size-1];size--;return j;}public String peek(){if(size==0){return null;}return Integer.toString(elem[size-1]);}}逆序单链表
逆序单链表可以用递归和栈。
递归实现：
public class stack2 {static class Node{String val ;Node next = null;public Node(String val) {this.val = val;}}public static void reparent(Node head){if(head==null){return;}reparent(head.next);System.out.println(head.val);}public static Node Build(){Node a = new Node("a");Node b = new Node("b");Node c = new Node("c");Node d = new Node("d");a.next = b;b.next = c;c.next = d;return a;}public static void main(String[] args) {Node head = Build();reparent(head);}
}栈实现：
public class stack2 {static class Node{String val ;Node next = null;public Node(String val) {this.val = val;}}public static void reparent(Node head){
// if(head==null){
// return;
// }
// reparent(head.next);
// System.out.println(head.val);Stack<String> stack = new Stack<>();for (Node cur = head;cur!=null;cur = cur.next){stack.push(cur.val);}while(!stack.isEmpty()){System.out.println(stack.pop());}}public static Node Build(){Node a = new Node("a");Node b = new Node("b");Node c = new Node("c");Node d = new Node("d");a.next = b;b.next = c;c.next = d;return a;}public static void main(String[] args) {Node head = Build();reparent(head);}
}队列（Queue）
队列，也是针对线性表，进行进一步的封装和限制，提供的操作也是是三个操作，入队列，出队列，取队首元素。
先进先出
队列实现
public static void main(String[] args) {//用链表实现QueueQueue<Integer> integers = new LinkedList<>();integers.offer(1);integers.offer(2);integers.offer(3);integers.poll();integers.peek();//判定队列是否为空if(integers.peek()==null){}//Queue没有isEmptyQueue是接口，而不是和Stack一样是类，所以Queue不能创建实例，只能创建其他类，实现该接口。
Queue可以创建Linkedlist对象，Linkedlist实现了Deque（双端队列，两端都可以进出），Deque又继承了Queue；但Queue不能创建Arraylist，但是队列可以用数组进行实现。
模拟实现Queue
数组实现Queue
public class MyArrayListQueue {private int [] arr = new int[10];private int head = 0;private int tail = 0;private int size = 0;//入队public void offer(int key){if(size==arr.length){return;}arr[tail] = key;tail++;if(tail==arr.length){tail = 0;}size++;}//出队列public int poll(){if(size==arr.length){return 0;}int elem = arr[head];head++;if(head==arr.length){head = 0;}size--;return elem;}//取队列元素public int peek(){if(size==arr.length){return 0;}int elem = arr[head];return elem;}public int Front() {if(size==0){return -1;}return arr[head];}public Boolean isEmpty(){return size==0;}@Overridepublic String toString() {StringBuilder stringBuilder = new StringBuilder();stringBuilder.append("{");for (int i = 0; i < size; i++) {stringBuilder.append(arr[i]);if(i<size-1){stringBuilder.append(",");}}stringBuilder.append("}");return stringBuilder.toString();}public static void main(String[] args) {MyArrayListQueue ak = new MyArrayListQueue();ak.offer(1);ak.offer(2);ak.offer(2);ak.offer(2);System.out.println(ak);}
}
链表实现Queue
public class MyqueueLinklist {static class Node{private int val;private Node next;public Node(int val) {this.val = val;this.next = null;}
}private Node head = null;private Node tail = null;//入队列public void offer(int key){Node newnode = new Node(key);if(head==null){head = newnode;tail = newnode;}tail.next = newnode;tail = newnode;}//出队列public int poll(){if(head==null){return -1;}int p = head.val;head = head.next;if(head==null){tail=null;}return p;}public int peek(){if(head==null){return -1;}int p = head.val;return p;}public Boolean isEmpty(){return head==null;}public int size(){Node cur = head;int index = 0;for(;cur!=null;cur=cur.next){index++;}return index;}}