Вопрос стека: выскочить в шаблон

Question

Во время выполнения я хочу ввести два типа данных: double и string.Одним из условий является то, что String должен отображаться в порядке ввода, а double - как обычное поведение стека LIFO.Другое условие состоит в том, что размер стека ограничен 10

Например, один пример времени выполнения

Вход Hello 1 World 2 blah blah 3 4 5

Выход Hello 5 World 4 blah blah 3 2 1

Мой первый вопрос: сколько способов решить эту проблему?Я решил эту проблему, используя 3 стека, один из которых хранит double, другой - строки, а другой используется для изменения порядка строк.

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

Так вот как будет выглядеть мой стек строк после нажатия

1. Hello *
2. World *
3. бла
4. бла ***

Так что при первом чтении мне нужно сделать конкретное чтение в этой позиции стекаи просто извлеките Hello из этого.Звездочка * оставлена ​​для дальнейшего использования, когда я сообщаю программе, что следующий всплывающий список имеет двойное значение.

Мой второй вопрос заключается в том, что мне интересно, есть ли какое-то другое более элегантное решение этой проблемы.Поскольку мое решение будет включать в себя некоторые манипуляции со строками, чтобы решить эту проблему.И на данный момент я на самом деле не использую функцию pop в случае строки, как это предполагается использовать.Я сделал решение в C ++, кстати.

Answer 1

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

Итак, это можно сделать с двумя стеками, используя только push / pop.

1. положить все в стек A.

2. вытолкнуть все из А на Б.

3. , если B.empty возвращается

4. , если B.top является двойным переходом 7

5. выведите B.top и извлеките его из B

6. Перейти к 3

7. вставьте все B в A

8. , пока A.top не является двойным щелчком A на B

9. выведите A.top и вытолкните из A

10. Перейти к 2.

Answer 2

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

Вы можете решить эту проблему, используя операции only push / pop с 5 стеками (технически только 4 будут использоваться прив любое время, но поскольку они имеют разные типы, вам нужно объявить все 5 в вашей программе):

стек 1: push удваивается в порядке ввода

стек 2: push строки на входеorder

stack 3: push типы данных (двойные или строковые) в порядке ввода

stack 4: обратный порядок строк в стеке 2

stack 5: обратный порядоктипов данных в стеке 3

Теперь извлекайте один тип данных за раз из стека 5, если он является двойным, извлекайте из стека 1, в противном случае извлекайте из стека 5 и печатайте извлеченное значение.

Редактировать: @jleedev отмечает, что нетОбщее решение, когда размер стека ограничен.То, что я описал выше, предполагает, что вы можете использовать несколько стеков, и каждый стек может содержать столько элементов, сколько присутствует во входных данных.