1. Queue

큐의 개념

• 일반적인 의미: 기다리는 줄, 대기열
• 자료구조에서의 의미: 자료 대기열 + FIFO(동적인 특징)
• FIFO(First-In-First-Out): 선입선출 방식을 말한다.

이미지 출처

큐 추상 자료형

• 큐 생성: 큐를 생성한다.
  • 큐의 크기 n 필요 (배열로 큐를 구현하는 경우)
• enqueue: 새로운 자료를 추가하는 연산
  • 큐가 가득 차 있는지 여부를 확인해야 한다.
  • (넘침(Overflow) 현상을 주의해야 한다.)
• dequeue: 가장 먼저 들어온 자료를 제거하는 연산
  • 큐가 비어있는지 여부를 확인해야 한다.
  • (부족(Underflow) 현상을 조심해야 한다.)
• peek: 가장 먼저 들어온 자료를 읽은 후 이를 반환하는 연산 (제거 x)
  • 큐가 비어있는지 여부를 확인해야 한다.
  • (부족(Underflow) 현상을 조심해야 한다.)
• 큐 삭제: 큐를 삭제한다.

사용 예

• 데이터를 입력된 순서대로 처리할 때 (콜센터 대기 순서)
• 프로세스 관리
• BFS(너비 우선 탐색) 알고리즘

파이썬 리스트로 큐 구현

구현

# 파이썬의 리스트(list)를 이용하여 큐를 구현

class Queue:
    # 빈 리스트로 큐 생성
    def __init__(self):
        self.data = []

    # 큐 크기 반환
    def __len__(self):
        return len(self.data)

    # 큐의 내부 자료를 문자열로 변환하여 반환
    def __str__(self):
        return str(self.data[::1])

    # 큐가 비어있는지 체크
    def is_empty(self):
        return len(self.data) == 0

    # 큐에 새로운 자료 추가
    def enqueue(self, item):
        self.data.append(item)

    # 큐의 첫 번째 자료 제거
    def dequeue(self):
        # 큐가 비어있는지 반드시 체크
        if self.is_empty():
            print("Queue Underflow")
            exit()

        # 비어있지 않으면 첫 번째 자료를 제거 후 반환
        return self.data.pop(0)

    # 큐의 최상위 자료 읽기(제거 x)
    def peek(self):
        # 큐가 비어있는지 반드시 체크
        if self.is_empty():
            print("Queue Underflow")
            exit()

        # 비어있지 않으면 첫 번째 자료를 읽은 후 반환
        return self.data[0]

    # 큐에 자료가 포함되어 있는지 여부 반환
    def contains(self, item):
        return item in self.data

    # 큐 초기화
    def clear(self):
        self.data = []

실행

# 큐 생성
queue = Queue()

# 큐 크기 출력
# 0
print(len(queue))

# 큐 비어있는지 여부 출력
# True
print(queue.is_empty())

# 큐에 자료 추가
queue.enqueue(1)
queue.enqueue(2)

# 큐 출력
# [1, 2]
print(queue)

# 큐에 자료 포함되어 있는지 여부 출력
# False
print(queue.contains(3))

# 첫 번째 자료 제거
queue.dequeue()

# 큐 출력
# [2]
print(queue)

# 첫 번째 자료 읽기
# 2
print(queue.peek())

# 큐 클리어
queue.clear()

# 큐 비어있는지 여부 한 번 더 확인
# True
print(queue.is_empty())

한계 및 보완

• 배열로 선형 큐를 구현하면 Dequeue 할 때마다 앞의 공간이 비게 된다(앞에서 빠져나가므로). 이를 채우기 위해 데이터를 계속 앞으로 이동시키는 것도 문제다(불필요한 데이터 이동과 함께 처리 속도가 느려짐)

• 다른 문제로, 시작 부분(front)과 끝 부분(rear) 포인터를 이용하는 경우, rear가 맨 끝을 가리킬 때 큐가 다 차지 않았는데도 가득 차 있다고 인식해 새로운 원소를 추가하지 못한다.
  

  이미지 출처

• 선형 큐의 문제를 보완하기 위해 원형 큐를 사용한다.

큐와 스택 구현 비교

이미지 출처

자료구조	동작	코드	설명
큐	초기화	queue = []	빈 리스트를 만듦
	자료 추가(enqueue)	queue.append(data)	리스트의 맨 뒤에 자료를 추가
	자료 삭제(dequeue)	data = queue.pop(0)	리스트의 맨 앞(0번 위치)에서 자료를 꺼냄
스택	초기화	stack = []	빈 리스트를 만듦
	자료 추가(push)	stack.append(data)	리스트의 맨 뒤에 자료를 추가
	자료 삭제(pop)	data = stack.pop()	리스트의 맨 뒤에서 자료를 꺼냄

스택에 대한 이해

2. 덱(Deque)

특징

• Doubled-ended queue
• 즉, 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료 구조
• 두 개의 포인터를 사용하여, 양쪽에서 삭제 또는 삽입이 가능하다.
• 큐(FIFO)와 스택(LIFO)을 합친 형태라고 볼 수 있다.

이미지 출처

이미지 출처

• Scroll(입력제한데크) : 입력이 한쪽 끝으로만 가능하도록 설정한 데크
  

  이미지 출처

• Shelf(출력제한데크) : 출력이 한쪽 끝으로만 가능하도록 설정한 데크
  

  이미지 출처

실행

from collections import deque

# 덱 생성
dq = deque()

# 덱의 끝 부분에 자료 추가
dq.append(1)
dq.append(2)
dq.append(3)
dq.append(4)

# 덱 출력
# deque([1, 2, 3, 4])
print(dq)

# 덱 크기 출력
# 4
print(len(dq))

# 가장 늦게 들어온 자료 삭제
dq.pop()

# 덱 출력
# deque([1, 2, 3])
print(dq)

# 가장 먼저 들어온 자료 삭제
dq.popleft()

# 덱 출력
# deque([2, 3])
print(dq)

# 덱의 앞 부분에 자료 추가
dq.appendleft(9)

# 덱 출력
# deque([9, 2, 3])
print(dq)

# 덱 클리어
dq.clear()

# 덱 출력
# deque([])
print(dq)

3. 원형 큐(Circular Queue)

특징

선형 큐와 유사하지만 복습하는 의미로 원형 큐의 요소를 간단히 살펴보면,

• 원형 큐(또는 버퍼)에 size를 지정해준다. (size 안에서 순환이 일어나기 때문)
• front: 원형 큐의 시작 head
• rear: 원형 큐의 마지막 tail
• enqueue: 큐에 새로운 자료를 추가하는 연산
• dequeue: 큐에서 먼저 들어온 자료를 제거하는 연산
• overflow: 큐가 가득 차 있을 때
• underflow: 큐가 비어 있을 때
  

  이미지 출처

Ref

• [자료구조] #18 5장 - 큐의 개념/큐 추상 자료형 - 이상진의 자료구조
• 모두의 알고리즘 with 파이썬, 이승찬님