자료구조 #2 Queue

1. Queue 자료 구조의 개념

---

1) Queue

1-1) Queue 의 특성

• 삽입 삭제의 위치가 제한적인 자료구조
    큐 뒤 : 삽입
    큐 앞 : 삭제

• 선입선출 구조(FIFO : First In First Out)
    큐에 삽입한 순서대로 원소가 저장
    가장 먼저 삽입(First In)된 원소는 가장 먼저 삭제(First Out) 된다

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

1-2) Queue 의 구조

• 머리 : 저장된 원소 중 첫 번째 원소
• 꼬리 : 저장된 원소 중 마지막 번째 원소

1-3) Queue 의 기본 연산

• enQueue(item) : 큐의 뒤쪽(rear 다음) 에 원소를 삽입하는 연산

• deQueue() : 큐의 앞쪽(front) 에서 원소를 삭제하고 반환하는 연산

• createQueue() : 공백 상태의 큐를 생성하는 연산

• isEmpty() : 큐가 공백 상태인지를 확인하는 연산

• isFull() : 큐가 포화 상태인지를 확인하는 연산

• Qpeek(0 : 큐의 앞쪽(front) 에서 원소를 삭제 없이 반환하는 연산

1-4) Queue 의 기본 연산 과정

• 공백 큐 생성 : createQueue()

• 원소 A 삽입 : enQueue(A)

• 원소 B 삽입 : enQueue(B)

• 원소 반환 / 삭제 : deQueue()

• 원소 C 삽입 : enQueue(C)

• 원소 반환 / 삭제 : deQueue()

• 원소 반환 / 삭제 : deQueue()

1-5) Queue 의 종류

• 선형 큐
    간단하고 기본적인 형태
    리스트 사용

• 원형 큐
    선형에서 발전된 형태
    리스트 사용

• 연결 큐
    연결 리스트 형식을 이용

• 우선순위 큐
    연결 큐의 응용

---

2) 선형 Queue

2-1) 1차원 리스트를 이용한 큐

• 큐의 크기 = 리스트의 크기

• front : 저장된 첫 번째 원소의 인덱스

• rear : 저장된 마지막 원소의 인덱스

2-2) 상태 표현

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

• 공백 상태 : front = rear

• 포화 상태 : rear = n - 1
    n : 리스트의 크기
    n - 1 : 리스트의 마지막 인덱스

2-3) 선형 큐의 구현

초기 : createQueue()

• 크기 n 인 1차원 리스트 생성

• front, rear = -1 로 초기화

삽입 : enQueue(item)

마지막 원소 뒤에 새로운 원소를 삽입하기 위해

• rear 값을 하나 증가시켜 새로운 원소를 삽입할 그 자리를 마련한다

• 그 인덱스에 해당하는 리스트 원서 Q[rear] 에 item 저장

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

삭제 : deQueue()

가장 앞에 있는 원소를 삭제하기 위해

• front 값을 하나 증가시켜 큐에 남아있는 첫 번째 원소로 이동함

• 새로운 첫 번째 원소를 리턴함으로써 삭제와 동일한 기능을 함

•   def deQueue() :
        global front
  
        if isEmpty() :
            print("Queue Empty")
  
        else : 
            front += 1
            return Q[front]

공백상태 및 포화상태 검사 : isEmpty(), isFull()

• 공백상태 : front = rear

• 포화상태 : rear = n - 1
    n : 리스트의 크기
    n - 1 : 리스트의 마지막 인덱스

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

검색 : Qpeek()

• 가장 앞에 있는 원소를 검색하여 반환하는 연산

• 현재 front의 한자리 뒤(front + 1) 에 있는 원소, 즉 큐의 첫 번째에 있는 원소를 반환

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

선형 큐의 문제점 : 잘못된 포화 상태 인식

• 리스트의 크기를 고정 -> 사용할 큐의 크기만큼을 미리 확보 -> 메모리의 낭비 발생

    삽입, 삭제를 계속할 경우 리스트의 앞부분에 활용할 수 있는 공간이 있음에도,
    rear = n - 1인 상태 즉, 포화 상태로 인식

