Найдите общие элементы стека и очереди

Опубликовано: 19 Сентября, 2022

Дан стек из M элементов и очередь из N элементов в отсортированном порядке. Задача состоит в том, чтобы выяснить общие элементы стека и очереди.

Примеры:

Input: stack = [1, 3, 5, 7], queue = [1, 2, 5, 9]
Output: 5, 1
Explanation: 1 and 5 is present in both stack and queue.

Input: stack = [1, 3], queue = [2, 4]
Output: Not Found
Explanation: There is no common element.

Подход: Данная проблема может быть решена с помощью следующей идеи:

As both are sorted, the top element of the stack will be the maximum and the front of the queue will be the minimum. So reverse any of them and compare the elements in top of stack and front of queue to find the common elements.

Следуйте иллюстрации ниже для лучшего понимания.

Иллюстрация:

Say, stack = [1, 3, 5, 7] where 7 is at the top and 
the queue = [1, 2, 5, 9] where 1 is at the front.

Say we are reversing the queue. Do the following to reverse the queue:

  • In first step:
    One by one pop the element from the queue(i.e., all the elements of queue) and push into stack.
            => After First Iteration, Stack = [1, 3, 5, 7, 1] and Queue = [2, 5, 9]
            => After Second Iteration, Stack = [1, 3, 5, 7, 1, 2] and Queue = [5, 9]
            => After Third Iteration, Stack = [1, 3, 5, 7, 1, 2, 5] and Queue = [9]
            => After Fourth Iteration, Stack = [1, 3, 5, 7, 1, 2, 5, 9] and Queue = []
  • In second step:
           => One by one pop the element from the stack(i.e., coming from queue)  and push into queue.
           => After First Iteration, Stack = [1, 3, 5, 7, 1, 2, 5] and Queue = [9]
           => After Second Iteration, Stack = [1, 3, 5, 7, 1, 2] and Queue = [9, 5]
           => After Third Iteration, Stack = [1, 3, 5, 7, 1] and Queue = [9, 5, 2]
           => After Fourth Iteration, Stack = [1, 3, 5, 7] and Queue = [9, 5, 2, 1]

Now the following for finding the common elements.

1st Step:
        => stack top < queue front.
        => Pop queue front.
        => So stack is [1, 3, 5, 7] and queue [5, 2, 1]

2nd step:
        => stack top > queue front
        => Pop stack top
        => So stack [1, 3, 5] and queue [5, 2, 1]

3rd step:
        => stack top = queue front
        => Pop stack top and queue front
        => So stack [1, 3] and queue [2, 1]
        => Common elements [5]

4th step:
        => stack top > queue front
        => Pop stack top
        => So stack [1] and queue [2, 1]

5th Step:
        => stack top < queue front.
        => Pop queue front.
        => So stack is [1] and queue [1]

6th step:
        => stack top = queue front
        => Pop stack top and queue front
        => So stack [] and queue []
        => Common elements [5, 1].

Выполните следующие шаги, чтобы решить проблему:

  • Перевернуть очередь.
  • Перемещайтесь по стеку и очереди, пока стек и очередь не станут пустыми.
    • Если вершина стека = начало очереди, это общий элемент.
    • В противном случае, если вершина стека> перед очередью, извлеките верхний элемент стека.
    • В противном случае вершина стека < начала очереди, извлеките передний элемент стека.
  • Распечатайте общие элементы.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(M+N), где M = размер очереди и N = размер стека
Вспомогательное пространство: O(M) для реверсирования элементов очереди

РЕКОМЕНДУЕМЫЕ СТАТЬИ