remove repeated vaules _stack&array

Question

I want to write a program to implement an array-based stack, which accept integer numbers entered by the user.the program will then identify any occurrences of a given value from user and remove the repeated values from the stack,(using Java programming language).

I just need your help of writing (removing values method) e.g. input:6 2 3 4 3 8 output:6 2 4 8

Answer 1

Consider Collection.contains (possibly in conjunction with Arrays.asList, if you are so unfortunate), HashMap, or Set.

It really depends on what you have, where you are really going, and what silly restrictions the homework/teacher mandates. Since you say "implement an array-based stack" I am assuming there are some silly mandates in which case I would consider writing a custom arrayContains helper* method and/or using a secondary data-structure (Hash/Set) to keep track of 'seen'.

If you do the check upon insertion it's just (meta code, it's your home work :-):

function addItem (i) begin
   if not contains(stack, i) then
      push(stack, i)
   end if
end

*You could use the above asList/contains if you don't mind being "not very efficient", but Java comes with very little nice support for Arrays and thus the recommendation for the helper which is in turn just a loop over the array returning true if the value was found, false otherwise. (Or, perhaps return the index found or -1... your code :-)

Answer 2

Assuming that the "no-duplicates" logic is a part of the stack itself, I would do the following:

1) Implement a helper method:

private boolean remove(int item)

This method should scan the array, and if it finds the item it should shrink the array by moving all subsequent items one position backwards. The returned value indicates whether a removal took place.

2) Now it is easy to implement the push method:

public void push(int item) {
    if (!remove(item)) {
        arr[topPos++] = item;
    }
}

Note that my solution assumes there is always enough space in the array. A proper implementation should take care of resizing the array when necessary.

Answer 3

The question is an interesting (or troubling) one in that it breaks the spirit of the stack to enforce such a constraint. A pure stack can only be queried about its top element.

As a result, doing this operation necessarily requires treating the stack not as a stack but as some other data structure, or at least transferring all of the data in the stack to a different, intermediate data structure.

If you want to accomplish this from within the stack class itself, others' replies will prove useful.

If you want to accomplish this from outside of the stack, using only the traditional methods of a stack interface (push() and pop()), your algorithm might look something like this:

1. Create a Set of Integers to keep track of values encountered so far.
2. Create a second stack to hold the values temporarily.
3. While the stack isn't empty,
   1. Pop off the top element.
   2. If the set doesn't contain that element yet, add it to the set and push it onto the second stack.
   3. If the set does contain the element, that means you've already encountered it and this is a duplicate. So ignore it.
4. While the second stack isn't empty,
   1. Pop off the top element
   2. Push the element back onto the original stack.

There are various other ways to do this, but I believe all would require some auxiliary data structure that is not a stack.

Answer 4

override the push method and have it run through the stack to determine whether the value already exists. if so, return false otherwise true (if you want to use a boolean return value).

basically, this is in spirit of the answer posted by Mr. Schneider, but why shrink the array or modify the stack at all if you can just determine whether a new item is a duplicate or not? if it's a duplicate, don't add it and the array does not need to be modified. am i missing something?