Algorithm_11

Queue

---

Queue의 특성

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

선형큐

• 1차원 배열을 이용한 큐
  • 큐의 크기 = 배열의 크기
  • front: 마지막으로 삭제된 인덱스
  • rear : 저장된 마지막 원소의 인덱스
• 상태표현
  • 초기 상태 : front = rear = -1
  • 공백 상태 : front == rear
  • 포화 상태 : rear == n-1

Queue의 연산자

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

1) 공백 큐 생성 : createQueue(); → front = rear = -1
2) 원소 A 삽입 : enQueue(A); → front = -1, rear = 0
3) 원소 B 삽입 : enQueue(B); → front = -1, rear = 1
4) 원소 삭제 : deQueue(); front = 0, rear = 1
5) 원소 C 삽입 : enQueue(); front = 0, rear = 2
6) 원소 반환/삭제 : deQueue(); front = 1, rear =2
7) 원소 반환/삭제 : deQueue(); front = 2, rear =2

Queue의 구현

• 삽입
  • rear 값을 하나 증가시켜 새로운 원소를 삽입할 자리를 마련
  • 그 인덱스에 해당하는 배열원소 Q[rear]에 item을 저장

    def enQueue(item):
    		global rear
         if isFull(): print("Queue Full")
         else:
         	rear = rear + 1
             Q[rear] = item

• 삭제
  • front 값을 하나 증가시켜 큐에 남아있는 첫 번째 원소 이동
  • 새로운 첫 번째 원소를 리턴함으로써 삭제와 동일한 기능함

    def deQueue():
    		if (isEmpty()): print(Queue_Empty())
         else: front = front + 1
         	return Q[front]

• 공백상태 및 포화상태 검사 : isEmpty(), isFull()
  • 공백상태 : front == rear
  • 포화상태 : rear == n-1

    def isEmpty():
    		return front == rear
    def isFull():
    		return rear == len(Q) - 1

• 검색
  • 가장 앞에 있는 원소를 검색하여 반환하는 연산
  • 현재 front 한 자리 뒤에 있는 원소, 즉 큐의 첫 번째에 있는 원소를 반환

    def Qpeek():
    		if isEmpty() : print("Queue_Empty()")
         else: return Q[front+1]

선형 큐 이용시의 문제점

• 잘못된 포화상태 인식
  • 인덱스 위치가 초기화 되지 않아 빈 공간이 있음에도 꽉찼다라고 봄
• 해결
  • 매 연산이 이루어 질때마다 배열을 앞부분으로 이동 → 큐의 효율성 떨어짐
  • 1차원 배열을 사용하되, 논리적으로는 배열의 처음과 끝이 연결된 원형 형태의 큐를 사용한다고 가정
• 인덱스의 순환
  • front와 rear의 위치가 배열의 마지막 인덱스인 n-1를 가리킨 후, 그 다음에는 논리적 순환을 이루어 배열의 처음 인덱스인 0으로 이동 → 나머지 연산자 mod 사용

---

삽입 위치 및 삭제 위치

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

원형 큐의 구현

• 초기 공백 큐 생성
  • front = rear = 0
  • 크기 n 차원 배열
• 공백상태 및 포화상태 검사 : isEmpty(), isFull()
  • 공백상태 : front == rear
  • 포화상태 : 삽입할 rear의 다음 위치 == 현재 front
    • (rear + 1) mod n == front

    def isEmpty():
    		return front == rear
    def isFull():
    		return (rear+1) % len(cQ) == front

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

    def enQueue(item):
    		global rear
         if isFull(): print("Queue Full")
         else:
         	rear = (rear + 1) % len(cQ)
             cQ[rear] = item

• 삭제
  • front 값을 조정하여 삭제할 자리 준비
  • 새로운 front 원소를 리턴함으로써 삭제와 동일한 기능함

    def deQueue():
    		if (isEmpty()): print("Queue_Empty()")
         else: front = (front + 1) % len(cQ)
         	return cQ[front]

---

연결 큐의 구조

• 단순 연결 리스트를 이용한 큐
  • 큐의 원소 : 단순 연결 리스트의 노드
  • 큐의 원소 순서 : 노드의 연결순서
  • front : 첫 번째 노드를 가리키는 링크
  • rear : 마지막 노드를 가리키는 링크
• 상태표현
  • 초기 상태 : front = rear = null
  • 공백 상태 : front = rear = null
• dequeu(덱)
  • 컨테이너 자료형 중 하나
  • deque 객체
    • 양쪽 끝에서 빠르게 추가와 삭제를 할 수 있는 리스트류 컨테이너
  • 연산
    • append(x) : 오른쪽에 x 추가
    • popleft() : 왼쪽에서 요소를 제거하고 반환

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

---

우선순위 큐

• 특성
  • 우선순위를 가진 항목들을 저장하는 큐
  • FIFO 순서가 아니라 우선순위가 높은 순서대로
• 적용 분야
  • 시뮬레이션 시스템
  • 네트워크 트레픽 제어
  • 운영체제의 테스크 스케줄링
• 배열을 이용하여 우선순위 큐 구현
  • 배열을 이용하여 자료 저장
  • 원소를 삽입하는 과정에서 우선순위를 비교하여 적절한 위치에 삽입하는 구조
  • 가장 앞에 최고 우선순위의 원소가 위치하게 됨
• 문제점
  • 배열을 사용하므로, 삽입이나 삭제 연산이 일어날 때 원소의 재배치가 발생
  • 이에 소요되는 시간이나 메모리 낭비가 큼

---

버퍼

• 버퍼

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

• 버퍼의 자료구조

  • 버퍼는 일반적으로 입출력 및 네트워크와 관련된 기능에서 사용
  • 순서대로 입력/출력/전달 되어야 하므로 FIFO 방식의 큐 활용