[2024.02.15] Queue 1

Queue (큐)

• 스택과 마찬가지로 삽입과 삭제의 위치가 제한적인 자료구조
  (큐의 뒤에서는 삽입만 하고, 큐의 앞에서는 삭제만 이루어지는 구조)
• 선입선출구조(FIFO): 큐에 삽입한 순서대로 원소가 저장되어, 가장 먼저 삽입된 원소는 가장 먼저 삭제된다.

• 큐의 기본 연산
  삽입 : enQueue
  삭제 : deQueue

• 큐의 주요 연산
  enQueue(item): 큐의 뒤쪽에 원소를 삽입하는 연산
  deQueue(): 큐의 앞쪽에서 원소를 삭제하고 반환하는 연산
  createQueue(): 공백 상태의 큐를 생성하는 연산
  isEmpty(): 큐가 공백 상태인지를 확인하는 연산
  isFull(): 큐가 포화상태인지를 확인하는 연산
  Qpeek(): 큐의 앞쪽에서 원소를 삭제없이 반환하는 연산

선형큐

• 1차원 배열을 이용한 큐
  큐의 크기 = 배열의 크기
  front: 저장된 첫번째 원소의 인덱스
  rear: 저장된 마지막 원소의 인덱스

• 상태 표현
  초기 상태: front = rear = -1
  공백 상태 front == rear
  포화 상태 rear == n-1 (n: 배열의 크기, n-1: 배열의 마지막 인덱스)

• 초기 공백 큐 생성
  크기 n인 1차원 배열 생성
  front와 rear를 -1로 초기화

N = 10  # 큐 생성
q = [0] * 10
front = rear = -1

연습문제1

큐를 구현하여 다음 동작을 확인해보자.
1. 세 개의 데이터 1, 2, 3을 차례로 큐에 삽입하고
2. 큐에서 세 개의 데이터를 차례로 꺼내서 출력한다.
1, 2, 3이 출력되어야 함

# 큐 생성
N = 10
q = [0] * 10
front = rear = -1

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

while front != rear: # 큐가 비어있지 않으면
    front += 1      # dequeue
    print(q[front])

• 강사님 코드

# 큐를 구현해서 1, 2, 3 원소를 순서대로 삽입
# 큐에서 값을 3개 꺼내 차례대로 출력한다

SIZE = 10
queue = [0] * SIZE
front = rear = -1 #초기화

# 큐 삽입 연산 enqueue
def enqueue(item):
    global rear
    # 큐가 이미 꽉 찬 상태일 때는 삽입 불가
    if is_full():
        return -1
    # 꼬리 rear를 1 증가시키고 그 위치에 요소를 삽입한다
    rear += 1
    queue[rear] = item

# 큐 삭제 연산 dequeue
def dequeue():
    global front
    # 큐가 비어 있을 때는 삭제 불가
    if is_empty():
        return -1
    # 머리 front를 1 증가시키고 그 위치의 요소를 반환한다
    front += 1
    return queue[front]

# 보조 연산
# is_full : queue가 가득 차 있는 상태
def is_full():
    return rear == SIZE - 1

# is_empty : queue가 비어 있는 상태
def is_empty():
    return front == rear

# q_peek : 꺼낼 요소를 미리 확인해 볼 수 있는 peek
def q_peek():
    return queue[front + 1]


enqueue(1)
enqueue(2)
enqueue(3)

item = dequeue()
print(item)
item = dequeue()
print(item)
item = dequeue()
print(item)

원형큐

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

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

• index의 순환
  front와 rear의 위치가 배열의 마지막 인덱스인 n-1를 가리킨 후, 그 다음에는 논리적 순환을 이루어 배열의 처음 인덱스인 0으로 이동해야 함. 이를 위해 나머지 연산자 mod를 사용함.

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

• 삽입 위치 및 삭제 위치
  

• 원형 큐의 연산 과정
  
  
  

• 초기 공백 큐 생성
  크기 n인 1차원 배열 생성
  front와 rear를 0으로 초기화

• 공백상태 및 포화상태 검사
  공백상태: front == rear
  포화상태: 삽입할 rear의 다음 위치 == 현재 front
  (rear+1) mod n == front

• 삽입: enQueue(item)
  마지막 원소 뒤에 새로운 원소를 삽입하기 위해
  1) rear 값을 조정하여 새로운 원소를 삽입할 자리를 마련함 : rear <- (rear+1) mod n
  2) 그 인덱스에 해당하는 배열원소 cQ[rear]에 item을 저장

• 삭제: deQueue(), delete()
  가장 앞에 있는 원소를 삭제하기 위해
  1) front 값을 조정하여 삭제할 자리를 준비함
  2) 새로운 front 원소를 리턴함으로써 삭제와 동일한 기능함

• 원형큐 구현 (강사님 코드)

