堆栈：概念和应用 — Java

本文解释了堆栈抽象数据类型 (adt) 的基本概念、其后进先出 (lifo) 原则、现实生活中的应用程序（例如浏览器历史记录导航和表达式求值），并提供了基本的 java自定义堆栈的实现。

在计算机科学中，堆栈是一种基本的抽象数据类型（adt），遵循后进先出（lifo）原则，这意味着最后添加到堆栈的项目将最先被删除。术语“堆栈”源自自助餐厅中常见的弹簧分配器中的一堆盘子的类比（carrano & henry，2018）。板被推入堆栈顶部并从顶部弹出，这使得推入和弹出操作成为堆栈 adt 功能的基础。

stack adt 中通常实现的操作有：

• push(e)：将新元素添加到堆栈顶部。
• pop(e)：移除并返回 stack 的顶部元素。
• peek(e)：返回顶部元素而不删除它。
• isempty()：检查堆栈是否为空。
• clear()：从堆栈中删除所有元素​

使用 stack adt 的一个现实场景是 web 浏览器历史记录导航。例如，每次用户离开网页时，浏览器都会将页面 url 推送到 url 历史堆栈上。当点击浏览器的“后退”按钮时，上一页的 url 会从历史堆栈的顶部弹出，而当前页面的 url 会被压入另一个堆栈，我们称之为 url 前向堆栈。相反，当用户点击“转发”按钮时，当前页面的 url 会被压入 url 历史堆栈，并弹出并显示 url 转发堆栈顶部的 url。

立即学习“Java免费学习笔记（深入）”；

stack adt 是强制选择的一个现实场景是在代数表达式求值中，特别是在将中缀代数表达式转换为后缀代数表达式时。在中缀表达式中，运算符放置在操作数之间（例如，a b）；这是人类而不是机器计算使用的常用方式，但它需要括号和优先级规则。另一方面，在后缀表达式中，运算符位于操作数之后（例如 a b ）；不需要括号，并且计算机更容易使用堆栈进行计算，它仅基于操作数和运算符的顺序。在这种情况下，stack adt 非常适合管理操作顺序。堆栈用于临时保存运算符，直到确定它们的优先级和结合性，以确保以正确的顺序计算代数表达式。这使得堆栈成为此类算法中高效且必不可少的 adt。

stack adt 的另一个强制应用是管理编程中的函数调用，特别是在支持递归的环境中，例如 java 虚拟机 (jvm) 或 c 运行时环境。当函数被调用时，函数的局部变量和返回地址被压入调用堆栈。例如，这允许 jvm 在函数执行完成后跟踪程序执行中返回的位置，特别是在递归和嵌套函数调用期间。

下面是一个简单的 java 程序，它模仿了 java 堆栈内存的基本功能。

import java.util.emptystackexception;

// custom stack class
public class mylinkedstack {
    private node top; 
    private int size; 

    // node class to represent each element in the stack
    private static class node {
        private t data;
        private node next;

        public node(t data) {
            this.data = data;
        }
    }

    public mystack() {
        this.top = null;
        this.size = 0;
    }

    public void push(t data) {
        node newnode = new node<>(data);
        newnode.next = top; // set the next reference to the current top
        top = newnode; // make the new node the top of the stack
        size++;
    }

    public t pop() {
        if (isempty()) {
            throw new emptystackexception();
        }
        t poppeddata = top.data;
        top = top.next; // remove the top node
        size--;
        return poppeddata;
    }

    public t peek() {
        if (isempty()) {
            throw new emptystackexception();
        }
        return top.data;
    }

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

    public int size() {
        return size;
    }
}
// class with main method to test the stack
class main {
    public static void mimicjavastackmemory(string[] args) {
        mylinkedstack stack = new mystack<>();

        stack.push(10);
        stack.push(20);
        stack.push(30);

        system.out.println("top element: " + stack.peek()); 
        system.out.println("stack size: " + stack.size()); 

        system.out.println("popped element: " + stack.pop()); 
        system.out.println("popped element: " + stack.pop()); 

        system.out.println("top element after popping: " + stack.peek());
        system.out.println("stack size after popping: " + stack.size()); 
    }
}

输出：

Top element: 30
Stack size: 3
Popped element: 30
Popped element: 20
Top element after popping: 10
Stack size after popping: 1

总而言之，堆栈是一种基本的抽象数据类型 (adt)，遵循后进先出 (lifo) 原则，非常适合浏览器历史记录导航和代数表达式求值等应用程序。它对于管理编程中的函数调用也至关重要，特别是在支持递归的环境中。

参考文献：

carrano, f.m. 和 henry, t.m.（2018 年，1 月 31 日）。 6.1 堆栈。 java 的数据结构和抽象（第五版）。皮尔逊。

最初于 2024 年 9 月 17 日发表于 alex.omegapy - medium。

以上就是堆栈：概念和应用 — Java的详细内容，更多请关注图灵教育其它相关文章！