栈(Stack)

概述

  • 栈就是一种 只允许在表尾进行插入和删除操作 的 线性表
  • 栈的特点
    • 先进后出 ,在表尾进行插入和删除操作

空栈.png
入栈.png
出栈.png

数组实现栈

  • crown
    • crown:使用bottom来确定栈顶所在数组的下标,默认为 -1
  • 空栈
    • 当空栈时 ,crown = -1
  • 栈是否为空
    • 当 crown = -1 时 ,栈为空 ,不能 遍历 ,出栈 , 获取栈顶元素
  • 栈是否已满
    • 当 crown = 数组.length - 1 时 ,栈已满 , 不能 入栈
  • 入栈
    • 栈未满,才能入栈
      • 先将 crown上移 ,再给数组下标为crown的元素赋值
    • 栈满 ,不能入栈
  • 出栈
    • 栈不为空 ,才能出栈
      • 将 crown往下移即可
    • 栈为空 ,不能出栈
  • 获取栈顶元素
    • 栈不为空 ,才能获取栈顶元素
      • 获得数组下标为crown的元素
    • 栈为空 ,不能出栈
  • 重置栈
    • 让crown = -1 即可
  • 打印栈
    • 遍历数组下标范围为 [ 0 , crown ] ,即可
public class ArrayStack {
    private int[] satck;
    private int size;
    private int crown = -1; // 栈顶
    public ArrayStack(int size){
        this.size = size;
        satck = new int[size];
    }
    //入栈操作
    public void push(int value){
        if (!isFull()){
            satck[++crown] = value;
        }
    }
    //出栈
    public void pop(){
        if (!isEmpty()){
            crown--;
        }
    }
    //判断是否为空
    public boolean isEmpty(){
        return crown == -1;
    }
    //判断栈是否已满
    public boolean isFull(){
       return crown == size-1;
    }
    //获取栈顶元素
    public int getTop(){
        if (!isEmpty()){
            return satck[crown];
        }
        return -1;
    }
    //重置栈
    public void  reset(){
        crown = -1;
    }
    //打印栈 , 从栈顶开始打印
    public void print(){
        int j = 0;
        for (int i = crown; i >= 0; i--) {
            System.out.println("第"+(++j)+"个元素为:" + satck[i]);
        }
    }
}

/**
 * @author 发着呆看星
 * @create 2023/4/18
 **/
public class ArrayStackTest {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        ArrayStack arrayStack = new ArrayStack(5);
        boolean p = true;
        while (p){
            System.out.println("==================栈的功能检测===================");
            System.out.println("1) 入栈");
            System.out.println("2) 出栈");
            System.out.println("3) 重置栈");
            System.out.println("4) 打印栈");
            System.out.println("5) 取出栈顶元素");
            System.out.println("6) 退出程序");
            System.out.print("请选择你需要的功能(1~~6):");
            int i = scanner.nextInt();
            int j;
            switch (i){
                case 1:
                    System.out.print("请选择你要入栈的数字:");
                    j = scanner.nextInt();
                    arrayStack.push(j);
                    break;
                case 2:
                    arrayStack.pop();
                    break;
                case 3:
                    arrayStack.reset();
                    break;
                case 4:
                    arrayStack.print();
                    break;
                case 5:
                    int top = arrayStack.getTop();
                    System.out.println("栈顶元素为:"+top);
                    break;
                case 6:
                    p = false;
                    break;
            }
        }
    }
}

链表实现栈

  • 实现思路
    • 入栈:将每一个入栈的元素添加为链表的首节点
    • 出栈:出栈则将链表的首节点进行删除
    • 由于链表可以无限长,所以不用担心栈满的问题
  • crown:代表栈顶元素的上一个元素 ,val属性默认为 -1 ,next 属性即为 栈顶元素
    • 当 next == null 时 ,代表空栈
  • 判断栈是否为空
    • 当crown.next == null 时 ,栈为空
  • 重置栈
    • 即将 crown的next属性置为null
  • 获取栈顶元素
    • 即获取链表首节点(获取crown的next属性所代表的节点)
  • 打印栈
    • 即遍历链表

链表空栈.png
链表入栈.png
链表出栈.png


/**
 * @author 发着呆看星
 * @create 2023/4/18
 **/
public class LinkedListStack {
    private ListNode crown = new ListNode(-1,null);
    // 判断是否为空
    public boolean isEmpty(){
        return crown.next == null;
    }
    // 入栈操作
    public void push(int value){
        ListNode temp = crown.next;
        crown.next = new ListNode(value, temp);
    }
    // 出栈操作
    public void pop(){
        if (!isEmpty()){
            crown.next = crown.next.next;
        }
    }
    // 取出栈顶元素
    public ListNode getTop(){
        return crown.next;
    }
    // 重置栈
    public void reset(){
        crown.next = null;
    }
    // 打印栈 ,从栈顶开始
    public void print(){
        ListNode temp = crown;
        int i = 0;
        while (temp.next != null){
            System.out.println("第"+(++i)+"个元素为:"+temp.next.val);
            temp = temp.next;
        }
    }
}
/**
 * @author 发着呆看星
 * @create 2023/4/18
 **/
