栈的基本应用

简介: 栈的基本应用

✨前言✨

之前已经学习过了栈的相关知识点,本次主要总结一下常见的栈的应用实例


1 出栈与入栈顺序问题:

1.1 选择题

一个栈的入栈顺序是A,B,C,D,E,则出栈顺序不可能的是?( )

A EDCBA

B DECBA

C DCEAB

D ABCDE

题目中隐含的条件就是出栈的同时也是可以进栈的

分析:

对于A选项而言就是不出栈,等A,B,C,D,E依次进栈之后依次出栈,所以是符合栈的后进先出特性的,对于B选项而言,等A,B,C,D进栈之后,在对D进行出栈,然后在将E进栈,然后再把E出栈,最后将C,B,A依次出栈,因此B选项也是正确的,对于C选项与B选项对于,很明显A是不能先于B出栈的,所以C选项是不符合的,D选项就是在进栈的同时进行出栈的操作,所以D选项也是符合要求的。

正确答案: C

1.2 编程题

代码题:OJ链接

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]){//当J下标元素与栈顶元素比较,是否相等,此时j必须是要有意义的,并且此时栈要不为空,才进行出栈操作
              stack.pop();
              j++;
          }
      }
      return stack.empty();//如果符合栈的特性,那么最后一定会是一个空栈。否则就是不符合栈的特性的
    }
}

2 中缀表达式转后缀表达式

2.1 填空题:

将(5+4)*3-2(中缀表达式也被称做为逆波兰式)转化为后缀表达式的结果为:

(1)按先加减后乘除的原则给表达式加括号

(2)在将符合移到对应的括号之后,就可以得到对应的后缀表达式

54+3*2-

2.2 编程题

逆波兰表达式求值:OJ链接

class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack  = new Stack<>();
        for(int i = 0;i<tokens.length;i++){
            String ch = tokens[i];
            if(!INT(ch)){
                //为整数值进栈
                stack.push(Integer.parseInt(ch));//将字符串转化为整数放入栈中
            }else{
                //如果为运算符
                int num1 = stack.pop();
                int num2 = stack.pop();
                int num=0;
                switch(ch){
                    case "+": 
                    num=num2+num1;
                    break;
                    case"-":
                    num=num2-num1;
                    break;
                    case"*":
                    num=num2*num1;
                    break;
                    case"/":
                    num=num2/num1;
                    break;
                }
                stack.push(num);
            }
           
        } 
        return kohaostack.peek();
    }
    public boolean INT(String val){
        //判断是否为符号
        if(val.equals("+")||val.equals("-")||val.equals("*")||val.equals("/")){
            return true;
        }
        return false;
    }
}

3 括号匹配问题

对于栈中,括号匹配问题是一个挺重要的一个笔试的考点,具体题目分析如下:

括号匹配问题详解链接

4 最小栈的问题

最小栈:OJ链接

class MinStack {
    Stack<Integer> stack;
    Stack<Integer> minStack;
    public MinStack() {
        stack=new Stack<>();
        minStack=new Stack<>();
    }
    
    public void push(int val) {
        if(minStack.empty()){
            stack.push(val);
            minStack.push(val);
            return;
        }
        if(minStack.peek()>=val){
            stack.push(val);
            minStack.push(val);
        }else{
            stack.push(val);
        }
    }
    
    public void pop() {
        if(stack.peek()>minStack.peek()){
            stack.pop();
        }else{
            stack.pop();
            minStack.pop();
        }
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int getMin() {
        return minStack.peek();
    }
}
目录
相关文章
|
6天前
数据结构——栈和队列
数据结构——栈和队列
8 1
|
9天前
|
存储 算法 调度
数据结构与算法-栈篇
数据结构与算法-栈篇
12 3
|
2天前
|
算法
$停车场管理系统 栈与队列
$停车场管理系统 栈与队列
5 1
|
2天前
|
存储 缓存 算法
|
6天前
数据结构 栈 / 队列(第9天)
数据结构 栈 / 队列(第9天)
|
6天前
|
存储 算法 程序员
【C++进阶】深入STL之 栈与队列:数据结构探索之旅
【C++进阶】深入STL之 栈与队列:数据结构探索之旅
15 4
|
7天前
|
C语言 C++
【数据结构】C语言实现:栈(Stack)与队列(Queue)
【数据结构】C语言实现:栈(Stack)与队列(Queue)
|
9天前
|
机器学习/深度学习 存储 算法
PHP中的数据结构及其在机器学习中的应用
本文探讨了PHP在机器学习中的作用,强调了数据结构的重要性。文中列举了PHP中的常见数据结构,如数组、对象、字典、链表、树和图,并解释了它们在机器学习场景下的应用。例如,数组用于特征向量,对象封装模型,字典存储特征映射,链表和树实现特定算法。通过示例代码展示了如何使用这些数据结构进行特征标准化和模型预测。文章总结指出,PHP的数据结构为机器学习提供了有效工具,随着技术发展,PHP在数据处理领域的应用将持续扩展。
19 4
|
9天前
数据结构初阶 栈
数据结构初阶 栈
10 1

热门文章

最新文章