[자료구조] 스택 / 큐 (+ Swift 구현)

스택 Stack

곡차곡 쌓아 올린 형태의 자료구조.

가장 마지막에 삽입된 자료가 가장 먼저 삭제되는 후입선출 LIFO (Last In First Out) 구조

정해진 방향으로만 쌓을 수 있고, top으로 정한 곳을 통해서만 삽입/삭제할 수 있다.

스택에서 top을 통해 삽입하는 연산을 push, top을 통해 삭제하는 연산을 pop 이라고 한다.

 

스택 활용 예시)

- 웹 브라우저 방문 기록 (뒤로 가기) : 가장 나중에 열린 페이지부터 다시 보여준다.

- 실행 취소 : 가장 나중에 실행된 것부터 실행을 취소한다.

 

큐 Queue

줄을 서서 기다리는 것. 

먼저 들어온 것이 먼저 나가는 선입선출 FIFO (First In First Out) 방식의 자료구조

큐는 한쪽 끝에서 삽입 작업이, 다른 쪽 끝에서 삭제 작업이 양쪽으로 이루어진다. 

큐의 가장 첫 원소를 front, 가장 끝 원소를 rear 라고 하며

큐의 rear에서 이루어지는 삽입 연산을 enQueue, front에서 이루어지는 삭제 연산을 deQueue 라고 한다.

 

큐 활용 예시)

데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 이용

- 은행 창구 업무

 

 

 

스택 / 큐 문제

프로그래머스 - 스택/큐

백준 - 스택, 큐

 

 

---

스택을 Swift 구조체로 구현해보았다. 

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

사실 Swift에서 스택을 굳이 만들어서 사용할 필요는 없다. 

push 는 그냥 배열에 append 하면 되고

pop 은 popLast() 가 제공되기 때문에 스택을 직접 만들어주지 않아도 배열을 스택처럼 활용이 가능하다.