Queue

큐는 선입선출 구조

Front : 저장된 원소 중 첫 번 째 원소(or 마지막으로 삭제된 인덱스)

Rear : 저장된 원소 중 마지막 원소

 

기본 연산

연산	기능
enQueue(item)	rear 뒤에 원소를 삽입
deQueue()	front에서 원소를 삭제하고 반환
createQueue()	공백의 큐를 생성
isEmpty()	큐가 공백인지 확인
isFull()	큐가 포화인지 확인
Qpeek()	front에서 삭제 없이 반환

 

연산 과정

1) 공백 큐 생성

 

createQueue()

2) 원소 A 삽입

enQueue(A)

rear += 1
Q[rear] = A

 

3) 원소 B 삽입

enQueue(B)

rear += 1
Q[rear] = B

 

4) 원소 반환/삭제

deQueue()

front +=1
tmp = Q[front]

 

5) 원소 C 삽입

enQueue(C)

rear += 1
Q[rear] = C

 

6) 원소 반환/삭제

deQueue()

7) 원소 반환/삭제

deQueue()

 

선형 큐의 구현

선형 큐

큐의 크기 = 배열의 크기

 

상태 표현

초기 상태 : front == rear == -1

공백 상태 : front == rear

포화 상태 : rear == n-1

 

초기 공백 큐 생성

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

---

<데이터 1,2,3을 차례로 큐에 삽입, 꺼내서 출력하기>

queue = []
queue.append(1)
queue.append(2)
queue.append(3)
'''
print(queue.pop(0))
print(queue.pop(0))
print(queue.pop(0))
'''
while queue:
    print(queue.pop(0))

이런 식으로 list처럼 해도 가능

But, queue의 길이가 짧아지며, 그걸 또 반환하기에 시간복잡도가 좋지 않음

 

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

이것이 Queue의 동작원리를 이해한 코드임

삭제 후 반환이 아닌 인덱스를 찾아 print만 하기에 시간복잡도가 빠름

---

선형 큐의 문제점

:잘못된 포화상태 인식

 배열의 앞부분에 공간이 있어도 rear=n-1인상태(포화상태)로 인식하여 삽입을 안 하게 됨

> 연산이 이루어질때 저장된 원소들을 배열 앞으로 모두 이동(front=-1유지)

    원소 이동에 시간이 오래 걸려 효율성이 안 좋음

선형 큐 문제의 해결방법 1

> 원형 큐(순환 큐) 사용

선형 큐 문제의 해결방법 2

 

원형 큐

원형 큐 구조

초기 공백 상태 : front = rear = 0

index의 순환

front,rear이 n-1일 때 이후에 순환을 통해 0으로 가야함

>  mod 사용

 

선형큐와의 삽입,삭제 차이

	삽입 위치	삭제 위치
선형 큐	rear += 1	front += 1
원형 큐	rear = (rear + 1) mod n	front = (front +1) mod n

 

연산 과정

1) create Queue

create Queue

2) enQueue(A)

enQueue(A)

3) enQueue(B)

enQueue(B)

4) deQueue()

deQueue()

5) enQueue(C)

enQueue(C)

6) enQueue(D)

enQueue(D)

front == (rear+1) % N	#이게 Full인 상태

즉, rear의 다음 자리가 front일 때가 full이라고 생각

(front는 비워줘야하므로)

 

원형 큐의 구현

상태 표현

공백상태 : front == rear

포화상태 : (rear + 1) mod n == front

---

연결 큐

단순 연결 리스트(linked list)를 이용한 큐

큐의 원소 : 리스트의 노드

큐의 원소 순서 : 노드의 연결 순서. 링크로 연결

front : 첫 번째 노드를 가리키는 링크

rear : 마지막 노드를 가리키는 링크

 

상태 표현

초기 상태 : front = rear = null

공백 상태 : front = rear = null

연결 큐의 상태

연산 과정

1) 공백 큐 생성

createLinkedQueue()

2) 원소 A 삽입

enQueue(A)

3) 원소 B 삽입

enQueue(B)

4) 원소 삭제

deQueue()

5) 원소 C 삽입

enQueue(C)

6) 원소 삭제

deQueue()

7) 원소 삭제

deQueue()

 

deque(덱)

deque 객체

양쪽 끝에서 빠르게 추가와 삭제를 할 수 있는 리스트류 컨테이너

그냥 리스트와 덱의 실행시간 차이

from collections import deque

# 리스트에서 pop
q = []
for i in range(100000):
    q.append(i)
while q:
    q.pop(0)
# 덱에서 popleft
dq = deque()
for i in range(100000):
    dq.append(i)
while dq:
    dq.popleft()

리스트 vs 덱

덱은 매우 빠르게 추가와 삭제를 할 수 있음

 

우선순위 큐

: Priority Queue

특성

우선순위를 가진 항목들을 저장하는 큐

FIFO 순서 X , 우선순위가 높은 순서로 나감

 

적용 분야

시뮬레이션 시스템

네트워크 트래픽 제어

운영체제의 테스크 스케쥴링

 

배열 우선순위 큐 구현

원소를 삽입할 때 우선순위로 적절한 위치에 삽입

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

배열 사용 > 연산에서 원소의 재배치 발생

시간과 메모리 낭비가 큼

cf) 리스트를 이용하여 자료를 저장하기도 함

Buffer

데이터를 다른 곳으로 전송할 때 일시적으로 그 데이터를 보관하는 메모리의 영역

버퍼의 자료 구조

일반적으로 입출력, 네트워크와 관련된 기능에서 이용

순서대로 입력,출력,전달이 되어야 함 > FIFO 방식의 큐가 활용됨

 

사용 예시

터미널에 text가 1MB가 넘는 데이터를 직접 넣는다면 후반의 데이터는 입력 버퍼 오류로 손실남

> 터미널에 text 파일을 넣거나, sys.stdin을 통해 open file을 지정하면 됨