Java中的栈和队列

用户11070251

发布于 2024-04-21 08:29:26

3570

发布于 2024-04-21 08:29:26

文章被收录于专栏：Pomath

1.前言

在计算机科学中，数据结构是用来组织和存储数据的方式，以便可以高效地访问和修改。栈和队列是两种最基本的数据结构，它们在各种计算过程中都有广泛的应用。本文将介绍栈和队列的概念、特性以及它们的一些常见应用。

2.栈

2.1概念

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵循后进先出的原则。

压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。

出栈：栈的删除操作叫做出栈。出数据在栈顶。

在现实中我们也有类似的场景，那就是子弹的发射，最后装填进去的子弹是最先发射出去。

2.2栈的使用

在Java中栈又是如何使用的呢？有以下这些方法。

方法	功能
Stack()	构造一个空的栈
E push (E e)	将e入栈，并返回e
E pop()	将栈顶元素出栈并返回
E peak()	获取栈顶元素
int size()	获取栈中有效元素个数
boolean empty()	检测栈是否为空

示例：

public static void main ( String [] args ) { Stack < Integer > s = new Stack (); s . push ( 1 ); s . push ( 2 ); s . push ( 3 ); s . push ( 4 ); System . out . println ( s . size ()); // 获取栈中有效元素个数 ---> 4 System . out . println ( s . peek ()); // 获取栈顶元素 ---> 4 s . pop (); // 4 出栈，栈中剩余 1 2 3 ，栈顶元素为 3 System . out . println ( s . pop ()); // 3 出栈，栈中剩余 1 2 栈顶元素为 3 if ( s . empty ()){ System . out . println ( " 栈空 " ); } else { System . out . println ( s . size ()); } }

2.3栈的实现

从上图中可以看到，Stack继承了Vector，Vector和ArrayList类似，都是动态的顺序表，不同的是Vector是线程安全的。

2.4栈的使用场景

函数调用：每当一个函数被调用时，计算机需要记住从哪里返回到调用它的代码。这通常是通过将返回地址推入栈中来实现的。当函数执行完毕，计算机会从栈中弹出地址，并返回到该地址指示的位置继续执行。
表达式求值：在计算器程序中，栈通常用来转换和评估算术表达式。例如，在将中缀表达式（常见的算术表达式）转换为后缀表达式（便于计算的形式）时，运算符会被推入栈中，等待操作数的到来。当所有操作数都准备好后，运算符会从栈中弹出并应用于操作数。
括号匹配：在文本编辑器或编程语言解析器中，栈可以用来检查括号是否正确匹配。遇到开括号时将其推入栈中，遇到闭括号时尝试从栈中弹出一个开括号并检查是否匹配。
页面访问：在Web浏览器中，栈常用来实现前进和后退功能。当用户访问新页面时，前一个页面会被推入栈中。用户点击后退按钮时，可以从栈中弹出最近访问的页面。
递归实现：在计算机程序中实现递归算法时，每次递归调用实质上是将问题的一部分推入栈中，等待当前问题解决后再处理。递归过程的每一步都在栈上有自己的存储空间，直到达到基本情况。
数制转换：在进行数制转换时，如十进制转八进制或其他进制，可以利用栈来临时存储转换过程中产生的余数，最后从栈顶开始依次输出即得到转换结果。

2.5栈、虚拟机栈、栈帧的区别

栈（Stack）：在Java中，栈是一种数据结构，它遵循后进先出（LIFO）的原则。Java的集合框架中提供了Stack类，它是以向量（Vector）为基础的一个实现，用于存储和管理数据的先进后出的顺序。
虚拟机栈（Virtual Machine Stack）：虚拟机栈是Java虚拟机（JVM）的一部分，它是线程私有的内存区域，与线程同生同灭。虚拟机栈主要用于存储方法调用过程中的相关信息，包括方法的局部变量、返回地址等。当方法被调用时，会在虚拟机栈上创建一个新的栈帧；方法调用结束后，对应的栈帧会被销毁。
栈帧（Stack Frame）：栈帧是虚拟机栈中的一个元素，每次方法调用时都会创建一个栈帧。每个栈帧包含了方法的局部变量表、操作数栈、动态链接以及方法返回地址等信息。局部变量表中存储了编译期可知的各种基本数据类型及对象引用类型的变量。栈帧随方法的调用而创建，随方法执行完毕而销毁。

综上所述，栈是一种通用的数据结构，用于维护数据的先进后出顺序；虚拟机栈是JVM内部为每个线程分配的一个特定区域，用于管理方法调用过程中的数据；而栈帧则是虚拟机栈中用于记录单个方法调用信息的数据块。

3.队列

3.1概念

队列：只允许在一端进行插入数据的操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出的特点。

入队列：进行插入操作的一端称为队尾。

出队列：进行删除操作的一端称为队头

这就类似于生活中排队打饭的场景，排在前面的先打到饭离开队伍，队伍最后的人最后打到饭离开队伍。

3.2队列的使用

在Java中，Queue是个接口，其底层是通过链表来实现的。

常见的方法及功能：

方法	功能
boolean offer(E e)	入队列
E poll()	出队列
peek()	获取队头元素
int size()	获取队列中有效元素的个数
boolean isEmpty()	检测队列是否为空

3.2队列的模拟实现

队列中既然可以存储元素，那底层肯定要有能够保存元素的空间，那么会选择顺序结构还是链式结构呢？

选择顺序结构还是链式结构实现队列，取决于具体的应用场景和需求。以下是两种实现方式的优缺点分析：

顺序队列的优点：

内存使用效率高：顺序队列通常使用数组实现，内存空间连续，利用率高。便于随机访问：数组的特性使得可以在常数时间内随机访问任何元素。操作简便：在队尾插入和队头删除操作的时间复杂度为O(1)。

顺序队列的缺点：

可能出现假溢出：当队列没有满但因为尾指针达到数组边界而无法插入新元素时。大小固定：需要预先定义队列的大小，不利于动态变化的数据量。

链式队列的优点：

大小动态可变：不需要预先定义大小，可以根据需要动态增长。不存在假溢出问题：链表的特性使得即使队列看起来已满，仍然可以继续添加元素。

链式队列的缺点：

内存使用效率低：由于链表需要额外的指针信息，会有额外的内存开销。不便于随机访问：链表不支持快速的随机访问，只能按序遍历。

综上所述，如果对内存使用效率和随机访问有较高要求，且能够接受固定大小的限制，那么顺序队列（特别是循环队列）可能是更好的选择。如果应用需要队列大小能够动态变化，或者对假溢出问题敏感，那么链式队列可能更适合。在实际应用中，应根据具体需求选择合适的数据结构来实现队列。

public class Queue {
    // 双向链表节点
    public static class ListNode{
        ListNode next;
        ListNode prev;
        int value;ListNode(int value){
            this.value = value;
        }
    }
    ListNode first; // 队头
    ListNode last; // 队尾
    int size = 0;
    // 入队列---向双向链表位置插入新节点
    public void offer(int e){
    ListNode newNode = new ListNode(e);
    if(first == null){
        first = newNode;
    // last = newNode;
    }else{
        last.next = newNode;
        newNode.prev = last;
    // last = newNode;
    }
    last = newNode;
    size++;
}
// 出队列---将双向链表第一个节点删除掉
public int poll(){
// 1. 队列为空
// 2. 队列中只有一个元素----链表中只有一个节点---直接删除
// 3. 队列中有多个元素---链表中有多个节点----将第一个节点删除
    int value = 0;
    if(first == null){
        return null;
    }else if(first == last){
        last = null;
        first = null;
    }else{
        value = first.value;
        first = first.next;
        first.prev.next = null;
        first.prev = null;
    }
    --size;
    return value;
}
// 获取队头元素---获取链表中第一个节点的值域
public int peek(){
    if(first == null){
    return null;
    }
    return first.value;
}
    public int size() {
        return size;
    }
    public boolean isEmpty(){
        return first == null;
    }
}