CC-11 : Merge stacks and remove duplicates.
Description:
Given 2 stacks, merge the 2 stacks after removing duplicates.
Test cases and expected outputs:
| Input Parameters |
Expected outputs |
Stack1
Stack nodes:
28<-21<-34<-17<-14<-9<-
Stack2
Stack nodes:
28<-14<-34<-23<-14<-8<-
|
Merged stacks, duplicates removed:
Stack nodes:
28<-21<-34<-17<-14<-9<-23<-8<-
|
Pseudocode:
| Initialize a Deque based stack for holding the merged elements.
|
| For each element in stack1:
Remove the top element from stack1.
If the current from stack1 is not present in merged elements stack, add the current from stack1 to merged elements stack.
|
| For each element in stack2:
Remove the top element from stack2.
If the current from stack2 is not present in merged elements stack, add the current from stack2 to merged elements stack.
|
| Return merged Deque stack.
|
Code:
public Deque< Integer > removeDuplicates(Deque< Integer > stack1,Deque< Integer > stack2) throws Exception{
Deque< Integer > merged=new LinkedList< Integer >();
int check;
int s1Size=stack1.size();
for (int idx=0; idx < s1Size; idx++) {
check=stack1.pollFirst();
if (merged.contains(check)==false) {
merged.offerLast(check);
}
}
int s2Size=stack2.size();
for (int idx=0; idx < s2Size; idx++) {
check=stack2.pollFirst();
if (merged.contains(check)==false) {
merged.offerLast(check);
}
}
return merged;
}
Click here to download and run code and test cases !
Below fully running code can be copied and run on Eclipse or other Java IDEs. Refer the classname in code below. If the class name below is "A", save the code below to a file named A.java before running it.
Be sure to try your own test cases to enhance your understanding !
You can also tweak the code to optimize or add enhancements and custom features.
import java.util.Deque;
import java.util.LinkedList;
import java.util.Iterator;
public class StackMergeRemDups {
public Deque< Integer > removeDuplicates(Deque< Integer > stack1,Deque< Integer > stack2) throws Exception{
Deque< Integer > merged=new LinkedList< Integer >();
int check;
int s1Size=stack1.size();
for (int idx=0; idx < s1Size; idx++) {
check=stack1.pollFirst();
if (merged.contains(check)==false) {
merged.offerLast(check);
}
}
int s2Size=stack2.size();
for (int idx=0; idx < s2Size; idx++) {
check=stack2.pollFirst();
if (merged.contains(check)==false) {
merged.offerLast(check);
}
}
return merged;
}
public static void printStack(Deque stack) throws Exception {
System.out.println();
System.out.println("**************************************************************************************************");
System.out.print("Stack nodes: ");
Iterator itr=stack.iterator();
System.out.print("(top of stack)");
while (itr.hasNext()) {
System.out.print(itr.next());
System.out.print(" <- ");
}
System.out.println();
System.out.println("**************************************************************************************************");
System.out.println();
Thread.sleep(2000);
return;
}
public static void main(String[] args) {
/***********************
Test cases given below:
***********************/
try {
Deque stack1=new LinkedList();
System.out.print("Stack1");
stack1.addFirst(9);
stack1.addFirst(14);
stack1.addFirst(17);
stack1.addFirst(34);
stack1.addFirst(21);
stack1.addFirst(28);
printStack(stack1);
Deque stack2=new LinkedList();
System.out.print("Stack2");
stack2.addFirst(8);
stack2.addFirst(14);
stack2.addFirst(23);
stack2.addFirst(34);
stack2.addFirst(14);
stack2.addFirst(28);
printStack(stack2);
StackMergeRemDups dups=new StackMergeRemDups();
System.out.println("Merged stacks, duplicates removed:");
Deque retVal=dups.removeDuplicates(stack1, stack2);
printStack(retVal);
}catch (Exception exception) {
System.out.print("Exception: "+ exception);
exception.printStackTrace();
}
}
}