public class LinkedListStackTest {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        LinkedListStack stack = new LinkedListStack();
        boolean p = true;
        while (p){
            System.out.println("==================栈的功能检测===================");
            System.out.println("1) 入栈");
            System.out.println("2) 出栈");
            System.out.println("3) 重置栈");
            System.out.println("4) 打印栈");
            System.out.println("5) 取出栈顶元素");
            System.out.println("6) 退出程序");
            System.out.print("请选择你需要的功能(1~~6):");
            int i = scanner.nextInt();
            int j;
            switch (i){
                case 1:
                    System.out.print("请选择你要入栈的数字:");
                    j = scanner.nextInt();
                    stack.push(j);
                    break;
                case 2:
                    stack.pop();
                    break;
                case 3:
                    stack.reset();
                    break;
                case 4:
                    stack.print();
                    break;
                case 5:
                    ListNode top = stack.getTop();
                    System.out.println("栈顶元素为:"+top);
                    break;
                case 6:
                    p = false;
                    break;
            }
        }
    }
}

原文链接:https://www.cnblogs.com/fzdkx/p/17332022.html

本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:栈(Stack) - Python技术站

(0)
上一篇 2023年4月18日
下一篇 2023年4月19日

相关文章

  • Go语言数据结构之二叉树必会知识点总结

    Go语言数据结构之二叉树必会知识点总结 二叉树是一种非常重要的数据结构,它被广泛应用于算法、数据处理等领域。在Go语言中,使用二叉树可以实现很多高级数据结构和算法。本文将为大家介绍二叉树相关的基本知识和操作,以及如何利用Go语言实现二叉树。 什么是二叉树? 二叉树是一种树形结构,由一个根节点和两个子树组成。它的每个节点最多有两个子节点,称为左子节点和右子节点…

    数据结构 2023年5月17日
    00
  • python中Apriori算法实现讲解

    下面是关于“Python中Apriori算法实现讲解”的完整攻略。 1. Apriori算法简介 Apriori算法是一种经典的关联规则挖掘算法,它可以从大规模数据集中挖掘出频繁项集和关联规则。Apriori算法的核心思想是利用频繁项集的性质,通过逐层扫描数据集,生成候选项集,并通过剪枝操作去除不满足最小支持度的项集,最终得到频繁项集和关联规则。 2. Py…

    python 2023年5月13日
    00
  • Python实现遗传算法(虚拟机中运行)

    Python实现遗传算法的完整攻略 遗传算法是一种常用的优化算法,它模拟自然选择和遗传机制,通过不断迭代优化问题的。遗传算法通常用于解决复的优化问题,例如组合优化、函数优化和机器学习。 在本文中,我们将介绍如何使用Python实现遗传算法。我们将分为以下几个步骤: 导入必要的库 定义问题 初始化种群 实现遗传算法 实现选择、交叉和变异操作 步1:导入必要的库…

    python 2023年5月14日
    00
  • Python实现求解斐波那契第n项的解法(包括矩阵乘法+快速幂)

    以下是关于“Python实现求解斐波那契第n项的解法(包括矩阵乘法+快速幂)”的完整攻略: 简介 斐波那契数列是一个非常经典的数列,它的每一项都是前两项的和。在本教程中,我们将介绍Python实现求解斐波那契第n项的解法,包括矩阵乘法和快速幂两种方法。 矩阵乘法 矩阵乘法是一种高效的求解斐波那契数列的方法。我们可以使用矩阵乘法的方式来计算斐波那契数列的第n项…

    python 2023年5月14日
    00
  • Python数据拟合与广义线性回归算法学习

    Python数据拟合与广义线性回归算法学习 数据拟合和广义线性回归是机器学习中常用的技术,用于建立数据模型并预测结果。本文将详细讲解Python实现数据拟合和广义线性回归算法的整个攻略,包括算法原理、实现过程和示例。 算法原理 数据拟合 数据拟合是一种用于建立数据模型的技术,基本思想是通过拟合已有数据来预测未来的结果。在Python中,可以使用numpy和s…

    python 2023年5月14日
    00
  • 使用python实现ANN

    以下是关于“使用Python实现ANN”的完整攻略: 简介 人工神经网络(Artificial Neural Network,ANN)是一种模拟人脑神经元之间相互作用的计算模型,它可以用于分类、回归和聚类等任务。在本教程中,我们将介绍如何使用Python实现ANN,并提供两个示例说明。 实现ANN 以下是使用Python实现ANN的代码: import nu…

    python 2023年5月14日
    00
  • C++数据结构之单链表的实现

    C++数据结构之单链表的实现可分为以下步骤: 1. 定义链表节点类 链表节点类需要包含两个成员变量,一个是存储数据的变量,另一个是指向下一个节点的指针变量。同时,需要实现构造函数和析构函数。 class Node{ public: int data; // 存储节点数据 Node* next; // 指向下一个节点的指针 Node(int data):dat…

    数据结构 2023年5月17日
    00
  • Python算法思想集结深入理解动态规划

    以下是关于“Python算法思想集结深入理解动态规划”的完整攻略: 简介 动态规划是一种常见的算法思想,它可以用于解决许多优化问题。在本教程中,我们将介绍如何使用Python实现动态规划算法,包括动态规划的基本原理、动态规划的实现方法、动态规划的优化等。 动态规划的基本原理 动态规划的基本原理是将一个大问题分解为多个小问题,并将小问题的解合并成大问题的解。动…

    python 2023年5月14日
    00
合作推广
合作推广
分享本页
返回顶部