1. Python技术站首页
  2. 数据结构

Java数据结构之栈与队列实例详解

• 数据结构

Java数据结构之栈与队列实例详解攻略

简介

栈和队列是常见的数据结构，在Java中也有对应的实现方式。本文将介绍栈和队列的概念、常见实现方式、应用场景和两个示例。

栈

概念

栈是一种具有后进先出（Last In First Out）特性的数据结构。栈可以使用数组或链表实现。

常见实现方式

基于数组的栈实现

使用数组作为底层存储结构实现栈时，需要注意栈顶指针和数组的下标对应的关系。在栈中，栈顶指针指向栈顶元素的下标，而数组下标从0开始，因此需要额外维护一个变量记录栈顶指针。

public class ArrayStack<E> {

    private final Object[] arr;
    private int top = -1;

    public ArrayStack(int capacity) {
        arr = new Object[capacity];
    }

    public boolean push(E e) {
        if (top == arr.length - 1) {
            return false;
        }
        arr[++top] = e;
        return true;
    }

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

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

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

}

基于链表的栈实现

使用链表作为底层存储结构实现栈时，每次插入或删除一个元素只需要改变指针的指向就可以了。

public class LinkedListStack<E> {

    private Node<E> top = null;

    private static class Node<E> {

        private final E value;
        private Node<E> next;

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

    }

    public boolean push(E e) {
        Node<E> newNode = new Node<>(e);
        newNode.next = top;
        top = newNode;
        return true;
    }

    public E pop() {
        if (top == null) {
            return null;
        }
        E value = top.value;
        top = top.next;
        return value;
    }

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

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

}

应用场景

栈的应用场景非常广泛，下面简单列举一些：

  1. 函数调用栈：在函数调用的时候，每个函数都有自己的局部变量和参数。这些变量和参数都保存在栈中，每次函数调用结束之后，这些变量和参数都会从栈中弹出。

  2. 浏览器历史记录：在浏览器中，每次访问一个新的页面都会把这个页面的信息压入栈中，每次返回上一个页面的时候就从栈中弹出最新的页面信息。

  3. 表达式求值：在计算机中，表达式求值的时候会用到栈。例如，中缀表达式需要转化成后缀表达式后再进行计算，转化过程中需要借助栈来存储操作符。

...

示例

示例一

给定一个仅由括号和字母组成的字符串，判断这个字符串中的括号是否成对出现。

例如：字符串“{}”是符合规则的，而字符串“{”就不符合规则。

public boolean isValid(String s) {
    Stack<Character> stack = new Stack<>();
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (c == '(' || c == '{' || c == '[') {
            stack.push(c);
        } else {
            if (stack.isEmpty()) {
                return false;
            }
            char top = stack.pop();
            if (c == ')' && top != '(') {
                return false;
            }
            if (c == '}' && top != '{') {
                return false;
            }
            if (c == ']' && top != '[') {
                return false;
            }
        }
    }
    return stack.isEmpty();
}

示例二

将一个数组中的元素从头到尾依次压入栈中，再依次从栈中弹出元素，输出的结果与原来的数组顺序相反。

public void reverse(int[] nums) {
    Stack<Integer> stack = new Stack<>();
    for (int i = 0; i < nums.length; i++) {
        stack.push(nums[i]);
    }
    for (int i = 0; i < nums.length; i++) {
        nums[i] = stack.pop();
    }
}

队列

概念

队列是一种具有先进先出（First In First Out）特性的数据结构。队列也可以使用数组或链表实现。

常见实现方式

基于数组的队列实现

使用数组作为底层存储结构实现队列时，需要注意队头指针和队尾指针的指向关系。在队列中，队头指针指向队列中第一个元素，队尾指针指向队列中最后一个元素的下一个位置。在入队或出队的时候分别更新队尾指针和队头指针即可。

public class ArrayQueue<E> {

    private final Object[] arr;
    private int front = 0;
    private int rear = 0;

    public ArrayQueue(int capacity) {
        arr = new Object[capacity + 1];
    }

    public boolean enqueue(E e) {
        if (front == (rear + 1) % arr.length) {
            return false;
        }
        arr[rear] = e;
        rear = (rear + 1) % arr.length;
        return true;
    }

    public E dequeue() {
        if (front == rear) {
            return null;
        }
        E value = (E) arr[front];
        front = (front + 1) % arr.length;
        return value;
    }

    public E peek() {
        if (front == rear) {
            return null;
        }
        return (E) arr[front];
    }

    public boolean isEmpty() {
        return front == rear;
    }

}

基于链表的队列实现

使用链表作为底层存储结构实现队列时，入队和出队操作只需要改变指针的指向就可以了。

public class LinkedListQueue<E> {

    private Node<E> head = null;
    private Node<E> tail = null;

    private static class Node<E> {

        private final E value;
        private Node<E> next;

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

    }

    public boolean enqueue(E e) {
        Node<E> newNode = new Node<>(e);
        if (tail == null) {
            head = newNode;
        } else {
            tail.next = newNode;
        }
        tail = newNode;
        return true;
    }

    public E dequeue() {
        if (head == null) {
            return null;
        }
        E value = head.value;
        head = head.next;
        if (head == null) {
            tail = null;
        }
        return value;
    }

    public E peek() {
        if (head == null) {
            return null;
        }
        return head.value;
    }

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

}

应用场景

队列的应用场景也非常广泛，下面简单列举一些：

  1. 任务队列：在线程池等多线程应用中，需要通过队列来存储任务，等待线程池中的线程来处理。

  2. 消息队列：在分布式系统中，需要通过消息队列来协调各个模块的数据交换。

  3. 广度优先搜索：在算法中，广度优先搜索需要用到队列。

