[수업기록] 알고리즘 : queue

240813

 

1. 큐의 특성

- 스택과 마찬가지로 삽입과 삭제의 위치가 제한적인 자료구조

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

- 큐의 예 : 서비스 대기행렬 

- 큐의 선입선출 구조 : 머리(front : 저장된 원소 중 가장 첫번째 원소 또는 삭제된 위치), 꼬리(rear : 저장된 원소 중 마지막 원소)

 

2. 큐의 기본 연산

- enQueue(item) : 큐 뒤쪽에 원소를 삽입하는 연산

- deQueue() : 큐 앞쪽 원소를 삭제하는 연산

- isEmpty() : 큐가 공백상태인가 확인

- isFull() : 큐가 포화상태인가 확인(rear == len(q)-1)

- createQueue() : 공백 큐 생성

-> 하지만 파이썬은 리스트라는 자료구조가 있어서 리스트로 쉽게 표현이 가능하다

 

3. 큐의 구현

- 선형큐 : 1차원 배열을 이용한 큐 

- 큐의 크기 = 배열의 크기

N = 10

q = [0] * 10
front = -1
rear = -1

rear += 1  # enqueue(1)
q[rear] = 1

rear += 1 # enqueue(2)
q[rear] = 2

rear += 1  # enqueue(3)
q[rear] = 3

front += 1 # dequeue()
print(q[front])

front += 1 # dequeue()
print(q[front])

front += 1 # dequeue()
print(q[front])

 

4. 연습문제

세개의 데이터 1,2,3을 차례로 큐에 삽입 후 하나씩 출력해본다.

- 방법 두가지 : 

- 빈 리스트 : append(), pop(0),

- 크기가 정해진 리스트 : front = rear = -1, front += 1, rear += 1

 

5. 선형 큐 단점 

- 잘못된 포화상태 인식

-> 원형 큐 활용 : 1차원 배열을 사용하되 논리적으로 배열의 처음과 끝이 연결되어 원형 형태의 큐를 이룬다고 가정

 

6. 원형 큐 구조

- front 변수 : 공백 상태와 포화 상태 구분을 쉽게 하기위해 front가 있는 자리는 사용하지 않고 항상 빈자리로 둠

---

7. deque(덱)

- 파이썬으로 que 자료구조를 구현할 때 deque를 사용함

- deque 객체는 양쪽 끝에서 빠르게 추가와 삭제를 할 수 있는 리스트류 트레이너

- 삽입 및 삭제시 시간복잡도 O(1) 

- 단점은 인덱스 슬라이싱이 불가(인덱스로 값 참조는 가능)

from collections import deque

q= deque() 
q.append(1) #enqueue()
t = q.popleft() #dequeue() #pop(0)

 

#%%
from collections import deque

# deque 생성
# 생성: O(k), k는 초기화에 사용된 이터러블의 길이
d = deque([1, 2, 3, 4, 5])
print("초기 deque:", d)
#초기 deque: deque([1, 2, 3, 4, 5])

# 오른쪽에 요소 추가
# append: O(1)
d.append(6)
print("append(6) 후:", d)
#append(6) 후: deque([1, 2, 3, 4, 5, 6])

# 왼쪽에 요소 추가
# appendleft: O(1)
d.appendleft(0)
print("appendleft(0) 후:", d)
#appendleft(0) 후: deque([0, 1, 2, 3, 4, 5, 6])  

# 오른쪽에서 요소 제거 및 반환
# pop: O(1)
popped = d.pop()
print("pop() 후:", d, "제거된 요소:", popped)
#pop() 후: deque([0, 1, 2, 3, 4, 5]) 제거된 요소: 6 

# 왼쪽에서 요소 제거 및 반환
# popleft: O(1)
popped_left = d.popleft()
print("popleft() 후:", d, "제거된 요소:", popped_left)
#popleft() 후: deque([1, 2, 3, 4, 5]) 제거된 요소: 0

# 특정 요소의 개수 세기
# count: O(n), n은 deque의 길이
count = d.count(3)
print("3의 개수:", count) #3의 개수: 1

# deque 회전 (양수: 오른쪽으로, 음수: 왼쪽으로)
# rotate: O(k), k는 회전하는 위치의 수.
d.rotate(2)
print("rotate(2) 후:", d) #rotate(2) 후: deque([4, 5, 1, 2, 3])
d.rotate(-2)
print("rotate(-2) 후:", d) #rotate(-2) 후: deque([1, 2, 3, 4, 5])

# 특정 요소의 인덱스 찾기
# index: O(n)
index = d.index(4)
print("4의 인덱스:", index) #4의 인덱스: 3

# deque 확장 (오른쪽)
# extend: O(k), k는 추가되는 이터러블의 길이
d.extend([7, 8, 9])
print("extend([7, 8, 9]) 후:", d)
#extend([7, 8, 9]) 후: deque([1, 2, 3, 4, 5, 7, 8, 9])

# deque 확장 (왼쪽)
# extend: O(k), k는 추가되는 이터러블의 길이
d.extendleft([-2, -1, 0])
print("extendleft([-2, -1, 0]) 후:", d)
#extendleft([-2, -1, 0]) 후: deque([0, -1, -2, 1, 2, 3, 4, 5, 7, 8, 9])

# deque 뒤집기
# reverse: O(n)
d.reverse()
print("reverse() 후:", d) 
#reverse() 후: deque([9, 8, 7, 5, 4, 3, 2, 1, -2, -1, 0])

# deque 내용 지우기
# clear: O(n)
d.clear()
print("clear() 후:", d) #clear() 후: deque([])

# 최대 길이 제한 deque 생성
limited_deque = deque(maxlen=3)
limited_deque.extend([1, 2, 3, 4, 5])
limited_deque.append(6)
print("최대 길이가 3인 deque:", limited_deque)
#최대 길이가 3인 deque: deque([4, 5, 6], maxlen=3)

---

8. 우선순위 큐 

- FIFO 순서가 아니라 우선순위가 높은 순서대로 먼저 나가게 됨

 

- 배열을 이용한 우선순위 큐 :

- 배열을 이용하여 자료 저장, 원소를 삽입하는 과정에서 우선순위를 비교하여 적절한 위치에 삽입

- 가장 앞에 최고 우선순위의 원소가 위치

- 문제점 : 배열을 사용하므로 삽입이나 삭제 연산이 일어날 때 원소의 재배치가 일어남 -> 메모리 낭비

 

9. 큐의 활용 : 버퍼(Buffer)

- 데이터를 한곳에서 다른 한 곳으로 전송하는 동안 일시적으로 그 데이터를 보관하는 메모리 영역

- 버퍼는 순서대로 입력/출력/전달되어야해서 FIFO 방식의 자료구조인 큐가 활용됨