Chapter 02. 큐

02-1 큐란?

큐(queue)

가장 먼저 들어간 자료가 가장 먼저 나오는 자료구조

선입선출(FIFO: First-In First-Out)

 

큐는 삽입과 삭제 연산이 같은 쪽이 아니라 서로 다른 쪽에서 일어남

삽입이 일어나는 곳을 후단(rear)이라 하고 삭제가 일어나는 곳을 전단(front)이라 부름

 

큐는 빠른 CPU와 속도가 상대적으로 느린 주변장치들 사이의 시간이나 속도 차이를 극복하기 위한 임시 기억 장치(버퍼(buffer))로 사용됨

 

큐의 연산

• enqueue(e): 새로운 요소 e를 큐의 맨 뒤에 추가
• dequeue(): 큐의 맨 앞에 있는 요소를 꺼내서 반환
• isEmpty(): 큐가 비어 있으면 True를, 아니면 False를 반환
• isFull(): 큐가 가득 차 있으면 True를, 아니면 False를 반환
• peek(): 큐의 맨 앞에 있는 요소를 삭제하지 않고 반환
• size(): 큐에 들어 있는 전체 요소의 수를 반환

포화 상태인 큐에 enqueue() 연산을 실행하는 경우 → 오버플로(overflow) 오류

공백인 큐에서 dequeue()나 peek() 연산을 실행하는 경우 → 언더플로(underflow) 오류

---

02-2 배열로 구현하는 큐

큐도 배열 구조와 연결된 구조로 구현할 수 있음

 

배열 구조의 큐를 위한 데이터

• array[]: 큐 요소들을 저장할 배열
• capacity: 큐에 저장할 수 있는 요소의 최대 개수
• rear: 맨 마지막(후단) 요소의 위치(인덱스)
• front: 첫 번째(전단) 요소 바로 이전의 위치(인덱스)

스택과 달리 삽입과 삭제가 다른 쪽에서 이루어지기 때문에 큐는 두 개의 변수가 필요

front는 큐의 첫 번째 요소가 아니라 그 요소 바로 앞의 위치를 가리킴 (front를 다르게 정의해도 됨)

 

선형 큐의 문제점과 원형 큐의 원리

용량이 5인 큐에 5개의 요소(A~E)를 삽입하고 두 번의 삭제를 순서대로 수행했다고 가정

C

D

E

 

→ F를 삽입하려면 문제 발생

큐의 앞부분에 공간이 있으나 rear를 더 증가시킬 수 없으므로 새로운 요소를 후단에 삽입할 수 없음

 

→ 큐의 요소들을 모두 최대한 앞으로 옮겨 후단에 공간을 확보한 다음 삽입해야 함

: 선형 큐(linear queue)

(요소들의 이동이 필요하므로 효율적이지 않음)

 

 

원형 큐(circular queue)

: 배열을 선형이 아닌 원형으로 생각 

실제로 배열이 원형이 되는 것이 아니라 인덱스 front와 rear를 원형으로 회전시키는 개념

 

• 전단 회전: front ← (front+1) % capacity
• 후단 회전: rear ← (rear+1) % capacity

front와 rear가 계속 증가하다가 용량과 같아지면 다시 0으로 만들어줌

 

원형 큐의 클래스 구현

클래스의 선언과 멤버변수 초기화

배열 구조를 이용한 원형 큐 클래스 선언, 생성자에서 멤버변수 선언, 초기화

class ArrayQueue:
    def __init__(self, capacity=10):    # 생성자 정의
        self.capacity = capacity    # 용량(고정)
        self.array = [None] * capacity  # 요소들을 저장할 배열
        self.front = 0  # 전단 인덱스
        self.rear = 0   # 후단 인덱스

 

공백 상태와 포화 상태를 검사하는 isEmpty()와 isFull() 연산

공백 상태: front == rear

포화 상태: front == (rear+1) % capacity (front가 rear의 바로 다음에 있는 경우)

(front==rear를 포화 상태로 할 경우 공백 상태와 구분이 되지 않으므로 원형 큐에서는 보통 하나의 자리를 비워둠)

    def isEmpty(self):
        return self.front == self.rear
    
    def isFull(self):
        return self.front == (self.rear + 1) % self.capacity

 

