前言: 本文构造
1. 什么是栈
2. 如何实现栈 —>jdk 如何实现栈
3. 栈的利用
4. 栈常见的算法题 ——> 枯燥栈
5. 未完待续
所有解决问题思路：栈先入后出的数据结构
1. 什么是栈？
1)栈 (Stack) 是一种 先入后出 的线性表
2) 栈(stack)是限度线性表中元素的插入和删除只能在线性表的同一端进行的一种非凡线性表。容许插入和删除的一端，为变动的一端，称为 栈顶 (Top)（咱们在栈顶进行的插入和删除称为入栈和出栈）另一端为固定的一端，称为 栈底 (Bottom)。
3) 依据栈的定义可知，最先放入栈中元素在栈底，最初放入的元素在栈顶，而删除元素刚好相同，最初放入的元素最先删除，最先放入的元素最初删除
栈像咱们的水桶（咱们加水和取水想入栈和出栈，而后也只能在有口的一端（栈顶）进行操作，封口的一端（栈底）无奈操作）
2. 如何实现栈？
2.1 对列实现栈
图解：
计划一：
代码：
class MyStack {
Queue<Integer> queue;
public MyStack() {queue = new LinkedList<Integer>();
}
public void push(int x) {
// 算出插入前所有元素个数
int n = queue.size();
// 插入新元素
queue.offer(x);
// 把后面元素从队头取出，插入队尾
for (int i = 0; i < n; i++) {queue.offer(queue.poll());
}
}
public int pop() {return queue.poll();
}
public int top() {return queue.peek();
}
public boolean empty() {return queue.isEmpty();
}
}
计划二：
class MyStack {
Queue<Integer> queue1;// 主队列
Queue<Integer> queue2;// 辅助队列
public MyStack() {queue1 = new LinkedList<Integer>();
queue2 = new LinkedList<Integer>();}
public void push(int x) {
// 元素插入辅助队列
queue2.offer(x);
// 主队列元素插入辅助队列
while (!queue1.isEmpty()) {queue2.offer(queue1.poll());
}
// 主辅替换，辅助队列变为空
Queue<Integer> temp = queue1;
queue1 = queue2;
queue2 = temp;
}
public int pop() {return queue1.poll();
}
/** Get the top element. */
public int top() {return queue1.peek();
}
/** Returns whether the stack is empty. */
public boolean empty() {return queue1.isEmpty();
}
}2.2: 数组实现栈
class ArrayStack {
private int maxSize; // 栈的大小
private int[] stack; // 数组，数组模仿栈，数据就放在该数组
private int top = -1;// top 示意栈顶，初始化为 -1
// 结构器
public ArrayStack(int maxSize) {
this.maxSize = maxSize;
stack = new int[this.maxSize];
}
// 栈满
public boolean isFull() {return top == maxSize - 1;}
// 栈空
public boolean isEmpty() {return top == -1;}
// 入栈 -push
public void push(int value) {
// 先判断栈是否满
if(isFull()) {throw new RuntimeException("栈满");
}
top++;
stack[top] = value;
}
// 出栈 -pop, 将栈顶的数据返回
public int pop() {
// 先判断栈是否空
if(isEmpty()) {
// 抛出异样
throw new RuntimeException("栈空，没有数据~");
}
int value = stack[top];
top--;
return value;
}
// 显示栈的状况[遍历栈]，遍历时，须要从栈顶开始显示数据
public void list() {if(isEmpty()) {System.out.println("栈空，没有数据~~");
return;
}
// 须要从栈顶开始显示数据
for(int i = top; i >= 0 ; i--) {System.out.printf("stack[%d]=%d\n", i, stack[i]);
}
}
}2.3:jdk 中的 Stack 如何实现
1. 次要是继承了 Vector
2.push(),pop(),empty(),peek()操作，在办法上加了 synchronized 润饰，所以效率比较慢，而后被划为不举荐应用。
public class Stack<E> extends Vector<E> {
private static final long serialVersionUID = 1224463164541339165L;
public Stack() {}
public E push(E item) {this.addElement(item);
return item;
}
public synchronized E pop() {int len = this.size();
E obj = this.peek();
this.removeElementAt(len - 1);
return obj;
}
public synchronized E peek() {int len = this.size();
if (len == 0) {throw new EmptyStackException();
} else {return this.elementAt(len - 1);
}
}
public boolean empty() {return this.size() == 0;
}
public synchronized int search(Object o) {int i = this.lastIndexOf(o);
return i >= 0 ? this.size() - i : -1;}
}3: 栈的利用？
1)函数的调用
比方：java 虚拟机栈（虚拟机为每个线程创立一个公有的栈，每个办法的调用都会创立一个栈帧，每一个办法从调用到办法返回都对应着一个栈帧入栈出栈的过程。
2）递归调用 -–> 深度搜寻（dfs）—-> 二叉树遍历（递归实现）
3)括号匹配
4）后缀表达式求值
等等等
4. 栈常见的算法题(由简到难)
- 无效的括号
办法一：辅助栈
class Solution {public boolean isValid(String s) {Stack<Character>stack = new Stack<Character>();
for(char c: s.toCharArray()){if(c=='(')stack.push(')');
else if(c=='[')stack.push(']');
else if(c=='{')stack.push('}');
else if(stack.isEmpty()||c!=stack.pop())return false;
}
return stack.isEmpty();}
}办法二：辅助栈 +HashMap
class Solution {public boolean isValid(String s) {int n = s.length();
if (n % 2 == 1) {return false;}
Map<Character, Character> pairs = new HashMap<Character, Character>() {{put(')', '(');
put(']', '[');
put('}', '{');
}};
Deque<Character> stack = new LinkedList<Character>();
for (int i = 0; i < n; i++) {char ch = s.charAt(i);
if (pairs.containsKey(ch)) {if (stack.isEmpty() || stack.peek() != pairs.get(ch)) {return false;}
stack.pop();} else {stack.push(ch);
}
}
return stack.isEmpty();}
}- 逆波兰表达式求值
class Solution {public int evalRPN(String[] tokens) {Deque<Integer> stack = new LinkedList<Integer>();
int n = tokens.length;
for (int i = 0; i < n; i++) {String token = tokens[i];
if (isNumber(token)) {stack.push(Integer.parseInt(token));
} else {int num2 = stack.pop();
int num1 = stack.pop();
switch (token) {
case "+":
stack.push(num1 + num2);
break;
case "-":
stack.push(num1 - num2);
break;
case "*":
stack.push(num1 * num2);
break;
case "/":
stack.push(num1 / num2);
break;
default:
}
}
}
return stack.pop();}
public boolean isNumber(String token) {return !("+".equals(token) || "-".equals(token) || "*".equals(token) || "/".equals(token));
}
}- 柱状图中最大的矩形
1. 暴力法：超出工夫限度，呜呜呜呜呜呜呜呜呜
class Solution {public int largestRectangleArea(int[] heights) {
int len=heights.length;
if (len==0){return 0;}
int res=0;
for (int i=0;i<len;i++){
int left=i;
int right=i;
int cur=heights[i];
// 从右到左找到最初大于等于以后数的下标
while(left>0&&heights[left-1]>=cur){left--;}
while (right<len-1&&heights[right+1]>=cur){right++;}
res= Math.max((right-left+1)*heights[i],res);
}
return res;
}
}2. 枯燥栈
class Solution {// 枯燥栈 + 哨兵节点(缩小边界的判断)
public int largestRectangleArea(int[] heights) {
int res=0;
int len=heights.length;
// 判断非凡状况
if (len==0){return 0;}
if (len==1){return heights[0];
}
// 新建哨兵节点
int[] newHeight=new int[len+2];
newHeight[0]=0;
System.arraycopy(heights,0,newHeight,1,len);
newHeight[len+1]=0;
len+=2;
// 用双端对列做为栈
Deque<Integer> stack=new LinkedList<>();
stack.addLast(0);
for (int i=1;i<len;i++){while (newHeight[i]<newHeight[stack.peekLast()]){int curHigh=newHeight[stack.pollLast()];
int curWidth=i-stack.peekLast()-1;
res=Math.max(curHigh*curWidth,res);
}
stack.addLast(i);
}
return res;
}
}TOList
有了后面的根底，这不得迎刃而解，噢哈哈哈哈哈
- 每日温度
1. 暴力法
2. 枯燥栈 - 接雨水
补充：232. 用栈实现队列
225. 用队列实现栈
5. 未完待续