Queues

Queues

---

스택과 더불어 매우 빈번히 이용되는 자료구조 큐에 대해 공부해보자.

큐 또한 데이터 원소를 한 줄로 늘어세우는 자료구조, 즉 선형 자료구조라는 측면에서는 선형 배열, 연결 리스트, 스택과 마찬가지이지만 다른 특성을 가지고 있다.

스택에서는 어느 시점에서 스택에 들어있는 데이터 원소를 꺼낼 경우, 가장 최근에 넣었던 원소, 즉 스택 최상단에 자리잡고 있는 원소가 꺼내진다. 이러한 특징을 우리는 후입선출 (LIFO)이라고 앞서 공부한 바 있다.

큐에서는 스택과는 반대로, 어느 시점에서 큐에 들어있는 데이터 원소를 꺼내면 큐에 들어있는 원소 중 가장 먼저 넣었던 것이 꺼내진다. 따라서 큐를 선입선출 (FIFO)이라고도 부른다.

데이터 원소를 큐에 넣는 동작을 인큐 (enqueue)연산이라고 부르며, 반대로 큐로부터 데이터 원소를 꺼내는 동작을 디큐(dequeue)연산이라고 부른다. 이 두가지 핵심 연산을 포함한 큐의 추상적 자료구조를 공부해본다.

큐는 한 쪽 끝에서 반대쪽 끝에서 뽑아내기 때문에 선입선출 특징을 가지는 선형 자료구조다.

큐의 추상적 자료구조 구현

(1) 배열을 이용하여 구현

Python 리스트와 메서드들을 이용

(2) 연결 리스트 (linked list)를 이용하여 구현

양방향 연결 리스트 이용

연산의 정의

size() - 현재 큐에 들어 있는 데이터 원소의 수

isEmpty() - 현재 큐가 비어 있는지를 판단

enqueue(x) - 데이터 원소 x를 큐에 추가

dequeue() - 큐의 맨 앞에 저장된 데이터 원소를 제거 또는 반환

peek() - 큐의 맨 앞에 저장된 데이터 원소를 반환 (제거하지는 않음)

# 배열로 구현한 큐

class ArrayQueue:

  def __init__(self):                    # 빈 큐 초기화, constructor method
    self.data = []

  def size(self):                            # 큐의 크기 리턴
    return len(self.data)

  def isEmpty(self):                    # 큐가 비어있는지 판단
    return size(self) == 0

  def enqueue(self, item):        # 현재 리스트 맨 끝에 데이터 원소 추가
    self.data.append(item)

  def dequeue(self):                    # 0번 idx, 즉 제일 앞 원소 삭제 및 반환
    return self.data.pop(0)

     def peek(self):                            # 0번 idx, 즉 제일 앞 원소 반환
    return self.data[0]

배열로 구현한 큐의 연산 복잡도

연산	복잡도
size()	$O(1)$
isEmpty()	$O(1)$
enqueue()	$O(1)$
dequeue()	$O(n)$
peek()	$O(1)$

dequeue()의 경우, 큐의 길이에 비례하는 복잡도를 갖는다.

왜냐하면, dequeue() 연산은 배열의 맨 앞 원소를 꺼내야 한다.

맨앞에 원소를 꺼내서 없앤다면 그 뒤에 있는 원소들을 한칸씩 앞으로 이동해야 하기 때문이다.