Рубрики

ВОРОТА | GATE-CS-2001 | Вопрос 41

Какое минимальное количество стеков размера n требуется для реализации очереди размера n?
(А) один
(Б) два
(С) три
(D) Четыре

Ответ: (Б)
Объяснение: Очередь может быть реализована с использованием двух стеков. Пусть реализуемая очередь будет q, а стеки, используемые для реализации q, будут stack1 и stack2. q может быть реализовано двумя способами:

Способ 1 (сделав операцию enQueue дорогостоящей)
Этот метод гарантирует, что вновь введенный элемент всегда находится на вершине стека 1, так что операция deQueue просто появляется из stack1. Чтобы поместить элемент в верхнюю часть stack1, используется stack2.

enQueue(q, x)
  1) While stack1 is not empty, push everything from satck1 to stack2.
  2) Push x to stack1 (assuming size of stacks is unlimited).
  3) Push everything back to stack1.

dnQueue(q)
  1) If stack1 is empty then error
  2) Pop an item from stack1 and return it

Способ 2 (делая операцию deQueue дорогостоящей)
В этом методе при работе в очереди новый элемент вводится в верхней части stack1. В операции удаления очереди, если стек2 пуст, тогда все элементы перемещаются в стек2 и, наконец, возвращается вершина стека2.

enQueue(q,  x)
  1) Push x to stack1 (assuming size of stacks is unlimited).

deQueue(q)
  1) If both stacks are empty then error.
  2) If stack2 is empty
       While stack1 is not empty, push everything from satck1 to stack2.
  3) Pop the element from stack2 and return it.

Источник: http://espressocode.top/queue-using-stacks/
Тест на этот вопрос

Рекомендуемые посты:

ВОРОТА | GATE-CS-2001 | Вопрос 41

0.00 (0%) 0 votes