Stack详解(Java)

发布时间:2024年01月17日

Stack

Java 中的 Stack 是一种基于后进先出(LIFO)原则的数据结构。Stack 类实现了一个标准的堆栈,它继承自 Vector 类,并提供了一些额外的方法来支持堆栈的操作。

下面是一些 Java Stack 类的详细解释:

  1. 构造方法:

    • Stack():创建一个空的堆栈。
  2. 核心方法:

    • push(E item):将元素压入堆栈的顶部。
    • pop():移除并返回堆栈顶部的元素。
    • peek():返回但不移除堆栈顶部的元素。
    • empty():检查堆栈是否为空。
    • search(Object o):在堆栈中搜索指定元素,并返回其相对于堆栈顶部的位置。
  3. 其他方法:

    • isEmpty():检查堆栈是否为空。
    • size():返回堆栈中的元素数量。

Stack 类提供了一个方便的方式来实现堆栈的行为。它使用向量(Vector)作为底层数据结构,因此可以动态调整大小以适应存储元素的需求。

Tips:Vector 是一种动态数组,它可以根据需要自动调整大小以容纳元素。

Vector 的特点包括:

  • Vector 是一个可变大小的数组,可以在运行时添加或删除元素。
  • Vector 保持元素的顺序,即元素的插入和删除操作会影响到其他元素的索引。
  • Vector 支持随机访问,可以通过索引来获取元素。
  • Vector 是线程安全的,即多线程环境下也可以安全地访问和修改。

由于 Stack 类继承自 Vector 类,所以 Stack 类内部使用 Vector 来存储堆栈中的元素。这意味着在 Stack 中可以使用 Vector 提供的方法和功能来操作堆栈。

然而,需要注意的是,虽然 Vector 是线程安全的,但在单线程环境下,使用 ArrayDeque 作为替代可能更好。ArrayDeque 是 Java 提供的另一种实现堆栈的类,它在性能上比 Vector 更高效。


1. ArrayDeque

ArrayDeque 是一个双端队列(deque)的实现,它可以在队列的两端进行元素的插入和删除操作。由于栈是一种只能在一端进行插入和删除的数据结构,因此可以使用 ArrayDeque 的一端来模拟栈的行为。

具体实现方式如下:

  1. 使用 ArrayDeque 创建一个空的双端队列对象:ArrayDeque<String> stack = new ArrayDeque<>();
  2. 使用 push() 方法将元素压入队列的一端,即栈顶部的位置:stack.push("Java");
  3. 使用 pop() 方法从队列的一端移除并返回栈顶部的元素:String topElement = stack.pop();
  4. 使用 peek() 方法返回但不移除栈顶部的元素:String topElement = stack.peek();
  5. 使用 isEmpty() 方法检查队列是否为空:boolean isEmpty = stack.isEmpty();

在 ArrayDeque 中,元素的插入和删除操作都是在同一端进行的,这样就满足了栈的后进先出(LIFO)的特性。

需要注意的是,由于 ArrayDeque 没有像 Stack 那样继承自 Vector,所以在性能上更高效,推荐在单线程环境中使用。

示例代码:

import java.util.ArrayDeque;

public class Main {
    public static void main(String[] args) {
        ArrayDeque<String> stack = new ArrayDeque<>();

        // 压入元素
        stack.push("Java");
        stack.push("Python");
        stack.push("C++");

        // 弹出并打印元素
        while (!stack.isEmpty()) {
            System.out.println(stack.pop());
        }
    }
}

2. LinkedList

LinkedList 是 Java 集合框架中的一种双向链表实现, 也可以被用作栈的实现方式,其原理与 ArrayDeque 类似,只需要在链表的头部进行元素的插入和删除操作即可。具体实现方式如下:

  1. 使用 LinkedList 创建一个空链表对象:LinkedList<String> stack = new LinkedList<>();
  2. 使用 push() 方法将元素插入链表的头部,即栈顶部的位置:stack.push("Java");
  3. 使用 pop() 方法从链表的头部移除并返回栈顶部的元素:String topElement = stack.pop();
  4. 使用 peek() 方法返回但不移除栈顶部的元素:String topElement = stack.peek();
  5. 使用 isEmpty() 方法检查链表是否为空:boolean isEmpty = stack.isEmpty();

同样地,由于 LinkedList 没有像 Stack 那样继承自 Vector,因此在性能上更高效,推荐在单线程环境中使用。

在 LinkedList 中,元素的插入和删除操作都是在链表的头部进行的,这样就满足了栈的后进先出(LIFO)的特性。
需要注意的是,在多线程环境下,LinkedList 并不是线程安全的,所以需要在多线程情况下使用时进行适当的同步处理。

示例代码:

import java.util.LinkedList;

public class Main {
    public static void main(String[] args) {
        LinkedList<String> stack = new LinkedList<>();

        // 压入元素
        stack.push("Java");
        stack.push("Python");
        stack.push("C++");

        // 弹出并打印元素
        while (!stack.isEmpty()) {
            System.out.println(stack.pop());
        }
    }
}

3. 数组实现

数组也可以用来实现栈,使用一个数组来存储栈元素,同时记录一个指向栈顶的指针。在入栈和出栈操作时,更新指针位置即可。

示例代码:

public class Stack {
    int[] data;
    int top;

    public Stack(int size) {
        data = new int[size];
        top = -1;
    }

    public void push(int value) {
        if (top == data.length - 1) {
            System.out.println("Stack is full");
            return;
        }
        data[++top] = value;
    }

    public int pop() {
        if (top < 0) {
            System.out.println("Stack is empty");
            return -1;
        }
        return data[top--];
    }

    public boolean isEmpty() {
        return top < 0;
    }

    public static void main(String[] args) {
        Stack stack = new Stack(3);

        // 压入元素
        stack.push(1);
        stack.push(2);
        stack.push(3);

        // 弹出并打印元素
        while (!stack.isEmpty()) {
            System.out.println(stack.pop());
        }
    }
}

以上是常见的栈实现方式。具体选择哪种实现方式取决于你的需求和偏好。需要注意的是,在单线程环境下,使用 ArrayDeque 或 LinkedList 可能会比使用 Stack 更高效。

在使用 Stack 时,需要注意以下事项:

  • 在调用 pop()peek() 方法之前,应先使用 empty() 方法检查堆栈是否为空,以避免异常。
  • Stack 是线程安全的,可以在多线程环境下使用。不过,在单线程环境中,建议使用 ArrayDeque 作为替代,因为 ArrayDeque 的性能更高。
文章来源:https://blog.csdn.net/weixin_48935611/article/details/135655496
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。