[Swift 자료구조] 스택(Stack) 큐(Queue) 구현하기

안녕하세요 여러분~!

자료구조 하면 빠질수 없는 기본중에 기본 스택과 큐 를 한번쯤 들어보셨을텐데요?

자료형은 둘 다 Array를 사용하지만 데이터 입출력 방식에서 차이가 있습니다.

 

스택(Stack) 이란?

스택은 Array로 나타내는 후입선출 형태의 선형 자료구조입니다.

후입선출 = LIFO(Last In First Out)

나중에 넣은 데이터부터 출력한다는 뜻인데요.

 

Swift로 구현해볼까요?

다음과 같이 리스트가 있습니다.

array = []

 

1부터 3까지의 숫자를 리스트에 입력해볼게요.

array.append(1)

array.append(2)

array.append(3)

array = [1,2,3]

 

출력은 어떻게 할까요?

스택은 나중에 넣은 데이터부터 출력하기 때문에

removeLast()를 이용해줄게요.

 

array.removeLast() 👉 3방출

array.removeLast() 👉 2방출

array.removeLast() 👉 1방출

 

큐(Queue) 란?

큐는 Array로 나타내는 선입선출 형태의 선형 자료구조입니다.

선입선출 = FIFO(First In First Out)

먼저 넣은 데이터부터 출력한다는 뜻인데요.

 

Swift로 구현해볼까요?

다음과 같이 리스트가 있습니다.

array = []

 

1부터 3까지의 숫자를 리스트에 입력해볼게요.

array.append(1)

array.append(2)

array.append(3)

array = [1,2,3]

 

출력은 어떻게 할까요?

큐는 먼저 넣은 데이터부터 출력하기 때문에

removeFirst()를 이용해줄게요.

 

array.removeFirst() 👉 1방출

array.removeFirst() 👉 2방출

array.removeFirst() 👉 3방출

 

이렇게 간단하게 스택과 큐를 구현할 수 있습니다.

라고 하고싶지만...!!

 

단순 구현이 목적이라면 위의 방법으로 구현하면 되겠지만

저희는 코딩테스트를 위한 알고리즘 공부를 하고있으니 시간복잡도를 고려해야됩니다.

 

append() 시간복잡도

우선 데이터 입력에 사용한 append() 함수는

Array의 빈공간에 데이터를 채우는 함수입니다.

이는 단순히 "특정 index에 데이터를 넣는다"는 동작만 실행하므로

시간복잡도 O(1)으로 동작이 가능합니다.

 

물론, 메모리 재할당 과정에서 조금 더 복잡한 로직이 실행되고

O(n)의 시간복잡도가 발생할 때도 있지만 드문 경우이므로

평균적인 시간복잡도는 O(1) 로 측정됩니다.

* 메모리 재할당 과정이 궁금하신 분은 따로 서치해보세요!

 

removeLast() 시간복잡도

스택의 데이터를 출력할 때 사용했던 removeLast() 함수입니다.

Array의 마지막 데이터를 출력하는 함수입니다.

이는 단순히 "마지막 index의 데이터를 출력한다"는 동작만 실행하므로

시간복잡도 O(1)으로 동작이 가능합니다.

 

removeFirst() 시간복잡도

큐의 데이터를 출력할 때 사용했던 removeFirst()함수입니다.

Array의 첫번째 데이터를 출력하는 함수입니다.

이때 첫 공간이 비면서 데이터를 전부 재정렬해야되는 상황이 벌어집니다.

그림으로 볼까요?

 

0부터 5까지 숫자가 채워진 Array가 있습니다.

이 Array에 removeFirst()를 하게되면 첫번째 데이터를 출력하면서

할당된 메모리에 빈공간이 생기게 됩니다.

이를 채우기 위해 데이터 전체를 정렬하는 작업이 진행됩니다.

다음과 같이 모든 요소가 한칸씩 앞으로 이동하게 되면

Array의 길이만큼의 동작을 수행하게 되므로

O(N)의 시간복잡도가 소요되겠네요.

 

이런 이유로 저희는 removeFirst() 함수를 쓸때 