• 더 이상의 삽입을 수행할 수 없다

선형 큐의 장/단점

• 장점 : 삽입, 삭제의 처리속도가 빠르다

• 단점 : 메모리 낭비가 심하다

단점 해결 방법

• 원형 큐 사용으로 메모리 절약

• 파이썬의 리스트 특성을 사용한 큐 사용으로 메모리 절약

  • 단점 : 삽입, 삭제 시 복사, 데이터 이동시키는 연산 수행에 많은 시간 소모

• 단순 연결 리스트로 구현한 큐 사용으로 메모리 동적 확보

• 큐 라이브러리 사용

---

3) 원형 Queue

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

• 원형 큐의 논리적 구조

3-1) 원형 큐의 특징

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

• Index 의 순환
    Front 와 rear 의 위치가 리스트의 마지막 인덱스인 n - 1 를 가리킨 후,
    논리적 순환을 이루어 리스트의 처음 인덱스인 0으로 이동해야 한다

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

• 삽입 위치 및 삭제 위치

  테이블 인덱스	삽입 위치	삭제 위치
  선형 큐	rear = rear + 1	front = front + 1
  원형 큐	rear = (rear + 1) % n	front = (front + 1) % n

3-2) 원형 큐의 구현

초기 공백 큐 생성 : createQueue()

• 크기 n 인 1차원 리스트 생성

• front, rear = 0 으로 초기화

공백상태 및 포화상태 검사 : isEmpty(), isFull()

• 공백상태 : front = rear

• 포화상태 : 삽입할 rear의 다음 위치 = 현재 front

• (rear + 1) % n = front

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

삽입 : enQueue(item)

마지막 원소 뒤에 새로운 원소를 삽입하기 위해

• rear 값을 조정하여 새로운 원소를 삽입할 자리를 마련한다

• : rear <- (rear + 1) % n

• 인덱스에 해당하는 리스트 원소 cQ[rear]에 item을 저장

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

삭제 : deQueue(), delete()

• 가장 앞에 잇는 원소를 삭제하기 위해

• front 값을 조정하여 삭제할 자리를 준비한다

• 새로운 front 원소를 리턴함으로써 삭제와 동일한 기능을 한다

•   def deQueue() :
        global front
  
        if isEmpty():
            print("Queue Empty")
  
        else :
            front = (front + 1) % len(cQ)
            return cQ[front]
  
    def delete() :
        global front
  
        if isEmpty():
            print("Queue Empty")
  
        else :
            front = (front + 1) % len(cQ)

파이썬으로 구현한 원형 큐의 삽입 및 삭제

• cQ_size = 3
  cQ = [0] * cQ_size
  
  front = rear = 0
  
  enQueue("A")
  enQueue("B")
  enQueue("C")
  
  print(deQueue())
  print(deQueue())
  print(deQueue())

---

4) 리스트의 특성을 사용한 Queue

4-1) 파이썬의 리스트 특성을 사용한 큐

• 리스트는 크기를 동적으로 변경할 수 있음

• 메모리 절약

• 삽입, 삭제 시 복사, 데이터를 이동시키는 연산을 수행하는데 많은 시간 소모

4-2) 리스트의 메서드

• append(item) : 마지막 위치에 원소 추가

• pop(index) : index 위치에 원소 삭제

front 는 리스트의 맨 앞 : -1

rear 는 리스트의 맨 뒤 : len(queue) - 1

4-3) 파이썬으로 구현한 원형 큐의 삽입 및 삭제

• 
  def enQueue(item) :
      queue.append(item)
  
  def deQueue() :
      if isEmpty() :
          print("Queue Empty")
  
      else :
          return queue.pop(0)
  
  def isEmpty() :
      return len(Queue) == 0
  
  def Qpeek() :
      if isEmpty() :
          print("Queue Empty")
  
      else :
          return queue[0]
  
  # 공백 리스트 생성
  # front = : -1
  # rear : len(queue) - 1
  queue = []
  
  enQueue("A")
  enQueue("B")
  enQueue("C")
  
  print(deQueue())
  print(deQueue())
  print(deQueue())

