Stack 2개로 Queue 만들기
개발 관련 정보들을 구글링하던 도중 면접에서 Stack 2개로 Queue 1개를 만들어보라는 질문을 받았다는 글을 보았다.
Stack 2개로 Queue를 만든다라는 아이디어를 보고 어떻게 구현하면 좋을지 구글링해보았고, 그러한 정보를 이 글에 담아보려 한다.
Stack(스택)은
Stack은 LIFO(Last-In First-Out) 구조다. 나중에 들어온 것이 먼저 나간다.
Queue(큐)는
Queue는 FIFO(First-In First-Out) 구조다. 먼저 들어온 것이 먼저 나간다.
Stack 2개로 Queue 1개 만들기
아래와 같이 Stack 2개를 둔다. 하나의 스택은 Inbox, 그리고 나머지 한 스택은 Outbox다.
Inbox로 원소가 들어오고, Outbox로부터 원소가 나간다. 즉, 사용자는 Inbox로 데이터를 push()하고, Outbox로부터 데이터를 pop() 한다.
한번 데이터를 넣어보자. 1이라는 데이터를 push하고 2라는 데이터를 순차적으로 push한다. 사용자가 데이터를 push()할 경우 Inbox로 들어온다.
이번엔, pop()을 해보자. pop()을 할 경우, Outbox로부터 pop()을 하는데 여기서 핵심적인 부분이 있다.
** Outbox로부터 pop을 할 때는 두 가지 케이스에 대해서 다른 코드를 수행한다. **
만약, Outbox Stack이 empty()==true일 경우
1. Inbox로부터 모든 데이터를 순차적으로 pop하여 Outbox로 push한다
2. Outbox로부터 데이터를 pop한다.
만약, Outbox Stack이 empty()==false일 경우
1. Outbox로부터 데이터를 pop한다.
현재 Outbox가 empty하므로 아래와 같이 수행된다.
왜 이렇게 해야만 할까?
Outbox에 원소가 남아있는 상태에서 Inbox로부터 pop and push를 수행하면 원소의 순서가 꼬인다.
Outbox에 남아있는 원소가 Inbox에 있는 원소보다 먼저 사용자로부터 push되었으므로, 순서 상 먼저 사용자로부터 pop되어야하는데, Outbox에 아직 pop되어야할 데이터가 남아있는 상태에서 Inbox로부터 pop and push를 진행할 경우 Outbox의 기존 원소 위에 쌓이므로 스택의 LIFO Rule에 의해서 순서가 꼬이게 된다. 즉, FIFO도, LIFO도 아닌 엉망인 자료구조가 만들어진다.
따라서 위의 룰을 지키도록 하자!