1.1 栈的定义
栈：一种特殊的线性表，其只允许在表尾进行插入和删除操作。
栈顶和栈底：允许插入和删除的一端称为栈顶（top），另一端称为栈底（bottom），栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据在栈顶。
栈分为顺序栈和链栈，我们先研究顺序栈，链栈等以后再说。
下方是栈继承的类，以及栈实现的接口。
1.2 栈的模拟实现（顺序栈）
栈一共包含6个方法，我们模拟实现中所有数据类型都用int类型代替。
push()方法
作用：此方法是让元素入栈。
实现原理：首先判断线性表是否已满，如果线性表已满，就需要扩容。之后就是将数据放入线性表，并将栈大小加一。
public void push(int val) { if(stack.length==stackSize) { stack=Arrays.copyOf(stack,2*stackSize); } stack[stackSize++]=val; }
pop()方法
作用： 此方法是让栈顶元素出栈。
实现原理：出栈的前提一直到栈中有元素；因此，我们先判断栈是否胃口，若为空栈，就抛出异常，让程序停下来，若不为空栈，就弹出栈底元素，并将栈大小减一。
public int pop() { if(empty()) { throw new RuntimeException("空栈！"); } return stack[--stackSize]; }
peek()方法
作用： 如他的名字一样，peek 偷看，看一眼栈顶的元素，但不出栈。
实现原理：判断栈是否为空，若是空栈不能偷看到元素，抛异常停止运行；若不为空栈返回栈底元素即可。
public int peek() { if(empty()) { throw new RuntimeException("空栈！"); } return stack[stackSize-1]; }
size()方法
作用： 得到栈中有多少个元素
实现原理：直接返回成员变量stackSize
栈模拟实现的全代码：
import java.util.Arrays; public class MyStack { private int[] stack; private int stackSize; public MyStack() { this.stack=new int[3]; } public void push(int val) { if(stack.length==stackSize) { stack=Arrays.copyOf(stack,2*stackSize); } stack[stackSize++]=val; } public int pop() { if(empty()) { throw new RuntimeException("空栈！"); } return stack[--stackSize]; } public int peek() { if(empty()) { throw new RuntimeException("空栈！"); } return stack[stackSize-1]; } public int size() { return stackSize; } public boolean empty() { if(stackSize==0) { return true; } return false; } }
1.3顺序栈和链栈的对比
栈有链栈和顺序栈之分，上方是用顺序表实现的名叫顺序栈；我们还可以使用链表实现，对于用链表实现栈，会很好实现，因为我们不需要考虑栈满的情况，若链栈满了，那可以说是你的计算机操作系统就面临崩溃。
时间复杂度：链栈和顺序栈，它们在时间复杂度上都是O(1)。
空间复杂度：顺序栈需要事先确定一个长度，可能会造成内存空间的浪费，但是优势是存取时定位方便；链栈每个元素都要有一个指针域，增加了内存的开销，但长度无限。
两者如何选择：如果栈的使用过程中元素变化不可预知，最好用链栈；若变化在可控范围内，使用顺序栈更好。
2.队列
2.1队列的定义
队列： 只允许在一端进行插入操作，而在另一端进行删除操作的线性表，允许插入的一端称为队尾，允许删除的一端称为对头。一种先进先出的线性表。
队列实现的接口：
在Java中，Queue是个接口，底层是通过链表实现的
2.1队列的模拟实现（单链表）
队列一共有5种方法
offer()函数
作用：将新元素入队，位置是单链表尾部。
实现原理：将给给定的数值new一个新节点，如果头节点为空，就让头结点和尾节点都等于noed，如果不为空，就使用尾插法将node插到链表尾部。
//入队 public void offer(int val) { Node node=new Node(val); if(head==null) { head=node; last=node; }else { last.next=node; last=last.next; } usedSize++; }
poll()函数
作用：将队头元素出队，位置单链表头指针所指元素。
实现原理：首先判断链表是否为空，若空，抛出异常；若不空，出头指针指的元素，并将使用大小减一。
//出队 public int poll() { if(isEmpty()) { throw new RuntimeException("队列空"); } int tmp=head.val; head=head.next; usedSize--; return val; }
peek()函数
作用：偷看一下队头元素，不出队
实现原理：将首先判断队列是否空，若空，抛出异常；若不为空，返回头节点所指数值。
public int peek() { if(isEmpty()) { throw new RuntimeException("队列空"); } int tmp=head.val; return val; }
size()函数
作用：返回有多少个元素
实现原理：直接返回成员变量usedSize
public int size() { return usedSize; }
isEmpty()函数
作用：将判断队列是否空。
实现原理：如果头节点是空，证明没有元素入队。
//判断空队列 public boolean isEmpty() { if(usedSize==0) { return true; } return false; }
队列实现的全代码
public class MyQueue { private int val; private int usedSize; static class Node { public int val; public Node next; public Node(int val) { this.val = val; } } private Node head; private Node last; //入队 public void offer(int val) { Node node=new Node(val); if(head==null) { head=node; last=node; }else { last.next=node; last=last.next; } usedSize++; } //出队 public int poll() { if(isEmpty()) { throw new RuntimeException("队列空"); } int tmp=head.val; head=head.next; usedSize--; return val; } //看队头 public int peek() { if(isEmpty()) { throw new RuntimeException("队列空"); } int tmp=head.val; return val; } //判断空队列 public boolean isEmpty() { if(usedSize==0) { return true; } return false; } public int getUsedSize() { return usedSize; } }
总结
1.栈和队列，他们都是特殊的线性表，只不过在删除和插入操作上做了限制。
2.栈(stack)是限制仅在表尾进行插入和删除操作的线性表。
3.队列(queue)是限制只允许一端进行插入操作，另一端进行删除操作的线性表。
