江苏亿之盛建设有限公司网站,wordpress域名空间,源码论坛网搭建,用家用电脑建设网站目录
1. 概念
2. 栈的使用
2.1 方法
2.2 示例
3. 栈的模拟实现
4. 栈的应用场景
4.1 题目1#xff1a;不可能的出栈序列
4.2 题目2#xff1a;逆序打印单链表
4.3 题目3#xff1a;逆波兰表达式求值
4.4 题目4#xff1a;括号匹配
4.5 题目5#xff1a;栈的压入…目录
1. 概念
2. 栈的使用
2.1 方法
2.2 示例
3. 栈的模拟实现
4. 栈的应用场景
4.1 题目1不可能的出栈序列
4.2 题目2逆序打印单链表
4.3 题目3逆波兰表达式求值
4.4 题目4括号匹配
4.5 题目5栈的压入、弹出训练
4.6 题目6最小栈 1. 概念
1栈是一种特殊的线性表其只允许在固定的一端进行插入和删除元素操作。
2进行数据插入和删除操作的一端称为栈顶另一端称为栈底。
3栈中的数据元素遵循后进先出的原则
4压栈栈的插入操作叫做进栈或压栈或入栈入数据在栈顶 出栈栈的删除操作叫做出栈出数据在栈顶
2. 栈的使用
2.1 方法
方法功能Stack()构造一个空栈E push(E e)将e入栈并返回eE pop()将栈顶元素出栈并返回E peek()获取栈顶元素int size()获取栈中有效元素个数boolean empty()检测栈是否为空
2.2 示例 public static void main(String[] args) {StackInteger stack new Stack();for(int i0;i5;i){stack.push(i); // 压栈}// 获取栈顶元素System.out.println(stack.peek());Integer a stack.pop(); // 出栈栈顶元素System.out.println(a);System.out.println(stack.peek());System.out.println(stack.size());}
3. 栈的模拟实现
Stack继承于Vector查Vector源码可知vector内部用数组实现故而模拟实现采用数组栈
1包类关系 2MyStack
package TestMyStack;import java.util.Arrays;public class MyStack {public int[] elem;public int useSize;public MyStack(){this.elem new int[10];}// 压栈public void push(int val){if(isFull()){// 扩容reSize();}elem[useSize] val;this.useSize;}// 判满public boolean isFull(){if(elem.length this.useSize){return true;}return false;}// 扩容public void reSize(){elem Arrays.copyOf(elem, 2*elem.length);}// 出栈并返回出栈元素public int pop(){if(isEmpty()){throw new EmptyException();}
// int val elem[this.useSize-1];
// this.useSize--;
// return val;return this.elem[--this.useSize];}// 判空public boolean isEmpty(){return this.useSize0;}// 获取栈顶元素public int peek(){return this.elem[this.useSize-1];}
}
3EmptyException
package TestMyStack;public class EmptyException extends RuntimeException{public EmptyException(){}
}
4. 栈的应用场景
4.1 题目1不可能的出栈序列
若进栈序列为1,2,3,4进栈过程中可以出栈则不可能的出栈序列是C A. 1,4,3,2 B. 2,3,4,1 C.3,1,4,2 D.3,4,2,1
4.2 题目2逆序打印单链表
1单链表的递归逆序打印法 public void fun1(ListNode pHead){// 递归逆序打印单链表if(pHead null){return;}if(pHead.next null){System.out.println(pHead.val);}fun1(pHead.next);System.out.println(pHead.val);}
2单链表的循环递归逆序打印法
public void fun2(ListNode pHead){StackListNode stack new Stack();ListNode cur head;while(cur!null){stack.push(cur);cur cur.next;}// 遍历栈while(!stack.isEmpty()){ListNode top stack.pop();System.out.print(top.val );}System.out.println();}
4.3 题目3逆波兰表达式求值
题目链接150. 逆波兰表达式求值 - 力扣LeetCode
解题思路遍历后缀算数表达式数组若为数据则入栈若为算术运算符则出栈栈顶两元素分别作为后操作数和前操作数再将计算结果入栈继续向后遍历数组循环操作直至栈中仅有一个元素就是最终值
代码
class Solution {public int evalRPN(String[] tokens) {StackInteger stack new Stack();for(String x: tokens){if(!isOperation(x)){stack.push(Integer.parseInt(x));}else{int num2 stack.pop();int num1 stack.pop();switch(x){case :stack.push(num1num2);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 x){if(x.equals()||x.equals(-)||x.equals(*)||x.equals(/)){return true;}return false;}
}
4.4 题目4括号匹配
题目链接20. 有效的括号 - 力扣LeetCode
代码
class Solution {public boolean isValid(String s) {StackCharacter stack new Stack();for(int i0;is.length();i){char ch s.charAt(i);if(ch( || ch{ || ch[){stack.push(ch);}else{// 第一种情况第一个就是右括号没有元素入栈栈为空直接返回假if(stack.empty()){return false; }// 第二种情况栈不为空判断是否匹配char ch2 stack.peek(); //栈顶元素必为左括号if(ch2 ( ch ) || ch2 { ch } || ch2 [ ch ]){stack.pop();}else{return false;}}}if(!stack.empty()){return false;}return true;}
}
4.5 题目5栈的压入、弹出训练
题目链接栈的压入、弹出序列_牛客题霸_牛客网
解题思路定义i下标遍历pushVj下标遍历popV将pushV的元素入栈当二者元素不相等时继续入栈pushV元素当二者元素相等时出栈栈顶元素i和j均
代码
import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可** * param pushV int整型一维数组 * param popV int整型一维数组 * return bool布尔型*/public boolean IsPopOrder (int[] pushV, int[] popV) {StackInteger stack new Stack();int j0;for(int i0;ipushV.length;i){stack.push(pushV[i]);while(jpopV.length !stack.empty() stack.peek().equals(popV[j])){stack.pop();j;}}return stack.empty();}
}
4.6 题目6最小栈
题目链接155. 最小栈 - 力扣LeetCode
解题思路为目标栈开辟一个储存最小值的栈依次遍历目标栈将最小的元素入栈最小栈最小栈栈顶元素就是目标栈的最小元素且能在常数时间内检索到最小元素
代码
class MinStack {private StackInteger stack;private StackInteger minStack;public MinStack() {stack new Stack();minStack new Stack();}public void push(int val) {stack.push(val);if(minStack.empty()){minStack.push(val);}else{ //minStack不为空if(val minStack.peek()){ // 如果要插入的值比minStack的栈顶元素小minStack.push(val); // 注意当valminStack栈顶元素时也需要将该元素入栈minStack// 因为stack出栈元素时如果该元素是minStack中的元素该元素也需要出栈// 以保证在出栈stack最小元素时minStack中的最小元素不受影响}}}public void pop() {if(!stack.empty()){Integer val stack.pop();if(val.equals(minStack.peek())){minStack.pop();}// 如果对元素拆箱为int类型就可使用进行判等}}public int top() {if(!stack.empty()){return stack.peek();}return -1;}public int getMin() {return minStack.peek();}
}