시간적인 비효율을 해결해야 합니다.

 

큐 구현방법

큐는 데이터 출력을 할 때 removeFirst()를 사용한다고 말씀드렸는데요.

시간복잡도를 고려한다면 다른 방법을 찾아봐야겠네요.

 

Array를 재배치 하지 않고 데이터를 출력하기 위해

데이터를 삭제시키는 방법이 아닌 방출할 위치를 기억시키는 방법이 있습니다.

(실제로 데이터가 삭제되지 않는다는 특징이 있습니다)

그림으로 볼까요?

 

다음과 같이 리스트가 있습니다.

array = [0,1,2,3,4,5]

 

현재 초기 상태이기 때문에 Head는 index 0 을 가리키고 있습니다.

이 상태에서 첫번째 요소를 방출시켜볼까요?

array[Head(=0)] 👉 0방출

이때 Head를 오른쪽으로 한 칸 움직여줍니다.

주의할점은 실제 Array에서는 0이 방출되지 않았고

Head를 이용해서 시작 index를 바꿔준 것입니다.

 

한 번 더 방출시켜볼까요?

array[Head(=1)] 👉 1방출

이제 어떻게 첫번째 요소를 방출하는지 이해가 되셨나요?

코드로 살펴볼까요?

class Queue {
    var elements: [Int] = []
    var head: Int = 0
    
    func append(_ element: Int) {
        elements.append(element)
    }
    
    func popleft() -> Int? {
        if head >= elements.count {
            return nil
        }
        
        let temp = elements[head]
        head += 1
        
        return temp
    }
}

 

코드를 보시면 어디에도 elements의 요소를 삭제시키는 코드가 없습니다.

삭제 대신 head로 시작 위치를 변경시킨다는 것이 핵심입니다.

 

그렇다면 의문이 생기네요.

길이가 100인 Array에서 요소를 50번 방출했다고 하면

50개의 요소는 사실상 의미 없는 메모리를 차지하고 있는 거네요.

 

시간 효율을 따지다가 공간 효율을 간과했네요.

이런 문제를 해결하기 위해 메모리를 정리해주는 코드를 삽입하도록 할게요.

func popleft() -> Int? {
    if head >= elements.count {
        return nil
    }

    let temp = elements[head]
    head += 1

    // 리스트가 너무 길어지면 리셋 작업 필요
    if head > 50 {
        elements.removeFirst(head)
        head = 0
    }

    return temp
}

 

head가 50이 넘게되면 약간의 시간복잡도가 소요되더라도

의미없는 앞의 요소들을 한번 정리하는 코드를 넣었습니다.

이렇게 공간 효율도 어느정도 고려한 코드가 되었네요.

 

또한 queue의 요소에 접근할 때 직접 접근할 수 없습니다.

queue.elements.count

queue.elements.isEmpty

왜냐면 저 elements에는 이미 우리가 방출시킨 요소도 포함되었기 때문이에요.

 

elements에 대한 판별이 필요할때는

Queue 클래스 안에서 미리 정의된 함수를 사용하도록 합니다.

var isEmpty: Bool {
    return head >= elements.count
}

var count: Int {
    return elements.count - head
}

var first: Int? {
    return isEmpty ? nil : elements[head]
}

 

.

.

.

다음 포스팅은 Queue를 이용한 BFS 문제 풀이로 돌아오겠습니다

(문제에 오류가 있거나 이해가 안 가시면 댓글 남겨주세용~😉)

.

.

.

 

👇 Queue 템플릿 전체보기

class Queue {
    var elements: [Int] = []
    var head: Int = 0
    
    func append(_ element: Int) {
        elements.append(element)
    }
    
    func popleft() -> Int? {
        if head >= elements.count {
            return nil
        }
        
        let temp = elements[head]
        head += 1
        
        if head > 50 {
            elements.removeFirst(head)
            head = 0
        }
        
        return temp
    }
    
    var isEmpty: Bool {
        return head >= elements.count
    }

    var count: Int {
        return elements.count - head
    }

    var first: Int? {
        return isEmpty ? nil : elements[head]
    }
}