---

5) 연결 Queue

5-1) 단순 연결 리스트(Linked List)를 이용한 큐

• 큐의 원소 : 단순 연결 리스트의 노드

• 큐의 원소 순서 : 노드의 연결 순서, 링크로 연결되어 있다

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

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

5-2) 상태 표현

• 초기 상태 : front = rear = None

• 공백 상태 : front = rear = None

• 포화 상태가 없다

• 

5-3) 연결 Queue 의 연산 과정

큐 생성 : createLinkedQueue()

• front와 rear 을 None 으로 초기화 시킨다

• 

원소 A 삽입 : enQueue(A)

• 원소 A를 추가하면 A 노드가 생성

• front 와 rear 의 값이 A의 위치를 가리킨다

• A 이외의 노드가 없기 때문에 A 노드의 링크에는 None이 저장된다

• 

원소 B 삽입 : enQueue(B)

• 원소 B를 추가

• 노드 A의 링크는 노드 B의 위치를 가리킨다

• rear 값도 B의 위치를 가리킨다

• 

원소 삭제 : deQueue()

• 삭제할 때에는 front 값이 A대신 A가 가리키는 B를 가리키면 된다

• 

원소 C 삽입 : enQueue(C)

• B의 링크가 C를 가리킨다

• rear 값도 C의 위치를 가리킨다

• 

원소 삭제 : deQueue()

• front 값이 B의 위치대신 B가 가리키던 C의 위치를 가리키게 된다 -> B삭제

• 

원소 삭제 : deQueue()

• 원소가 하나뿐이므로 front 와 rear 값이 None 으로 초기화 -> 큐가 비어있는 상태

• 

5-4) 연결 Queue 구현

초기 공백 큐 생성 : createLinkedQueue()

• 리스트 노드 없이 포인터 변수만 생성한다

• front 와 rear 를 None 으로 초기화

• front = None
  rear = None

공백 상태 검사 : isEmpty()

• 공백상태 : front = rear = None

• def is Empty() :
      return front == None

삽입 : enQueue(item)

• 새로운 노드 생성 후 데이터 필드에 item 저장

• 연결 큐가 공백인 경우, 아닌 경우에 따라 front, rear 변수 지정

• # 연결 큐의 삽입 연산
  def enQueue(item) :
      global front, rear
  
      # 새로운 노드 생성
      newNode = Node(item)
  
      if isEmpty() :
          front = newNode
  
      else :
          rear.next = newNode
  
      rear = newNode

삭제 : deQueue()

• old 가 지울 노드를 가리키게 하고, front 재설정

• 삭제 후 공백 큐가 되는 경우, rear 도 None로 설정

• old 가 가리키는 노드를 삭제하고 메모리 반환

• # 연결 큐의 삭제 연산
  def deQueue() :
      global front, rear
  
      if isEmpty() :
          print("Queue Empty")
          return None
  
      item = front.item
      front = front.next
  
      if isEmpty() :
          rear = None
  
      return item

파이썬으로 구현한 연결 큐

•   class Node :
        def __init__(self, item, n=None) :
            self.item = item
            self.next = n
  
        # 연결 큐의 삽입 연산
        def enQueue(item) :
            global front, rear
  
            # 새로운 노드 생성
            newNode = Node(item)
  
            if front == None :
                front = newNode
  
            else : 
                rear.next = newNode
  
            rear = newNode
  
        def isEmpty() :
            return front == None
  
        def deQueue() :
            global front, rear
  
            if isEmpty() :
                print("Queue Empty")
                return None
  
            item = front.item
            front = front.next
  
            if front == None :
                rear = None
  
            return item
  
        def Qpeek() :
            return front.item
  
        def printQ() :
            f = front
            s = ""
  
            while f :
                s += f.item + " "
                f = f.next
  
            return s

