Queue   큐, 대기열

(2023-09-23)

1. 큐, 대기열 (Queue)

  ㅇ [일반] 
     - 대기 열을 지어 기다리고 있다는 수학적인 용어

  ㅇ [자료구조]
     - 컴퓨터 알고리즘의 저장구조로써 활용되는, 자료구조 종류 중 하나

  ㅇ [스케줄링]
     - 대기 큐 중에서 우선 처리 규칙


2. [자료구조]  큐 (Queue)

  ㅇ 한쪽 끝에서 삽입되고, 다른 한쪽 끝으로 삭제되는 리스트 구조의 일종임

  ㅇ 큐의 특징 
     - 데이터의 입력,출력이 정해진 위치에서 만 가능 
        . 자료 추가(삽입,입력)는 끝(rear)에서 만 가능
        . 자료 반환(삭제,출력)은 처음(front)에서 만 가능
        . 한편, 스택에서는, 자료의 삭제/추가가 모두 한쪽 끝(top)에서 만 가능
     - 전후/선후 관계가 1:1
        . 즉, 선형자료구조 임

  ㅇ 큐의 구분  :  입출력 순서/처리 방법에 따라 달라짐                  ☞ 큐잉 정책 참조
     - 일반적인 큐 (Genaral Queue)
        . 삽입된 순서에 따라 삭제됨 
           .. 가장 일반적인 경우 :  FIFO (선입선출 : 먼저 들어간 것이, 먼저 처리됨)
     - 우선순위 큐 (Priority Queue)
        . 임의 순서로 삽입되나(입력/추가), 일정 순서로 삭제됨/출력됨/제거됨
           .. 입력은 임의 순서이나,
           .. 출력은 반드시 일정한/정해준 순서를 갖음

  ㅇ 큐의 용어
     - 큐에 자료 추가  :  인큐 (Enqueue)
     - 큐에서 자료 제거 및 반환  :  디큐 (Dequeue)
     - 큐 자료 접근(자료 제거가 아닌 반환 만)  :  피크 (Peek)
     - 처음/전단 자료  :  프런트 (Front) 또는 헤드 (Head)
     - 마지막/후단 자료  :  리어 (Rear) 또는 테일 (Tail)

  ㅇ 큐의 연산(동작)
     - 큐 생성  :  createQueue()
     - 큐 삭제(메모리 해제)  :  deleteQueue()
     - 큐 포화 여부  :  isFull()
     - 공백 큐 여부  :  isEmpty(q)
        . 큐 q가 비었으면 true
     - 인큐  :  enqueue(q,i)
        . 큐 q의 끝(테일)에 항목 i를 추가
     - 디규  :  dequeue(q)
        . 큐 q의 처음(헤드)에서 항목 제거 후 다음 항목을 헤드로 만듬
        . 큐가 비었으면 오류 발생시킴
     - 피크  :  peek()

  ㅇ 큐의 구현 방법
     - 배열을 이용하는 방법
     - 연결 리스트를 이용하는 방법

  ㅇ 주요 용도
     - 작업들 간에 처리 순서를 관리하는 등


3. [스케줄링]  큐 처리 방식 

  ※ ☞ 큐잉 정책(Queuing) 참조
     - 입출력(삽입,삭제) 순서에 대한 정책에 따라 여러 큐잉 형태 있음
        . 선입선출 (FIFO), 선입후출 (FILO) 등

   1.   2. 우선순위 큐  


Copyrightⓒ written by 차재복 (Cha Jae Bok)               기술용어해설 후원
"본 웹사이트 내 모든 저작물은 원출처를 밝히는 한 자유롭게 사용(상업화포함) 가능합니다"