SIZE = 10
queue = [0] * SIZE
front = rear = 0

# 큐 삽입 연산 enqueue
def enqueue(item):
    global rear
    # 큐가 이미 꽉 찬 상태일 때는 삽입 불가
    if is_full():
        return -1
    # 꼬리 rear를 1 증가시키고 그 위치에 요소를 삽입한다
    rear = (rear + 1) % SIZE
    queue[rear] = item


# 큐 삭제 연산 dequeue
def dequeue():
    global front
    # 큐가 비어 있을 때는 삭제 불가
    if is_empty():
        return -1
    # 머리 front를 1 증가시키고 그 위치의 요소를 반환한다
    front = (front + 1) % SIZE
    return queue[front]


# 보조 연산
# is_full : queue가 가득 차 있는 상태
def is_full():
    # 머리와 꼬리가 맞닿은 상태
    return (rear+1) % SIZE == front

# is_empty : queue가 비어 있는 상태
def is_empty():
    return front == rear

# q_peek : 꺼낼 요소를 미리 확인해 볼 수 있는 peek
def q_peek():
    return queue[(front + 1) % SIZE]


enqueue(1)
enqueue(2)
enqueue(3)

item = dequeue()
print(item)
item = dequeue()
print(item)
item = dequeue()
print(item)

연결 큐

• 단순 연결 리스트를 이용한 큐
  큐의 원소: 단순 연결 리스트의 노드
  큐의 원소 순서: 노드의 연결 순서. 링크로 연결되어 있음
  front: 첫번째 노드를 가리키는 링크
  rear: 마지막 노드를 가리키는 링크

• 연결 큐의 연산 과정
  
  
  

(참고) deque(덱)

• 컨테이너 자료형 중 하나
• deque 객체: 양쪽 끝에서 빠르게 추가와 삭제를 할 수 있는 리스트류 컨테이너
• 연산:
  append(x): 오른쪽에 x 추가
  popleft(): 왼쪽에서 요소를 제거하고 반환. 요소가 없으면 IndexError

from collections import deque

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

from collections import deque

q = deque()
q.append(1)
q.append(2)
print(q.popleft())
print(q.popleft())

• 강사님 코드

from collections import deque
# deque(데크, double-end queue)
#양쪽에서 값을 삽입/삭제

# 데크 객체 생성 (초기화)
q = deque()

# 삽입 enqueue (뒤에 원소를 추가)
q.append(1) # 뒤에 원소를 추가
# q.appendleft(1)  # 앞에 원소를 추가

# 삭제 dequeue (앞에서 원소를 삭제)
#q.pop()  # 뒤에서 원소를 삭제
item = q.popleft()
print(item)

우선순위 큐

• 우선순위 큐의 특성
  우선순위를 가진 항목들을 저장하는 큐
  FIFO 순서가 아니라 우선순위가 높은 순서대로 먼저 나가게 된다.

• 우선순위 큐의 구현
  배열을 이용한 우선순위 큐
  리스트를 이용한 우선순위 큐

• 배열을 이용하여 우선순위 큐 구현
  배열을 이용하여 자료 저장
  원소를 삽입하는 과정에서 우선순위를 비교하여 적절한 위치에 삽입하는 구조
  가장 앞에 최고 우선순위의 원소가 위치하게 됨

• 문제점
  배열을 사용하므로, 삽입이나 삭제 연산이 일어날 때 원소의 재배치가 발생함. 이에 소요되는 시간이나 메모리 낭비가 큼.

• 강사님 코드

from heapq import heappop, heappush
# 기본적으로 리스트 자료형을 사용하여 동작 수행
hq = [] # 힙으로 사용할 리스트

# 우선순위 큐에 값을 삽입하는 연산 enqueue -> heappush 함수
heappush(hq, 30)
heappush(hq, 10)
heappush(hq, 50)
heappush(hq, 100)
heappush(hq, 0)

# 우선순위 큐에 삭제를 하는 연산 dequeue -> heappop 함수
item = heappop(hq)
print(item) #0
item = heappop(hq)
print(item) #10
item = heappop(hq)
print(item) #30
item = heappop(hq)
print(item) #50
item = heappop(hq)
print(item) #100

# enqueue할 때 음수 부호 붙이고 dequeue할 때 -item으로 출력하면 값이 큰 것부터 출력됨.

버퍼

• 버퍼
  : 데이터를 한 곳에서 다른 한 곳으로 전송하는 동안 일시적으로 그 데이터를 보관하는 메모리의 영역
  버퍼링: 버퍼를 활용하는 방식 또는 버퍼를 채우는 동작을 의미한다.

• 버퍼의 자료구조
  : 버퍼는 일반적으로 입출력 및 네트워크와 관련된 기능에서 이용된다. 순서대로 입력/출력/전달되어야 하므로 FIFO 방식의 자료구조인 큐가 활용된다.