[자료구조] Queue (큐)

큐(Queue)는 무엇일까?

기본적인 자료 구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out)구조로 저장하는 형식을 말한다.

영어 단어 queue는 표를 사러 일렬로 늘어선 사람들로 이루어진 줄을 말하기도 하며, 먼저 줄을 선 사람이 먼저 나갈 수 있는 상황을 연상하면 된다. 나중에 집어 넣은 데이터가 먼저 나오는 스택과는 반대되는 개념이다.

프린터의 출력 처리나 윈도 시스템의 메시지 처리기, 프로세스 관리 등 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 이용된다.

 

큐 (Queue)

---

큐의 구현

1. 배열 사용 : 구현이 쉽지만 크기가 동적이 아니고, 런 타임시 필요에 따라 늘어나거나 줄어들지 않는다.
2. 연결 리스트 사용 : 크기가 동적이라 편리하고 런타임 시 필요에 따라 크기가 확장 및 축소될 수 있다. 하지만 포인터를 위한 추가 메모리 공간이 필요하게 된다.

---

큐의 동작

• enqueue() - 큐에 끝(rear)에 항목을 추가
• dequeue() - 큐에 맨 앞(front)에 항목을 제거
• peek() - 큐에 맨 앞(front)에 있는 항목을 반환
• isfull() - 큐가 가득 찼는지 확인
• isempty() - 큐가 비어 있는지 확인

 

큐에 끝(Rear)에서 요소를 추가하는 작업을 enqueue라고 하며 큐에 맨 앞(Front)에서 요소를 제거하는 작업을 dequeue라고 한다.

가득 찬 큐에 요소를 추가하려고 할 때 Overflow가 발생하며, 빈 큐에서 요소를 제거하려고 할 때 Underflow가 발생한다

---

큐의 종류

 

선형 큐

막대 모양으로 된 큐이다.

크기가 제한되어 있고 빈 공간을 사용하려면 모든 자료를 꺼내거나 자료를 한 칸씩 옮겨야 한다는 단점이 있다.

다음은 선형 큐의 작동 방식이다.

DATA : A B C D E

선형 큐

 

 

원형(환영) 큐 

선형 큐의 문제점(배열로 큐를 선언할시 큐의 삭제와 생성이 계속 일어났을때, 마지막 배열에 도달후 실제로는 데이터공간이 남아있지만 오버플로우가 발생)을 보완한 것이 원형 큐이다.

front가 큐의 끝에 닿으면 큐의 맨 앞으로 자료를 보내어 원형으로 연결 하는 방식이다.

DATA : A B C D E

환영 큐

 

 

 

출처: 위키백과, 나무위키