Реализуйте и объедините два стека в O (1)

Question

Мне где-то задавали этот вопрос.

Мне дали 2 стека. Я должен реализовать следующие операции:

// Pass one of the stacks and a value to insert
push(Stack stack, value)    
pop(Stack stack, val)    
merge(Stack s1, Stack s2)

Мне нужно выполнить вышеуказанные операции со стеком, такие как push и pop в O (1) . До сих пор я использовал связанный список для успешной реализации этих операций.

Но как мне объединить два стека в O (1) ? Я не мог найти, как это сделать в O (1) .

Может быть, мне нужно использовать какую-то другую структуру данных или что-то еще?

Answer 1

Это действительно легко, если ваши объекты стека сохраняют оба конца стека (верх / низ, начало / конец, голова / хвост и т. Д.). Я буду использовать top / bottom для этого ответа.

Когда вы реализуете push / pop, вы работаете с верхним объектом. Нижняя часть останется прежней (если только стек не пуст), а узел, который его представляет, будет иметь следующий указатель, равный нулю.

Итак, чтобы объединить два стека, вы берете нижнюю часть одного, наведите его навершины другого и возвращают «новый» стек, сформированный из других указателей.

Stack merge(Stack s1, Stack s2) {
  // join the stacks
  s2.bottom.next = s1.top

  // make a nice object to give back
  Stack result;
  result.bottom = s1.bottom
  result.top = s2.top

  // cleanup the parameters so they don't mess up the new structure.
  s1.bottom = s1.top = s2.bottom = s2.top = null;

  return result;
}

Если у вас нет двух указателей, хорошо удерживаемых в объекте стека, вам нужно будет пройти один из стековполучить то, что будет сохранено здесь как дно, делая сложность O (N).

Answer 2

Я хотел бы дать другую перспективу, перспективу программирования / объекта. Если у вас нет указателя на конец стека, как предлагалось ранее, и в случае, если средство слияния сначала возвращает элементы одного стека, а затем другой, то есть определяет порядок между ними - это реальноеВажное соображение вы не обращали. Вы можете следовать следующему подходу

Создать StackList объект, который расширяет Stack Пример Java:

class StackList extends Stack

Теперь, удерживайте в нем связанный список стеков, объединение тривиальнодобавив стеки в список, pop/push просто вызовет методы pop/push главного стека.