栈
栈与队列是两种数据结构
栈（Stack）
栈是一种特殊的线性表，只允许在固定的一段进行插入和删除 元素的操作，进行数据插入和删除的一段叫做栈顶，另一端叫做栈底,栈中的元素必须要满足： ==先进后出==
栈的使用
在了解了栈的结构之后，我们先进行栈的使用
public static void main(String[] args) {
Stack<Integer> stack = new Stack<>();
stack.push(10);//向栈里面添加元素
stack.push(20);
stack.push(30);
stack.push(40);
int val = stack.peek();//查看并返回栈顶元素，不删除栈顶元素，只是看一眼（peek）
System.out.println(val);
int val2 = stack.pop();//查看并返回栈顶元素，并且删除它
System.out.println(val2);
val = stack.peek();
System.out.println(val);//此时val就会30，因为40已经被pop弹出了
boolean flg = stack.empty();//判断栈是否为空
System.out.println(flg);
System.out.println(stack.size());//由于stack继承了Vector，所以stack也有size（）
}模拟实现栈
import java.lang.reflect.Array;
import java.util.Arrays;
public class MyStack {
public int[] elem;
public int usedSize;//usedSized既可以用来记录当前栈里的数据个数，也可以当做下标用来存放数据
public static final int DEFAULT_CAPACITY=10;
public MyStack() { //构造方法
elem=new int[DEFAULT_CAPACITY];
}
public void push(int data) { //压栈---往栈里面放数据
//首先要判断栈是否满了
if(isFull()){
elem = Arrays.copyOf(elem, 2 * elem.length);//进行扩容
}
elem[usedSize]=data;
usedSize++;
}
public boolean isFull() {
return usedSize == elem.length;
}
public int pop() { //获取栈顶元素并且删除
if (isEmpty()) {
throw new StackEmptyException("栈为空！");
}
int oldVal = elem[usedSize - 1];//获取栈顶的元素
usedSize--;//直接减少栈中的有效数据来达到删除的效果
return oldVal;
}
public boolean isEmpty() {
return usedSize == 0;
}
public int peek() { //将上面的pop删除usedSize--就可以了
if (isEmpty()) {
throw new StackEmptyException("栈为空！");
}
return elem[usedSize - 1];//获取栈顶的元素，不删除
}
public int size() {
return usedSize;
}
}栈的存储方式
栈不仅可以是顺序存储，还可以是链式存储
顺序存储
单链表存储
双链表存储
关于栈的题目
1、不可能的出栈顺序
这种题目都有一种隐式条件：可以一边入栈一边出栈（入栈的过程中可以出栈）
一个栈的入栈序列是a,b,c,d,e则栈的不可能的输出序列是：（）
A edcba B decba C dceab D abcde这种题目只需要画一个栈的图，试一下就可以知道答案了
本题答案是C
2、中缀表达式的转换
oj题目
括号匹配判断
给定一个只包括'('，')'，'{'，'}'，'['，']'的字符串s，判断字符串是否有效。
整体思路：
class Solution {
public boolean isValid(String s) {
Stack<Character> stack=new Stack<>();
for( int i=0;i<s.length();i++){
char ch=s.charAt(i);
if(ch=='('||ch=='['||ch=='{'){
stack.push(ch);
}else{
//说明ch是右括号
if(stack.empty()){ //右括号多
return false;
}
char top=stack.peek();
if(ch==')'&&top=='('||ch=='}'&&top=='{'||ch==']'&&top=='['){//括号匹配
stack.pop();//将左括号删除，i后移
}else{ //括号不匹配
return false;
}
}
}
if(stack.empty()){
return true;
}else{ //循环走完，栈还有左括号，说明左括号多了
return false;
}
}
}
//时间复杂度和空间复杂度都是O(n)逆波兰表达式求值
根据逆波兰表示法，求表达式的值。有效的算符包括
+、-、*、/。每个运算对象可以是整数，也可以是另一个逆波兰表达式
class Solution {
public int evalRPN(String[] tokens) {
Stack<Integer>stack=new Stack<>();
for(String x:tokens){
if(!isOperation(x)){
//不是符号,是数字
stack.push(Integer.parseInt(x));//将字符x转换成数字x存入栈中
}
else{
int num2=stack.pop();
int num1=stack.pop();
switch (x){
case "+":
stack.push(num1+num2);
break;
case "-":
stack.push(num1-num2);
break;
case "*":
stack.push(num1*num2);
break;
case "/":
stack.push(num1/num2);
break;
}
}
}
return stack.pop();
}
//判断是否为加减乘除符号
private boolean isOperation(String op){ //字符串比较用equals
if(op.equals("+")||op.equals("-")||op.equals("*")||op.equals("/")){
return true;
}else{
return false;
}
}
}栈的出栈顺序判断
给定两个数组，其中一个为入栈顺序的数组，另一个是出栈顺序的数组，判断出栈顺序的数组是否正确
将 i 下标的元素放入到栈中，判断 j 下标的元素与栈中的元素是否相同，要是相同，则弹出，j后移，要是不相同，i就后移，继续入栈，直至 i 遍历完所有的元素
import java.util.*;
import java.util.ArrayList;
public class Solution {
public boolean IsPopOrder(int [] pushA,int [] popA) {
Stack<Integer>stack=new Stack<>();
int j=0;
for(int i=0;i<pushA.length;i++){
stack.push(pushA[i]);
while(j<popA.length&&!stack.empty()&&stack.peek()==popA[j]){
stack.pop();
j++;
}
}
return stack.empty();//要是栈为空，就说明出栈顺序正确
}
}但是还有有一点问题
这道题给的是整型数组，所以可以使用==来比较，以后万一要比较两个栈顶（引用类型）进行比较，就绝对不能用 ==进行比较
就要用equals比较
import java.util.*;
import java.util.ArrayList;
public class Solution {
public boolean IsPopOrder(int [] pushA,int [] popA) {
Stack<Integer>stack=new Stack<>();
int j=0;
for(int i=0;i<pushA.length;i++){
stack.push(pushA[i]);
while(j<popA.length&&!stack.empty()&&stack.peek().equals(popA[j])){ //这样子更好
stack.pop();
j++;
}
}
return stack.empty();//要是栈为空，就说明出栈顺序正确
}
}
