Как перевернуть стек?

Question

Может быть, это слишком простой вопрос, но, пожалуйста, поделитесь, как перевернуть любой вид стека?

Answer 1

Правильный ответ может быть «не переворачивать стек».

Если какое-то ограничение означает, что вам абсолютно необходимо перевернуть стек, ваш вопрос уже получен. Но я не могу не задаться вопросом почему вы хотите перевернуть стек - для меня это означает, что вы используете неправильную структуру данных.

Если его все толкает, то наоборот, тогда все трещит; это очередь.

Если толчки, выталкивания и реверсы смешаны в случайном порядке, вы, вероятно, захотите структуру данных, которая конкретно поддерживает эти операции ... это будет сбивать с толку, когда кто-то читает «стек», но структура действительно является чем-то другим.

Не уверен насчет scala, но некоторые языки имеют двустороннюю очередь, специально предназначенную для представления линейной коллекции с доступом к элементам head и tail - это может быть именно то, что вам нужно. Если нет, то двусвязный список будет хорошо работать; или просто старый список подойдет, если O (n) pop() -эквивалент не является проблемой.

Если ваша pop() эквивалентная операция не знает, с какого конца получить элемент (например, один фрагмент кода вызывает reverse, а другой код просто говорит «дай мне элемент» и не знает или нет был вызван обратный), инкапсулировать очередь с флагом для направления следующим образом. Это даст вам те же функциональные возможности без необходимости что-либо реверсировать.

(извините за очень псевдокод, scala отсутствует в моем наборе инструментов).

ReversableStack {
    DoublyLinkedList backingStore;
    Boolean forward;

    get() {
        if (forward) return backingStore.take_head();
        else return backingStore.take_tail();
    }

    put(item) {
        if (forward) backingStore.add_head(item);
        else backingStore.add_tail(item);
    }

    reverse() {
        forward = !forward;
    }
}

Answer 2

make new stack;
while (old stack not empty)
    x = pop(old stack)
    push x on new stack

Или вызовите reverse в стеке, но обратите внимание, что это возвращает List, если применяется к mutable.Stack.Он возвращает Stack, если вы используете immutable.Stack.

Answer 3

Я не говорю на Scala, но в соответствии с документом, который вы просто называете reverse в стеке .

Answer 4

public void reverse(Stack st) { 
    int m = (int)st.Pop(); 
    if (st.Count != 1) 
        reverse(st); 
    Push(st , m); 
} 

public void Push(Stack st , int a) { 
    int m = (int)st.Pop(); 
    if (st.Count != 0) 
        Push(st , a); 
    else 
        st.Push(a); 
    st.Push(m); 
}

Answer 5

Просто циклически извлекайте из него значения и помещайте их в другой стек.