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

数据结构-栈(详解)

目录

    • 一、栈的基本概念
    • 二、栈的基本操作
    • 三、栈的实现方式
      • 1. 数组实现栈
      • 2. 链表实现栈
    • 四、栈的应用场景
    • 五、总结

一、栈的基本概念

栈(Stack)是一种特殊的线性表,它只允许在表的一端进行插入和删除操作。这一端称为栈顶(Top),另一端称为栈底(Bottom)。栈具有后进先出(Last In First Out,LIFO)的特点,即最后插入的元素最先被删除。

二、栈的基本操作

  • push(element):将元素插入到栈顶。
  • pop():删除栈顶的元素,并返回该元素。
  • peek():返回栈顶的元素,但不删除它。
  • isEmpty():判断栈是否为空。
  • size():获取栈中元素的数量。

三、栈的实现方式

1. 数组实现栈

使用数组实现栈时,需要定义一个固定大小的数组来存储栈中的元素,同时使用一个指针(top)指向栈顶的位置。

public class ArrayStack {
    private int[] array;
    private int top;

    public ArrayStack(int capacity) {
        array = new int[capacity];
        top = -1;
    }

    public void push(int element) {
        if (top == array.length - 1) {
            throw new StackOverflowError("Stack is full");
        }
        array[++top] = element;
    }

    public Integer pop() {
        if (top == -1) {
            return null;
        }
        return array[top--];
    }

    public Integer peek() {
        if (top == -1) {
            return null;
        }
        return array[top];
    }

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

    public int size() {
        return top + 1;
    }
}

2. 链表实现栈

使用链表实现栈时,可以动态地添加和删除节点,不需要预先定义栈的大小。链表实现的栈通常包含一个头节点,指向栈顶。

public class LinkedListStack {
    private Node top;

    private static class Node {
        int value;
        Node next;

        public Node(int value) {
            this.value = value;
        }
    }

    public LinkedListStack() {
        top = null;
    }

    public void push(int element) {
        Node newNode = new Node(element);
        newNode.next = top;
        top = newNode;
    }

    public Integer pop() {
        if (top == null) {
            return null;
        }
        int element = top.value;
        top = top.next;
        return element;
    }

    public Integer peek() {
        if (top == null) {
            return null;
        }
        return top.value;
    }

    public boolean isEmpty() {
        return top == null;
    }

    public int size() {
        int count = 0;
        Node current = top;
        while (current != null) {
            count++;
            current = current.next;
        }
        return count;
    }
}

四、栈的应用场景

栈在计算机科学和实际应用中有着广泛的应用,以下是一些常见的场景:

  • 括号匹配:在编译器设计和文本编辑器中,使用栈来检查括号是否匹配。
  • 逆波兰表达式:栈可以用于计算逆波兰表达式(后缀表达式)的值。
  • 页面回退:浏览器的回退功能可以使用栈来记录访问历史。
  • 递归实现:在递归算法中,系统使用栈来保存函数调用的状态。

五、总结

栈是一种具有后进先出特性的线性表,适用于需要按照相反顺序处理元素的场景。可以通过数组或链表来实现栈,数组实现的栈具有固定大小,而链表实现的栈则更加灵活。掌握栈的基本操作和实现方式,能够帮助我们在实际开发中更好地解决相关问题。希望本文的讲解和示例对您有所帮助,如果您对栈或其他数据结构有任何疑问,欢迎随时交流探讨!


http://www.kler.cn/a/585466.html

相关文章:

  • 【瞎折腾/Dify】使用docker离线部署Dify
  • Unity中解锁图片像素点,动态闭合轨迹检测
  • 【2025】基于python+django的慢性病健康管理系统(源码、万字文档、图文修改、调试答疑)
  • LeeCode题库第643题
  • [目标检测] 训练之前要做什么
  • 【深度学习|目标检测】YOLO系列anchor-based原理详解
  • SpringBoot旅游管理系统的设计与实现
  • [Java]栈 虚拟机栈 栈帧讲解
  • 蓝桥每日打卡--查找有序数组中的目标值
  • kotlin与MVVM的结合使用总结(二)
  • 工业三防平板AORO-P300 Ultra,开创铁路检修与调度数字化新范式
  • python多种数据类型输出为Excel文件
  • 【模块化编程】数据标签 转 独热编码
  • SSL 和 TLS 认证
  • 汉朔科技业绩高增长:市占率国内外遥遥领先,核心技术创新强劲
  • 六十天前端强化训练之第十七天React Hooks 入门:useState 深度解析
  • 嵌入式硬件--开发工具-AD使用常用操作
  • 今日《AI-人工智能-编程》-3月13日
  • 音视频处理工具 FFmpeg 指令的使用(超级详细!)
  • 电子电子架构 --- 车载ECU信息安全