끄적끄적 개발 블로그입니다.

5 분 소요

Queue의 정의

큐(Queue)는 줄을 서서 기다리다, 대기열이라는 뜻을 가지고 있습니다.

큐의 예시를 살펴 보겠습니다.

슈퍼마켓에서 계산을 기다리는 사람들이 줄을 서 있을 때, 먼저 줄을 선 사람이 먼저 계산을 마치고 나가는 것과 같습니다.

여기서 계산대 옆에서 줄을 대기하는 것이 큐이고, 사람을 데이터로 비유할 수 있습니다.

명절 때 고향을 찾아가려고 많은 자동차들이 고속도로를 이용합니다. 고속도로에는 톨케이트가 있고, 자동차들은 톨게이트에 도착한 순서대로 통행료를 내고 통과합니다.

여기서는 톨게이트를 큐, 자둉차는 데이터로 비유할 수 있습니다.

Queue의 구조

자료구조 Queue는 Stack과 반대되는 개념으로, 먼저 들어간 데이터(data)가 먼저 나오는 FIFO(First In First Out) 혹은 LILO(Last In Last Out)을 특징으로 가지고 있습니다.

입력의 방향과 출력의 방향이 각각 고정되어 있으며, 데이터를 입력할 시에는 큐의 끝에서(rear), 데이터를 출력할 때는 큐의 맨 앞에서(front) 진행됩니다.

여기서 Queue에 데이터를 넣는 것을 ‘enqueue’, 데이터를 꺼내는 것을 ‘dequeue’라고도 하며, 자료구조 Queue는 데이터(data)가 입력된 순서대로 처리할 때 주로 사용합니다.

Queue의 특징

  1. FIFO (First In First Out)

    먼저 들어간 데이터가 제일 처음에 나오는 선입선출의 구조로 되어 있습니다.

  2. 두 개의 입출력 방향을 가지고 있습니다.

    Queue 자료구조는 데이터의 입력, 출력 방향이 다릅니다. 데이터를 입력할 때는 큐의 맨 끝(rear)으로만 입력이 가능하며 데이터를 출력할 때는 큐의 맨 앞(front)으로만 출력이 가능합니다. 즉, 큐는 데이터를 입력하는 곳과 출력하는 곳이 각각 정해져 있으며 이렇게 총 2개의 입출력 방향을 가지고 있습니다. 만약 입출력 방향이 같다면 Queue 자료구조라고 볼 수 없습니다.

  3. 데이터는 하나씩 넣고 뺄 수 있습니다.

    앞서 말했듯, Queue 자료구조는 데이터를 넣을 때는 큐의 맨 뒷부분에서 뺄 때는 큐의 맨 앞부분에서 처리를 진행합니다. 각 처리 시마다 한 개의 데이터를 넣거나 뺄 수 있습니다. 즉, 큐에 한 개씩 여러 번 데이터를 넣어 큐 내부에 데이터가 여러 개 쌓여 있다고 하더라도, 데이터를 뺄 때는 큐의 맨 앞에서 한 번에 한 개의 데이터만을 뺄 수 있습니다.