새로운 요소 e를 삽입하는 enqueue(e) 연산

    def enqueue(self, item):    # 삽입 연산
        if not self.isFull():   # 포화 상태가 아닌 경우
            self.rear = (self.rear + 1) % self.capacity
            self.array[self.rear] = item
        else: pass

 

맨 앞의 요소를 삭제하는 dequeue() 연산

    def dequeue(self):
        if not self.isEmpty():
            self.front = (self.front + 1) % self.capacity
            return self.array[self.front]
        else: pass

 

맨 앞의 요소를 들여다보는 peek() 연산

    def peek(self):
        if not self.isEmpty():
            return self.array[(self.front + 1) % self.capacity]
        else: pass

 

전체 요소의 수를 구하는 size() 연산

    def size(self):
        return (self.rear - self.front + self.capacity) % self.capacity

rear-front로 요소의 수를 계산, 음수 값이 될 수도 있기에 추가로 용량을 더해 양수로 만듦

 

큐의 내용을 출력하는 display() 연산

큐에 저장된 모든 요소를 큐에 들어온 순서대로 출력하는 연산

    def display(self, msg):
        print(msg, end='= [ ')
        for i in range(self.front+1, self.front+1+self.size()):
            print(self.array[i%self.capacity], end=' ')
        print("]")

맨 앞의 요소는 front+1에 위치, 출력할 요소의 수는 size()개

인덱스는 시계 방향으로 회전되어야 하므로 나머지 연산%를 적용

 

큐의 활용

import random
q = ArrayQueue(8)

q.display("초기 상태")
while not q.isFull():
    q.enqueue(random.randint(0,100))
q.display("포화 상태")

print("삭제 순서: ", end='')
while not q.isEmpty():
    print(q.dequeue(), end=' ')
print()

 

원형 큐를 링 버퍼로 사용하기

링 버퍼(ring buffer): 오래된 자료를 버리고 항상 최근의 자료를 유지하는 용도로 사용하는 원형 큐

가장 오래된 데이터를 삭제해서 큐를 계속 포화 상태로 유지

    def enqueue2(self, item):
        self.rear = (self.rear + 1) % self.capacity
        self.array[self.rear] = item
        if self.isEmpty(): # front==rear
            self.front = (self.front + 1) % self.capacity

 

삽입 후가 공백이면 front==rear → 포화 상태에서 새로운 데이터를 삽입한 상태

front를 회전시켜 가장 오래된 요소를 삭제

 

링 버퍼의 테스트 프로그램

q = ArrayQueue_Ring(8)

q.display("초기 상태")
for i in range(6):
    q.enqueue2(i)
q.display("삽입 0-5")

q.enqueue2(6); q.enqueue2(7)
q.display("삽입 6, 7")

q.enqueue2(8); q.enqueue2(9)
q.display("삽입 8, 9")

q.dequeue(); q.dequeue()
q.display("삭제 x2")

 

 

02-3 덱이란?

덱(deque): double-ended queue의 줄임말, 전단과 후단에서 모두 삽입과 삭제가 가능한 큐

 

덱의 연산

• addFront(e): 새로운 요소 e를 전단에 추가
• addRear(e): 새로운 요소 e를 후단에 추가
• deleteFront(): 덱의 전단 요소를 꺼내서 반환
• deleteRear(): 덱의 후단 요소를 꺼내서 반환
• getFront(): 덱의 전단 요소를 삭제하지 않고 반환
• getRear(): 덱의 후단 요소를 삭제하지 않고 반환
• isEmpty(): 덱이 비어있으면 True를 아니면 False를 반환
• isFull(): 덱이 가득 차 있으면 True를 아니면 False를 반환
• size(): 덱에 들어 있는 전체 요소의 수를 반환

덱의 구현도 원형 덱(circular deque)으로 구현하는 것이 좋음

 

deleteRear, addFront 연산 주의

→ enqueue와 dequeue 연산과는 달리 인덱스를 하나씩 줄여야 함 (반시계 방향 회전)

• 전단 회전(반시계 방향): front ← (front-1+capacity) % capacity
• 후단 회전(반시계 방향): rear ← (rear-1+capacity) % capacity

 

 

02-4 상속을 이용한 덱의 구현

앞에서 구현한 원형 큐 클래스를 상속(inheritance)하여 원형 덱 클래스 구현

 

