원형큐 구현하기

1. 문제

2. 입출력

3. 입출력 예시

4. 문제 설계

• 단순 선형 큐에서는 투 포인터 front와 rear가 계속 증가만 하게 되므로, 배열의 앞 공간을 낭비하게 됨
• 따라서 큐 내의 데이터의 개수를 유지하는 별도의 count를 두어 overflow와 underflow를 파악하고, 데이터의 개수를 파악하며,
• front와 rear가 배열의 끝에 도달하게 되면 0으로 초기화 해줌으로써 단순 선형 큐의 단점을 해결할 수 있음

5. 전체 코드

//MARK: - 원형큐 구현하기

//MARK: - Framework
import Foundation

//MARK: - Type
struct Queue {
    //MARK: - Property
    var array: [Int]
    var f: Int
    var r: Int
    var count: Int
    var capacity: Int
    
    //MARK: - Initialzier
    init(_ capacity: Int) {
        self.capacity = capacity
        self.f = 0
        self.r = 0
        self.count = 0
        self.array = Array(repeating: 0, count: capacity)
    }
    
    //MARK: - Method
    mutating func push(_ data: Int) -> Void {
        if self.count >= self.capacity {
            print("Overflow")
        } else {
            self.array[self.r] = data
            self.r += 1
            self.count += 1
            
            self.r = self.r >= self.capacity ? 0 : self.r
        }
    }
    
    mutating func pop() -> Void {
        if self.count <= 0 {
            print("Overflow")
        } else {
            self.array[self.f] = 0
            self.f += 1
            self.count -= 1
            
            self.f = self.f >= self.capacity ? 0 : self.f
        }
    }
    
    func front() -> Int {
        return self.count <= 0 ? -1 : self.array[self.f]
    }
    
    func size() -> Int {
        return self.count
    }
}

//MARK: - Function
func solution() -> Void {
    //MARK: - Input
    guard let input = readLine()?.components(separatedBy: " ") else { return }
    
    let n: Int = input.map { Int($0) }[0] ?? 0
    let m: Int = input.map { Int($0) }[1] ?? 0
    var queue: Queue = Queue(n)
    
    //MARK: - Process & Output
    for _ in 0..<m {
        guard let inputData = readLine()?.components(separatedBy: " ") else { return }
        let operation: Int = inputData.map { Int($0) }[0] ?? 0
        
        switch operation {
        case 1:
            let data: Int = inputData.map { Int($0) }[1] ?? 0
            queue.push(data)
        case 2:
            queue.pop()
        case 3:
            print(queue.front() == -1 ? "NULL" : "\(queue.front())")
        default:
            break
        }
    }
}
solution()

 

전체코드는 여기에서 확인할 수 있습니다.