이번 글은 서강대학교 소정민 교수님의 강의와 Ellis Horowitz의「Fundamentals of Data Structures in C」를 바탕으로 작성했음을 밝힙니다.

큐(Queue)

From Textbook

A Queue is an ordered list in which all insertions take place at one end and all deletions take place at the opposite end. Given a queue $Q = (a_0, ... , a_{n-1})$, $a_0$ is the front element, $a_{n-1}$ is the rear element, and $a_{i+1}$ is behind $a_i$. Since the first element inserted into a queue is the first element removed, queues are also known as FIFO lists.

From Wiki

큐(Queue)는 컴퓨터 과학 분야에서 쓰이는 컴퓨터의 기본적인 자료 구조의 한 가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO 구조로 저장하는 형식을 말한다. 나중에 집어 넣은 데이터가 먼저 나오는 스택과는 반대되는 개념이다.

1.1 ADT

• Object : a finite ordered list with zero or more elements
• Functions : CreateQ, IsFullQ, AddQ(enQue), IsEmptyQ, DeleteQ(deQue)

1.2 큐의 특징

• Chronologically Ordered List의 한 종류입니다.
• 프린터의 출력 처리나 윈도우 시스템의 메시지 처리기, 프로세스 관리 등 데이터가 입력된 시간 순서대로 처리해랴 할 필요가 있는 상황에 이용됩니다.

1.3 큐의 장단점

장점

• 작동 방식이 직관적입니다(입력된 순서대로 처리). 따라서 실생활에서 많이 이용됩니다.

단점

• 크기가 제한적입니다.
• (C에서) 큐가 비어있어도, 비어있지 않다고 판단할 수 있습니다.(rear가 배열의 마지막에 있을 경우)

1.4 시간복잡도

• 삽입 : $O(1)$
• 삭제 : $O(1)$
• 탐색 : $O(n)$