3월 6일 TIL (Stack, Queue)

Queue

• 큐는 First-In-First-Out 구조를 갖고 있다.
• 즉 먼저 들어온 데이터가 먼저 빠져 나가는 구조이다.
• 예시 : 맛집 대기줄, (먼저온 사람이 먼저 들어간다)
• Swift에서는 따로 Queue를 제공하지 않고, 직접 Array를 이용해서 구현해야한다.

struct Queue<T> {
    private var queue: [T] = []
    
    public var count: Int {
        return queue.count
    }
    
    public var isEmpty: Bool {
        return queue.isEmpty
    }
    
    public mutating func enqueue(_ element: T) {
        queue.append(element)
    }
    
    public mutating func dequeue() -> T? {
        return isEmpty ? nil : queue.removeFirst()
    }
}

var queue = Queue<Int>()
queue.enqueue(10)
queue.enqueue(20)
queue.dequeue() // 10

Stack

• 스택은 Last-In-First-Out 구조를 갖고 있다.
• 즉 마지막에 들어온 구조가 제일 먼저 빠지는 구조이다.
• 예시: 벽돌쌓기 ( 맨 아래에 있는 벽돌을 꺼내기 위해서는 위에서부터 뺴야한다)
• 마찬가지로 stack도 Array로 직접 구현해야 한다.

struct Stack<T> {
    private var stack: [T] = []
    
    public var count: Int {
        return stack.count
    }
    
    public var isEmpty: Bool {
        return stack.isEmpty
    }
    
    public mutating func push(_ element: T) {
        stack.append(element)
    }
    
    public mutating func pop() -> T? {
        return isEmpty ? nil : stack.popLast()
    }
}

var stack = Stack<Int>()
stack.push(10)
stack.push(20)
stack.pop() // 20

• 만약 구조체를 만들지 않고 사용하려면, array의 아래 함수들만 사용해도 된다.

let arr : [Int] = [1,2,3,4,5]
arr.append(6) // [1,2,3,4,5,6] 마지막에 추가 (Stack Queue 둘다 사용)
arr.removeFirst() // [2,3,4,5,6] 처음 요소 삭제 (Queue 사용), 단 nil일 경우 대비
arr.popLast() // [2,3,4,5] 마지막 요소 삭제 (Stack 사용), 단 nil 일 경우 대비