Queue
- 큐(Queue) 의 특성
스택과 마찬가지로 삽입과 삭제의 위치가 제한적인 자료구조
큐의 뒤에서는 삽입만 하고 큐의 앞에서는 삭제만 하는 구조
선입선출구조
( ↔ 스택 : 후입선출구조 )
머리(front) : 마지막으로 삭제된 인덱스, 삭제하는 위치
꼬리(rear) : 저장된 원소 중 마지막 원소, 삽입하는 위치
- 큐의 기본 연산
enQueue : 삽입
deQueue : 삭제
- 큐의 사용을 위해 필요한 주요 연산
enQueue() : 큐 뒤쪽에 원소 삽입
deQueue() : 큐 앞쪽에서 원소 삭제하고 반환
createQueue() : 공백 상태의 큐를 생성
isEmpty() : 큐가 공백 상태인지 확인
isFull() : 큐가 포화상태인지 확인
Qpeek() : 큐의 앞쪽에서 원소를 삭제하지 않고 반환
- 선형큐
1차원 배열을 이용한 큐
→ 큐의 크기 = 배열 크기
front : 가장 먼저 삽입된 원소의 앞 인덱스 ( 그래서 front는 보통 빈 공간을 가리킴 )
rear : 저장된 마지막 원소의 인덱스
초기 상태 : front = rear = -1
공백 상태 : front == rear
포화 상태 : rear == n-1
초기 공백 큐 생성
→ 크기 n인 1차원 배열 생성
→ front 와 rear 를 -1 로 초기화
- 삽입 : enQueue(item)
마지막 원소 뒤에 새로운 원소를 삽입하기 위해 rear 값을 하나 증가시켜 삽입 자리를 마련
그 인덱스에 해당하는 배열원소 Q[rear]에 item을 저장
- 삭제 : deQueue()
가장 앞에 있는 원소를 삭제하기 위해 front 값을 하나 증가시켜 큐의 가장 앞 원소로 이동
첫 번째 원소를 리턴하여 삭제와 동일한 기능 수행
- 공백 상태 및 포화 상태 검사 : isEmpty(). isFull()
공백 상태 : front == rear
포화 상태 : rear == n-1 (n : 배열의 크기, n-1 : 배열의 마지막 인덱스)
- 검색 : Qpeek()
가장 앞에 있는 원소를 검색하여 반환하는 연산
현재 front의 한자리 뒤(front +1)에 있는 원소, 즉 큐의 첫 번째에 있는 원소를 반환
# 큐 생성
N = 10
q = [0] * N
front = rear = -1
rear += 1 # enqueue(10)
q[rear] = 10
rear += 1 # enqueue(20)
q[rear] = 20
rear += 1 # enqueue(30)
q[rear] = 30
while front != rear: # 큐가 비어있지 않으면
front += 1 # dequeue()
print(q[front])
- 선형 큐 이용 시 문제점
잘못된 포화상태 인식
→ 배열의 앞부분에 활용할 수 있는 공간이 있을 때도 rear = n-1 면 포화상태로 인식하여 더 이상 삽입할 수 없다.
→ 매 연산이 이루어질 때마다 저장된 원소들을 배열의 앞부분으로 이동시키면 해결할 수 있지만, 원소 이동에 많은 시간이 소요되어 큐의 효율성이 떨어지게 된다.
→ 1차원 배열을 사용하되, 논리적으로 배열의 처음과 끝이 연결되어 ‘원형 형태의 큐’를 이룬다고 가정하고 사용하여 해결할 수 있다.
- 원형 큐의 구조
초기 공백 상태
→ front = rear = 0
index의 순환
→ front와 rear의 위치가 배열의 마지막 인덱스인 n-1를 가리킨 후, 그 다음에는 논리적 순환을 이루어 배열의 처음 인덱스인 0으로 이동해야 한다. 이를 위해 나머지 연산자 mod를 사용한다.
front 변수
→ 공백 상태와 포화 상태 구분을 쉽게 하기 위해 front가 있는 자리는 사용하지 않고 항상 빈자리로 둔다.
삽입 위치 및 삭제 위치 (선형 / 원형)
삽입 : rear = rear + 1 / rear = (rear + 1) mod n
삭제 : front = front + 1 / front = (front + 1) mod n
- 원형 큐의 구현
초기 공백 큐 생성
→ 크기 n인 1차원 배열 생성
→ front와 rear를 0으로 초기화
공백상태 : front == rear
포화상태 : 삽입할 rear의 다음 위치 == 현재 front, 즉 (rear + 1) mod n == front
삽입 : enQueue(item)
삭제 : deQueue(), delete()
# 저장소
SIZE = 5
Q = [0] * SIZE
front = rear = 0
def enQueue(item):
global rear
# full => (rear + 1) % SIZE == front
if (rear + 1) % SIZE == front:
print('FULL!!!')
return
rear = (rear + 1) % SIZE
Q[rear] = item
def deQueue():
global front
# empty-check 는 front == rear
front = (front + 1) % SIZE
return Q[front]
def isEmpty():
return front == rear
def isFull():
return (rear + 1) % len(Q) == front
enQueue(1)
enQueue(2)
enQueue(3)
enQueue(4)
enQueue(5)
print(Q)
print(front, rear)
while not empty():
print(deQueue())
# FULL!!!
# [0, 1, 2, 3, 4]
# 0 4
# 1
# 2
# 3
# 4
- 연결 큐의 구조
단순 연결 리스트(linked list)를 이용한 큐
큐의 원소 : 단순 연결 리스트의 노드
큐의 원소 순서 : 노드의 연결 순서. 링크로 연결되어 있다.
front : 첫 번째 노드를 가리키는 링크
rear : 마지막 노드를 가리키는 링크
초기 상태 = 공백 상태 : front = rear = null
- deque (덱)
컨테이너 자료형 중 하나
deque 객체
→ 양쪽 끝에서 빠르게 추가와 삭제를 할 수 있는 리스트류 컨테이너
append(x) : 오른쪽에 x 추가
popleft() : 왼쪽에서 요소를 제거하고 반환한다. 요소가 없으면 IndexError
from collections import deque
q = deque()
q.append(1)
q.append(2)
print(q.popleft())
print(q.popleft())
# dq = deque()
# for i in range(10000):
# dq.append(1)
# print('append')
# while dq:
# dq.popleft()
# print('end')
# 덱은 리스트 선형 큐는 비슷하지만, 그냥 리스트의 append(), pop() 연산이 꽤나 느려서
# 똑같은 연산이라도 덱을 사용하면 더 빠르다.
- 우선순위 큐
우선순위 큐의 특성
→ 우선순위를 가진 항목들을 저장하는 큐
→ 들어온 순서에 상관없이 우선순위가 높은 순으로 먼저 나가게 된다.
우선순위 큐의 적용 분야
→ 시뮬레이션 시스템, 네트워크 트래픽 제어, 운영체제의 데스크 스케줄링
우선순위 큐의 구현 → 배열, 리스트 등을 이용하여 구현
우선순위 큐의 기본 연산 : 일단 큐이기 때문에 동일하게 enQueue, deQueue 를 사용
- 배열을 이용한 우선순위 큐 구현
원소를 삽입하는 과정에서 우선순위를 비교하여 적절한 위치에 삽입하는 구조
가장 앞에 최고 우선순위의 원소가 위치하게 된다.
문제는 소요되는 시간이나 메모리 낭비가 크고 배열을 사용하므로, 삽입이나 삭제 연산이 일어날 때 원소의 재배치가 발생하는 것
- 큐의 활용 : 버퍼
버퍼 : 데이터를 한 곳에서 다른 한 곳으로 전송하는 동안 일시적으로 그 데이터를 보관하는 메모리의 영역
버퍼링 : 버퍼를 활용하는 방식 또는 버퍼를 채우는 동작을 의미한다.
버퍼의 자료구조
→ 버퍼는 일반적으로 입출력 및 네트워크와 관련된 기능에서 이용된다.
→ 순서대로 입력/출력/전달되어야 하므로 FIFO 방식의 자료구조인 큐가 활용된다.