스위프트 | "스택, 큐, 덱 구현"하기 (Swift5 | Stack, Queue, Deque)

 

 

백준 1935번을 풀다가, 스위프트엔 스택 & 큐가 없다는 사실을 알게 되었습니다. (+ 물론 덱은 당연히 없었습니다..)

지난번 게시글과 똑같은 상황이죠?

네. 구현해야 합니다... (스택은 아닐지도~ 아래에서 설명합니다.)

 

https://developer-p.tistory.com/145

스위프트 | "순열과 조합 구현"하기 (Swift5 | Permutation, Combination)

 

---

 

여러 게시글을 찾아보면서, 현재 제가 이해할 수 있는 수준의 코드를 입맛에 맞게 구현했습니다.

 

---

 

스택

Stack

 

스택 이미지.

 

스택은 LIFO입니다. (Last in First out)

그 말인 즉,

⚬ 늘 마지막에 element 추가 = .append = 시간 복잡도 O(1).

⚬ 늘 마지막에 element 삭제 = .popLast = 시간 복잡도 O(1).

따라서 배열을 스택처럼 이용하면 됩니다. ( = 스택은 구현 안 해도 됩니다!)

 

그래도 구현한다면,

스택 구현

// Stack 구현 연습
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 myStack: Stack = Stack<Int>()
myStack.push(10)
print(myStack.pop()!)
print(myStack.pop())

참고한 글 : https://babbab2.tistory.com/85?category=908011 

 

---

 

큐

Queue

 

큐 이미지.

 

백준 2164번은 큐 문제입니다. 하지만 스위프트엔 큐가 없죠...

처음엔 (배열을 통해) 큐의 로직만 구현했더니 시간 초과가 납니다.

 

(아래 더보기는 시간 초과가 나는 코드의 일부입니다.)

 

큐 로직만 구현 - 느림

 

// Queue 구현 연습
struct Queue<T> {
    private var queue: [T] = []
    
    private var count: Int {
        return queue.count
    }
    
    private var isEmpty: Bool {
        return queue.isEmpty
    }
    
    public mutating func enQueue(_ element: T) {
        queue.append(element)
    }
    
    public mutating func deQueue() -> T? {
        return queue.isEmpty ? nil : queue.removeFirst()
    }
    
}

var myQueue: Queue = Queue<Int>()
myQueue.enQueue(5)
myQueue.enQueue(10)
myQueue.enQueue(13)
myQueue.deQueue()

참고한 글 : https://babbab2.tistory.com/84

---

 

배열 2개를 사용해서 큐를 구현했더니 속도도 훨씬 빨라지고 시간제한을 통과할 수 있었습니다.

 

큐 구현 - 빠름 (배열 2개 사용)

class Queue<T> {
    var enQueue: [T]
    var deQueue: [T] = []
    
    var count: Int {
        return enQueue.count + deQueue.count
    }
    
    var isEmpty: Bool {
        return enQueue.isEmpty && deQueue.isEmpty
    }
    
    init(_ queue: [T]) {
        self.enQueue = queue
    }
    
    func push(_ element: T) {
        enQueue.append(element)
    }
    
    func pop() -> T {
        if deQueue.isEmpty {
            deQueue = enQueue.reversed()
            enQueue.removeAll()
        }
        return deQueue.popLast()!
    }
    
}

let N = Int(readLine()!)!
var temp = [Int]()
for i in 1...N {
    temp.append(i)
}
var myQueue: Queue = Queue<Int>(temp)

참고한 글 : https://icksw.tistory.com/65

 

---

덱

Deque

 

덱은 큐와는 다르게, 양방향 pop이 가능합니다.

 

덱(Deque) 구현 - (배열 2개 사용)

class Deque<T>{
    var enQueue: [T]
    var deQueue: [T] = []
    
    var count: Int {
        return enQueue.count + deQueue.count
    }
    
    var isEmpty: Bool {
        return enQueue.isEmpty && deQueue.isEmpty
    }
    
    init(_ queue: [T]) {
        enQueue = queue
    }
    
    func pushFirst(_ element: T) {
        deQueue.append(element)
    }
    
    func pushLast(_ element: T) {
        enQueue.append(element)
    }
    
    func popFirst() -> T {
        if deQueue.isEmpty {
            deQueue = enQueue.reversed()
            enQueue.removeAll()
        }
        return deQueue.popLast()!
    }
    
    func popLast() -> T {
        if enQueue.isEmpty {
            enQueue = deQueue.reversed()
            deQueue.removeAll()
        }
        return enQueue.popLast()!
    }
    
}

참고한 글 : https://icksw.tistory.com/213

 

덱(Deque) 구현 - firstIndex추가 Ver. (2022.03.21 추가)

덱(Deque) 구현 - firstIndex추가 Ver.

참고한 글 : https://developer.apple.com/documentation/swift/array/2994722-firstindex

class Dequeue<T: Comparable> {
    var enQueue: [T]
    var deQueue: [T] = []
    
    var count: Int {
        return enQueue.count + deQueue.count
    }
    
    var isEmpty: Bool {
        return enQueue.isEmpty && deQueue.isEmpty
    }
    
    init(_ queue: [T]) {
        enQueue = queue
    }
    
    func pushLast(_ element: T) {
        enQueue.append(element)
    }
    
    func pushFirst(_ element: T) {
        deQueue.append(element)
    }
    
    func popLast() -> T {
        if enQueue.isEmpty {
            enQueue = deQueue.reversed()
            deQueue.removeAll()
        }
        return enQueue.popLast()!
    }
    
    func popFirst() -> T {
        if deQueue.isEmpty {
            deQueue = enQueue.reversed()
            enQueue.removeAll()
        }
        return deQueue.popLast()!
    }
    
    func firstIndex(_ num: T) -> Int {
        let newQue = deQueue.reversed() + enQueue
        if let i = newQue.firstIndex(where: {$0 == num}) {
            return i
        }
        return 0
    }
}

---

스위프트가 기본 제공 함수가 적다는 건 매우 아쉽습니다.

그래도 공부할수록 재밌는 것 같습니다.

 

 

코드 중 이해가 안 되는 부분이 있거나, 잘못된 부분이 있다면 편하게 댓글 부탁드립니다.

---

https://developer-p.tistory.com/145

스위프트 | "순열과 조합 구현"하기 (Swift5 | Permutation, Combination)

https://developer-p.tistory.com/190

스위프트 | "(최소)힙 구현"하기 (Swift5 | Heap - MinHeap)