스택 두개로 큐 만들기

스택은 한쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 구조(LIFO)로 되어 있습니다. 

넣을 땐 Push라고 하고 넣어준 자료를 꺼내는 것을 Pop이라 합니다.

 

iOS에서 스택은 대표적으로 navigation stack이 있습니다.

공식문서에 살펴보면 계층에 대한 드릴 다운 인터페이스를 제공하기 위해 스택으로 관리한다고 나와있습니다.

 

 

스택과는 반대대는 개념인 큐를 살펴봅시다.

큐는 먼저 집어 넣은 데이터가 먼저 나오는(FIFO) 구조로 저장하는 형식을 말합니다.

 

iOS에서는 대표적으로 Dispatch Queue가 있겠죠.

비동기식으로 동시에 수행 할 수 있는 손쉬운 방법이죠.

 

여기까지 스택과 큐의 특징을 살펴봤습니다. 

---

 

그럼 본론으로 

 

Q. 스택 두개로 어떻게 큐로 만들 수 있을까요

A. 스택 두개를 inBox와 outBox로 나누어 용도에 맞게 사용해줍니다.

 

 

 

그림과 같이 inBox는 push 넣는 용도로 outBox는 pop 꺼내는 용도로 사용해줍니다.

 

코드로 ㄱ ㄱ

 

struct Stack {
    var stack = [Int]()
    
    mutating func pop() -> Int? {
        return stack.popLast()
    }
    
    mutating func push(element: Int) {
        return stack.append(element)
    }
    
    func isEmpty() -> Bool {
        return stack.isEmpty
    }
}

var inBox = Stack()
var outBox = Stack()

일단 스위프트니까 스택 구조체를 만들어줍니다. 주ㅠ륵ㅠ

스택에 필요한 pop함수와 push함수 isEmpty함수를 만들어줍니다.

마지막으로 inBox, outBox 변수를 생성해줍니다.

 

여기까지 스택에 필요한 기본 구조체 완성.

 

큐처럼 사용하기로 했으니 함수명은 enQueue, deQueue로 했습니다.

 

func enQueue(item: Int) {
    inBox.push(element: item)
}

inBox는 push용도로 사용하기로 했죠.

enQueue를 통해 item을 넣으면 inBox에 차곡차곡 쌓이게 됩니다.

 

func deQueue() -> Int? {
    if outBox.isEmpty() {
        while (!inBox.isEmpty()) {
            outBox.push(element: inBox.pop()!)
        }
    } 
    return outBox.pop()
}

outBox는 pop용도로 사용하기로 했죠.

먼저 if 문을 통해 outBox가 비었는지 확인을 해줍니다.

만약에 outBox가 비어있다면 inBox가 빌 때까지 inBox에서 하나씩 pop 해서 outBox에 넣어줍니다.

그리고 while문이 끝나면 outBox를 pop 해줍니다. 

*outBox가 비지 않았다면 while문을 거치지 않고 바로 outBox를 pop 해 outBox상단에 있는 값을 리턴하겠죠.

이게 다예요!

 

예를 들어 볼게요.

 

enQueue함수를 통해 4 3 2 1을 차례대로 넣어줍니다.

enQueue(item: 4) enQueue(item: 3) enQueue(item: 2) enQueue(item: 1)

두둥

 

enQueue함수에서 매개변수로 받은 item을 inBox에 push를 해줍니다.

스택 특성상 먼저 넣은 item이 inBox 가장 아래에 쌓이게 됩니다. 

4 3 2 1 순으로 넣었으니 먼저 넣은 4가 inBox의 하단에 존재하게 되겠죠.

위 그림과 같이 1이 상단에 존재하고 하단에 4가 존재하게 됩니다.

 

deQueue함수를 호출하면 4가 출력됩니다.

 

왜?

 

outBox가 비어있으니 true가 되어 while문을 실행됩니다.

아까 inBox 제일 상단에는 1이 상단에 존재했으니 1이 가장 먼저 pop 되겠죠.

이렇게 inBox가 빌 때까지 inBox에서 하나씩 pop 해 outBox에 push를 해줍니다.

 

1 2 3 4 순으로 outBox에 하나씩 push 됩니다.

결과적으로 outBox에는 1이 가장 먼저 들어갔으니 1이 하단에

가장 늦게 들어간 4가 상단에 존재하게 됩니다.

 

위에 deQueue함수를 호출하면 4가 출력된다는 게 이해되시나요?

 

enQueue에 4를 제일 먼저 넣어주고 deQeue를 통해 4가 먼저 출력됨으로 스택 두 개로 큐처럼 사용할 수 있음을 확인했습니다.