스택으로 큐 구현하기

스택으로 큐를 구현할 때는 2개의 스택을 사용하게 됩니다.

스택 2개를 사용해서 큐의 push와 pop을 구현합니다.

위 이미지 처럼 push를 하게되면 stack input에 쌓이게 됩니다.

이때 pop을 해줄경우 stack input에서 pop한 내용을 그대로 반환하면 그냥 stack이랑 다를게 없습니다.
때문에 pop을 하기 전에 stack input에 있는 값을 하나씩 pop해서 stack out에 push 해줍니다.

그럼 이와 같은 상태가 되고

그 후 stack out에서 pop을 해주면 큐와 같이 FIFO 구조로 pop이 가능합니다

그리고 pop한 다음 스택은 위와 같은 상황이 됩니다.

이때 계속해서 pop을 하는 것이 아닌 중간에 push를 해준다음 다시 pop을 하려면 어떻게 해야할 까요?

그 때는 push는 stack input에 값을 넣어주고 pop을 할때는 stack out에 남아있는 값을 반환해 주다가 stack out에 값이 없을 때 stack input에 있는 값을 모두 stack out으로 옮겨주면됩니다.

예를 들어보겠습니다.

01 - push 1
02 - push 2
03 - push 3
04 - push 4
05 - pop
06 - pop
07 - push 5
08 - push 6
09 - pop
10 - pop
11 - pop
12 - pop
13 - push 7
14 - pop

이와 같은 순서로 진행을 하는 것을 그림으로 표현한다면

1~4 는 아까 예시로 나타낸것과 같이 이미지처럼 push 되고

5, 6을 진행하면 이와 같이 pop됩니다

그 후 7, 8을 진행하려면 그냥 처음처럼 stack input에 넣어주면 됩니다.

그 다음이 중요한데 9~ 12는 pop을 연속 4번 수행하는 상황입니다.
이 때는 우선 stack out에 남아있는 값 부터 pop을 진행합니다.

그 후 또 pop명령이 있지만 stack out에는 값이 없으므로 stack input에 있는 값을 stack out으로 아까와 같은 방식으로 옮겨줍니다. 이때 stack input에서도 값이 없으면 fail값을 반환해야합니다.(ex : -1)

그 후 pop을 해주면 정상적으로 반환할 수 있습니다.

나머지 13, 14 처음 예시와 동일하게 진행이 됩니다.

---

정리

push : stack input에 push

pop : stack out에 값이 있다면 stack oup을 pop
       값이 없다면 stack input의 값을 하나씩 pop하고 stack out에 push하여 모두 옮긴 후 stack out을 pop
       stack input에도 값이 없다면 fail

size : stack input의 크기 + stack out의 크기

empty : stack input과 stack out이 모두 empty라면 true 하나라도 값이 있으면 false

front : pop과 마찬가지로
        stack out에 값이 있다면 stack out의 top 출력
        값이 없다면 stack input의 값을 모두 옮긴 후 stack out을 top 출력
        stack input에도 값이 없다면 fail