Queue 자료 구조의 이점

  1. 데이터를 순차적으로 처리할 수 있습니다.

    큐는 선입선출(First-In-First-Out, FIFO) 원칙을 따르므로, 가장 먼저 삽입된 데이터가 가장 먼저 삭제되고, 가장 나중에 삽입된 데이터는 가장 나중에 삭제됩니다. 이 특성 덕분에, 처리해야 할 데이터나 작업을 순차적으로 처리할 수 있습니다.

    큐의 가장 앞(front)에서는 가장 오래전에 삽입된 데이터가 위치하고, 가장 뒤(rear)에는 가장 최근에 삽입된 데이터가 위치합니다. 즉, 데이터를 삽입하는 순서와 삭제하는 순서가 일치하게 유지됩니다.

    이런 구조는 데이터 처리나 작업 처리에서 순서가 중요한 경우에 유용합니다. 예를 들어, 프린터에서 인쇄 요청이 들어온 순서대로 처리해야 하는 경우, 은행에서 대기 중인 고객 순서를 결정하는 경우, 채팅 시스템에서 메시지를 보내는 순서를 결정하는 경우 등에 큐를 활용할 수 있습니다.

  2. 삽입과 삭제가 각각 양 끝에서 이루어지며 중간에 위치한 데이터를 삭제할 수 없으므로, 다른 자료 구조에 비해 상대적으로 빠른 속도를 보입니다.

    큐의 삽입과 삭제는 각각 큐의 끝단에서 이루어지기 때문에, 중간에 위치한 데이터를 삭제할 수 없습니다. 이것은 배열과 같은 다른 자료 구조와 다릅니다.

    배열의 경우, 중간에 있는 데이터를 삭제하려면 삭제한 원소 이후의 모든 데이터를 한 칸씩 앞으로 이동시켜야 합니다. 이 때문에 중간에 위치한 데이터를 삭제한다면, 이후의 배열을 복사하고 다시 순회하며 데이터를 삽입하는 과정을 거쳐야 합니다. 삭제한 원소 뒤에 새로운 데이터를 삽입하려면 빈자리를 만들기 위해 이후의 원소들을 한 칸씩 뒤로 밀어야 하므로 삽입할 때도 전체 배열을 순회해야 합니다.

    반면 큐에 데이터를 삽입할 때에는 큐의 끝단에서 새로운 데이터를 추가하는 것으로 끝나며, 데이터를 삭제할 때는 큐의 첫 번째 데이터를 삭제하는 것으로 끝납니다. 따라서, 큐에서 요소를 삽입하거나 삭제할 시 단 한 번의 실행만으로 처리할 수 있습니다.

    이러한 이유로 큐는 삽입과 삭제가 빈번하게 일어나는 상황에서 상대적으로 빠른 속도를 보이며, 데이터나 작업을 차례대로 처리해야 하는 상황에서 효과적으로 사용될 수 있습니다.

Queue 자료 구조의 한계

큐는 데이터를 가장 먼저 추가한 위치에서부터 차례로 데이터를 처리하며, 가장 나중에 추가된 위치에서 새로운 데이터를 추가합니다. 이러한 구조 때문에 큐는 특정 위치의 데이터를 조회하거나 수정하는 상황에는 적합하지 않습니다.

Queue의 실제 사용 사례

컴퓨터 장치들 사이에서 데이터를 주고받을 때, 각 장치 사이에 존재하는 속도의 차이나 시간 차이를 극복하기 위해 임시 저장소로서 큐를 사용합니다. 이를 버퍼(buffer) 라고 합니다. 아래 이미지는 버퍼링(buffering) 의 개념을 보여주고 있습니다.

대부분의 컴퓨터 장치에서 발생하는 이벤트는 불규칙적으로 발생합니다. 반면, CPU와 같이 발생한 이벤트를 처리하는 장치는 일정한 처리 속도를 갖습니다. 불규칙적으로 발생한 이벤트를 규칙적으로 처리하기 위해 버퍼(buffer)를 사용합니다.

큐의 기본 동작

큐는 일렬로 나열된 데이터를 가지며, Rear(뒷부분)는 새로운 요소가 삽입되는 위치를, Front(앞부분)는 요소가 제거되는 위치를 나타냅니다.

Enqueue()

  • 새로운 요소를 큐의 가장 뒷부분(rear)에 추가합니다.
  • 큐가 가득 차 있는 경우, 해당 작업은 실패하게 됩니다.
def enqueue(queue, item):
    queue.insert(0, item)

# 사용 예
queue = []
enqueue(queue, "apple")
enqueue(queue, "banana")
enqueue(queue, "cherry")
print(queue)  # ['cherry', 'banana', 'apple']

# 리스트를 활용했을 경우
queue = []

queue.insert(0, 1)
queue.insert(0, 2)
queue.insert(0, 3)

print(queue) # [3, 2, 1]

Dequeue()

  • 큐의 제일 앞부분(front)에 위치한 요소를 제거하고 반환합니다.
  • 큐가 비어있는 경우, 해당 작업은 실패하게 됩니다.
def dequeue(queue):
    if not queue:
        return "Queue is empty."
    else:
        return queue.pop(0)

# 사용 예
queue = ["apple", "banana", "cherry"]
print(dequeue(queue))  # 'apple'
print(queue)  # ['banana', 'cherry']

# 리스트를 활용했을 경우
queue = [1, 2, 3]

queue.pop(0)
print(queue) # [2, 3]

