Самый эффективный способ перевернуть стек и добавить в ArrayList

Question

У меня есть две коллекции - ArrayList и Stack. Я использую стек, потому что мне нужна была простая функция pop/push для этого бита кода. ArrayList по существу является переменной out, так как это небольшая часть кода в функции.

Итак, переменные определены как таковые, затем выполняется код для добавления элементов в стек.

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

/* other code.. */ 

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

/* code that adds stuff to the stack */ 

Вопрос заключается в том, что в настоящее время у меня есть полностью заселен стек, как я поместить его в из ArrayList в обратном порядке, то из поп-заказа.

Мое первое придуманное решение было

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

... который работает, но я беспокоюсь об эффективности добавления элемента к началу ArrayList (который заставляет все существующие элементы, нужно перенести. это связанный список (я считаю) .. большое дело, но все равно беспокойство). Кроме того, я запускаю это через цикл ... возможно, излишне.

Итак, мое второе решение, которое не связано с циклом (по крайней мере, в моем коде, я уверен, что обратные вызовы делают это).

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

Я знаю, что мне не нужно выделять список, но он будет содержать более чистый код. Однако я не уверен, что это даст мне особенно полезную производительность.

Итак, мой вопрос: какие из них, вероятно, будут наиболее эффективными для наборов размеров от SMALL до MEDIUM? Если будет более эффективное решение, что бы это было?

Answer 1

Порядок Iterable<T> реализация Stack<T> идет в нужном вам порядке в любом случае, так что вы можете просто использовать

new ArrayList<String>(stack); 

Вот короткий, но полный пример:

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); 
     } 
    } 
} 

Это печатает:

Bottom 
Middle 
Top 

(это противоположный порядок, который вы получили бы, если бы вы их вытащили).

EDIT: Еще один вопрос - он действительно нужен в ArrayList<String>? Stack<T> инвентарь List<T>; какие особенности ArrayList вам нужны? (Я не говорю, что вы не нуждаются в них, просто проверяя!)

Answer 2

Подкласс ArrayList и добавьте метод pop и push. Используйте это как класс Stack.

Когда вы будете готовы, назначить его на ArrayList переменной, и вы готовы

Answer 3

использование Stack.ToArray прост:

@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

Если вам не нужно его как массив, но другой стек будет работать, то почему бы не:

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

Быстрый, простой и легко увидеть, что это делает.

Answer 5

Стек подкласс коллекций и коллекций имеет reverse method, поэтому вы можете просто сделать -

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