Java栈的理解

    选择打赏方式

栈(stack)

根据英文单词也可以理解为堆,这两个都可以用来表示Java的这种数据结构

栈的特点

  1. 栈区别于链表,它是一种先进后出的序列表
  2. 栈是一种限制插入和删除只能在线性表的同一端进行的一种序列表,允许插入和修改的一端称为顶端,不能更改的一端称为尾端
  3. 最先放入的数据在栈底,最后放入的数据在栈顶
  4. 删除数据的时候最后放入的数据先删除,最先放入的数据最后删除
  5. 取出数据的时候最后放入的数据最先取出,最先放入的数据最后取出

栈的应用场景

  1. 子程序的调用:在跳往子程序之前,会将下一个指令的地址存放在栈中,直到子程序执行完之后再将地址取出,回到原来的子程序中。
  2. 处理递归调用:和子程序的调用类似,只是除了存储地址之外,还将变量,参数存入栈中
  3. 二叉树的遍历
  4. 图形的深度优化(depth-first)搜索方法

使用数组模拟栈

  1. 定义一个top作为栈顶
  2. 入栈:找到栈顶,top++,将此时top对应的栈中存入数据
  3. 出栈;找到栈顶,记录栈顶的top值,将top--,返回原来的top对应的值

    代码实现

package com.snake;

import java.util.Scanner;

public class ArrayStack {
    public static void main(String[] args) {
        ArrayStackDemo stack = new ArrayStackDemo(5);
        String key = "";
        boolean loop = true;
        Scanner scanner = new Scanner(System.in);
        while (loop) {
            System.out.println("show");
            System.out.println("exit");
            System.out.println("push");
            System.out.println("pop");
            System.out.println("请输入");
            key = scanner.next();
            switch (key) {
                case "show":
                    stack.list();
                    break;
                case "exit":
                    scanner.close();
                    loop = false;
                    break;
                case "push":
                    System.out.println("请输入一个数");
                    int value = scanner.nextInt();
                    stack.push(value);
                    break;
                case "pop":
                    try {
                        int res = stack.pop();
                        System.out.println("取出的数据为:"+res);
                    }catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                default:
                    break;
            }
        }
        System.out.println("程序退出");
    }
}

class ArrayStackDemo {
    private int maxSize;
    private int[] stack;
    //表示栈顶
    private int top = -1;

    public ArrayStackDemo(int maxSize) {
        this.maxSize = maxSize;
        stack = new int[maxSize];
    }

    //判断栈满
    public boolean stackIsfull() {
        return top == maxSize - 1;
    }

    public boolean stackEmpty() {
        return top == -1;
    }

    //入栈
    public void push(int value) {
        if (stackIsfull()) {
            System.out.println("栈满");
            return;
        }
        top++;
        stack[top] = value;
    }

    public int pop() {
        if (stackEmpty()) {
            throw new RuntimeException("栈空");
        }
        int value = stack[top];
        top--;
        return value;
    }

    public void list() {
        if (stackEmpty()) {
            System.out.println("栈空");
            return;
        }
        for (int i = top; i >= 0; i--) {
            System.out.println(i + "=" + stack[i]);
        }
    }
}
版权声明:若无特殊注明,本文为《若离风》原创,转载请保留文章出处。
本文链接:https://www.rlfit.cn/post-57.html
正文到此结束

热门推荐

发表吐槽

你肿么看?

你还可以输入 250 / 250 个字

嘻嘻 大笑 可怜 吃惊 害羞 调皮 鄙视 示爱 大哭 开心 偷笑 嘘 奸笑 委屈 抱抱 愤怒 思考 日了狗 胜利 不高兴 阴险 乖 酷 滑稽

评论信息框
可使用QQ号实时获取昵称+头像

私密评论

吃奶的力气提交吐槽中...


既然没有吐槽,那就赶紧抢沙发吧!