当前位置: 首页 > biancheng >正文

Java数据结构 | 栈及其应用

目录

一 、 栈

二、栈的模拟实现

三、 栈的应用


一 、 栈

:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。栈中的数据元素遵守先进后出LIFO(Last In First Out)的原则。

栈顶(Top):线性表允许进行插入删除的那一端。 栈底(Bottom):固定的,不允许进行插入和删除的另一端。 空栈:不含任何元素的空表。

  • 栈的使用

方法功能
Stack()构造一个空的栈
E push(E e)将e入栈,并返回e
E pop()将栈顶元素出栈并返回
E peek()获取栈顶元素
int size()获取栈中有效元素个数
boolean empty()检测栈是否为空

根据栈的底层代码可以得知。栈的底层就是使用数组来实现的

Java 集合框架中的 Stack 继承自 Vector

  • 由于 Vector 有 4 个构造函数,加上 Stack 本身的一种,也就是说有 5 中创建 Stack 的方法

  • 跟 Vector 一样,它是可以由数组实现的栈

那么就可以使用数组来简单的模拟实现栈

二、栈的模拟实现

那么就可以使用数组来简单的模拟实现栈

  • 栈的模拟实现

    • 初始化栈

    public class MyStack {
        public int elem[];
    ​
        public int usedsize;
    ​
        //设置一个默认的大小
        public static final int DEFAULT_SIZE = 10;
    ​
        public MyStack(){
            this.elem = new int[DEFAULT_SIZE];
        }
    • 压栈的实现

     public int push(int val){
         //将val压入栈,并返回val,判断栈是否为满,如栈满则进行扩容
            if(isFull()){
                elem = Arrays.copyOf(elem,2*elem.length);
            }
         //使用数组实现栈时,栈顶元素的下标即usedsize-1,在usedsize下标处新增元素即可
            this.elem[usedsize] = val;
            usedsize++;
            return val;
        }
    • 判满实现

    public boolean isFull(){
            return usedsize == elem.length;
        //如果usedsize等于数组的长度则满
      }
    • 元素出栈

     public int pop(){
           if(isEmpty()){
               throw new StackEmptyException("此时栈为空");
           }
         //先将usedsize--再返回
           return elem[--usedsize];
     }
    • 判空实现

    public boolean isEmpty(){
            return usedsize == 0;
    }
    //自定义异常
    public class StackEmptyException extends RuntimeException{
        public StackEmptyException() {
        }
        public StackEmptyException(String message) {
            super(message);
        }
    }
    • 获取栈顶元素(仅获取不改变位置)

    public int peek(){
           if(isEmpty()){
               throw new StackEmptyException("此时栈为空");
           }
           return elem[usedsize-1];
    }
    • 测试

    public class TestStack {
        public static void main(String[] args) {
            MyStack stack = new MyStack();
            stack.push(1);
            stack.push(2);
            stack.push(3);
            stack.push(4);
            stack.push(5);
            stack.push(6);
            System.out.println(stack.peek());
            System.out.println(stack.pop());
            System.out.println(stack.pop());
        }
    }

     

三、 栈的应用

  • 改变元素的序列

若进栈序列为 1,2,3,4 ,进栈过程中可以出栈,则下列不可能的一个出栈序列是()

A: 1,4,3,2 B: 2,3,4,1 C: 3,1,4,2 D: 3,4,2,1

根据栈先进后出的性质,结合题目中进栈的过程中也可以出栈,如A选项:1进1出,2进3进4进,4出3出2出即符合题意,同理C选项,1进2进3进3出之后不可能直接出1,故C选项不可能实现。

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

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

先进后出,依次入栈,依次出栈,故B选项合理

  • 逆波兰表达式求值( 后缀表达式)

逆波兰表达式是一种后缀表达式,所谓后缀就是指算符写在后面。

平常使用的算式则是一种中缀表达式,如 ( 1 + 2 ) * ( 3 + 4 ) 。 该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。

(a+b)*c-(a+b)/e的后缀表达式为:

(a+b)*c-(a+b)/e

→((a+b)*c)((a+b)/e)-

→((a+b)c*)((a+b)e/)-

→(ab+c*)(ab+e/)-

→ab+c*ab+e/-

思路:构造一个判断运算符的函数,然后判断为数字则入栈,遇到运算符则弹出两个元素进行相关操作,将运算得到的结果再次入栈,直至将最后的元素弹出栈即为最后的结果。

( ( 1 2 + ) ( 3 4 + ) * )

1,2先入栈,遇到运算符+即出栈,1,2相加得3入栈,3,4同理得7入栈,最后遇到 * ,3,7出栈相乘得结果为21

代码实现:

  public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
      //字符数组进行遍历
        for(String x : tokens){
            if(!isOperation(x)){
                //使用parseInt()函数将字符串转换为整型
                stack.push(Integer.parseInt(x));
            }else{
                //如果遇到运算符,弹出数据进行相关操作
                int num2 = stack.pop();
                int num1  = stack.pop();
                switch(x){
                    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 s){
        if(s.equals("+")||s.equals("-")||s.equals("*")||s.equals("/")){
            return true;
        }else{
            return false;
        }
    }
  • 将递归转化为循环

如:逆序打印链表

递归实现逆序打印

 public void display(ListNode head){
        if(head == null){
            return;
        }
     //直到链表末尾,再归回去
        if(head.next == null){
            System.out.println(head.val+" ");
            return;
        }
        display(head.next);
        System.out.println(head.val+" ");
}

使用栈实现逆序打印

public void display(ListNode head){
        if(head == null){
            return;
         }
        Stack<ListNode> stack  = new Stack<>();
        ListNode cur = head;
         while(cur!= null){
              stack.push(cur);
              cur = cur.next;
             }
        while(!stack.empty()){
            ListNode ret =   stack.pop();
            System.out.println(ret.val+" ");
        }
    }

利用栈先进后出的特性,将链表的节点都加入栈中,然后再依次出栈,并打印栈中节点的 val 的值,即实现了链表的逆序打印。

ced485cbb11e458d81a746890b32cf3f.gif

相关文章:

  • 牛客练习赛#84 F 莫比乌斯反演+杜教筛+技巧+斐波那契数列和gcd的结论+矩阵快速幂
  • ZZNUOJ_用C语言编写程序实现1342:支配值数目(附完整源码)
  • java毕业设计后勤管理系统餐饮评价监督系统(附源码、数据库)
  • 前端基础学习笔记
  • 【TS】联合类型--类型断言--类型推断
  • 谈笑风声的秘密
  • QT影城网上售票系统
  • NetCDF数据在ArcMap中的使用
  • 打怪升级(考验思路)
  • 持续精进,改变自己