Neste artigo, exploraremos dois métodos para remover elementos duplicados de uma pilha em Java. Compararemos uma abordagem direta com loops aninhados e um método mais eficiente usando um HashSet. O objetivo é demonstrar como otimizar a remoção de duplicatas e avaliar o desempenho de cada abordagem.

Declaração do problema

Escreva um programa Java para remover o elemento duplicado da pilha.

Entrada

Stack data = initData(10L);

Saída

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

Para remover duplicatas de uma determinada pilha, temos 2 abordagens -

• Abordagem ingênua: crie dois loops aninhados para ver quais elementos já estão presentes e evitar adicioná-los ao retorno da pilha de resultados.
• Abordagem HashSet: Use um Set para armazenar elementos únicos e aproveite sua O(1) complexidade para verificar se um elemento está presente ou não.

Gerando e clonando pilhas aleatórias

Abaixo está o programa Java que primeiro constrói uma pilha aleatória e, em seguida, cria uma duplicata dela para uso posterior -

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 ajuda a criar uma pilha com um tamanho especificado e elementos aleatórios variando de 1 a 100.

manualCloneStack ajuda a gerar dados copiando dados de outra pilha, usando-os para comparação de desempenho entre as duas ideias.

Remover duplicatas de uma determinada pilha usando a abordagem Naïve

A seguir estão as etapas para remover duplicatas de uma determinada pilha usando a abordagem Naïve -

• Inicie o cronômetro.
• Crie uma pilha vazia para armazenar elementos exclusivos.
• Itere usando o loop while e continue até que a pilha original esteja vazia, pop o elemento superior.
• Verifique se há duplicatas usando resultStack.contains(element) para ver se o elemento já está na pilha de resultados.
• Se o elemento não estiver na pilha de resultados, adicione-o ao resultStack.
• Registre o horário de término e calcule o tempo total gasto.
• Retornar resultado

Exemplo

Abaixo está o programa Java para remover duplicatas de uma determinada pilha usando a abordagem Naïve -

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;
}

Para abordagem ingênua, usamos

while (!stack.isEmpty())

resultStack.contains(element)

Remova duplicatas de uma determinada pilha usando abordagem otimizada (HashSet)

A seguir estão as etapas para remover duplicatas de uma determinada pilha usando uma abordagem otimizada -

• Iniciar o cronômetro
• Crie um conjunto para rastrear elementos vistos (para verificações de complexidade O(1)).
• Crie uma pilha temporária para armazenar elementos exclusivos.
• Itere usando o while loop continue até que a pilha esteja vazia.
• Remova o elemento superior da pilha.
• Para verificar as duplicatas usaremos seen.contains(element) para verificar se o elemento já está no conjunto.
• Se o elemento não estiver no conjunto, adicione-o à pilha vista e à pilha temporária.
• Registre o horário de término e calcule o tempo total gasto.
• Retorna o resultado

Exemplo

Abaixo está o programa Java para remover duplicatas de uma determinada pilha usando HashSet −

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;
}

Para uma abordagem otimizada, usamos

Set seen

Usando as duas abordagens juntas

Abaixo estão as etapas para remover duplicatas de uma determinada pilha usando as duas abordagens mencionadas acima -

• Para inicializar os dados, estamos usando o método initData(Long size) para criar uma pilha preenchida com números inteiros aleatórios.
  
• Clonar a pilha estamos usando o método cloneStack(Stack stack) para criar uma cópia exata da pilha original.
• Gere a pilha inicial com initData.
• Clone esta pilha usando cloneStack.
• Aplique a abordagem ingênua para remover duplicatas da pilha original.
• Aplique a abordagem otimizada para remover duplicatas da pilha clonada.
• Exiba o tempo necessário para cada método e os elementos exclusivos produzidos por ambas as abordagens

Exemplo

Abaixo está o programa Java que remove elementos duplicados de uma pilha usando as duas abordagens mencionadas acima -

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));
    }
}

Saída

Comparação

* A unidade de medida é nanossegundo.

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

Conforme observado, o tempo de execução da Ideia 2 é menor do que o da Ideia 1 porque a complexidade da Ideia 1 é O(n²), enquanto a complexidade da Ideia 2 é O(n). Assim, quando o número de pilhas aumenta, o tempo gasto em cálculos também aumenta com base nisso.