数据结构之栈底层代码实现(数组)以及相关练习题一

题外话

我对不起我的家人们,昨天我偷懒了,只学习了但是并没有写博客,我一定痛改前非,希望家人们给我一个机会!!!(九十度直角鞠躬!)

正题

今天用数组实现一下栈底层代码.

栈底层代码详解

private int[] elem;
private  int usedSize;//代表数组已有元素数量
private  static final int DEAULT_CAPACITY=10;
//模拟栈底层代码(数组)
public stackBottom()
{
    elem=new int[DEAULT_CAPACITY];
}
//添加元素,但要先判断是否满了,满了要扩容
public void push(int x)
{
    if (full())
    {
        elem= Arrays.copyOf(elem,elem.length*2);
    }
    //添加元素
    elem[usedSize]=x;
    //数组元素数量加1
    usedSize++;
}
public boolean full()
{
    //如果usedSize和数组元素数量一样说明满了
    if (usedSize==elem.length)
    {
        return true;
    }
    return false;
}
//先判断是否为空,没有元素无法删除
public int pop()
{
    if (empty())
    {
        throw new EmptyException("数组为空!!");
    }
    //把删除元素保存到old
    int old=elem[usedSize-1];
    usedSize--;
    return old;
}
public boolean empty()
{
    if (usedSize==0)
    {
        return true;
    }
    return false;
}

数组为空异常代码

public class EmptyException extends RuntimeException{
    public EmptyException(String msg)
    {
        super(msg);
    }
}

相关练习题

第一题

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

首先我们都知道栈是先进后出的原则,

A.我们先把1放进去再拿出来,再把2,3,4放进去再拿出来,就是1432

B.我们先把1,2放进去,再把2拿出来,再把3放进去拿出来,再把4放进去拿出来,最后把1拿出来,就是2341

C.我们先把1,2,3放进去,再把3拿出来,我们如果再拿只能拿2(先进后出),不可能拿出来1,所以C是我们要选的

D.我们先把1,2,3放进去,把3拿出来,再把4放进去拿出来,最后把2,1拿出来,就是3,4,2,1

第二题

2.一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，则元素出栈的顺 序是（ B）。

A: 12345ABCDE   B: EDCBA54321   C: ABCDE12345   D: 54321EDCBA

这道题就很明显了,遵循先进后出原则,出栈顺序就是EDCBA54321

第三题

给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。

请你计算该表达式。返回一个表示表达式值的整数。

先介绍一下逆波兰表达式

逆波兰表达式

逆波兰式（Reverse Polish Notation，RPN，或逆波兰记法），也叫后缀表达式（将运算符写在操作数之后）。

以上是官方版本,现在我简单给大家讲解一下

只需要记住逆波兰表达式也叫后缀表达式,

ab+c*ab+e/-  这个就是逆波兰表达式也是后缀表达式

(a+b)*c-(a+b)/e 这是它的中缀表达式,也就是大家数学经常见到的写法

这道题实际上就是把后缀变成中缀把结果算出来就可以了

这里主要就是用栈来解答

这道题出的有点难了,一般不会这么难

第三题代码详解

public int evalRPN(String[] tokens) {
    //先创建一个栈
    Stack<Integer> s=new Stack<>();
    //用foreach循环
    for (String x : tokens) {
        //将数字放入s.push
        if (!isOperation(x)) {
            s.push(Integer.parseInt(x));
        } 
        //如果是运算符,建立两个int变量,取出栈两个元素,利用switch进行加减乘除
        else {
            int num2 = s.pop();
            int num1 = s.pop();
            switch (x) {
                case "+":
                    s.push(num1 + num2);
                    break;
                case "-":
                    s.push(num1 - num2);
                    break;
                case "*":
                    s.push(num1 * num2);
                    break;
                case "/":
                    s.push(num1 / num2);
                    break;
            }
        }
    }
    return s.pop();
}
//判断是否是运算符
private boolean isOperation(String s)
{
    if (s.equals("+")||s.equals("-")||s.equals("*")||s.equals("/"))
    {
        return true;
    }
    return false;
}

小结

今天到此为止,送给大家一句话:

先当孙子再当爷,先穿袜子再穿鞋,多的不说少的不唠,一起努力!!