数据结构java版之栈

云惠网小编 2022年1月17日09:17:47
评论
3958字阅读13分11秒
摘要

# 一、栈的基本概念区分# 二、常见题型考查目录# 一、栈的基本概念区分# 二、常见题型考查一、栈的基本概念区分什么是栈什么是Java虚拟栈什么是栈帧

广告也精彩

 

 

经典题目之最小栈155. 最小栈 - 力扣(LeetCode) (leetcode-cn.com)icon-default.png?t=LBL2https://leetcode-cn.com/problems/min-stack/解题思路:

import java.util.*;
//自己实现栈
public class MyStack {
public int[] elem;
//判断放入的个数,即容量的大小
public int usedSize;
public MyStack(){
this.elem=new int[5];
}
//关于入栈
public void push(int val){
//第一步,判断是否满栈
if(isFull()){
//扩容
Arrays.copyOf(this.elem,2*this.elem.length);
}
this.elem[this.usedSize]=val;
this.usedSize++;
}
public boolean isFull(){
return this.usedSize==this.elem.length;
}
//出栈
public int pop(){
if(isEmpty()){
throw new RuntimeException("栈为空");
}
int oldVal=this.elem[usedSize-1];
this.usedSize--;
return oldVal;
}
//获取栈顶元素
public int peek(){
if(isEmpty()){
throw new RuntimeException("栈为空");
}
return this.elem[usedSize-1];
}
public boolean isEmpty(){
return this.usedSize==0;
}
}

相关代码:

什么是栈帧 ?

调用函数的时候,我们会为这个函数在JVM虚拟机栈中开辟一块内存叫做栈帧

二、栈的常见操作以及常见题型考查

import java.util.*;
public class TestDemo {
public static void main(String[] args) {
Stack<Integer> stack=new Stack<>();
//入栈
stack.push(1);
stack.push(2);
System.out.println(stack);
//查看栈顶元素
System.out.println(stack.peek());
System.out.println(stack);
//出栈
System.out.println(stack.pop());
System.out.println(stack);
System.out.println(stack.isEmpty());
}
}

1.对常见操作进行测试:

由源码判断出栈的底层为数组:

1.栈的常见操作

目录 

二、栈的常见操作以及常见题型考查

什么是Java虚拟栈 ?

 此时,Java虚拟机栈只是JVM中的一块内存,该内存一般用来存放,例如:局部变量

 

注意:stack.pop() 的操作是出栈栈顶元素,此后栈顶元素将不复存在 

           而stack.peek()的操作是查看栈顶元素,此后该栈顶元素依旧存在 

方法 解释
E push(E item) 入栈
E pop() 出栈
E peek() 查看栈顶元素
boolean empty() 判断栈是否为空

一、栈的基本概念区分

什么是栈?

栈实际上是一种数据结构,特点是后进先出

 

class MinStack {
private Stack<Integer>stack;
private Stack<Integer>minStack;
public MinStack() {
stack=new Stack<>();
minStack=new Stack<>();
}
public void push(int val) {
stack.push(val);
if(!minStack.empty()){
int top=minStack.peek();
if(top>=val){
minStack.push(val);
}
}else{
minStack.push(val);
}
}
public void pop() {
int popVal=stack.pop();
if(!minStack.empty()){
int top=minStack.peek();
if(popVal==top){
minStack.pop();
}
}
}
public int top() {
return stack.peek();
}
public int getMin() {
return minStack.peek();
}
}

在出栈时注意是引用还是非引用类型

第一类:关于入栈和出栈的题目 

 解析要点:

①第一步查看首元素,确定入栈序列

②不熟悉地话建议画出栈图进行理解

代码解决:栈的压入、弹出序列_牛客题霸_牛客网 (nowcoder.com)https://www.nowcoder.com/practice/d77d11405cc7470d82554cb392585106?tpId=13&&tqId=11174&rp=1&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking

import java.util.*;
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();
}
}

 第二类:中缀表达式转后缀表达式(逆波兰表达式)

简易解题思想:加括号

eg.(5+4)*3-2

①将每个运算符所在的表达式加上括号至最外一层

(((5+4)*3)-2)

②将所有符号移至相对应括号外

(((54)+3)*2)-

③数字顺序不变,去掉括号

54+3*2-

思考???如何通过后缀表达式计算一个值呢???

利用栈

解题思路:

①当i指向数字时,入栈数字。当i指向运算符时,将入栈的数字分别放于其左右

②循环上述步骤

 代码实现:150. 逆波兰表达式求值 - 力扣(LeetCode) (leetcode-cn.com)https://leetcode-cn.com/problems/evaluate-reverse-polish-notation/

class Solution {
public int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack<>();
for(int i = 0;i < tokens.length;i++) {
String val = tokens[i];
if(isOperation(val) == false) {
//如果不是运算符
stack.push(Integer.parseInt(val));
}else {
//到底是什么运算符
int num2 = stack.pop();
int num1 = stack.pop();
switch(val) {
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 x) {
if(x.equals("+") || x.equals("-") ||x.equals("*") ||x.equals("/")) {
return true;
}
return false;
}
}

第三类:

经典题目之有效的括号 

20. 有效的括号 - 力扣(LeetCode) (leetcode-cn.com)https://leetcode-cn.com/problems/valid-parentheses/

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()){
//右括号多
System.out.println("右括号多");
return false;
}
char top=stack.peek();//哪个左括号
if(top=='{' && ch=='}'||top=='(' && ch==')'||top=='[' && ch==']'){
stack.pop();
}else{
//左右括号不匹配
System.out.println("左右括号不匹配");
return false;
}
}
}
if(!stack.empty()){
//左括号多
System.out.println("左括号多");
return false;
}
return true;
}
}

 2.自己动手操作实现栈 

一、栈的基本概念区分

本文转自 https://blog.csdn.net/weixin_58850105/article/details/122509541

腾讯云618
云惠网小编
SpringCloud -- Config、Bus解析 java

SpringCloud — Config、Bus解析

1、Config1.1、概述简介1. 分布式面临的问题微服务意味着要将单体应用中的业务拆分成一个个子服务,每个服务的粒度相对较小,因此系统中会出现大量的服务。由于每个服务都需要必要...
Java数据结构-了解复杂度 java

Java数据结构-了解复杂度

2.实例分析与计算  四.写在最后  // 计算斐波那契递归fibonacci的时间复杂度 int fibonacci(int N) { return N < 2 ? N : fibonacci...
Java数据结构-认识顺序表 java

Java数据结构-认识顺序表

目录二.顺序表1.概念及结构2.顺序表的实现打印顺序表获取顺序表的有效长度在pos位置新增元素判断是否包含某个元素查找某个元素对应的位置获取/查找pos位置的元素给pos位置的元素...
腾讯云618

发表评论