Queue

 

Queue

• 한쪽 끝(rear)에서 데이터의 삽입(enqueue)이 일어나고, 반대쪽 끝(front)에서 삭제(dequeue)가 일어나는 선형 자료구조
• 그런 구조이기 때문에 FIFO의 형태로 동작

 

시간 복잡도

rear나 front 외, 원소들의 확인 및 변경은 원칙적으로 불가능

연산의 시간 복잡도

Rear나 front에 원소 추가(enqueue), 제거(dequeue)	O(1)
Rear나 front의 원소 확인	O(1)

 

구현

• 배열이나 연결리스트 등으로 구현 가능
• 구현

struct Queue<T> {
    private var array: [T?] = []
    private var frontIndex = 0
    
    var front: T? { 
        guard frontIndex < array.count, let element = array[frontIndex] else {
            return nil
        }
        return element 
    }
    
    var back: T? { 
        guard let element = array.last else {
            return nil
        }
        return element
    }
    
    var size: Int { 
        array.count - frontIndex  // 큐의 앞부분이 제거되어있을 수 있기 때문에
    }
    var isEmpty: Bool { size == 0 }
    
    mutating func push(_ newElement: T) {
        array.append(newElement)
    }
    
    mutating func pop() -> T? {
        guard frontIndex < array.count, let element = array[frontIndex] else {
            return nil
        }
        
        array[frontIndex] = nil
        frontIndex += 1
        
        // 배열의 25%이상이 비어있다면 -> 남은 원소들 앞으로 당겨줌
        if Double(frontIndex) / Double(array.count) * 100 >= 25 {
            array.removeSubrange(0 ..< frontIndex)
            frontIndex = 0
        }
        
        return element
    }
}

 

종류

Linear Queue

• 가장 기본적인 형태의 큐
• 배열로 구현 시 삭제가 발생할 때마다 앞쪽에 낭비되는 공간 생김

 

Circular Queue

• 관념적인 원형의 형태
• 낭비되는 공간 없이 메모리를 효율적으로 사용 가능

 

 

Circular Queue

Linear Queue는 FIFO 구조로 enqueue 혹은 dequeue 발생 시 데이터를 재정렬해줘야 한다. 이 때 시간 복잡도는 O(n)이다. 이 오버헤드를 줄이기 위하여 원형 큐가 탄생했다.

 

https://velog.io/@angel_eugnen/%EC%9B%90%ED%98%95-%ED%81%90

 

원형 큐는 위 이미지와 같이 큐의 동작을 원형처럼 동작하도록 변형된 것이다.

삭제하려는 위치를 가리키는 front 포인터와 추가하려는 위치를 가리키는 rear 포인터를 이용하여 구현한다.

 

1. front 포인터와 rear 포인터를 0으로 초기화한다.

• 둘 다 인덱스 0부터 시작

 

2. 요소를 삽입하는 경우

• rear포인터에 요소를 넣어주기
• rear 포인터를 +1해줌
• rear 포인터는 다음 요소가 삽입될 위치를 가리키고 있음

 

3. 요소를 제거하는 경우

• dequeue는 실제 물리적인 삭제가 이루어지도록 하지 않음. 
• 그저 논리적으로 삭제된 것처럼 보이도록 front 포인터를 +1 해줌
• 요소가 존재하는 범위는 front부터 (rear - 1)까지임.
  • rear는 새로운 요소를 지정할 인덱스를 가리키기 때문에 요소는 rear - 1에 존재하고 있음

 

4. 실제 요소가 제거되는 경우는?

• 배열의 크기가 5라고 할 때, 인덱스는 0부터 4임, front는 1로 0에있는 요소가 논리적으로 사라졌다고 가정.
• 위 상황에서 rear의 인덱스가 4이고, 요소를 추가한다면 rear + 1을 해줘야 함.
• 근데 배열의 크기가 5인데 rear가 5라는 것은 배열의 범위를 넘어선 것이죠?
• 이 때는 다시 rear를 0으로 돌려줌. 그리고 새로운 요소를 추가할 때, 논리적으로는 제거되었던 0에있는 기존 요소를 새로운 요소로 덮어씌움
• 이것이 선형 큐의 오버헤드를 줄여주는 원형 큐의 목적 달성임.

 

 

예제

1. 큐를 사용해 만들 수 있는 프로그램에는 어떤 것들이 있을까요? 이유와 함께 설명하세요.

정답

• 프린터: 한 번에 하나의 작업을 처리
• 프로세스 스케줄링: 프로세스가 리소스 사용을 위해 대기하는 순서를 관리하기 위해 큐 사용 가능

 

2. 큐 2개로 스택의 push, pop 동작을 구현하는 방법과, 그 시간 복잡도에 대해 서술하세요.

정답

• push
  • 첫 번째 큐에 데이터 Push
  • 시간 복잡도: O(1)
• pop
  • 첫 번째 큐의 마지막 요소를 제외한 나머지를 두 번째 큐로 옮긴 후, 첫 번째 큐에 남아있는 요소 pop
  • 두 번째 큐로 옮긴 요소들 다시 첫 번째 큐로 옮김
  • 시간 복잡도 O(n)

 

• • • • • •