在本文中，我们将探讨两种在 Java 中从堆栈中删除重复元素的方法。我们将比较使用嵌套循环的简单方法和使用 HashSet 的更有效方法。目标是演示如何优化重复删除并评估每种方法的性能。

问题陈述

编写一个Java程序，从堆栈中删除重复元素。

输入

Stack data = initData(10L);

输出

Unique elements using Naive Approach: [1, 4, 3, 2, 8, 7, 5]
Time spent for Naive Approach: 18200 nanoseconds

Unique elements using Optimized Approach: [1, 4, 3, 2, 8, 7, 5]
Time spent for Optimized Approach: 34800 nanoseconds

要从给定堆栈中删除重复项，我们有两种方法 -

• 天真的方法：创建两个嵌套循环来查看哪些元素已经存在并防止将它们添加到结果堆栈返回中。
• HashSet方法：使用Set来存储唯一元素，并利用其O(1)复杂度来检查元素是否存在。

生成和克隆随机堆栈

下面是 Java 程序首先构建一个随机堆栈，然后创建它的副本以供进一步使用 -

private static Stack initData(Long size) {
    Stack stack = new Stack  ();
    Random random = new Random();
    int bound = (int) Math.ceil(size * 0.75);
    for (int i = 0; i  manualCloneStack(Stack  stack) {
    Stack  newStack = new Stack  ();
    for (Integer item: stack) {
        newStack.push(item);
    }
    return newStack;
}

initData 帮助创建一个具有指定大小和范围从 1 到 100 的随机元素的 Stack。

manualCloneStack 通过从另一个堆栈复制数据来帮助生成数据，用它来比较两种想法的性能。

使用 Naïve 方法从给定堆栈中删除重复项

以下是使用 Naïve 方法从给定堆栈中删除重复项的步骤 -

• 启动计时器。
• 创建一个空堆栈来存储唯一元素。
• 使用while循环迭代并继续，直到原始堆栈为空弹出顶部元素。
• 使用 resultStack.contains(element) 检查重复项以查看该元素是否已在结果堆栈中。
• 如果该元素不在结果栈中，则将其添加到结果栈中。
• 记录结束时间并计算总花费时间。
• 返回结果

例子

下面是使用 Naïve 方法从给定堆栈中删除重复项的 Java 程序 -

public static Stack idea1(Stack stack) {
  long start = System.nanoTime();
  Stack resultStack = new Stack  ();

  while (!stack.isEmpty()) {
    int element = stack.pop();
    if (!resultStack.contains(element)) {
      resultStack.add(element);
    }
  }
  System.out.println("Time spent for idea1 is %d nanosecond".formatted(System.nanoTime() - start));
  return resultStack;
}

对于朴素方法，我们使用

while (!stack.isEmpty())

resultStack.contains(element)

使用优化方法 (HashSet) 从给定堆栈中删除重复项

以下是使用优化方法从给定堆栈中删除重复项的步骤 -

• 启动计时器
• 创建一个 Set 来跟踪看到的元素（用于 O(1) 复杂性检查）。
• 创建临时堆栈来存储唯一元素。
• 使用 while循环进行迭代，直到堆栈为空。
• 从堆栈中移除顶部元素。
• 要检查重复项，我们将使用 seen.contains(element) 来检查该元素是否已在集合中。
• 如果该元素不在集合中，则将其添加到可见堆栈和临时堆栈中。
• 记录结束时间并计算总花费时间。
• 返回结果

例子

下面是使用 HashSet 从给定堆栈中删除重复项的 Java 程序 -

public static Stack idea2(Stack stack) {
    long start = System.nanoTime();
    Set seen = new HashSet();
    Stack tempStack = new Stack();

    while (!stack.isEmpty()) {
        int element = stack.pop();
        if (!seen.contains(element)) {
            seen.add(element);
            tempStack.push(element);
        }
    }
    System.out.println("Time spent for idea2 is %d nanosecond".formatted(System.nanoTime() - start));
    return tempStack;
}

对于优化方法，我们使用

Set seen

结合使用两种方法

以下是使用上述两种方法从给定堆栈中删除重复项的步骤 -

• 初始化数据，我们使用initData(Long size)方法创建一个充满随机整数的堆栈。
  
• 克隆堆栈我们使用 cloneStack(Stack stack) 方法 来创建原始堆栈的精确副本。
• 使用initData.
生成初始堆栈
• 使用 cloneStack 克隆此堆栈。
• 应用朴素方法从原始堆栈中删除重复项。
• 应用优化方法从克隆堆栈中删除重复项。
• 显示每种方法所花费的时间以及两种方法产生的独特元素

例子

下面是使用上述两种方法从堆栈中删除重复元素的 Java 程序 -

import java.util.HashSet;
import java.util.Random;
import java.util.Set;
import java.util.Stack;

public class DuplicateStackElements {
    private static Stack initData(Long size) {
        Stack stack = new Stack();
        Random random = new Random();
        int bound = (int) Math.ceil(size * 0.75);
        for (int i = 0; i  cloneStack(Stack stack) {
        Stack newStack = new Stack();
        newStack.addAll(stack);
        return newStack;
    }
    public static Stack idea1(Stack stack) {
        long start = System.nanoTime();
        Stack resultStack = new Stack();

        while (!stack.isEmpty()) {
            int element = stack.pop();
            if (!resultStack.contains(element)) {
                resultStack.add(element);
            }
        }
        System.out.printf("Time spent for idea1 is %d nanoseconds%n", System.nanoTime() - start);
        return resultStack;
    }
    public static Stack idea2(Stack stack) {
        long start = System.nanoTime();
        Set seen = new HashSet();
        Stack tempStack = new Stack();

        while (!stack.isEmpty()) {
            int element = stack.pop();
            if (!seen.contains(element)) {
                seen.add(element);
                tempStack.push(element);
            }
        }
        System.out.printf("Time spent for idea2 is %d nanoseconds%n", System.nanoTime() - start);
        return tempStack;
    }
    public static void main(String[] args) {
        Stack data1 = initData(10L);
        Stack data2 = cloneStack(data1);
        System.out.println("Unique elements using idea1: "   idea1(data1));
        System.out.println("Unique elements using idea2: "   idea2(data2));
    }
}

输出

比较

* 测量单位是纳秒。

public static void main(String[] args) {
    Stack data1 = initData();
    Stack data2 = manualCloneStack(data1);
    idea1(data1);
    idea2(data2);
}

据观察，想法 2 的运行时间比想法 1 短，因为想法 1 的复杂度为 O(n²)，而想法 2 的复杂度为 O(n)。所以，当堆栈数量增加时，计算所花费的时间也会在此基础上增加。