Truncating A Java Stack

Question

I have a Stack<String> defined in Java that I use for navigation through a workflow.

What I would like to do is ensure that all values in the stack are unique: when a transition to a "previous" state occurs, I want to remove everything off the stack AFTER the first occurrence of the previous state in the stack.

Is there an easy way to do this?

Edit: More information was requested. Here's an example of the contents of a stack:

[state2, state3, state2, state1, startState]

I need the ability to accept a String, check the stack and see if there are multiple occurrences of it, then pop elements until the "bottommost" occurrence of that String. "Truncate" was probably a bad description of what I wanted to do... "pop until I hit an arbitrary index" is probably closer to what I need.

Pop until arriving at the previous state? Doesn't seem that 'hard'; although "first occurrence" could use clarification - e.g. closest to top or bottom of the stack? — user2864740, Apr 02 '15 at 19:02
There is a remote possibility of a duplicate string in the stack. If I pop from the stack, I need to pop until the first occurrence of that string. If I were using a list I would get the index and create a subList, but there isn't a such thing as a subStack. — Jason, Apr 02 '15 at 19:04
Can you clarify further what this means? The current description makes it mean like a pop will remove the head AND everything else except for the value one below the head? — Necreaux, Apr 02 '15 at 19:07
@Jason, Stack implements List (among many other interfaces). So you can still get a subList. — davmac, Apr 02 '15 at 19:59

score 1 · Answer 1 · edited May 23 '17 at 12:09

1

Consider using deque. Below is the link which explains why should you use it over stack.

Why should I use Deque over Stack?

edited May 23 '17 at 12:09

Community

1
1

answered Apr 02 '15 at 19:07

chetank

392
3
17

score 1 · Answer 2 · answered Apr 02 '15 at 20:01

Stack implements List (among various other interfaces). Get a ListIterator for the last element, and move it backwards until you find an occurrence of the new state, counting how many elements along the way, and then pop that many elements. (If you don't find the new state, then of course you don't pop anything, and you push the new state onto the stack instead).

This might not be particularly efficient, but it will certainly work. If you also want it to be efficient, you probably need to use another data structure (either instead of or as well as the stack). One possibility is to use a Map (in addition to the stack) to keep track of which states are on the stack together with the index at which they occur, or at least a Set to keep track of which states are on the stack (you can then just pop states until you find the one you are looking for). You would maintain the stack and the map or set in parallel.

Or if you were serious about:

"pop until I hit an arbitrary index" is probably closer to what I need.

... then surely this would suffice:

int numberToPop = stack.size() - arbitraryIndex - 1;
while (numberToPop-- > 0) {
    stack.pop();
}

score 0 · Answer 3 · answered Apr 02 '15 at 20:11

Would it simplify your overall code if you created your own container that is basically a set that's a stack? Something like (not a complete implementation):

public class StackSet<T> {
    private final Set<T> set;
    private final Deque<T> queue;

    public StackSet(){
        set = new HashSet<>();
        queue = new ArrayDeque<>();
    }

    public void push(T value){
        if(set.add(value)){
            queue.push(value);
        }
    }

    public T pop(){
        return queue.pop();
    }
}

That should guarantee no duplicates.

score 0 · Answer 4 · answered Apr 02 '15 at 21:48

Here's an example of a truncate method with Deque instead of Stack.

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Collection;
import java.util.Deque;

public class ExampleDeque 
{

  public static void main(String[] args)    
  {
    Deque<String> deque = new ArrayDeque<String>();
    deque.offer("startState");
    deque.offer("state1");
    deque.offer("state2");
    deque.offer("state3");
    deque.offer("state2");

    System.out.println("Before");
    print(deque);
    deque = truncate(deque, "state2");
    System.out.println("After");
    print(deque);
  }

  static Deque<String> truncate (Deque<String> deque, String value)
  {
    if(!deque.contains(value)) return deque;

    String[] array = deque.toArray(new String[deque.size()]);
    for(int i = 0; i < array.length;  i++)
    {
      if(array[i] == value)
      {
        String[] truncated = Arrays.copyOfRange(array, 0, i + 1);
        Collection<String> collection = Arrays.asList(truncated);   
        return new ArrayDeque<>(collection);
      }
    }
    return null;
  }

  static void print(Deque<String> deque)
  {
    for(String s : deque)
      System.out.println(s);
    System.out.println();
  }
}

Truncating A Java Stack

4 Answers4