[LC] 225. Implement Stack using Queues

[seungriyou]

https://leetcode.com/problems/implement-stack-using-queues/ (similar to #20)

Approach

2개의 queue(deque) q1, q2를 가지고 하나의 stack을 만드는 문제.

q1을 메인 queue로, q2는 pop 시 사용하는 임시 queue로 사용하고, 편의성을 위해 _top attribute를 가지도록 했다.

pop() 메서드의 동작만 두 개의 queue를 이용해서 구현하면 된다.

1. stack 처럼 동작하기 위해 q1에 가장 나중에 추가된 원소 하나만 남을 때까지 popleft 하여 q2에 append 한다. 동시에 _top도 기록한다.
2. q1에 남은 마지막 원소, 즉 stack에서 pop 해야하는 원소를 popleft 한다.
3. q1과 q2를 맞바꾼다.
4. 2번에서 popleft 한 원소를 반환한다.

[!note] 두 개의 stack을 이용해서 하나의 queue를 만드는 #20 문제 & 두 개의 queue를 이용해서 하나의 stack을 만드는 이번 문제

➡️ "순서가 반대"인 자료구조로 만들기 위해서는 모든 원소를 한 차례 더 옮기면 된다는 점을 사용한다.

Complexity

• Time: O(n) (pop())
• Space: O(n)