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

В оценке квалификации в рамках экзамена 98-361, Программное обеспечение Основы разработки, этот вопрос всплывает:Нужно ли объединять эти стеки?

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

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

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

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

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

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

источник

2012-02-13 Mike Hofer

Я думаю, что вы правы. Похоже, мне не нужно было указывать * два стека, если они не должны были сливаться. – Blorgbeard

@Blorgbeard: Это то, что я думал. Специфика «двух стеков», казалось, подразумевала, что они хотели, чтобы они слились. Любой шанс вы можете ответить на этот вопрос, чтобы получить кредит? –

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

источник

2012-02-13 11:27:32 Blorgbeard

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

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) - для решения выше

источник

2012-02-13 11:06:43 Shai

Почему бы просто не использовать управляемый стек для этого? Я думаю, что это больше того, что им нужно. Но решение выше, вероятно, должно быть в порядке. – leppie

Не отвечает на вопрос П. .. – Blorgbeard

Это мой способ интерпретации вопроса, для чего нужен -1? это ответ * I * дал бы на этот вопрос, и ОП наверняка найдет это сообщение полезным. ОП упомянул, что он понял это, объединившись и сортируя; Это правда, что знание того, как на самом деле что-то кодировать, важно в собеседовании, но некоторые работодатели * делают * искать оптимизированное решение, а не простое, медленное. Инженеры-разработчики, безусловно, должны помнить об этом! – Shai

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

источник

2012-02-13 11:39:04 FacticiusVir

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

ответ

Смежные вопросы