[자료구조] 스택, 큐, 덱

로빈·2022년 5월 22일
0

Algorithm, Data Structure

목록 보기
2/12

스택(Stack)

  • Last In First Out
struct Stack<T> {
    private var array = [T]()
    
    var isEmpty: Bool {
        return array.isEmpty
    }
    
    var count: Int {
        return array.count
    }
    
    mutating func push(_ element: T) {
        array.append(element)
    }
    
    mutating func pop() -> T? {
        return array.popLast()
    }
    
    var top: T? {
        return array.last
    }
}

큐(Queue)

  • First In First Out
  • 배열 2개를 이용한 큐(enqueue용과 dequeue용 2개)
  • removeFirst()는 시간복잡도가 O(n)이므로, 시간복잡도가 O(1)인 reversed() 사용한 후 popLast()로 원소를 가져온다.
import Foundation

struct Queue<T> {
    private var enqueueArray: [T] = [] 
    private var dequeueArray: [T] = []
    
    var isEmpty: Bool {
        return enqueueArray.isEmpty && dequeueArray.isEmpty
    }
    
    var count: Int {
        return enqueueArray.count + dequeueArray.count
    }
    
    mutating func enqueue(_ element: T) {
        enqueueArray.append(element)
    }
    
    // dequeueArray가 비어있으면 enqueueArray를 뒤집어서 dequeueArray로 가져옴
    // 가져왔으니 enqueueArray 비워줌
    mutating func dequeue() -> T? {
        if dequeueArray.isEmpty {
            dequeueArray = enqueueArray.reversed()
            enqueueArray.removeAll()
        }
        // dequeueArray에서 마지막 원소를 꺼낸다.
        return dequeueArray.popLast()
    }
    
    var front: T? {
        return dequeueArray.last ?? enqueueArray.last
    }
}

덱(Deque)

  • 덱(Deck) 이라고 읽는다
  • 양방향 삽입, 삭제가 가능한 자료구조
  • 위에 큐와 비슷하게 배열 2개를 이용해서 구현한 덱
import Foundation

struct Dequeue<T> {
    private var enqueueArray: [T] = []
    private var dequeueArray: [T] = []
    
    var isEmpty: Bool {
        return enqueueArray.isEmpty && dequeueArray.isEmpty
    }
    
    var count: Int {
        return enqueueArray.count + dequeueArray.count
    }
    
    mutating func enqueueFront(_ element: T) {
        dequeueArray.append(element)
    }
    
    mutating func enqueue(_ element: T) {
        enqueueArray.append(element)
    }
    
    mutating func dequeue() -> T? {
        if dequeueArray.isEmpty {
            dequeueArray = enqueueArray.reversed()
            enqueueArray.removeAll()
        }
        
        return dequeueArray.popLast()
    }
    
    mutating func dequeueBack() -> T? {
        if enqueueArray.isEmpty {
            enqueueArray = dequeueArray.reversed()
            dequeueArray.removeAll()
        }
        
        return enqueueArray.popLast()
    }
    
    var front: T? {
        return dequeueArray.last ?? enqueueArray.last
    }
    
    var back: T? {
        return enqueueArray.last ?? enqueueArray.last
    }
}

출처

profile
IOS 앱개발 공부중

0개의 댓글