In an ArrayList of Stacks, why are the indexes incorrect if a Stack(s) are empty?

Question

I have an ArrayList of Stacks, in which I add an element to one of the Stacks and iterate through the list printing the index of each Stack.

Then I remove the element from the previous Stack, add it to the next Stack, print the index of each Stack, and continue this for all Stacks in the ArrayList.

However, when any of the Stacks are empty there is very unusual behavior in getting the index of each Stack in the ArrayList. The Stack that is not empty will have the correct index value, whereas the Stacks that are empty will have incorrect index values.

Furthermore, it seems that if the Stack containing an element(s) is at index 0 all other index values will be 1. If the Stack containing an element(s) is at any other index it will have the correct index value and all other index values will be 0.

Here is my code:

import java.util.List;
import java.util.Stack;
import java.util.ArrayList;

public class ListOfStacks {

    // instance variables:
    List<Stack<Integer>> stacks;
    private static final int NUMBER_OF_STACKS = 3;

    // constructor:
    ListOfStacks() {
        this.stacks = new ArrayList<Stack<Integer>>(NUMBER_OF_STACKS);

        // adding the stacks to the list here:
        for (int i = 0; i < NUMBER_OF_STACKS; i++) {
            this.stacks.add(new Stack<Integer>());
        }
    }

    // instance methods:
    void addElement(int stackIndex, int element) {
        this.stacks.get(stackIndex).add(element);
    }
    void removeElement(int stackIndex) {
        this.stacks.get(stackIndex).pop();
    }
    void printIndexes(int stackIndex, int element) {
        System.out.printf("The stack at index %d now contains %d" +
            "(the other stacks are empty):%n", stackIndex, element);

        for (Stack<Integer> stack : this.stacks) {
            System.out.printf("index %d%n", this.stacks.indexOf(stack));
        }
        System.out.println();
    }

    // main method:
    public static void main(String[] args) {
        ListOfStacks list = new ListOfStacks();
        int index = 0, number = 5;

        // adding the number 5 to the stack at index 0:
        list.addElement(index, number);
        list.printIndexes(index, number);

        // now removing that element, and adding it to the stack at index 1:
        list.removeElement(index++);
        list.addElement(index, number);
        list.printIndexes(index, number);

        // now removing that element, and adding it to the stack at index 2:
        list.removeElement(index++);
        list.addElement(index, number);
        list.printIndexes(index, number);
    }
} // end of ListOfStacks

...and here is the output (for an ArrayList of three Stacks):

The stack at index 0 now contains 5 (the other stacks are empty):
index 0
index 1
index 1

The stack at index 1 now contains 5 (the other stacks are empty):
index 0
index 1
index 0

The stack at index 2 now contains 5 (the other stacks are empty):
index 0
index 0
index 2

score 6 · Accepted Answer · answered Mar 23 '13 at 20:19

6

The reason that you get the wrong index numbers has to do with the way indexOf is implemented in List. Underneath it makes a call to Stack.equals(). This determines whether the Stacks are equal element wise. When you call list.indexOf with an empty Stack, it will return the index of the first empty stack in the list.

answered Mar 23 '13 at 20:19

DeltaLima

5,864
1
16
32

Thanks @DeltaLima for the help, so how can I then implement "normal" indexing behavior with empty Stacks? – Ian Campbell Mar 23 '13 at 20:41
Well... Without some more knowledge about what you are trying to achieve that is a bit difficult to answer. I wonder whether the choice of List is the right one. Wouldn't a simple array work here? – DeltaLima Mar 23 '13 at 20:48
Thanks @DeltaLima, I have tried to use an array of Stacks before but with several errors (see: http://stackoverflow.com/questions/15530118/how-can-i-instantiate-an-array-of-stacks-of-type-int/15530140#comment22001592_15530140 ). My purpose is to create an appropriate structure to solve the Tower of Hanoi problem. – Ian Campbell Mar 23 '13 at 20:56
So, I have found that to initialize an array of Stacks as in `this.stack = new Stack[3];`, there is the warning "`Type safety: The expression of type Stack[] needs unchecked conversion to conform to Stack[]`". A possible solution though is to use the annotation `@SuppressWarnings("unchecked")` above a constructor and/or method, but may not be safe (don't know why though). – Ian Campbell Mar 28 '13 at 07:34

score 1 · Answer 2 · answered Mar 23 '13 at 20:23

indexOf(Object o) 
          Returns the index of the first occurrence of the specified element in this list, or -1 if this list does not contain the element.

A stack in java is basically a vector and the vector class has this for equals

 /**
  969        * Compares the specified Object with this Vector for equality.  Returns
  970        * true if and only if the specified Object is also a List, both Lists
  971        * have the same size, and all corresponding pairs of elements in the two
  972        * Lists are <em>equal</em>.  (Two elements {@code e1} and
  973        * {@code e2} are <em>equal</em> if {@code (e1==null ? e2==null :
  974        * e1.equals(e2))}.)  In other words, two Lists are defined to be
  975        * equal if they contain the same elements in the same order.
  976        *
  977        * @param o the Object to be compared for equality with this Vector
  978        * @return true if the specified Object is equal to this Vector
  979        */
  980       public synchronized boolean equals(Object o) {
  981           return super.equals(o);
  982       }

So what is happening is the indexof is finding the first empty stack seeing it as equal and returning that index.

So when index 0 has elements and the others have no elements the first stack that is equal to an empty stack is position 1.

if another element has data and the first element is equal and you are looking for an empty stack it will always stop and return index 0.

Thanks @Midpipps, so do I need to override `.equals(Object o)` and/or `.indexOf(Object o)` to implement "normal" indexing behavior? — Ian Campbell, Mar 23 '13 at 20:39
You could make a class that extends the stack class and override the equals method to be a reference equality. I don't know if that is the best way to go about it but it should give you the answer you are looking for. — Midpipps, Mar 23 '13 at 21:12

In an ArrayList of Stacks, why are the indexes incorrect if a Stack(s) are empty?

2 Answers2