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

Java深入了解数据结构之栈与队列的详解

• 数据结构

Java深入了解数据结构之栈与队列的详解

1. 栈的概念

栈(Stack)是一种先进后出的数据结构，类似于一个箱子，新的物品只能放到箱子的顶部，旧的物品只能从箱子的顶部取出。栈通常有下面几个基本操作：

  1. push：将元素压入栈中，放在栈顶。
  2. pop：将栈顶元素弹出，如果栈为空，则抛出异常。
  3. peek：返回栈顶元素，但不将其弹出，如果栈为空，则抛出异常。
  4. isEmpty：判断栈是否为空。
  5. size：返回栈的元素数量。

2. 栈的实现

数组实现

数组实现栈非常简单，使用一个数组和一个指针top来实现，top表示栈顶元素的位置。具体实现代码如下：

public class ArrayStack<E> {

    private static final int DEFAULT_CAPACITY = 10;

    private Object[] data; // 栈数组
    private int top; // 栈顶指针
    private int size; // 栈内元素数量

    // 构造函数，可以指定初始容量
    public ArrayStack(int initialCapacity) {
        if (initialCapacity <= 0) {
            throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
        }
        data = new Object[initialCapacity];
        top = -1;
    }

    // 默认构造函数，容量为10
    public ArrayStack() {
        this(DEFAULT_CAPACITY);
    }

    public void push(E item) {
        if (size == data.length) {
            resize(data.length * 2);
        }
        data[++top] = item;
        size++;
    }

    public E pop() {
        if (isEmpty()) {
            throw new NoSuchElementException("Stack is empty");
        }
        E item = (E) data[top];
        data[top--] = null; // help gc
        size--;
        if (size > 0 && size == data.length / 4) {
            resize(data.length / 2);
        }
        return item;
    }

    public E peek() {
        if (isEmpty()) {
            throw new NoSuchElementException("Stack is empty");
        }
        return (E) data[top];
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public int size() {
        return size;
    }

    private void resize(int capacity) {
        Object[] newData = new Object[capacity];
        for (int i = 0; i < size; i++) {
            newData[i] = data[i];
        }
        data = newData;
    }
}

链表实现

链表实现栈同样非常简单，使用一个链表和一个指针top来实现，top表示栈顶元素的位置。

public class LinkedListStack<E> {

    private Node top; // 栈顶指针
    private int size; // 栈内元素数量

    public void push(E item) {
        top = new Node(item, top);
        size++;
    }

    public E pop() {
        if (isEmpty()) {
            throw new NoSuchElementException("Stack is empty");
        }
        E item = top.item;
        top = top.next;
        size--;
        return item;
    }

    public E peek() {
        if (isEmpty()) {
            throw new NoSuchElementException("Stack is empty");
        }
        return top.item;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public int size() {
        return size;
    }

    private class Node {
        E item;
        Node next;

        Node(E item, Node next) {
            this.item = item;
            this.next = next;
        }
    }
}

3. 队列的概念

队列(Queue)是一种先进先出的数据结构，类似于排队。新来的人只能排在队尾，离开的人只能从队首离开。队列通常有下面几个基本操作：

  1. add：将元素插入队尾。
  2. remove：删除并返回队首元素，如果队列为空，则抛出异常。
  3. element：返回队首元素，但不将其移除，如果队列为空，则抛出异常。
  4. offer：将元素插入队尾，与add方法类似，但是如果队列已满，则返回false。
  5. poll：删除并返回队首元素，与remove方法类似，但是如果队列为空，则返回null。
  6. peek：返回队首元素，但不将其移除，与element方法类似，但是如果队列为空，则返回null。

4. 队列的实现

数组实现

数组实现队列同样非常简单，使用一个数组和两个指针front和rear来实现，front表示队首元素的位置，rear表示队尾元素的位置。具体实现代码如下：

public class ArrayQueue<E> {

    private static final int DEFAULT_CAPACITY = 10;

    private Object[] data; // 队列数组
    private int front; // 队首指针
    private int rear; // 队尾指针
    private int size; // 队列元素数量

