[자료구조] 스택 2개로 큐를, 큐 2개로 스택을

CS 면접에서 자료구조의 스택과 큐에 대한 문제에 대한 답을 써보려고 한다.

Q1. 스택 2개로 큐 구현하는 법, 시간복잡도는 어떻게 될까?

정말 생각지도 못한 질문이라 생각하는데 꽤 걸렸다.
스택 2개로 큐를 어떻게 구현할 수 있을까?
먼저 스택과 큐의 특징을 정리해보자

스택

• FILO의 특징으로 처음 들어간게 나중에 나온다.
• push와 pop 모두 O(1)이 걸린다.

큐

• FIFO로 처음 들어간게 처음으로 나온다.
• push와 pop 모두 O(1)이 걸린다.

그러면 스택 2개를 이용해 큐를 구현한다는 것은
스택을 이용해 처음 들어간게 처음으로 나와야 한다는 얘기다.

처음 스택의 상태가 다음과 같다고 하자

이걸 1-2-3 순으로 나가게 해야 한다.
처음 스택에서 3-2-1 순으로 빠지는 것을 다시 스택을 통해 reverse를 해주면 1-2-3 순으로 빠지게 된다.
즉, pop해서 다른 스택에 push해서 모두 옮겨놓고, pop을 해주면 된다.

만약에 이 상태에서 새로운 요소가 들어온다면?
같은 방식으로 1번째 스택에 저장하고 2번째 스택이 비어있을 경우, 다시 옮기는 방식으로 하면 된다.

시간 복잡도는? (N: stack 1에 들어있는 요소의 개수)

if push를 할 경우:
	1번째 스택에 push // O(1)
else if pop을 할 경우:
	if 2번째 스택 is empty:
    	1번째 스택에 있는 요소들을 모두 2번째 스택으로 옮김 //O(N)
    else:
    	2번째 스택에서 pop // O(1)  

push: O(1)
pop: 최대 O(N)

Q2. 큐 2개로 스택을 구현하는 법, 시간복잡도는 어떻게 될까?

이번엔 반대의 질문이다.
1-2-3으로 들어온 것이 3-2-1 순으로 나가야 한다.

• 처음 상태
  
• pop 할 경우
  queue 1에 있는 요소 1개만 남기고 2번째 큐로 옮겨줘야 한다. 그리고 pop을 해준다.
  
• 이 다음에 push를 할 경우

1. 로직을 편하게 하려면 pop할 때, 다시 1번째로 옮겨주고, 1번째 큐에 push를 하는 방법이 있을 것이다.
2. 만약 시간을 줄이는 쪽을 한다면, 큐가 비어있지 않은 쪽에 push를 하는 방법이 있을 겻이다.
   

시간복잡도는?

//1번째 방법
if push 할 경우:
	1번째 큐에 push //O(1)
else if pop을 할 경우:
	1번째 큐에 있는 요소를 1개 제외하고 2번째로 옮김 //O(N-1)
    1번째 큐 pop //O(1)

//2번째 방법
if push할 경우:
	if 1번째 큐 is empty: //O(1)
    	2번째 큐에 push //O(1)
    else if 2번째 큐 is empty: //O(1)
    	1번째 큐에 push //O(1)
else pop할 경우:
	if 1번째 큐 is empty: //O(1)
    	2번째 큐에 있는 요소를 1개 제외하고 1번째로 옮김  //O(N-1)
        2번째 큐 pop //O(1)
    else if 2번째 큐 is empty: //O(1)
    	1번째 큐에 있는 요소를 1개 제외하고 2번째로 옮김  //O(N-1)
        1번째 큐 pop //O(1)

push: O(1)
pop: O(N)