Most efficient way to reverse a stack and add to a

Question

I have two collections - an ArrayList and a Stack. I use the stack because I needed some simple pop/push functionality for this bit of code. The ArrayList is essentially the out variable as this is a small section of code in the function.

So, the variables are defined as such, then code is run to add elements to the stack.

ArrayList<String> out = new ArrayList<String>();

/* other code.. */

Stack<String> lineStack = new Stack<String>();

/* code that adds stuff to the stack */

The question is, now that I have a fully populated stack, how do I place it in the out ArrayList in a reverse order then from the pop order.

My first thought up solution was

 while(!lineStack.empty()) {
     out.add(0, lineStack.pop());
 }

... which works, but I worry about the efficiency of adding an element to the beginning of the ArrayList (which forces all existing elements to need to shift.. it's a linked list (I believe).. big deal.. but still a concern). Also, I am running this through a loop... perhaps unnecessarily.

So, my second solution that didn't involve looping (at least in my code, i'm sure the back end calls are doing it).

 List l = lineStack.subList(0, lineStack.size());
 out.addAll(l);

I know I don't need to allocate the list, but it'll keep for cleaner code. However, I am not sure if this will give me a particularly helpful performance gain.

So, my question is: Which of these will likely be most efficient for SMALL to MEDIUM size sets? If there is a more efficient solution, what would it be?

Answer 1

Stack is subclass of Collections and Collections has reverse method, So you can just do -

   Stack originalStack = ...
   Collections.reverse(originalStack);

Answer 2

Subclass the ArrayList and add a pop and push method. Use this as the Stack class.

When you are ready, assign it to an Arraylist variable and you're ready

Answer 3

making use of Stack.toArray is simple:

@Test
public void stackToList() {
    Stack<String> stack = new Stack<String>();
    stack.push("aaa");
    stack.push("bbb");
    stack.push("ccc");
    List<String> list=  Arrays.asList(stack.toArray(new String[0]));
    Assert.assertEquals(Arrays.asList("aaa", "bbb", "ccc"), list);
}

Answer 4

If you don't need it as an array, but another stack would work, why not:

Stack<String> reversedStack = new Stack<String>(); while (!oldStack.empty()) { reversedStack.push(oldStack.pop()); }

Quick, simple, and easy to see what it's doing.

Answer 5

The Iterable<T> implementation order of Stack<T> goes in the order you want anyway, so you can just use

new ArrayList<String>(stack);

Here's a short but complete example:

import java.util.*;

public class Test
{
    public static void main(String[] args)
    {
        Stack<String> stack = new Stack<String>();
        stack.push("Bottom");
        stack.push("Middle");
        stack.push("Top");

        List<String> list = new ArrayList<String>(stack);

        for (String x : list)
        {
            System.out.println(x);
        }
    }
}

This prints out:

Bottom
Middle
Top

(which is the opposite order to what you'd get if you popped them).

EDIT: One other question - do you really need it in an ArrayList<String> anyway? Stack<T> implements List<T>; what special features of ArrayList do you need? (I'm not saying you don't need them, just checking!)