    public ArrayQueue(int initialCapacity) {
        if (initialCapacity <= 0) {
            throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
        }
        data = new Object[initialCapacity];
        front = 0;
        rear = -1;
    }

    public ArrayQueue() {
        this(DEFAULT_CAPACITY);
    }

    public void add(E item) {
        if (size == data.length) {
            resize(data.length * 2);
        }
        data[++rear % data.length] = item;
        size++;
    }

    public E remove() {
        if (isEmpty()) {
            throw new NoSuchElementException("Queue is empty");
        }
        E item = (E) data[front];
        data[front++] = null; // help gc
        size--;
        if (size > 0 && size == data.length / 4) {
            resize(data.length / 2);
        }
        return item;
    }

    public E element() {
        if (isEmpty()) {
            throw new NoSuchElementException("Queue is empty");
        }
        return (E) data[front];
    }

    public boolean offer(E item) {
        if (size == data.length) {
            return false;
        }
        data[++rear % data.length] = item;
        size++;
        return true;
    }

    public E poll() {
        if (isEmpty()) {
            return null;
        }
        return remove();
    }

    public E peek() {
        if (isEmpty()) {
            return null;
        }
        return (E) data[front];
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public int size() {
        return size;
    }

    private void resize(int capacity) {
        Object[] newData = new Object[capacity];
        for (int i = 0, j = front; i < size; i++, j++) {
            newData[i] = data[j % data.length];
        }
        data = newData;
        front = 0;
        rear = size - 1;
    }
}

链表实现

链表实现队列也非常简单，使用一个链表和两个指针front和rear来实现，front表示队首元素的位置，rear表示队尾元素的位置。

public class LinkedListQueue<E> {

    private Node front; // 队首指针
    private Node rear; // 队尾指针
    private int size; // 队列元素数量

    public void add(E item) {
        Node node = new Node(item, null);
        if (rear == null) {
            front = node;
            rear = node;
        } else {
            rear.next = node;
            rear = node;
        }
        size++;
    }

    public E remove() {
        if (isEmpty()) {
            throw new NoSuchElementException("Queue is empty");
        }
        E item = front.item;
        front = front.next;
        if (front == null) {
            rear = null;
        }
        size--;
        return item;
    }

    public E element() {
        if (isEmpty()) {
            throw new NoSuchElementException("Queue is empty");
        }
        return front.item;
    }

    public boolean offer(E item) {
        Node node = new Node(item, null);
        if (rear == null) {
            front = node;
            rear = node;
        } else {
            rear.next = node;
            rear = node;
        }
        size++;
        return true;
    }

    public E poll() {
        if (isEmpty()) {
            return null;
        }
        return remove();
    }

    public E peek() {
        if (isEmpty()) {
            return null;
        }
        return front.item;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public int size() {
        return size;
    }

    private class Node {
        E item;
        Node next;

        Node(E item, Node next) {
            this.item = item;
            this.next = next;
        }
    }
}

5. 示例说明

示例1: 使用栈实现括号匹配

我们可以使用栈来实现括号匹配，思路如下：

  1. 从左到右扫描字符串中的每个括号。
  2. 如果是左括号，则将其压入栈中。
  3. 如果是右括号，则从栈中弹出一个元素。
  4. 如果弹出的元素不是相应的左括号，则说明括号不匹配，返回false。
  5. 如果扫描完整个字符串后栈为空，则说明括号匹配，返回true。

代码实现如下：

public class BracketMatch {

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

示例2: 使用队列实现击鼓传花

我们可以使用队列来实现击鼓传花，思路如下：

  1. 从1号到n号给每个人标上编号，形成一个环状队列。
  2. 从第一个人开始报数（1，则出队列），将花传给下一个人，再重新进入队列。
  3. 不断进行此操作，直到最后只剩下一个人。

代码实现如下：

public class PassGame {

    public static int play(int n, int m) {
        ArrayQueue<Integer> queue = new ArrayQueue<>();
        for (int i = 1; i <= n; i++) {
            queue.add(i);
        }
        while (queue.size() > 1) {
            for (int i = 1; i < m; i++) {
                queue.add(queue.remove());
            }
            queue.remove();
        }
        return queue.remove();
    }
}

6. 总结

本文详细讲解了栈和队列的概念和实现方式，通过两个示例说明了如何使用栈和队列解决实际问题。栈和队列是基本的数据结构之一，本文的内容适合初学者学习。

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

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

相关文章

