[자료구조와 알고리즘 with Python] Chapter 2 : Queue & Deque

Chapter 2 : Queue & Deque (큐와 덱)

큐는 스택과 같이 자료들을 일렬로 나열하여 저장하는 선형 자료구조다.
하지만 입출력 방식이 입구와 출구가 따로 나눠지지 않은 스택과 달리,
큐는 입구와 출구가 따로 나누어져 있고 입구로 먼저 들어간 자료가 먼저 출구로 나온다.

큐는 갑자기 데이터가 몰려드는 경우 이를 잠시 보관할 장소로 사용된다.
큐보다 입출력이 약간 더 자유로운 덱도 함께 공부할 예정이다.

01 "큐란?"

먼저 들어온 데이터가 먼저 나가는 선입선출(FIFO: First-In First-Out)의 특징을 갖는 자료구조.

시간이나 속도 차이를 극복하기 위한 임시 기억 장치(버퍼_buffer)로 사용된다.

01. 큐의 연산

삽입과 삭제가 핵심 연산

01) 삽입 - enqueue(e)

새로운 요소 e를 큐의 맨 뒤에 추가.

스택과 동일하게 포화 상태에서 enqueue() 연산을 실행하면 Overflow(오버플로) 오류가 발생한다.

02) 삭제 - dequeue()

큐의 맨 앞에 있는 요소를 꺼내어 반환.

+) peek() : 큐의 맨 앞에 있는 요소를 삭제하지 않고 반환.

스택과 동일하게 공백 상태에서 dequeue() 연산을 실행하면 Underflow(언더플로) 오류가 발생한다.

03) isEmpty(), isFull()

isEmpty() : 큐가 비어 있으면 True, 비어 있지 않으면 False 반환
isFull() : 큐가 가득 차 있으면 True, 차 있지 않으면 False 반환.

04) size()

큐에 들어 있는 전체 요소의 수를 반환.

---

02 "배열로 구현하는 큐"

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

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

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

용량이 5인 공백 상태의 선형 큐(linear queue)에서 5번의 enqueue가 발생하고 2번의 dequeue가 발생했다. 이후 추가로 enqueue를 실행하기 위해서는 후단에 모여있는 요소들을 전단으로 이동시키고 enqueue가 진행되므로 효율적이지 않다.

이러한 문제점들을 해결하기 위해 나온 방법이 원형 큐(circular queue) 이다.
실제 배열이 원형으로 되는 것이 아니라 인덱스 front와 rear를 원형으로 회전시키는 개념이다.

[front, rear 인덱스 위치]

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

03. 원형 큐의 클래스 구현

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

#코드 2.1a: 원형 큐-클래스 정의와 생성자
class ArrayQueue:
    def __init__(self, capacity = 10):
        self.capacity = capacity
        self.array = [None]*capacity
        self.front = 0
        self.rear = 0

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

front가 rear의 바로 다음에 있으면 포화 상태.

#코드 2.1b: 원형 큐-공백 상태(isEmpty)와 포화 상태(isFull) 검사 ☆
    def isEmpty(self):
        return self.front == self.rear

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

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

#코드 2.1c: 원형 큐-삽입 연산(enqueue)
    def enqueue(self, item):
        if not self.isFull():
          self.rear = (self.rear+1)%self.capacity
          self.array[self.rear]=item
        else:
            pass

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

#코드 2.1d: 원형 큐-삭제 연산(dequeue)
    def dequeue(self):
        if not self.isEmpty():
            self.front = (self.front+1)%self.capacity
            return self.array[self.front]
        else:
            pass

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

#코드 2.1e: 원형 큐-상단 들여보기 연산(peek)
    def peek(self):
        if not self.isEmpty():
            return self.array[(self.front+1)%self.capacity]
        else:
            pass

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

(rear-front)가 음수라면 추가로 용량을 더해 양수로 만들어야 한다.

#코드 2.1f: 원형 큐-전체 요소의 수(size)
    def size(self):
        return (self.rear-self.front+self.capacity)%self.capacity

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

#코드 2.1g: 원형 큐-전체 요소를 화면으로 출력(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("]")

04. 큐의 활용

#코드 2.2: 원형 큐-테스트 프로그램
import random
q = ArrayQueue(8)

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

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

> 출력
초기 상태= []
포화 상태= [75 38 20 37 38 64 30 ]
삭제 순서: 75 38 20 37 38 64 30 

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

