[자료구조와 알고리즘 with 파이썬] 02 큐

02-1 큐란?
02-2 배열로 구현하는 큐
02-3 덱이란?
02-4 상속을 이용한 덱의 구현
02-5 파이썬에서 큐와 덱 사용하기

---

02-1 큐란?

큐(queue)

• 가장 먼저 들어간 자료가 가장 먼저 나오는 자료구조
• 선입선출(FIFO: First-In First-Out)
• 후단(rear): 삽입이 일어나는 곳
• 전단(front): 삭제가 일어나는 곳
• 예) 시간이나 속도 차이를 극복하기 위한 임시 기억 장치(버퍼(buffer))

큐의 연산

큐의 연산(* 상태를 변환시키는 연산)

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

오류 상황

1. 오버플로(overflow): 포화 상태인 큐에 enqueue() 연산을 실행하는 경우
2. 언더플로(underflow): 공백인 큐에서 dequeue()나 peek() 연산을 실행하는 경우

Quiz

1. 40, 50
2. C, D, E, B, A
3. 4
4. 3

---

02-2 배열로 구현하는 큐

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

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

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

• 선형 큐는 큐의 모든 요소들을 최대한 앞으로 옮겨 후단에 공간을 확보한 다음 삽입해야 하므로 효율적이지 못함
• 원형 큐는 인덱스 front와 rear를 원형으로 회전시키는 개념
• front나 rear가 증가하다가 용량(capacity)과 같아지면 다시 0으로 만들어주는 개념

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

원형 큐의 클래스 구현

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

class ArrayQueue:
	def __init__(self, capacity=10):
    	self.capcity = capacity
        self.array = [None] * capacity
        self.front = 0
        self.rear = 0

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

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

큐의 내용을 출력하는 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("]")

큐의 활용

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()

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

링 버퍼

• 자료들이 연속으로 들어왔을 때, 최근에 들어온 데이터만 저장하고 오래된 데이터는 버리는 원형 큐
• 가장 오래된 데이터를 삭제해서 큐를 계속 포화 상태로 유지하는 것

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

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")

Quiz

1. front == rear, front == (rear+1) % capacity
2. rear = 6, front = 8
3. 13, 14, 15, 16, 17, 18, 19, 20

---

02-3 덱이란?

덱(deque)

• 전단과 후단에서 모두 삽입과 삭제가 가능한 큐
• 중간에 삽입하거나 삭제하지는 못함

덱의 연산

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

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

Quiz

1. addRear(), deleteFront() / addFront(), deleteRear()
2. addFront(), deleteFront() / addRear(), deleteRear()

---

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

상속(inheritance)

• 불필요한 코드의 복사가 필요 없어 클래스의 전체 코드가 짧고 간결해짐

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

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

# ArrayQueue 부모 클래스, CircularDeque 자식 클래스ㅡ
class CircularDeque(ArrayQueue):
	def __init__(self, capacity=10):
    	super().__init__(capacity)

• super(): 자식클래스의 메서드에서 부모를 부르는 함수
• 생성자는 상속되지 않음

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

• 추가적인 코드 필요없이 바로 사용 가능

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

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

def addRear(self, item): self.enqueue(item)
def delete(self): return self.dequeue()
def getFront(self): return delf.peek()

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

• 덱에만 있는 기능은 자식 클래스에서 새로 구현

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
    else: pass
    
def getRear(self): 
	if not self.isEmpty():
    	return self.array[self.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 삽입")

Quiz

1. 3, 7
2. 4, 6
3. isEmpty(), isFull(), size(), display()

---

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

queue 모듈의 Queue 사용하기

import queue
q = queue.Queue(maxsize=20)

• maxsize = 0, 용량 제한이 없는 큐 객체를 만듦

  enqueue(), dequeue() = pull(), get()
  isEmpty(), isfull() = empty(), full()
  peek() = 제공하지 않음

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()

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

import collections.          
dq = collections.deque() # 용량이 무한대인 덱 객체 생성

• 스택이나 큐로도 사용 가능

• addFront(), deleteFront() = appendleft(), popleft()
• addRear(), deleteRear() = append(), pop()
• isEmpty() = dq
• isFull() = 의미 없음
• getFront(), getRear() = 제공하지 않음

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(“전단 삭제 2번, 후단 삭제 3번“, dq)

for i in range(9, 14): dq.appendleft(i)
print(“전단에 9~13 삽입         ”, dq)

print(“덱은 공백 상태 아님“ if dq else “덱은 공백 상태”)

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

Quiz

1. pull(), get()
2. 3

—-

연습문제

01

5, 3

02

def clear()
    front = rear

03

12 15 18

04

def enqueue(self, e):
    S1.append(e)

def dequeue(self):
    if len(S2)==0:
        while not len(S1)==0:
            S2.append(S1.pop())
    else: print(S2.pop())

05

def func(q, n):
    if n >= 2:
        n1 = q.dequeue()
        n2 = q.dequeue()
        q.append(n2)
        q.append(n1 + n2)