새로 추가되는 연산은 addFront, getRear, deleteRear 뿐

→ 상속으로 기존 클래스에 기능을 추가한 새로운 클래스를 만들어 코드를 짧고 간결하게 구현

 

원형 큐를 상속하여 구현하는 원형 덱 클래스

클래스의 상속과 멤버변수 초기화

class CircularDeque(ArrayQueue_Ring):    # ArrayQueue_Ring: 부모 클래스 / CircularDeque: 자식 클래스
    def __init__(self, capacity=10):    # 생성자는 상속되지 않으므로 다시 구현해야 함
        super().__init__(capacity)  # 부모의 생성자를 호출하여 부모 클래스의 데이터 초기화

ArrayQueue_Ring: 부모 클래스 / CircularDeque: 자식 클래스

super(): 자식 클래스의 메서드에서 부모를 부르는 함수

생성자는 상속되지 않음

 

isEmpty(), isFull(), size(), display() 연산

부모 클래스에서 구현된 것을 그대로 사용

추가적인 코드가 전혀 필요 없이 바로 사용할 수 있음

 

addRear(e), deleteFront(), getFront() 연산

원형 큐의 enqueue, dequeue, peek와 같은 동작을 하지만 이름이 다르기에

자식 클래스에 멤버함수로 추가하고, 이미 구현된 부모 클래스의 해당 연산을 호출

    def addRear(self, item): self.enqueue2(item)
    def deleteFront(self): return self.dequeue()
    def getFront(self): return self.peek()

deleteFront와 getFront는 전단 요소를 반환해야 하므로 결과를 return

 

addFront(e), deleteRear(), getRear() 연산

    def addFront(self, item):
        if not self.isFull():   # 포화 상태가 아닐 경우
            self.array[self.front] = item   # front에 요소 삽입입
            self.front = (self.front-1+self.capacity) % self.capacity   # front를 반시계 방향으로 회전
        else: pass

    def deleteRear(self):
        if not self.isEmpty():  # 공백 상태가 아닐 경우
            item = self.array[self.rear]    # rear 요소 복사해둠
            self.rear = (self.rear-1+self.capacity) % self.capacity # rear를 반시계 방향으로 회전
            return item # 복사해둔 요소 반환
        else: pass

    def getRear(self):
        if not self.isEmpty():  # 공백 상태가 아닐 경우
            return self.array[self.rear]    # rear 요소 반환
        else: pass

 

원형 덱의 활용

dq = CircularDeque()

for i in range(9):
    if i%2==0: dq.addRear(i)
    else: dq.addFront(i)
dq.display("홀수는 전단 짝수는 후단 삽입")

for i in range(2): dq.deleteFront()
for i in range(3): dq.deleteRear()
dq.display("전단 삭제 2번, 후단 삭제 3번")

for i in range(9, 14): dq.addFront(i)
dq.display("전단에 9~13 삽입")

 

 

02-5 파이썬에서 큐와 덱 사용하기

파이썬에서 제공하는 모듈 사용

queue 모듈의 Queue 사용하기

import queue	# 파이썬의 queue 모듈 포함
q = queue.Queue(maxsize=20)	# 큐 객체 생성(최대크기 20)

maxsize: 큐의 용량 / maxsize가 0이면 용량의 제한이 없는 큐 객체

연산	ArrayQueue	queue.Queue
삽입/삭제	enqueue(), dequeue()	put(), get()
공백/포화 상태 검사	isEmpty(), isFull()	empty(), full()
전단 들여다보기	peek()	제공하지 않음

 

collections 모듈의 deque 클래스 사용하기

collections 모듈에서 내장 자료형인 튜플리안 딕셔너리에 대한 확장 데이터 구조들을 제공

import collections	# 파이썬의 collections 모듈 포함
dq = collections.deque() # 용량이 무한대인 덱 객체 생성

연산	CircularDeque	collections.deque
전단 삽입/삭제	addFront(), deleteFront()	appendleft(), popleft()
후단 삽입/삭제	addRear(), deleteRear()	append(), pop()
공백 상태 검사	isEmpty()	dq (예: if dq : …)
포화 상태 검사	isFull()	의미 없음
들여다보기	getFront(), getRear()	제공하지 않음

 

collections.dequeue 에서는 전단(front) 대신 좌단(left) 사용