इस लेख में, हम जावा में स्टैक से डुप्लिकेट तत्वों को हटाने के लिए दो तरीकों का पता लगाएंगे। हम एक सीधे दृष्टिकोण की तुलना नेस्टेड लूप्स और हैशसेट का उपयोग करके एक अधिक कुशल विधि से करेंगे। लक्ष्य यह प्रदर्शित करना है कि डुप्लिकेट निष्कासन को कैसे अनुकूलित किया जाए और प्रत्येक दृष्टिकोण के प्रदर्शन का मूल्यांकन किया जाए।

समस्या का विवरण

स्टैक से डुप्लिकेट तत्व को हटाने के लिए एक जावा प्रोग्राम लिखें।

इनपुट

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

किसी दिए गए स्टैक से डुप्लिकेट हटाने के लिए, हमारे पास 2 दृष्टिकोण हैं -

• निष्पक्ष दृष्टिकोण: यह देखने के लिए कि कौन से तत्व पहले से मौजूद हैं, दो नेस्टेड लूप्स बनाएं और उन्हें परिणाम स्टैक रिटर्न में जोड़ने से रोकें।
• हैशसेट दृष्टिकोण: अद्वितीय तत्वों को संग्रहीत करने के लिए एक सेट का उपयोग करें, और यह जांचने के लिए कि कोई तत्व मौजूद है या नहीं, इसकी O(1) जटिलता का लाभ उठाएं।

यादृच्छिक स्टैक उत्पन्न करना और क्लोन करना

नीचे बताया गया है कि जावा प्रोग्राम पहले एक यादृच्छिक स्टैक बनाता है और फिर आगे उपयोग के लिए इसका एक डुप्लिकेट बनाता है -

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 तक के यादृच्छिक तत्वों के साथ एक स्टैक बनाने में मदद करता है।

manualCloneStack ​दो विचारों के बीच प्रदर्शन तुलना के लिए इसका उपयोग करके दूसरे स्टैक से डेटा कॉपी करके डेटा उत्पन्न करने में मदद करता है।

Naive दृष्टिकोण का उपयोग करके दिए गए स्टैक से डुप्लिकेट हटाएं

Naive दृष्टिकोण का उपयोग करके किसी दिए गए स्टैक से डुप्लिकेट को हटाने का चरण निम्नलिखित है -

• टाइमर प्रारंभ करें।
• अद्वितीय तत्वों को संग्रहीत करने के लिए एक खाली स्टैक बनाएं।
• while लूप का उपयोग करके पुनरावृति करें और तब तक जारी रखें जब तक कि मूल स्टैक खाली न हो जाए, शीर्ष तत्व को पॉप करें।
• यह देखने के लिए कि क्या तत्व पहले से ही परिणाम स्टैक में है, resultStack.contains(element) का उपयोग करके डुप्लिकेट की जांच करें।
• यदि तत्व परिणाम स्टैक में नहीं है, तो उसे परिणाम स्टैक में जोड़ें।
• अंत समय रिकॉर्ड करें और बिताए गए कुल समय की गणना करें।
• वापसी परिणाम

उदाहरण

Naive दृष्टिकोण का उपयोग करके दिए गए स्टैक से डुप्लिकेट को हटाने के लिए नीचे जावा प्रोग्राम दिया गया है -

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)

अनुकूलित दृष्टिकोण (हैशसेट) का उपयोग करके दिए गए स्टैक से डुप्लिकेट हटाएं

अनुकूलित दृष्टिकोण का उपयोग करके किसी दिए गए स्टैक से डुप्लिकेट को हटाने के चरण निम्नलिखित हैं -

• टाइमर प्रारंभ करें
• देखे गए तत्वों को ट्रैक करने के लिए एक सेट बनाएं (O(1) जटिलता जांच के लिए)।
• अद्वितीय तत्वों को संग्रहीत करने के लिए एक अस्थायी स्टैक बनाएं।
• while लूप का उपयोग करके पुनरावृति तब तक जारी रखें जब तक स्टैक खाली न हो जाए।
• स्टैक से शीर्ष तत्व को हटा दें।
• डुप्लिकेट की जांच करने के लिए हम यह जांचने के लिए seen.contains(element) का उपयोग करेंगे कि क्या तत्व पहले से ही सेट में है।
• यदि तत्व सेट में नहीं है, तो इसे दृश्य और अस्थायी स्टैक दोनों में जोड़ें।
• अंत समय रिकॉर्ड करें और बिताए गए कुल समय की गणना करें।
• परिणाम लौटाएं

उदाहरण

हैशसेट का उपयोग करके दिए गए स्टैक से डुप्लिकेट को हटाने के लिए नीचे जावा प्रोग्राम है -

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(स्टैक स्टैक) विधि का उपयोग कर रहे हैं।
• initData के साथ प्रारंभिक स्टैक जेनरेट करें।
• cloneStack का उपयोग करके इस स्टैक को क्लोन करें।
• मूल स्टैक से डुप्लिकेट हटाने के लिए  निष्क्रिय दृष्टिकोण लागू करें।
• क्लोन किए गए स्टैक से डुप्लिकेट को हटाने के लिए अनुकूलित दृष्टिकोण लागू करें।
• प्रत्येक विधि के लिए लिया गया समय और दोनों दृष्टिकोणों द्वारा उत्पादित अद्वितीय तत्वों को प्रदर्शित करें

उदाहरण

नीचे जावा प्रोग्राम है जो ऊपर उल्लिखित दोनों तरीकों का उपयोग करके स्टैक से डुप्लिकेट तत्वों को हटा देता है -

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) है। इसलिए, जब ढेरों की संख्या बढ़ती है, तो उसके आधार पर गणना पर लगने वाला समय भी बढ़ जाता है।