栈（Stack）
栈的概念
栈是一种特殊的线性表，只允许在一端进行插入和删除。栈遵循后进先出，分别在栈顶删除、栈底插入。
栈的常用方法
栈的一些方法，例如：出栈、入栈、取栈顶元素、是否为空、栈中元素个数等；
模拟实现栈(数组实现)
知道这些方法，接下来我们来模拟实现一个栈：数组实现栈出栈入栈的复杂度都是O(1)。
如果是单链表的话，用头插法入栈出栈的复杂度是O(1)；用尾插法是实现入栈出栈都需要将链表全部访问一遍所以复杂度是O(n)。但如果是双链表的话，不管哪边插入都可以实现入栈出栈复杂度是O(1)。双链表是一个很好用的链表，以后的算法中会经常使用。
- 栈的底层时数组，通过计数器比较栈中元素个数是否超过数组长度，再实现一个构造方法。
private int elem[];
private int size;
public MyStack(){
this.elem = new int[3];
}- 接着实现入栈方法；大致的流程就是判断栈中元素是否满，满了则扩容，没满就将元素放到数组的栈顶中。
//栈中所开辟的数组是否满
public boolean isFull(){
if (elem.length == size){
return true;
}
return false;
}
//增加元素（入栈）
public int push(int data){
if (isFull()){
elem =Arrays.copyOf(elem,elem.length*2);
}
elem[size] = data;
size++;
return data;
}- 出栈；出栈前还需要判断栈中是否为空，空栈就没有元素可以出栈，不是空就直接返回出栈的元素，并且计数器也要-1。
//判断栈是否为空
public boolean isempty(){
if (size == 0){
return true;
}else{
return false;
}
}
//减少元素（出栈）
public int pop(){
if(isempty()){
return -1;
}
return elem[size--];
}- 取出栈顶元素；取出前也需要判断栈中是否为空，不为空就返回栈顶元素。
//取出栈顶元素
public int peek(){
if (isempty()){
return -1;
}
return elem[size-1];
}队列（Queue）
队列的概念
队列是只允许一端插入，另一端删除的特殊线性表。也就是先进先出，分别再队尾插入，对头删除 。
不同于栈的是，栈（Stack）是一个类，底层是顺序表（也可以用链表实现栈）；而队列（Queue） 是一个接口，底层是链表。所以队列在实例化时必须实例化LinkedList的对象（LinkedList实现了Queue接口）。
public static void main(String[] args) {
Queue<Integer> queue = new LinkedList<>();
queue.offer(12);
queue.offer(24);
queue.poll();
System.out.println(queue);//[24]
}队列的常用方法
队列 的一些方法，例如：出队列、入队列、获取队头元素、是否为空、队列中元素个数等；
模拟实现队列
- 先创建一个结点，通过结点实现入队出队
static class ListNode {
private int val;
private ListNode prev;
private ListNode next;
public ListNode (int val){
this.val = val;
}
}
private ListNode front;//队尾
private ListNode rear;//队头- 入队；可以假设为头插法进入，详细分为第一次进入（直接将队头队尾等于这个新的结点）和往后进入（头插法进入）。
//入队 头插法
public void offer(int data){
ListNode node = new ListNode(data);
if (isEmpty()){
front = rear = node;
}else{
front.prev = node;
node.next = front;
front = node;
}
}- 出队；如果入队是头插，那么出队就是尾出，还要注意是否队列为空。
public boolean isEmpty(){
if (front == null){
return true;
}
return false;
}
//出队 删除头结点
public int poll(){
if(isEmpty()){
return -1;
}
int val = rear.val;
if (front == rear){
front = rear = null;
}else{
rear.prev.next = null;
rear = rear.prev;
}
return val;
}- 队中元素个数，以及遍历整个队列
//队列元素个数
public int size(){
ListNode cur = front;
int count = 0;
while (cur != null){
count++;
cur = cur.next;
}
return count;
}
//遍历
public void display(){
ListNode cur = front;
while (cur != null){
System.out.print(cur.val+" ");
cur = cur.next;
}
System.out.println();
}循环队列
由于我们对队列的不断入队与出队，导致队中出现浪费许多空间，所以就有循环队列的由来。它通过浪费一个空间来检验队列是否可以继续进入，循环队列是数组实现的。
循环队列的原理其实挺简单的，主要抓住取模 ，明白原理就相对容易些。
模拟实现循环队列
需要注意的是加一时不是只加一而是加一后还要取模；减一也是不是只减一，还需要考虑下标为0时不能减一而是数组长度减一、其它情况直接减一即可。
class MyCircularQueue {
private int elem[];
private int front;
private int rear;
public MyCircularQueue(int k) {
this.elem = new int[k+1];//这里由于要浪费一个空间，所以在构造时加上
}
//入队
public boolean enQueue(int value) {
if (isFull()){
return false;
}
elem[rear] = value;
rear = (rear+1)%elem.length;
return true;
}
//出队
public boolean deQueue() {
if (isEmpty()){
return false;
}
front = (front+1)%elem.length;
return true;
}
//获取队头元素
public int Front() {
return elem[front];
}
//获取队尾元素
public int Rear() {
int r = (rear == 0)?elem.length-1:rear-1;
return elem[r];
}
//是否为空
public boolean isEmpty() {
if(front == rear){
return true;
}
return false;
}
//是否为满
public boolean isFull() {
if ((rear+1)%elem.length == front){
return true;
}
return false;
}
}双端队列（Deque）
双端队列允许两端都可以进行入队和出队的队列。Deque是一个接口，也必须创建LinkedList的对象。
栈和队列都可以使用这个接口
Deque<Integer> stack = new ArrayDeque<>();//双端队列的线性实现（数组）
Deque<Integer> queue = new LinkedList<>();//双端队列的链式实现
