Stacks - Removing Duplicates

[Rachell Zammit]

Hello guys I am trying to write a method that will remove duplicates from a stack of Integers but I have no idea what Im doing! Could somebody please explain what I'm doing wrong.


This is the Main

public class Finals2 {
public static Stack<Integer> slist = new Stack<Integer>();
public static void main(String[] args) {
slist.push(1);
slist.push(4);
slist.push(4);
slist.push(6);
slist.push(7);
slist.push(8);
slist.push(10);
slist.push(10);
slist.push(10);
slist.push(11);
Stack<Integer> res1 = removeDoubles(slist);
System.out.println(slist);

And the Method

 public static Stack<Integer> removeDoubles(Stack<Integer> s) {
Stack<Integer> returner = new Stack<Integer>();
int head = s.peek();
while(!s.isEmpty()) {
if (s.pop() == head) {
int bin = s.pop();
}
else
{
returner.push(s.pop());
}
}
return returner;
} 

[Campbell Ritchie]

You should get a piece of paper and write down how I would do it without a computer. Only then should you even try to write any code.

[Campbell Ritchie]

Also write down what you mean by removing duplicates. What happens when you have a stack like this?
1-5-2-5-23-5-76-5-99-0-5-1-5-34-5

[Piet Souris]

There's one advantage about not knowing what you're doing: with a little bit of luck you might be doing it correct ;)

What you are doing is:

in the removeDoubles method:

first you make head equal to 11 (being the top of the stack).

next: in your while loop at line 7, you pop up 11, compare that to head and of course, you get equality. So bin will be made equal
to 10 (since you are using pop() again), so effectively eliminating 11 and 10 from your original stack.

next: since Stack s is not empty yet, you pop() the next one from s, being 10. Since that is not 11, it gets pushed in returner.

next: the first 10 is popped, and, being unequal to 11, is also pushed in returner. So you have a duplicate here.

And so on. So, assuming that by "removing duplicates" you mean that there should be no duplicates, you see that you are not achieving
your goal in this way. Even worse: if you would have started, in line 7 of your main() method, with "slist.push(11)" you would have gotten an error in line 9.

But maybe worst of all: even if you got this method to eliminate all duplicates, this method would inverse your initial Stack, and that is a bad thing for the usual Stack!

So, what can be done about the duplicates? Well, following Campbells advises is always a good thing to do.

Then, my advise would be: eliminating duplicates from a Stack is a nasty thing. Do you really need a Stack?
If so, then probably the easiest thing would be to eliminate getting duplicates in your stack in the first place. If you look at the Stack API,
you see that it implements the Collection interface. Now, one of the methods of that interface is "contains". See if you can make use of this
in your main() method.

[Rachell Zammit]

Thanks for the advice guys, I have been plugging away at this method for past couple hours and there isn't too much info I could find about stacks and queues. I'm really not getting how they work properly. For me the logic is there with the below code but all I'm getting is an empty stack.


I haven't used the collections interface or similar because it came from a random question I found which was...

"The method removeDouble whose heading is
public Stack<Integer> removeDouble(Stack<Integer> s)
takes a stack of integers s sorted in ascending order from top to bottom. The method should
remove any double element in the stack and return the resulting stack sorted in ascending order.
For instance, if the stack s contains 1, 4, 4, 6, 7, 8, 10, 10, 10, 11, 21 from top to
bottom, then the result should be the stack 1, 4, 6, 7, 8, 10, 11, 21.
Implement the method removeDouble. You may assume the existence of the method reverseStack.
whose heading is
public Stack<Integer> reverseStack(Stack<Integer> s)
and whose effect is to return a stack in reverse order of the stack s.

 public static Stack<Integer> removeDoubles(Stack<Integer> s) {
Stack<Integer> returner = new Stack<Integer>();
while(!s.isEmpty()) {
int n = s.pop(); //remove and return top value. Store it in n
if (s.peek() != n) { //peak at the next value and compare it with previous value n
returner.push(s.pop()); //if the values are differnet, then add it to the new stack.
}
}
return returner;
}

[Winston Gutkowski]

 

Rachell Zammit wrote:Thanks for the advice guys, I have been plugging away at this method for past couple hours and there isn't too much info I could find about stacks and queues.

Personally, I wouldn't worry about it. From the wording of the question, it sounds to me like you're only allowed to use a Stack anyway; and it can't be a java.util.Stack, because that class doesn't have a reverseStack() method.

I suspect they're trying to see if you can do the job just with Stack's basic methods, plus the one they gave you.

I'm really not getting how they work properly. For me the logic is there with the below code but all I'm getting is an empty stack.

Then plainly the logic isn't there with the below code, is it?

Tip: Forget about duplicates for a second and just try this:

public static Stack<Integer> removeDoubles(Stack<Integer> s) {
Stack<Integer> returner = new Stack<Integer>();
while(!s.isEmpty()) {
returner.push(s.pop());
}
return returner;
}

Run it, and print out the contents of the resulting Stack. What do you get and why?

Also: what does the Stack you passed to removeDoubles() look like?

That'll probably help you to work out what's going on, and if need be, add print statements in for each iteration of the loop. Once you understand what's happening, then you'll be ready to tackle the "duplicates" stuff.

HIH

Winston