Thread: Counting duplicates in a Stack

Hey guys , I am having a problem with my code , consider this problem:


Write a method compressDuplicates that accepts a stack of integers as a parameter and that replaces each sequence of duplicates with a pair of values: a count of the number of duplicates, followed by the actual duplicated number. For example, suppose a variable called s stores the following sequence of values:

bottom [2, 2, 2, 2, 2, -5, -5, 3, 3, 3, 3, 4, 4, 1, 0, 17, 17] top

If we make the call of compressDuplicates(s);, after the call s should store the following values:

bottom [5, 2, 2, -5, 4, 3, 2, 4, 1, 1, 1, 0, 2, 17] top

This new stack indicates that the original had 5 occurrences of 2 at the bottom of the stack followed by 2 occurrences of -5 followed by 4 occurrences of 3, and so on. This process works best when there are many duplicates in a row. For example, if the stack instead had stored:

bottom [10, 20, 10, 20, 20, 10] top

Then the resulting stack after the call ends up being longer than the original:

bottom [1, 10, 1, 20, 1, 10, 2, 20, 1, 10] top

If the stack is empty, your method should not change it. You may use one queue as auxiliary storage to solve this problem. You may not use any other auxiliary data structures to solve this problem, although you can have as many simple variables as you like. You may not use recursion to solve this problem. For full credit your code must run in O(n) time where n is the number of elements of the original stack.




I wrote a code but still having a problem with it , and guys am I allowed to use 3 while loops ? Thanks !

 
public void compressDuplicates(Stack<Integer> s ){
 Stack<Integer> backup= new Stack<Integer>();
    int count = 1;
    while(!s.isEmpty()){
     int temp = s.pop();
        backup.push(temp);
        while (!s.isEmpty()){
           int temp2 = s.pop();
            backup.push(temp2);
                if( temp == temp2);
                    count++;
 
        }
               backup.push(count);
    }
 
    while(!backup.isEmpty()){
    s.push(backup.pop());
    }
 
}
 
 
 
// example 1   Expected output : 	bottom [5, 2, 2, -5, 4, 3, 2, 4, 1, 1, 1, 0, 2, 17] top            My output:      	                //bottom [17, 2, 2, 2, 2, 2, -5, -5, 3, 3, 3, 3, 4, 4, 1, 0, 17, 17] top

I don't think you need to make this problem so complicated. Break it down into a few simple rules.

• Read element off stack and remember it
• Keep popping until this number is different and count the number of times you pop
• Once you encounter a different number, push your count then your number onto your temporary stack
• When there are no more elements left in the original stack, reverse the order of the temp stack to get it into the correct orientation

Taking Parranoia's suggestion a step further, Sets don't allow duplicate items, returning false when adding a duplicate item is attempted. Instead of "remembering it," items popped from the stack could be added to a Set. Any attempts to add that receive a 'false' response could be counted as duplicates. If identifying the duplicates is required, then the duplicate items could be stored in another collection, perhaps another Set if duplicate duplicates are not desired.

Originally Posted by GregBrannon

Taking Parranoia's suggestion a step further, Sets don't allow duplicate items, returning false when adding a duplicate item is attempted. Instead of "remembering it," items popped from the stack could be added to a Set. Any attempts to add that receive a 'false' response could be counted as duplicates. If identifying the duplicates is required, then the duplicate items could be stored in another collection, perhaps another Set if duplicate duplicates are not desired.

I'm not sure that would work quite right as it isn't gathering duplicates from throughout the stack, it is only gathering consecutive duplicates.