• front = None
  rear = None
  
  enQueue("A")
  enQueue("B")
  enQueue("C")
  printQ()
  
  print(deQueue())
  print(deQueue())
  print(deQUeue())

---

6) 큐 모듈

6-1) 큐 모듈에 정의된 클래스

• queue.Queue(maxsize)
  • 선입선출(FIFO First-In, First-Out) 큐 객체를 생성

• queue.LifoQueue(maxsize)
  • 스택 개념의 후입선출(LIFO Last-In, First-Out) 큐 객체 생성

• queue.PriorityQueue(maxsize)
  • 우선 순위 큐 객체를 생성, 입력되는 아이템의 형식은(순위, 아이템)의 튜플로 입력되며,
  • 우선 순위는 숫자가 작을수록 높은 순위를 가진다

• maxsize는 최대 아이템수, 지정하지 않거나 음수이면 내용만큼 늘어난다

• 제시된 3개의 클래스는 다음과 같은 메서드를 동일하게 가진다

• 메서드	내용
  qsize()	큐 객체에 입력된 아이템의 개수를 반환
  put(item, [ block, [ timeout ]])	큐 객체에 아이템을 입력
  get([block, [ timeout ]])	생성된 큐 객체 특성에 맞추어, 아이템 1개를 반환
  empty()	큐 객체가 비어있으면 True 리턴
  full()	큐 객체가 꽉차있으면 True 리턴

• 클래스의 정렬 방식에 따라 get 계열의 메서드 결과가 달라진다

6-2) 큐 모듈 활용

• import queue
  
  # FIFO 구조 큐 생성
  q = queue.Queue()
  
  q.put("A")
  q.put("B")
  q.put("C")
  
  while not q.empty() :
      print(q.get())

---

2. Queue 의 활용

---

1) 우선 순위 큐

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

• FIFO 순서가 아니라 우선 순위가 높은 순서대로 먼저 나가게 된다

  • 우선 순위가 같은 경우 : 먼저 들어온 순서대로 나가게 된다

1-1) 우선순위 큐 적용 분야

  1) 시뮬레이션 시스템

  2) 네트워크 트래픽 제어

  3) 운영체제의 태스크 스케줄링

1-2) 구현

• 리스트를 이용한 우선순위 큐

• 우선순위 큐 라이브러리 사용

1-3) 기본 연산

• 삽입 : enQueue

• 삭제 : deQueue

• 

1-4) 리스트를 이용한 우선순위 큐의 구현

1) 리스트를 이용하여 자료 저장

2) 원소를 삽입하는 과정에서 우선순위를 비교하여 적절한 위치에 삽입하는 구조

3) 가장 앞에 최고 우선순위의 원소가 위치하게 된다

a) 문제점

• 리스트를 사용하므로, 삽입이나 삭제 연산이 일어날 때 원소의 재배치가 발생한다
• -> 소요되는 시간이 많이 걸린다

b) 해결 방법

• PriorityQueue(maxsize) 클래스 사용

• 힙 자료구조 사용

---

2) 버퍼

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

• 버퍼링 : 버퍼를 활용하는 방식 또는 버퍼를 채우는 동작을 의미한다

2-1) 버퍼의 자료 구조

• 일반적으로 입출력 및 네트워크와 관련된 기능에서 사용된다

• 순서대로 입력/출력/전달 됭야 하므로 FIFO 방식의 자료구조인 큐가 활용 된다

2-2) 버퍼 활용 예 : 키보드 버퍼의 수행 과정

  1) 사용자가 키보드를 입력한다 :
  ex: A P S Enter

  2) 키보드 입력 버퍼에 입력한 순서대로 저장

  3) 키보드 입력 버퍼에 Enter 키 입력이 들어오게 되면 이를 프로그램 실행 영역에 전달하여
  순서대로 연산을 실행 한다