  • 详解C语言实现空间索引四叉树

    详解C语言实现空间索引四叉树攻略 四叉树是一种常见的空间索引方法，可以有效地处理二维或三维空间中的数据。本攻略将详细介绍使用C语言实现空间索引四叉树的方法，包括数据结构的设计，插入和查询操作的实现。 数据结构设计 结点结构体 struct QuadtreeNode { int depth; // 结点深度 double x, y; // 结点中心坐标 dou…

    数据结构 2023年5月17日
    00

  • 数据结构之线性表

    Linear_list 类型定义 一个线性表是n个数据元素的有限序列，线性表中的元素个数n定义为线性表的长度，n=0时成为空表；抽象数据类型： InitList(&L) //构造空线性表L DestroyList(&L) //销毁线性表L ClearList(&L) //将L重置为空表 ListEmpty(L) //若L为空表返回TR…

    算法与数据结构 2023年4月25日
    00

  • 手撕HashMap（二）

    这里再补充几个手撕HashMap的方法 1、remove() remove 方法参数值应该是键值对的键的值，当传入键值对的键的时候，remove 方法会删除对应的键值对 需要利用我们自己先前创建的 hashcodeList 来实现，hashcodeList 存入了所有被使用的 hashcode 值，方便后续的操作 在 put() 中，当添加新的键值对时，就会…

    算法与数据结构 2023年4月18日
    00

  • C语言数据结构之简易计算器

    C语言数据结构之简易计算器攻略 简介 这是一个基于C语言的简易计算器，可以实现加、减、乘、除四个基本运算。 实现步骤 首先，需要声明四个变量，分别表示运算符、被加数、被减数、被乘数和被除数。 char op; double n1, n2, result; 然后，需要通过scanf()函数获取用户输入的运算符和数字。 printf(“请输入运算符和数字：\n”…

    数据结构 2023年5月17日
    00

  • golang优先级队列的实现全过程

    下面是关于”golang优先级队列的实现全过程”的详细讲解。 什么是优先级队列？ 优先级队列是一种常用的数据结构，它可以帮我们按照一定规则（即优先级）将元素按照大小排序，并支持快速插入、删除和查询最大或最小的元素等操作。我们可以将优先级队列想象成一个具有优先级的、自动排序的队列，其中优先级高的元素（比如数字大的元素）排在前面，优先级低的元素（比如数字小的元素…

    数据结构 2023年5月17日
    00

  • C++数据结构之list详解

    C++数据结构之list详解 什么是list？ list是C++ STL库中的一个数据结构，它能够以O(1)的复杂度在任何位置进行插入或删除操作，当然它也支持随机访问指定位置的元素。list属于双向链表，它内部结构为指针连接不同的节点。 如何使用list？ 包含头文件 在C++中使用list，需要包含头文件#include <list>。 定义l…

    数据结构 2023年5月17日
    00

  • 线段树好题！ P2824 [HEOI2016/TJOI2016]排序 题解

    题目传送门 前言 线段树好题！！！！咕咕了挺久的一道题目，很早之前就想写了，今天终于找了个时间A掉了。 题意 给定一个 \(1\) 到 \(n\) 的排列，有 \(m\) 次操作，分两种类型。1.0 l r表示将下标在 \([l, r]\) 区间中的数升序排序。2.1 l r表示将下标在 \([l, r]\) 区间中的数降序排序。给定一个数 \(q\) 询问…

    算法与数据结构 2023年4月17日
    00

  • 数据结构与算法之手撕排序算法

    数据结构与算法之手撕排序算法 本篇攻略介绍如何手撕常见的排序算法。 冒泡排序 冒泡排序是一种通过不断交换相邻元素来排序的方法。它的时间复杂度为$O(n^2)$。 def bubble_sort(nums): for i in range(len(nums)): for j in range(len(nums)-i-1): if nums[j] > nu…

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