[자료구조] Queue 알아보기

1. Queue란?

추가되는 자료를 차례대로 저장하여, 저장된 순서에 의해 데이터가 나오는,
선입선출( First-In-First-Out )의 선형 자료구조이다.

먼저 저장된 데이터가 나중 저장된 데이터 보다 항상 앞서 나오기 때문에 선입선출의 특성을 지니고 있으며, 저장된 자료들 사이의 선후 관계가 모두 1:1 이기에 '선형' 자료구조라고 부른다.

Queue에서 반환은 앞(front)에서만 가능하고 자료의 추가는 뒤(rear)에서만 가능하다.

 

a) enqueue(item)

새로운 자료를 큐에 추가하는 것을 enqueue라고 한다.

제일 먼저 A가 빈 큐에 추가되면, 큐의 front와 rear은 A를 가르키게 된다. 그 다음 단계로 저장된 A의 위쪽으로 새로운 자료 B가 저장되며 rear은 B를 가르키게된다. rear가 가르키는 자료는 항상 추가되는 자료의 위치이다. (큐의 마지막 자료를 가르킨다)

 

b) dequeue()

큐에서 자료를 꺼내는 것을 dequeue이라고 한다.

큐에서 front가 가르키고 있는 자료를 제거하고 이를 반환한다. 반환하게 되면 front가 가르키고 있는 자료의 다음 자료로 front의 위치가 이동한다. 

 

b) peek()

자료를 제거하거나 추가하지 않고 해당 자료에 접근만 하는 것을 피크(peek)라고 한다. 

단, 이 경우에도 큐의 front가 가르키고 있는 자료에만 접근을 할 수 있다. 

 

c) 파이썬으로 queue 구현하기 

일반적으로 파이썬으로 queue를 구현할 때에는 `collections` 모듈의 `deque`를 활용한다.

from collections import deque

# 큐 생성
queue = deque()

# 요소 삽입
queue.append(1)
queue.append(2)
queue.append(3)

# 요소 삭제
deleted_element = queue.popleft()  # 큐의 왼쪽에서 요소 삭제 및 반환
print("삭제된 요소:", deleted_element)

# 큐 출력
print("큐의 상태:", queue)

# 큐가 비어 있는지 확인
if not queue:
    print("큐는 비어 있습니다.")
else:
    print("큐에 요소가 있습니다.")

# 큐의 길이 확인
print("큐의 길이:", len(queue))

# 큐의 첫 번째 요소 확인 (삭제하지 않고)
first_element = queue[0]
print("첫 번째 요소:", first_element)

 

이외에도 파이썬에는 리스트에서 지정한 인덱스의 자료를 반환하는 `pop(item)`과 자료의 마지막에 추가하는 `append()` 함수를 통해 구현할 수 있다.

2. 언제 주로 사용하는가?

멀티 테스킹을 위한 프로세스 방식을 구현하기 위해 많이 사용된다. (운영체제, 네트워크 등)

데이터(data)가 입력된 순서대로 처리할 때 주로 사용한다.

3. 주의 할 점

스택과 같이 큐의 크기만큼 자료가 들어가 있는 상황일 때 enqueue를 하게되면 overflow 현상이 발생하고, 큐에 자료가 없을 때 dequeue를 하게되면 underflow 현상이 발생한다.

4. 시간 복잡도

제나 삽입시 맨 위에 데이터를 삽입하거나 삭제하기 때문에 시간복잡도는 늘 O(1) 의 시간복잡도를 가진다. 하지만 특정 데이터를 찾을 때는 특정 데이터를 찾을 때까지 수행을 해야하므로 O(n) 의 시간 복잡도를 가진다.

5. 관련 문제

프로그래머스 - 프로세스

def solution(priorities, location):
    length = len(priorities)  
    location_list = [i for i in range(length)]  # 위치를 표현할 배열 생성 
    queue = [i for i in priorities] #(깊은 복사)
    answer = []  
    
    while queue:  # 큐에 데이터가 있는 동안 반복
        data = queue[0]  # 큐의 첫 번째 데이터를 확인
        locate_data = location_list[0]  # 인덱스 리스트의 첫 번째 데이터를 확인
        
        if max(queue) == data:  # 큐에서 가장 큰 우선순위를 가진 데이터인지 확인
            queue.pop(0)  # 큐에서 데이터를 추출 (Dequeue)
            answer.append(location_list.pop(0))  # 해당 데이터의 인덱스를 정답 리스트에 추가
        else:  # 우선순위가 낮은 경우
            queue.append(queue.pop(0))  # 데이터를 큐의 맨 뒤로 보냄 (Enqueue)
            location_list.append(location_list.pop(0))  # 해당 인덱스도 맨 뒤로 보냄 (Enqueue)
        
        if location in answer:  # 원하는 위치가 정답 리스트에 있는지 확인
            break  # 원하는 위치를 찾았으므로 반복문을 종료
    
    return len(answer)  
    #원하는 위치를 찾았을때 break를 걸었기에 answer의 길이가 곧 원하는 위치가 실행되는 순서와 같음

 

프로그래머스 - 다리를 지나는 트럭

def solution(bridge_length, weight, truck_weights):
    time = 0 #소요된 시간 
    movetime = [] #트럭이 다리를 건널때의 시간을 저장하는 큐 
    wait_truck = truck_weights[:]  #배열 전체 복사 (큐)
    move_truck = [] #다리를 건너는 트럭 큐
    while wait_truck or move_truck: #다리를 건너는 트럭과 대기 트럭이 모두 없을때까지 반복
        time += 1 
        # 만약 다리 위에 트럭이 있고, 다리를 전부 지났다면
        if move_truck and time - movetime[0] == bridge_length:
            movetime.pop(0) #건너는 트럭의 시간 리스트에서 삭제 (dequeue)
            move_truck.pop(0) #건너는 트럭 리스트에서 삭제(dequeue)
        # 대기 중인 트럭이 있고, 다음 트럭을 추가해도 다리 무게를 초과하지 않는 경우  
        if wait_truck and sum(move_truck) + wait_truck[0] <= weight:
            move_truck.append(wait_truck[0]) #다리를 건너는 트럭 리스트에 추가 (enqueue)
            movetime.append(time) #건너기 시작할때의 시간 추가 (enqueue)
            wait_truck.pop(0) #대기 트럭에서 삭제 (dequeue)
    return time

 

---

[참조문서 / 자료]

열혈강의 자료구조(도서)