残疾人无障碍网站建设,wordpress弹出提示框,网络营销和网上销售的区别,晋城市住建设局网站文章目录 一 栈栈的概念:栈的实现#xff1a;栈的数组实现默认构造方法压栈获取栈元素的个数出栈获取栈顶元素判断当前栈是否为空 java提供的Stack类Stack实现的接口#xff1a; LinkedList也可以当Stack使用虚拟机栈#xff0c;栈帧#xff0c;栈的三个概念 二 栈的一些算… 文章目录 一 栈栈的概念:栈的实现栈的数组实现默认构造方法压栈获取栈元素的个数出栈获取栈顶元素判断当前栈是否为空 java提供的Stack类Stack实现的接口 LinkedList也可以当Stack使用虚拟机栈栈帧栈的三个概念 二 栈的一些算法题1 逆序打印单链表。2[括号匹配](https://leetcode-cn.com/problems/valid-parentheses)3[逆波兰表达式求值](https://leetcode-cn.com/problems/evaluate-reverse-polish-notation/)逆波兰表达式 4 [出入栈次序匹配](https://www.nowcoder.com/practice/d77d11405cc7470d82554cb392585106?tpId13tqId11174rp1ru/activity/ojqru/ta/coding-interviews/question-ranking)5[最小栈](https://leetcode-cn.com/problems/min-stack/)总结 一 栈
栈的概念:
栈也是一种线性表栈只允许在表的一端进行插入与删除操作所以栈中数据的特征的先进后出先进来的后出去。 栈顶是栈进行插入与删除操作的表的一端 栈底不允许插入删除操作的一端 压栈将数据插入到栈中 出栈将数据移除栈
栈的实现
栈的底层可以由数组实现也可以由链表实现 栈由数组实现时栈的压栈与出栈的时间复杂度均为O1。 栈由单链表实现时 如果采用尾插法压栈操作时间复杂度为On,如果有last指针则 压栈时间复杂度为O(1),但是出栈的时间复杂度一定为On。 如果采用头插法则压栈与出栈的时间复杂度均为O1. 栈由双链表实现时不论采用头插法与尾插法时间复杂度均为O(1)。
栈的数组实现
当栈使用数组实现时栈的插入与删除操作时间复杂度均为O1
public class MyStack {static int DEFAULT_SIZE 10; //设置默认的数组大小private int [] element ; //实现栈的数组int usedsize 0 ; //栈中有效元素的个数//默认构造方法public MyStack() {}//入栈public void push(int val) {}//出栈public int pop() {}//获取栈顶元素 但是不删除public int peek() { }//获取栈元素个数public int size(){} //判空public boolean isEmpty() { }
}默认构造方法
默认申请10个空间
public MyStack(){this.element new int[10];}压栈
思想先判断栈满没满如果满了则扩容然后进行压栈 public void push(int data){//先判断栈是否有空间if(usedsizeelement.length){//如果没有空间//则扩容this.element Arrays.copyOf(element,2*element.length);}//保证空间后this.element[usedsize] data;}获取栈元素的个数
思想直接返回usedsize public int size(){return usedsize;}出栈
思想先判断栈是否为空为空则抛出异常不为空则返回栈顶元素值并且usedsize-1. public int pop(){//要判断栈是否为空如果为空则退出try{if (isEmpty()) {//2. 问题出现,构造参数的形参问题super()调用父类的构造方法throw new EmptyException(EmptyException异常报错);}}catch (EmptyException e){e.printStackTrace();}int val this.element[usedsize-1];usedsize -- ;return val;}获取栈顶元素
思想与出栈逻辑相同只是usedsize值不需-1 。 public int peek(){try{if (isEmpty()) {throw new EmptyException(EmptyException异常报错);}}catch (EmptyException e){e.printStackTrace();}return this.element[usedsize-1];}判断当前栈是否为空
思想直接判断usedsize 是否为0即可。 public boolean isEmpty(){return usedsize 0;}java提供的Stack类 Stack实现的接口 接口说明 1. 继承Cloneable接口支持克隆其他接口暂时还没搞明白以后更新补充LinkedList也可以当Stack使用
java提供的LinkedList类也可以当做栈来使用LinkedList的方法列表如下
public class Test {public static void main(String[] args) {LinkedListInteger stack new LinkedList();stack.push(5);stack.push(2);stack.pop();stack.pop();stack.pop();}
}虚拟机栈栈帧栈的三个概念
虚拟机栈是JVM中的一块内存。 栈帧是为一个方法函数分配的内存。 栈是一种数据结构。
二 栈的一些算法题
1 逆序打印单链表。
采用递归的方法
// 递归方式
void printList(Node head){if(null ! head){printList(head.next);System.out.print(head.val );}
}采用栈的方法
void printList(Node head){if(null head){return;}StackNode s new Stack();// 将链表中的结点保存在栈中Node cur head;while(null ! cur){s.push(cur);cur cur.next;}
// 将栈中的元素出栈while(!s.empty()){System.out.print(s.pop().val );}
}2括号匹配
题解1 . 对于这个题无法直接看出其数学模型必须先画图列出各种情况再判断 从图中可以分析出要实现判断括号匹配
就要使得每一个左括号和右括号能够与对应位置的右括号进行匹配判断且当所有的左括号右括号判断完时其对应的右括号左括号也判断完毕即满足左括号个数与右括号个数相当的情况。如果第一个括号是右括号说明此括号没有对应的左括号说明一定为字符串一定括号不匹配。
实现思想遍历字符串遇到左括号则存入栈中遇到右括号则与栈顶元素比较相匹配则继续循环如果不匹配或栈为空则返回false。
class Solution1 {public boolean isValid(String s) {Stack Character stack new Stack();//采用for循环这样可以找到字符串中的字符for(int i 0;is.length();i) {char ch s.charAt(i);if (ch { || ch [ || ch () {//问题java提供的栈是否需要手动扩容stack.push(ch);} else {//如果是右括号的内容if (stack.isEmpty()) {return false;} else {char ch2 stack.peek(); //当获取栈顶元素时栈可能为空//栈区不能为空if (((ch } ch2 {) || (ch ] ch2 [) || (ch ) ch2 ())) {//说明匹配//将栈顶的元素去除stack.pop();} else {//如果不匹配情况1 如果栈中还没有左括号则一定不匹配return false;}}}}// 如果栈表为空说明匹配完毕if(stack.isEmpty()){return true;}return false;}
}3逆波兰表达式求值
逆波兰表达式
逆波兰表达式即后缀表达式后缀表达式是由中缀表达式转换而成。 所谓中缀表达式即我们平常所写的±*/的算式 我们平常所写的中缀表达式中是有优先级的即先乘除后加减有括号先算括号里面的 但是计算机是不能够识别优先级的为了能够使计算机计算我们将中缀表达式的规则 表达成后缀表达式的形式这样计算机便能够计算算式。
中缀表达式转换成后缀表达式的的规则
先将中缀表达式中能够加括号的部分都加上括号然后将所有的运算符移到所在 最近扩号之外。然后去除掉所有括号即得到后缀表达式。
后缀表达式的运算规则 遍历整个表达式遇到运算符时则将运算符前面的两个数作为操作数计算 得出的结果替代两个操作数然后继续遍历表达式循环上次操作。 本题只是要求按照后缀表达式的规则计算结果 实现思想遍历表达式遇到操作数即将操作数压入栈中遇到运算符则进行两次出栈 获取两个操作数进行计算需要注意的是第一次出栈的是右操作数第二次出栈的是左操作数 然后将计算的结果再进行压栈然后循环此操作。
class Solution {public int evalRPN(String[] tokens) {//创建一个栈创建栈时不需要考虑栈的空间大小StackInteger stack new Stack();//采用foreach进行遍历栈for (String str : tokens) {if (!isOperator(str)) {int a Integer.parseInt(str);stack.push(a);} else {int val2 stack.pop();int val1 stack.pop();//如果为运算符switch (str) {case : stack.push(val1 val2);break;case - : stack.push(val1 - val2);break;case * : stack.push(val1 * val2);break;case / : stack.push(val1 / val2);break;}}}return stack.peek();}
总结 1. 字符串形式的运算符不能直接转换成运算符 2. 后缀表达式先进栈的是左操作数后进栈的是右操作数当我们需要出栈时第一次获取栈顶元素是右操作数第二次获取栈顶元素才是左操作数。
4 出入栈次序匹配 class Solution2{public boolean IsPopOrder (int[] pushV, int[] popV) {// write code hereStackInteger stack new Stack();int j 0;for(int i 0; i pushV.length;i) {stack.push(pushV[i]);while(!stack.empty() j popV.length stack.peek() popV[j]) {stack.pop();j;}}return stack.empty();}
}
5最小栈
题解 如果只用一个栈的话我们不可能实现题目的要求只有能将栈的最小值时刻储存起来才能实现题目的要求。因此我们实现两个栈一个栈用于存储数据另一个最小栈用于存放栈当前的最小值。
实现思想入栈的规则
普通栈一定要放最小栈如果为空或者栈顶元素小于压入的数据则放入最小栈中如果压入的数据与最小栈栈顶元素相当也放入最小栈中。因为最小栈中的元素必须与普通栈的最小值保持同步即必须与出栈的规则相匹配。 出栈的规则 如果普通栈的栈顶元素与最小栈栈顶元素相同则最小栈也需要出栈。
class MinStack {//创建两个栈Stack Integer stack new Stack(); //普通栈Stack Integer minStack new Stack();//最小栈public MinStack() {}
public void push(int val) {//压栈压入数据//普通栈一定要压入stack.push(val);//然后判断最小栈是否压入if(minStack.empty()){minStack.push(val);}else{if(valminStack.peek()){minStack.push(val);}}}public void pop() {//出栈//普通栈一定出栈int val stack.pop();//最小栈出栈//如果两栈的栈顶元素相同则出栈if(val minStack.peek()){minStack.pop();}}public int top() {//获取栈顶元素if(!stack.empty()){return stack.peek();}return -1 ;}public int getMin() {if(minStack.empty()){return -1;}return minStack.peek();}}总结
在使用栈时最常用的运用是根据栈先进后出的特性将一段有序的数据转为逆序后再进行操作使用。
