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日

相关文章

  • 深入理解Objective-C中类的数据结构

    深入理解Objective-C中类的数据结构 在Objective-C中，类作为面向对象编程的基础，是必不可少的概念。理解Objective-C中类的数据结构，对于开发者理解iOS应用程序的底层原理，以及编写高质量代码具有重要的意义。 类的数据结构 一个Objective-C类由以下几部分组成： isa指针：指向该类对象的元类，元类是描述一个类的对象。isa…

    数据结构 2023年5月17日
    00

  • C语言植物大战数据结构希尔排序算法

    C语言植物大战数据结构希尔排序算法 什么是希尔排序 希尔排序是一种基于插入排序的排序算法，也叫做“缩小增量排序”。和插入排序不同的是，希尔排序的插入排序是对一定间隔的元素进行插入排序，而不是对数组中相邻的元素进行排序。 希尔排序的流程和方法 希尔排序的主要流程是根据元素间的间隔d，分组进行插入排序，依次减小d值。最后当d=1的时候，再按照插入排序的方法对整个…

    数据结构 2023年5月17日
    00

  • JavaScript 处理树数据结构的方法示例

    下面是“JavaScript 处理树数据结构的方法示例”的完整攻略。 什么是树数据结构 树形数据结构是一种非常重要的数据结构，常被用于模拟现实中大量的层级结构。例如：文件目录、网站导航等。其是由一个根节点和若干个子节点构成的，每个节点可以有0个或多个子节点。 使用 JavaScript 处理树形数据结构 了解了树形数据结构后，我们可以使用 JavaScrip…

    数据结构 2023年5月17日
    00

  • 手撕HashMap（二）

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

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

  • Java concurrency集合之LinkedBlockingDeque_动力节点Java学院整理

    Java Concurrency集合之LinkedBlockingDeque_动力节点Java学院整理 LinkedBlockingDeque是什么？ LinkedBlockingDeque是java.util.concurrent包下一个双向阻塞队列，用于在多线程的环境中处理元素序列，它支持在队列两端添加和移除元素。LinkedBlockingDeque可…

    数据结构 2023年5月17日
    00

  • Python数据结构与算法的双端队列详解

    Python数据结构与算法的双端队列详解 双端队列（deque）是一种具有队列和栈的性质的数据结构。与队列和栈不同的是双端队列允许从两端添加和删除元素。Python语言中内置了deque模块，使得在实现双端队列时更加方便快捷。 1.双端队列基本操作 from collections import deque # 创建双端队列 d = deque() # 在队…

    数据结构 2023年5月17日
    00

  • C#数据结构之堆栈(Stack)实例详解

    C#数据结构之堆栈(Stack)实例详解 在编程中，我们经常需要保存一些数据，这些数据可以根据其进入的先后顺序以及其他规则进行处理和访问。其中，堆栈(Stack)是一种简单但是非常有用的数据结构。本文将为大家详细讲解堆栈(Stack)的概念、用法以及C#中的实现方法。 堆栈(Stack)概述 堆栈(Stack)是一种后进先出(LIFO)的数据结构。也就是说，…

    数据结构 2023年5月17日
    00

  • Java数据结构之链表、栈、队列、树的实现方法示例

    Java数据结构之链表、栈、队列、树的实现方法示例 链表 链表是一种线性数据结构，由节点的集合构成。每个节点包含两部分，数据部分和指针部分。数据部分用于存储数据，指针部分用于指向下一个节点。 单向链表示例 public class LinkedList<E>{ private Node<E> head; private int siz…

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