一.栈的概念

一种特殊的线性表，只能从固定的一端插入和删除元素。

栈中元素遵循先进后出的原则。

二.模拟实现

public class MyStack {public int size;public int[] array;public  MyStack(){array =new int[10];}private void grow(){array = Arrays.copyOf(array,array.length*2);}public int size(){return size;}private boolean isFull(){return size==array.length;}public Boolean empty(){return size==0;}public void push(int data){if (isFull()){grow();}array[size]=data;size++;}public int pop(){if (empty()){return -1;}return array[--size];}public int peek(){if (empty()){return -1;}return array[size-1];}
}

注意：

该模拟实现底层是靠数组，除了数值，还可以用链表。

单向链表：

采用尾插法时，push和pop时间复杂度为O (n), 原因是压栈时要遍历链表到尾部压栈，如果在尾部定义一个尾节点时 时间复杂度为O (1)。出栈时后进先出，尾部最后进，要遍历到倒数第二个节点，才能删除尾节点。

采用首插法时，push和pop时间复杂度都为O (1),原因是遍历链表时出栈时，刚好遵循先进后出的原则。

双向链表：

无论是尾插法还是首插法，push和pop时间复杂度为O (1).

三.栈的方法

四.中缀表达式转后缀表达式

五.栈的使用

1.逆序打印链表

 public boolean isValid(String s) {Stack<Character> stack1 =new Stack<>();for(int i=0;i<s.length();i++){char ch =s.charAt(i);if(ch=='('||ch=='{'||ch=='['){stack1.push(ch);}else{//字符串没遍历完的情况if(stack1.empty()){return false;}//比较相不相等if(stack1.peek()=='(' && ch==')'||stack1.peek()=='{'&&ch=='}'||stack1.peek()=='['&&ch==']'){stack1.pop();   //相等就弹出一个字符}else{return false; }}}//栈中有剩余的情况if(stack1.empty()){return true;}else{return false;}}

2.逆波兰表达式求值

    public int evalRPN(String[] tokens) {Stack<Integer> stack =new Stack<>();int sum =0;for(int i=0;i<tokens.length;i++){if(tokens[i].equals("+")||tokens[i].equals("-")||tokens[i].equals("*")||tokens[i].equals("/")){int val2=stack.pop();int val1=stack.pop();switch(tokens[i]){case "+" :sum=val1+val2;break;case "-" :sum=val1-val2;break;     case "*" :sum=val1*val2;break;     case "/" :sum=val1/val2;break;}stack.push(sum);}else{stack.push(Integer.valueOf(tokens[i]));}}return stack.pop();}

3.最小栈

class MinStack {public Stack<Integer> stack1;public Stack<Integer> stack2;public MinStack() {stack1 =new Stack<>();stack2 =new Stack<>();}public void push(int val) {stack1.push(val);if(stack2.empty()||val<=stack2.peek()){stack2.push(val);}}public void pop() {if(stack1.empty()){return;}if(stack1.peek().equals(stack2.peek())){  stack1.pop();stack2.pop();}else{stack1.pop();}}public int top() {if(stack1.empty()){    return -1;}return stack1.peek();}public int getMin() {if(stack1.empty()){return -1;}return stack2.peek();}
}

注意：

其中的pop方法必须用equals来进行比较，因为是Integer类型，范围较小，超出范围时会创建新对象存储值，用 == 去比较时就是比的是地址

六.队列的模拟实现

采用先进先出的原则。

用数组实现不行，原因如下：

所以采用单向链表或双向链表

单向链表：

采用头差法，push时间复杂度为O (1)和pop时间复杂度为为O (n),因为尾部元素为最先进的元素，得遍历到倒数第二个节点才能删除

采用尾插法，在定义一个尾节点，push和pop时间复杂度和空间复杂度为O (1)

双向链表：

俩种都可以

模拟实现：

public class MyQueue {class ListNode{public int val;public ListNode next;public ListNode pre;public ListNode(int val) {this.val = val;}}private ListNode head;private ListNode last;private int size;public int size(){return size;}public boolean isEmpty(){return size==0;}public void offer(int value){ListNode node =new ListNode(value);if (head==null){head=last=node;}else {last.next=node;node.pre=last;last=last.next;}size++;}public int poll(){if (isEmpty()){return -1;}int ret=0;if(head.next==null){ret =head.val;head=last=null;}else {ret =head.val;head=head.next;head.pre=null;}size--;return ret;}public int peek(){if (isEmpty()){return -1;}return head.val;}

七.循环队列

1.保留一个位置

class MyCircularQueue {public int[] array;public int front;public int rear;public MyCircularQueue(int k) {array =new int[k+1];}public boolean enQueue(int value) {if(isFull()){return false;}array[rear] =value;rear=(rear+1)%array.length;return true;}public boolean deQueue() {if(isEmpty()){return false;}front=(front+1)%array.length;return true;}public int Front() {if(isEmpty()){return -1;}return array[front];}public int Rear() {if(isEmpty()){return -1;}return array[(rear-1+array.length)%array.length];}public boolean isEmpty() {return rear==front;}public boolean isFull() {return (rear+1)%array.length==front;}
}

除此之外，还可以通过size记录元素数量来判断队列是否满了或空的

八.双端队列（Deque）

双端队列（Deque）是指允许两端都可以进行入队和出队操作的队列，那就说明元素可以从队头出队和入队，也可以从队尾出队和入队。