Java实现最小栈 - 代码案例展示 |21xrx.com

Java实现最小栈 - 代码案例展示

2023-06-19 15:14:03 深夜i -- --

Java 最小栈代码案例

在数据结构和算法中，最小栈是一个特殊的栈，能够支持在常量时间复杂度内获取最小元素。Java是一种常用编程语言，在其它语言中已经有很多实现最小栈的案例，那么Java中该如何实现呢？

首先，我们需要了解什么是最小栈。最小栈是基于栈的数据结构，除了常规的入栈(push)和出栈(pop)操作外，还需要支持获取栈中的最小元素(getMin)，且该操作时间复杂度为O(1)。

我们可以通过一个数据结构来实现最小栈，该数据结构记录了每个元素入栈时的最小值。每新增一个元素时，将该元素和当前栈内的最小值一同入栈；出栈时，也同时弹出最小值。由于我们在入栈和出栈时记录了当前最小值，因此可以常数时间复杂度内获取最小值。

下面是Java语言实现最小栈的代码：


import java.util.Stack;
public class MinStack {
  private Stack
  stack;
 
  private Stack
  minStack;
 
  public MinStack() {
    stack = new Stack<>();
    minStack = new Stack<>();
  }
  public void push(int x) {
    stack.push(x);
    if (minStack.isEmpty() || x <= minStack.peek()) {
      minStack.push(x);
    }
  }
  public void pop() {
    if (stack.peek().equals(minStack.peek())) {
      minStack.pop();
    }
    stack.pop();
  }
  public int top() {
    return stack.peek();
  }
  public int getMin() {
    return minStack.peek();
  }
}

上面的代码中，我们使用了两个栈stack和minStack，其中stack为普通栈存储元素，minStack存储每个元素入栈后的最小值。在入栈时，如果当前元素比minStack的栈顶元素小或minStack为空，则将当前元素入minStack；出栈时，如果要弹出的元素是最小值，同样也需要将minStack的栈顶元素弹出。

最小栈的实现非常简单，使用两个栈即可实现常数时间复杂度的操作，确保了最小值的高效获取。我们可以将该数据结构应用于解决各种问题，例如需要寻找数组区间内的最小值，或者需要寻找最近邻特定元素的场景下。

三个

上一篇: idea打包java可执行jar包

下一篇: C语言中的printf函数及其功能

评论区

()

相似文章