栈和队列学习记录

一、栈

1.栈的概念

操作受限的线性表-----栈：栈只允许在表的一端进行插入和删除操作，这一端被称为栈顶（Top），另一端则是栈底（Bottom）。这种受限的操作方式使得栈遵循后进先出（LIFO，Last In First Out）的原则，即最后进入栈的元素最先出栈.

压栈：栈的插⼊操作叫做进栈/压栈/⼊栈，⼊数据在栈顶。

出栈：栈的删除操作叫做出栈。出数据在栈顶。

2.栈的使用

public class Test {public static void main(String[] args) {Stack<Integer> stack=new Stack<>();stack.push(1);stack.push(2);stack.push(3);stack.push(4);System.out.println(stack.size());//获取元素个数 4System.out.println(stack.pop());//将栈顶元素出栈并返回 4System.out.println(stack.peek());//获取栈顶元素 3System.out.println(stack.peek());//           3System.out.println(stack.isEmpty());//        true}
}

Stack继承了Vector，Vector和ArrayList类似，都是动态的顺序表，不同的是 Vector是线程安全的。

3.栈的面试题

1.20. 有效的括号 - 力扣（LeetCode）

 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{if(stack.empty()){return false;}if(!(stack.peek()+" ").equals(ch+" ")){return false;}else{stack.pop();}}}if(!stack.empty()){return false;}return true;}
}

根据题意，是要判断字符串中的括号是否相对应，可将字符串拆解，判断该字符是左括号还是右括号，如果是左括号则直接压入stack栈中，如果是右括号，则取出stack栈顶比较是否相同，作比较时要先判断stack是否为空，如果为空则无需比较，直接返回false即可，比较时如果不相同直接返回false即可，相同则接着往下走，直至遍历完字符串，然后判断stack中是否还有元素，如果stack为空，则返回true，不为空返回false

2.150. 逆波兰表达式求值 - 力扣（LeetCode）

逆波兰表示法（Reverse Polish Notation，RPN），也称为后缀表示法，是一种将运算符置于操作数之后的表达式表示方法。中缀表示法转为后缀表示法，就是将运算符往后移动一个运算级。

示例：

中缀表达式：(3 + 4) * 2         逆波兰表达式：3 4 + 2 *
中缀表达式：5 + (6 - 2) * 3    逆波兰表达式：5 6 2 - 3 * +

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

将字符串拆开，用for循环遍历每个元素，如果该元素不是运算符就放到栈stack中，如果是运算符则用两个变量接受stack栈顶的元素，然后进行运算，运算后的结果再压入栈中，需要注意的是先取出的栈放在运算表达式的后一个位置，直至遍历完每个元素，返回栈中剩余的一个元素即可，

3.栈的压入、弹出序列_牛客题霸_牛客网

public boolean IsPopOrder (int[] pushV, int[] popV) {// write code hereStack<Integer> stack=new Stack<>();int j=0;for(int i=0;i<pushV.length;i++){stack.push(pushV[i]);while((!stack.empty())&&stack.peek()==popV[j]){j++;stack.pop();}}return stack.empty();}

该题考查的是栈的压入弹出顺序是否合法，我们可以通过一个for循环来遍历pushV，在每一层for循环当中，先将所遍历的该元素放到栈中，然后用while循环来判断stack栈顶元素和popV[j]元素的值是否相同，如果相同则将栈顶元素弹出，j++，一直循环即可，但在while循环条件中要有一个stack不为null的前提，否则会出现空指针异常。

二、队列