queue.pop(0)
print(queue) # [3]

Peek()

  • 큐의 앞부분(front)에 위치한 요소를 반환합니다.
  • 조회 연산을 수행하더라도 큐에서 요소가 제거되지 않습니다.
  • 큐의 가장 앞(front)에 위치한 요소를 확인할 수 있습니다.
def peek(queue):
    if not queue:
        return "Queue is empty."
    else:
        return queue[0]

# 사용 예
queue = ["apple", "banana", "cherry"]
print(peek(queue))  # 'apple'

# 리스트를 활용했을 경우
queue = [1, 2, 3]

peek = queue[0]
print(peek) # 1

queue.pop(0)

peek = queue[0]
print(peek) # 2

IsEmpty

  • 큐가 비어있는지 확인하는 작업입니다.
  • 큐가 비어있으면 true를 반환하고, 비어있지 않으면 false를 반환합니다.
  • 큐가 비어있는지 여부를 확인하여 추가적인 조치를 취할 수 있습니다.
def isEmpty(queue):
    return len(queue) == 0

# 사용 예
queue = ["apple", "banana", "cherry"]
print(isEmpty(queue))  # False
queue = []
print(isEmpty(queue))  # True

# 리스트만 활용했을 경우
queue = [1, 2, 3]
isEmpty = False;

if len(stack) == 0:
		isEmpty = True
else:
		isEmpty = False

print(isEmpty) # False

큐의 시간 복잡도와 공간 복잡도

큐의 시간복잡도(Time Complexity)

  • Enqueue(삽입)

    연산: O(1)

    • 큐의 맨 뒤(rear)에 데이터를 삽입하는 연산입니다.
    • 배열을 사용한 구현에서는 데이터를 삽입할 위치를 기억하는 변수(rear)를 증가시키는 것으로 수행됩니다.
    • 연결 리스트를 사용한 구현에서는 리스트의 맨 뒤에 노드를 추가하는 연산으로 수행됩니다.
    • 어떤 경우에도 데이터를 삽입하는 데에는 상수 시간이 소요됩니다.

  • Dequeue(삭제)

    연산: O(1)

    • 큐의 맨 앞(front)에서 데이터를 제거하는 연산입니다.
    • 배열을 사용한 구현에서는 데이터를 제거할 위치를 기억하는 변수(front)를 1 증가시키는 것으로 수행됩니다.
    • 연결 리스트를 사용한 구현에서는 리스트의 맨 앞에서 노드를 제거하는 연산으로 수행됩니다.
    • 어떤 상황에서도 데이터를 제거하는 데에는 상수 시간이 소요됩니다.

  • Peek(조회)

    연산: O(1)

    • 큐의 맨 앞(front)에서 데이터를 조회하는 연산입니다.
    • 배열이나 연결 리스트에서는 맨 앞의 데이터에 접근하는 것이 간단하므로 상수 시간에 수행됩니다.
    • 데이터를 제거하지 않고 조회하는 연산이므로 큐의 크기에 영향을 주지 않습니다.

큐의 공간복잡도(Space Complexity)

  • 큐의 공간 복잡도는 큐에 저장되는 데이터의 개수에 비례합니다.
  • 배열을 사용한 구현에서는 배열 혹은 리스트의 크기가 큐의 최대 크기를 결정하므로 O(N)입니다. (N은 큐에 저장되는 데이터의 개수)
  • 연결 리스트를 사용한 구현에서는 필요한 만큼의 노드를 동적으로 생성하므로 실제 데이터 개수에 따라 공간이 사용됩니다. 따라서 최대 O(N)입니다.

스택과 큐의 비교

스택과 큐의 공통점

스택과 큐 모두 선형 자료구조로, 순차적으로 데이터를 저장하고 조작합니다. 둘 다 데이터의 추가와 제거를 통해 동작하며, 데이터를 임시로 저장하는 데 사용되는 경우가 많습니다.

스택과 큐의 차이점

스택과 큐의 주요 차이점은 데이터의 추가와 제거 방식입니다. 스택에서는 데이터의 추가와 제거가 같은 곳에서 이루어지는 반면, 큐에서는 데이터의 추가가 한 쪽 끝에서, 제거가 반대 쪽 끝에서 이루어집니다.

업데이트:

댓글남기기

참고