swift 자료구조 queue 코드로 정리2 - stack을 이용해서 구현

swift 자료구조 queue 코드로 정리2 - stack을 이용해서 구현

 

 

지난 포스팅(swift 자료구조 queue 코드로 정리 - 큐 일상생활 예제)에서 큐의 기본 정의와 array로 큐를 구현해 보았습니다.

지난 포스팅에 이어서 이번 포스팅에는 두개의 스택을 이용해서 큐를 구현해 보고자 합니다.

 

 

두개의 스택 leftStack과 rightStack 변수를 생성합니다. 이 두 변수의 타입은 배열 입니다. 

왼쪽 스택과 오른쪽 스택 모두 합쳐서 하나의 스택이 되는 구조입니다.

 

그럼 왼쪽 스택과 오른쪽 스택은 각각 무슨 용도일까요?

 

먼저 오른쪽 스택은 큐에서 enqueue 에 사용됩니다.

즉, 자료구조 큐에 데이터를 삽입을 하면 오른쪽 스택(rightStack)에 삽입을 합니다.

 

왼쪽스택은 큐의 dequeue에 사용됩니다.

즉, 자료구조 큐에서 데이터를 꺼낼때 왼쪽 스택(leftStack)에서 꺼냅니다.

 

 

더블 스택 구현

먼저 아래와 같이 구조체로 더블스택을 만들어주고, 두개의 스택 변수를 작성해 줍니다.

// 더블 스택 구현
public struct QueueStack<T>:Queue{

    public typealias Element = T
    
    // 아래 array 두개 합해서 전체 stack 임.
    // 디큐 담당 array
    private var leftStack:[T] = []
    // 인큐 담당 array
    private var rightStack:[T] = []
    

    public init() { }

}
// 출력용
extension QueueStack:CustomStringConvertible{
    public var description: String{
        let printLast = leftStack.reversed() + rightStack
        return String(describing: printLast)
    }
}

 

enqueue 함수

인큐는 오른쪽 배열에, 디큐는 왼쪽 배열에서 진행

 

위에서 enqueue는 오른쪽 배열 제일 마지막에 값을 넣는다고 정의했습니다.

    // enqueue는 우측 스택(array)에 넣는다.
    public mutating func enqueue(_ element: T) -> Bool {
        rightStack.append(element)
        return true
    }

 

isEmpty 

또한 두 배열 모두 더해서 하나의 큐라고 정의했기 때문에 큐의 빈값을 체크할 때도 두 배열 모두 비었는지 체크 합니다.

    // 왼쪽 스택과 오른쪽 스택이 모두 비어야 empty
    public var isEmpty: Bool{
        return leftStack.isEmpty && rightStack.isEmpty
    }

 

dequeue

왼쪽 배열에서 디큐를 할때 오른쪽 배열을 뒤집은 다음 왼쪽 배열에 할당해준다.

큐에서 값을 꺼낼 때는 왼쪽 배열에서 꺼낸다고 했습니다.

이때 주목해볼 부분이 왼쪽 배열에 값이 처음에는 없다는 것입니다.

위에서 큐에 데이터를 삽입 할 때는 오른쪽 배열에 넣어준다고 했는데, 당연히 왼쪽 배열에는 아무 값이 없습니다.

따라서 왼쪽 배열은 처음에는 비어있습니다.

그리고 오른쪽 배열을 거꾸로 뒤집에서 왼쪽 배열에다가 넣어주고 오른쪽 배열은 전부 비워줍니다.

그럼 왼쪽 배열에서 popLast 하면 배열의 제일 앞에 있던 요소가 reversed() 함수 호출로 제일 뒤로 이동 했기 때문에 큐의 형태와 동일하게 dequeue 처리가 됩니다.

 

    public mutating func dequeue() -> T? {
        //좌측 스택이 비어 있으면
        //우측 배열 뒤집어서 좌측 스택에 할당해주고 좌측스택(array)의 마지막 요소를 삭제한다.
        if leftStack.isEmpty{
            leftStack = rightStack.reversed()
            rightStack.removeAll()
        }
        return leftStack.popLast()
    }

 

peek

큐의 제일 앞에 있는 요소를 리턴하는 함수 입니다.

왼쪽 배열이 안비었으면 왼쪽 배열의 마지막에서 요소를 꺼냅니다.

왜 왼쪽 배열은 마지막 요소를 꺼낼까요?

왜냐면 왼쪽 배열은 오른쪽 배열을 reversed() 거꾸로 뒤집었기 때문에 배열의 제일 앞에 있는 요소가 제일 뒤로가있기 때문입니다.

 

이어서 왼쪽 배열이 비었으면 우측 배열의 제일 첫번째 요소를 리턴해줍니다.

    public var peek: T?{
        return !leftStack.isEmpty ? leftStack.last : rightStack.first
    }

 

QueueStack 테스트

아래와 같이 스택큐를 생성하고 강아지, 새, 토끼, 거북이를 순서대로 인큐 했습니다.

그리고 한번의 peek 와 한번의 dequeue, 그리고 공룡을 enqueue 했습니다.

var queueStack = QueueStack<String>()
queueStack.enqueue("강아지")
queueStack.enqueue("새")
queueStack.enqueue("토끼")
queueStack.enqueue("거북이")

print("\n")
print(queueStack)

print(queueStack.isEmpty)
print(queueStack.peek)
queueStack.dequeue()

print("\n")
print(queueStack)

queueStack.enqueue("공룡")

print("\n")
print(queueStack)

 

출력

["강아지", "새", "토끼", "거북이"]
false
Optional("강아지")

["새", "토끼", "거북이"]

["새", "토끼", "거북이", "공룡"]

 

성능

 

Queue.zip

0.02MB

참고

코딩퀴즈 - ios

https://apps.apple.com/kr/app/%EC%BD%94%EB%94%A9%ED%80%B4%EC%A6%88/id1625309702

 

코딩퀴즈 - aos

https://play.google.com/store/apps/details?id=com.codingquiz.myapplication

 

https://www.raywenderlich.com/books/data-structures-algorithms-in-swift/