[Swift] Queue 큐 구현하기 (배열 / 연결리스트 / Two Stack / Head 방식)

Queue를 구현하는 다양한 방식들.

Queue 구현하기 - (1) 배열

가장 쉽지만 가장 추천하지 않는 방법

struct Queue<T>: CustomStringConvertible {

    private var elements: [T] = []
    public init() {}

    var isEmpty: Bool {
        elements.isEmpty
    }

    var peek: T? {
        elements.first
    }

    var description: String {
        if isEmpty { return "Queue is empty..." }
        return "---- Queue start ----\n"
            + elements.map({"\($0)"}).joined(separator: " -> ")
            + "\n---- Queue End ----"
    }

    mutating func enqueue(_ value: T) {
        elements.append(value)
    }

    mutating func dequeue() -> T? {
        isEmpty ? nil : elements.removeFirst()
    }
}

Queue 구현하기 - (2) 연결리스트(Singly Linked List)

class Node<T>: CustomStringConvertible {

    var value: T
    var next: Node?

    var description: String {
        guard let next = next else { return "\(value)" }
        return "\(value) -> " + String(describing: next)
    }

    init(value: T, next: Node? = nil) {
        self.value = value
        self.next = next
    }
}


struct Queue<T>: CustomStringConvertible {

    var front: Node<T>?

    var rear: Node<T>?

    init() { }

    var isEmpty: Bool {
        return front == nil
    }

    var description: String {
        guard let front = front else { return "Empty Queue" }
        return String(describing: front)
    }

    var peek: T? {
        return front?.value
    }
}

extension Queue {

    mutating private func push(_ value: T) {
        front = Node(value: value, next: front)
        if rear == nil {
            rear = front
        }
    }

    mutating func enqueue(_ value: T) {
        if isEmpty {
            self.push(value)
            return
        }

        rear?.next = Node(value: value)
        rear = rear?.next
    }

    mutating func dequeue() -> T? {
        defer {
            front = front?.next
            if isEmpty {
                rear = nil
            }
        }
        return front?.value
    }
}

Queue 구현하기 - (3) Stack 두 개를 사용해 구현 (two stacks)

struct TwoStackQueue<T>: CustomStringConvertible {

    private var leftStack: [T] = []
    private var rightStack: [T] = []

    var isEmpty: Bool {
        leftStack.isEmpty && rightStack.isEmpty
    }

    var peek: T? {
        leftStack.isEmpty ? rightStack.first : leftStack.last
    }

    var description: String {

        if isEmpty {
            return "Queue is empty..."
        }
        var allElements: [T] = []
        if leftStack.isEmpty == false {
            allElements.append(contentsOf: leftStack.reversed())
        }
        allElements.append(contentsOf: rightStack)

        return "---- Queue start ----\n"
            + allElements.map({"\($0)"}).joined(separator: " -> ")
            + "\n---- Queue End ----"
    }
}

extension TwoStackQueue {

    mutating func enqueue(_ element: T) {
        rightStack.append(element)
    }
}

extension TwoStackQueue {

    mutating func dequeue() -> T? {

        if isEmpty {
            return nil
        }

        if leftStack.isEmpty {
            leftStack = rightStack.reversed()
            rightStack.removeAll()
        }

        return leftStack.removeLast()
    }
}

Queue 구현하기 - (4) head를 사용해 구현

public struct Queue<T> {
      fileprivate var array = [T?]()
      fileprivate var head = 0

      public var isEmpty: Bool {
            return count == 0
      }

      public var count: Int {
            return array.count - head
      }

      public mutating func enqueue(_ element: T) {
            array.append(element)
      }

      public mutating func dequeue() -> T? {
            guard head < array.count, let element = array[head] else { return nil }

            array[head] = nil
            head += 1

            let percentage = Double(head)/Double(array.count)
            if array.count > 50 && percentage > 0.25 {
              array.removeFirst(head)
              head = 0
            }

            return element
      }

      public var front: T? {
            if isEmpty {
              return nil
            } else {
              return array[head]
            }
      }
}