최근에 들어온 요소들만 용량에 맞게 저장되도록 하고 오래된 데이터는 버리는 것을 "링 버퍼(ring buffer)"
가장 오래된 데이터를 삭제해서 큐를 계속 포화 상태로 유지하는 것이다.

#코드 2.3a: 원형 큐-링 버퍼를 위한 삽입 연산
    def enqueue2(self, item):
        self.rear = (self.rear+1)%self.capacity
        self.array[self.rear] = item
        if self.isEmpty():
            self.front = (self.front+1)%self.capacity

• 링 버퍼 테스트 프로그램 코드

#코드 2.3b: 링 버퍼의 테스트 프로그램
q = ArrayQueue(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")

> 출력
초기 상태= []
삽입 0-5= [0 1 2 3 4 5 ]
삽입 6, 7= [1 2 3 4 5 6 7 ]
삽입 8, 9= [3 4 5 6 7 8 9 ]
삭제 X2= [5 6 7 8 9 ]

---

03 "덱이란?"

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

덱은 스택이나 큐보다 입출력이 자유로워 연산도 몇 가지 추가된다.

01. 삽입 - addFront(e), addRear(e) ≒ enqueue(e)

새로운 요소 e를 Front는 전단에, Rear는 후단에 추가.

02. 삭제 - deleteFront(), deleteRear() ≒ dequeue()

덱의 요소 중 Front는 전단에, Rear는 후단에 있는 것을 꺼내어 반환.

+) getFront(), getRear() ≒ peek() : 덱의 전단/후단 요소를 삭제하지 않고 반환.

03. isEmpty(), isFull(), size() → 기존 큐와 동일.

04. 주의

기존 덱과 방향이 반대인 deleteRear, addFront의 연산은 반시계 방향 회전을 의미하여 주의해야한다.

[front, rear 인덱스 위치]

• deleteRear()
  : 후단 삭제 (후단 회전_반시계 방향) - rear ← (rear-1+capacity) % capacity
• addFront()
  : 전단 삽입 (전단 회전_반시계 방향) - front ← (front-1+capacity) % capacity

04 "상속을 이용한 덱의 구현"

덱에서는 원형 덱을 어떻게 구현하면 좋을까?
이럴 땐 상속(inheritance)이라는 객체지향 프로그래밍 기법을 사용하는 거이 효율적이다.

*스택에서 클래스를 이용해 구현했던 것과 동일하다. 👉🏻 chapter 1. 스택

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

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

앞에서 구현한 원형 큐 클래스 ArrayQueue를 상속하여 새로운 원형 덱 클래스 CircularDeque를 만든다.
(ArrayQueue : 부모 클래스, CircularDeque : 자식 클래스)

# 코드 2.4a: 원형 덱 - 큐를 상속한 클래스 정의
class CircularDeque(ArrayQueue):    # ArrayQueue - 부모 클래스 / CircularDeque - 자식 클래스
    def __init__(self, capacity = 10):
        super().__init__(capacity)

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

부모 클래스에서 구현이 되었기 때문에 자식 클래스에서는 추가적인 코드가 필요 없이 바로 사용할 수 있다.

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

이 연산들은 원형 큐의 enqueue, dequeue, peek과 같은 동작을 하기 때문에 자식 클래스에 멤버 함수로 추가하고, 이미 구현된 부모 클래스의 해당 연산을 호출하면 된다.

# 코드 2.4b: 원형 덱 - 동작이 동일한 연산
    def addRear(self, item):
        self.enqueue(item)
    def deleteFront(self):
        return self.dequeue()
    def getFront(self):
        return self.peek()

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

덱에만 있는 연산이므로 자식 클래스에서 새로 구현해줘야한다.

# 코드 2.4c: 원형 덱 - 추가된 연산
    def addFront(self, item):
        if not self.isFull():
            self.array[self.front] = item
            self.front = (self.front-1+self.capacity)%self.capacity
        else:
            pass

    def deleteRear(self):
        if not self.isEmpty():
            item = self.array[self.rear];
            self.rear = (self.rear-1+self.capacity)%self.capacity
            return item
        else:
            pass

    def getRear(self):
        if not self.isEmpty():
            return self.array[self.rear]
        else:
            pass

02. 원형 덱의 활용

덱 객체를 생성하고 0~8의 숫자 중에서 홀수는 전단에, 짝수는 후단에 삽입한다.
다음으로 전단에서 2번, 후단에서 3번 삭제를 하고, 마지막으로 전단에 5번 삽입한다.
해당 과정을 만든 코드를 이용하여 구현해 보자.

