栈(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日

相关文章

  • C++LeetCode数据结构基础详解

    C++LeetCode数据结构基础详解攻略 什么是LeetCode? LeetCode是一个专门为程序员提供的算法题平台。平台上汇集了各种算法、数据结构和编程题,用户可以在平台上挑战各种难度的算法用来提高自己的编程能力和算法素养。 如何学习LeetCode? 学习LeetCode的关键是掌握数据结构和算法。下面介绍如何结合具体的C++代码来学习LeetCod…

    数据结构 2023年5月17日
    00
  • Python中22个万用公式的小结

    下面是详细讲解“Python中22个万用公式的小结”的完整攻略。 1. 求和公式 求和公式是Python中最基本的公式之一,用于计算一组数的和。求和公式的数学表示如下: $$\sum_{i=1}^{n} a_i = a_1 + a_2 + … + a_n$$ 其中,$a_i$表示第$i$个数,$n$表示数的个数。 下面是Python实现求和公式的示例: …

    python 2023年5月14日
    00
  • Java数据结构及算法实例:插入排序 Insertion Sort

    Java数据结构及算法实例:插入排序 Insertion Sort 算法简介 插入排序是一种简单的排序算法,它的工作方式是每次将一个待排序的元素与前面已经排好序的元素逐个比较,并插入到合适的位置。插入排序的时间复杂度为O(n^2),是一种比较低效的排序算法。 算法实现 以下是使用Java语言实现插入排序算法的代码: public static void in…

    数据结构 2023年5月17日
    00
  • 在Python中实现贪婪排名算法的教程

    在Python中实现贪婪排名算法的教程 贪婪排名算法是一种常用的排序算法,其基本思想是根据每个元素的权重值进行排序,从而得到排名列表。在Python中可以使用sorted()函数实现贪婪排名算法。本文将详细讲解Python实现贪婪排名算法的完整攻略,包算法原理、Python实现过程和示例。 算法原理 贪婪排名算法的基本思想是:根据每个素的权重值进行排序,从而…

    python 2023年5月14日
    00
  • Python基本运算几何运算处理数字图像示例

    Python基本运算、几何运算、处理数字图像示例 Python是一种高级编程语言,它具有简单易学、功能强大、可扩展性强等特点。本文将介绍Python中的基本运算、几何运算和数字图像处理,并提供两个示例说明。 1. 基本运算 Python中的基本运算包括加、减、乘、除、取模、幂等运算。这些运算符可以用于数字、字符串、列表、元组等数据类型。 1.1 数字运算 a…

    python 2023年5月14日
    00
  • 14道基础Python练习题(附答案)

    14道基础Python练习题攻略 这篇攻略将介绍14道基础Python练习题的解法,包括变量、数据类型条件语句、循环句、函数等基础知识点。每道题目会提供详细的解题思路和代码实现,并附带个示例说明。 题目1:变量交换 题目描述:编写一个程序,交换两个变量的值。 解题思路:可以使用一个临时变量来交换两个变量的值。 a = 5 b = 10 # 交换变量的值 te…

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

    以下是详细的讲解: C++数据结构之哈希表的实现 哈希表的概念 哈希表是一种能够实现快速查找的散列表,通过将关键字映射到哈希表中的一个位置来实现快速查找。哈希表的查询、删除时间复杂度为O(1),操作效率非常高,所以常常被用来对大量数据进行检索。 哈希表的实现 哈希函数 哈希函数的主要作用就是将任意长度的输入数据转化为固定长度的散列值,一般采用对关键字进行取模…

    数据结构 2023年5月17日
    00
  • Java数据结构之链表、栈、队列、树的实现方法示例

    Java数据结构之链表、栈、队列、树的实现方法示例 链表 链表是一种线性数据结构,由节点的集合构成。每个节点包含两部分,数据部分和指针部分。数据部分用于存储数据,指针部分用于指向下一个节点。 单向链表示例 public class LinkedList<E>{ private Node<E> head; private int siz…

    数据结构 2023年5月17日
    00
合作推广
合作推广
分享本页
返回顶部