栈（Stack）
栈的概念
栈是一种特殊的线性表，只允许在固定的一端进行插入和删除操作，进行数据插入和删除的一端称为栈顶，另一端称为栈底。栈的数据遵循后进先出LIFO（Last In First Out）的原则。
压栈：栈的插入操作叫做压栈/进栈/入栈，入的数据在栈顶。
出栈：栈的删除操作叫做出栈，出的数据在栈顶。
栈的常用方法
//入栈 public void push(int val) //将栈顶元素出栈并返回 public int pop() //获取栈顶元素 public int peek() //检测栈是否为空 public boolean isEmpty()
模拟实现栈
构造一个空栈
public class MyStack { private int[] elem; private int usedSize;//栈的实际元素个数 private static final int DEFAULT_CAPACITY = 10; //初始化栈的大小为DEFAULT_CAPACITY public MyStack() { this.elem = new int[DEFAULT_CAPACITY]; } }
实现push方法（入栈）
public void push(int val) { //判断栈是否已满 满就扩容 if (this.elem.length == usedSize) { this.elem = Arrays.copyOf(this.elem,this.elem.length*2); } this.elem[usedSize] = val; usedSize++; }
实现pop方法（将栈顶元素出栈并返回）
如果栈为空，返回栈顶元素就会报错，我们可以自定义一个异常用来解决报错问题
public class emptyException extends RuntimeException { public emptyException() { } public emptyException(String message) { super(message); } }
public int pop() { //如果为空栈就抛出一个异常 if (usedSize==0){ throw new emptyException(); } int oldVal = this.elem[usedSize-1]; usedSize--; return oldVal; }
实现peek方法（获取栈顶元素）
public int peek() { //如果为空栈就抛出一个异常 if (usedSize==0){ throw new emptyException(); } return this.elem[usedSize-1]; }
实现isEmpty方法（检测栈是否为空）
public boolean isEmpty() { //判断栈是否为空 只需要判断栈的实际元素个数是否为0即可 return usedSize==0; }
队列（Queue）
队列的概念
队列是只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列遵循先进先出FIFO（First in First Out）的原则。在Java里面Queue 是一个接口，底层是通过链表实现的。
入队列：进行插入的一端称为队尾。
出队列：进行删除的一端称为队头。
队列的常用方法
//入队 public void offer(int x) //出队 public int poll() //获取队头元素x public int peek() //获取队列中有效元素的个数 public int size() //检测队列是否为空 public boolean isEmpty()
队列的模拟实现
双链表模拟实现队列
public class MyQueue { static class ListNode { public int val; public ListNode next; public ListNode prev; public ListNode(int val) { this.val = val; } } public ListNode front;//队头 public ListNode rear;//队尾 public int usedSize = 0;//队列实际元素个数 }
实现offer方法（入队）
public void offer(int x) { ListNode node = new ListNode(x); //队列为空 if (front==null){ front=rear=node; }else { node.next=front; front.prev=node; front=node; } usedSize++; }
实现poll方法（出队）
public int poll(){ //队列为空 if (front==null){ return -1; } int ret = rear.val; //队列中只有一个元素 if (front==rear){ front=null; rear=null; usedSize--; return ret; } //删除尾节点 rear=rear.prev; rear.next=null; usedSize--; }
实现peek方法（获取队头元素）
public int peek(){ if (front==null){ return -1; } return front.val; }
实现size方法（获取队列中有效元素的个数）
public int size(){ return usedSize; }
实现isEmpty方法（检测队列是否为空）
public boolean isEmpty(){ return front==null; }
循环队列模拟实现
public class MyCircularQueue { public int[] elem; public int front;//队头 public int rear;//队尾 //构造循化队列 public MyCircularQueue(int len) { this.elem = new int[len+1]; } //入队 public boolean enQueue(int val){ //判断队列是否装满 if (isFull()){ return false; } elem[rear] = val; rear = (rear+1)%elem.length; return true; } //检测队列是否装满 private boolean isFull() { return (rear+1)%elem.length==front; } //出队 public boolean deQueue(){ if (isFull()){ return false; } front = (front+1)%elem.length; return true; } //获取队头元素 public int getFront(){ if (isEmpty()){ return -1; } return elem[front]; } //检测队列是否为空 public boolean isEmpty(){ return front==rear; } }
