Нужно ли объединять эти стеки? - PullRequest
Новая
       0

Нужно ли объединять эти стеки?

0 голосов
/ 13 февраля 2012

При оценке квалификации в рамках экзамена 98-361 «Основы разработки программного обеспечения» всплывает вопрос:

Сценарий 3-3: Использование стеков

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

Теперь у меня уже есть этот сценарий. Мое решение состоит в том, чтобы перебрать два отдельных стека, объединить их в список, выталкивая их элементы до тех пор, пока стек не опустеет, и отсортировать список в правильном порядке.

Однако меня поразило, что вопрос немного расплывчат в том, стоит ли мне объединять стеки. Это вид подразумеваемого, но это вид из не.

Если бы вы читали этот вопрос, как бы вы его интерпретировали?

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

Ответы [ 3 ]

3 голосов
/ 13 февраля 2012

Моя точка зрения: 

DECLARE NEW_LIST;
INT COUNT = STACK_A.COUNT() + STACK_B.COUNT()

FOR I=0 TO COUNT-1
    IF STACK_A.PEEK() > STACK_B.PEEK()
       NEW_LIST.ADD(STACK_A.POP())
    ELSE
       NEW_LIST.ADD(STACK_B.POP());

Теперь у вас есть NEW_LIST, который отсортирован - вам просто нужно определиться с порядком печати (обратный для возрастающего порядка)

Предполагается m, n - это начальные размеры двух стеков,

Объединение обоих стеков и последующая сортировка списка обойдутся вам дороже -

O((n+m)log(n+m)) для быстрой сортировки , чтоочевидно, медленнее, чем

O(m+n) - для решения выше

1 голос
/ 13 февраля 2012

Я думаю, что вы правы.Это было мое первоначальное толкование (хотя я согласен, что это кажется немного расплывчатым).И, если подумать, мне кажется, что нет необходимости указывать два стека, если они не должны быть объединены.

0 голосов
/ 13 февраля 2012

Этот вопрос звучит как установка для сортировки слиянием;чтобы получить содержимое обоих в объединенном, отсортированном (но обратном) порядке, вы несколько раз просматриваете верхнюю часть каждого стека, чтобы увидеть, какое значение ниже (то есть, раньше в сортировке по убыванию), выталкиваете значение из этого стека иподтолкнуть его к третьему стеку.Повторяйте до тех пор, пока оба исходных стека не станут пустыми, и поскольку ваш третий стек равен FILO, элементы, добавленные вами в порядке убывания, будут отображаться в порядке возрастания.

...