# 코드 2.5: 원형 덱의 테스트 프로그램
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("전단에서 두번, 후단에서 세번 삭제")

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

> 출력
홀수는 전단, 짝수는 후단 삽입= [7 5 3 1 0 2 4 6 8 ]
전단에서 두번, 후단에서 세번 삭제= [3 1 0 2 ]
전단에 5번(9~13) 삽입= [13 12 11 10 9 3 1 0 2 ]

---

05 "파이썬에서 큐와 덱 사용하기"

01. queue 모듈의 Queue 사용하기

파이썬의 queue 모듈은 스택과 함께 큐를 제공해 주는데, 큐 클래스 이름은 Queue이고 import 문으로 queue 모듈을 포함시킨 다음 사용할 수 있다.
Queue 클래스의 멤버함수 이름이 ArrayQueue와는 약간 다르고 peek()연산도 제공되지 않는 것에 유의해야 한다.

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

이제 queue 모듈을 이용해서 위의 원형 덱 활용 예제를 실행해보자.

# 코드 2.6: queue모듈의 Queue 테스트
import queue
import random

q = queue.Queue(8)

print("삽입 순서: ", end='')
while not q.full():
    v = random.randint(0,100)
    q.put(v)
    print(v, end=' ')
print()

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

> 출력
삽입 순서: 75 84 13 66 72 92 82 59 
삭제 순서: 75 84 13 66 72 92 82 59 

02. collections 모듈의 deque 사용하기

파이썬은 collections라는 모듈에서 내장 자료형인 튜플이나 딕셔너리에 대한 확장 데이터 구조들을 제공하는데, defaultdict, counter, deque, namedtuple 등 다양한 클래스를 포함하고 있다.
이 중에서 deque를 사용해보고 CircularDeque의 주요 연산은 다음과 같이 대응 된다.

연산	CircularQueue	collections.deque
전단 삽입, 삭제	addFront(), deleteFront()	appendleft(), popleft()
후단 삽입, 삭제	addRear(), deleteRear()	append(), pop()
상단 들여다보기	getFront(), getRear()	-
공백 상태 검사	isEmpty()	dq (예: if dq: ~ )
포화 상태 검사	isFull()	의미 X (무제한인 덱이 만들어지기 때문)

이제 collections 모듈을 이용해서 원형 덱 활용 예제를 실행해보자.

# 코드 2.7: collections 모듈의 deque 클래스 테스트
import collections
dq = collections.deque()

print("덱은 공백 상태 아님" if dq else "덱은 공백 상태")
for i in range(9):
    if i%2==0:
        dq.append(i)
    else:
        dq.appendleft(i)
print("홀수는 전단, 짝수는 후단 삽입   ", dq)

for i in range(2):
    dq.popleft()
for i in range(3):
    dq.pop()
print("전단에서 두번, 후단에서 세번 삭제", dq)

for i in range(9,14):
    dq.appendleft(i)
print("전단에 5번 삽입              ", dq)

print("덱은 공백 상태 아님" if dq
      else "덱은 공백 상태")
# python 3항 연산자 "참인_경우_값 if 조건신 else 거짓인_경우_값"

> 출력
덱은 공백 상태
홀수는 전단, 짝수는 후단 삽입    deque([7, 5, 3, 1, 0, 2, 4, 6, 8])
전단에서 두번, 후단에서 세번 삭제 deque([3, 1, 0, 2])
전단에 5번 삽입               deque([13, 12, 11, 10, 9, 3, 1, 0, 2])
덱은 공백 상태 아님

+) 파이썬 3항 연산자

c언어에서는 '조건식 ? (참인 경우 값) : (거짓인 경우 값)'과 같은 방법으로 3항 연산자 ? : 를 지원한다. 파이썬에서는 이러한 3항 연산자를 다음과 같이 제공한다.

(참인 경우 값) if 조건식 else (거짓인 경우 값)

따라서 print("덱은 공백 상태 아님" if dq else "덱은 공백 상태")코드에서 dq에 항목이 하나라도 있으면 즉, 공백 상태 검사 조건식에 참(True)인 경우라면 "덱은 공백 상태 아님"을 출력하고, 공백 상태라면 거짓(False)이므로 "덱은 공백 상태"를 출력하게 된다.

---

<후기>

오늘도 재밌었던 자료구조 큐와 덱 개념이었다.
앞으로 더 복합적이고 효율적인 자료구조 개념들이 기대가 된다.