Стек, использующий очередь

Question

Я просматривал некоторые вопросы интервью и наткнулся на это. Это заставило меня рвать на себе волосы.

Кто-нибудь знает, как реализовать стек с использованием очереди?.

Answer 1

push: вставить элемент в конец очереди.

pop: удалить элемент спереди, сразу вставить его сзади, повторить N-1 раз, где N - размерочереди, затем удалите последний элемент и верните его.

Answer 2

Концепция использования одной очереди для реализации стека требует O (2n) или (машинно-независимого) O (n) пространственной сложности.Но когда вы работаете с массивом большого размера, двойной размер может быть недоступен, а также временная сложность O (n ^ 2) или точно O (n * (n + 1) / 2), если вы пытаетесь использовать только одиночереди.

Answer 3

Версия A:

кнопка:

поставить в очередь1

поп:

в то время как размер очереди1 больше 1, отправка элементов из очереди1 в очередь2 удалите очередь и верните последний элемент queue1, затем переключите имена queue1 и queue2

Версия B:

кнопка:

поставить в очередь2 поставить в очередь все элементы queue1 в queue2, затем переключить имена queue1 и queue2

поп:

запрос из очереди1