...

示例

示例一

给定一个由数字组成的数组和一个数字k，求这个数组中所有长度为k的连续子数组的和。

例如：给定数组[1,2,3,4,5,6]和k=3，输出[6,9,12,15]。

public int[] findSubArraySum(int[] nums, int k) {
    int[] result = new int[nums.length - k + 1];
    LinkedListQueue<Integer> queue = new LinkedListQueue<>();
    int index = 0;
    int sum = 0;
    for (int i = 0; i < nums.length; i++) {
        queue.enqueue(nums[i]);
        sum += nums[i];
        if (queue.size() > k) {
            sum -= queue.dequeue();
        }
        if (queue.size() == k) {
            result[index++] = sum;
        }
    }
    return result;
}

示例二

将一个数组中的元素从头到尾依次加入队列中，再依次从队列中取出元素，输出的结果与原来的数组顺序相同。

public void print(int[] nums) {
    LinkedListQueue<Integer> queue = new LinkedListQueue<>();
    for (int i = 0; i < nums.length; i++) {
        queue.enqueue(nums[i]);
    }
    while (!queue.isEmpty()) {
        System.out.println(queue.dequeue());
    }
}

本站文章如无特殊说明，均为本站原创，如若转载，请注明出处：Java数据结构之栈与队列实例详解 - Python技术站

赞 (0)
0 0 打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2023年5月17日
下一篇 2023年5月17日

相关文章

  • python学习数据结构实例代码

    “Python学习数据结构实例代码”的完整攻略如下： 1. 学习前提 在学习Python数据结构之前，需要具备一定的Python基础知识，包括语法、数据类型、操作符、控制流等基础知识。 2. 学习步骤 2.1 选择学习资料 可以选择阅读相关书籍或者参加在线课程来学习Python数据结构。推荐一些经典的学习资料： 《Python基础教程》第二版（作者：Magn…

    数据结构 2023年5月17日
    00

  • C语言数据结构实现银行模拟

    C语言数据结构实现银行模拟攻略 背景介绍 银行模拟是计算机学科中一个重要的数据结构实践练习项目。它涉及到队列（Queue）等数据结构的应用，也是计算机基础课程的一个重要组成部分。 代码实现 1. 队列的实现 首先，我们需要实现一个队列（Queue）结构体，包含 QueueSize、Front、Rear 三个成员变量： struct Queue { int Q…

    数据结构 2023年5月17日
    00

  • 使用C语言构建基本的二叉树数据结构

    下面是使用C语言构建二叉树数据结构的步骤和示例： 1. 定义二叉树结构体类型 定义一个二叉树的结构体，包含节点值、左右子节点等信息： typedef struct TreeNode { int val; struct TreeNode* left; struct TreeNode* right; } TreeNode; 2. 实现创建二叉树的函数 实现一个函…

    数据结构 2023年5月17日
    00

  • C语言位图算法详解

    C语言位图算法详解攻略 什么是位图算法？ 位图算法，顾名思义，就是用位来表示某个信息或数据，其通常用于对大量数据的处理和存储，以及对某类数据的快速搜索和查找。在计算机科学中，位图算法往往指的是基于0和1的二进制位操作。在C语言中，我们可以使用unsigned char数组来实现位图算法。 位图算法的优缺点 优点 空间利用效率高：用1bit来表示一个信息或数据…

    数据结构 2023年5月17日
    00

  • Javascript数据结构与算法之列表详解

    Javascript数据结构与算法之列表详解 简介 本文旨在讲解Javascript中数据结构和算法的列表。 列表定义和实现 列表是一组有序的数据，每个列表中的数据项称为元素。在Javascript中，列表可以用数组来实现。数组的好处是它能够存储任意类型的数据，而且可以根据需要动态地调整数组的大小。下面是一个创建列表的基本模板： function List(…

    数据结构 2023年5月17日
    00

  • JavaScript树形数据结构处理

    对于“JavaScript树形数据结构处理”的完整攻略，我将从以下几个方面进行讲解： 树形数据结构的简介 树形数据结构在JavaScript中的表示 树形数据结构的处理方法 示例说明 树形数据结构的简介 树形数据结构，是一种常见的数据结构，由多个节点组成，每个节点有一个父节点和多个子节点。树形数据结构通常用来表示层级关系的数据。 树形数据结构在JavaScr…

    数据结构 2023年5月17日
    00

  • JavaScript数据结构yocto queue队列链表代码分析

    JavaScript数据结构yocto queue队列链表代码分析 什么是队列？ 队列（Queue）是一种基础的数据结构，属于线性结构，它的特点是在队列尾插入元素，同时在队列头删除元素，遵循先进先出（FIFO）的原则。队列可以简单的理解为排队，先到达的先被服务，而后到达的则等在队列尾排队等待。队列的应用非常广泛，例如排队系统、消息队列等。 队列的实现方式 队…

    数据结构 2023年5月17日
    00

  • 解析Facebook的数据库查询引擎Presto在美团的应用

    解析Facebook的数据库查询引擎Presto在美团的应用 什么是Presto？ Presto是一个面向分布式查询的数据引擎，由Facebook开发并开源。它支持SQL查询，可以在不同类型的数据源中查询数据（如Hadoop HDFS、Hive等），具有快速、可扩展、灵活等特点。 Presto在美团的应用 美团使用Presto来进行大数据分析，帮助其优化运营…

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