큐 (자료 구조)

위키백과 ― 우리 모두의 백과사전.

큐(queue)는 컴퓨터의 기본적인 자료 구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO (First In First Out) 구조로 저장하는 형식을 말한다. 영어단어 queue는 표를 사러 일렬로 늘어선 사람들로 이루어진 줄을 말하기도 하며, 먼저 줄을 선 사람이 먼저 나갈 수 있는 상황을 연상하면 된다.

나중에 집어 넣은 데이터가 먼저 나오는 스택과는 반대되는 개념이다.

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

큐 의 구조

DATA : A B C D E

 

PUSH(A)

A

 

PUSH(B)

B

A

 

PUSH(C)

C

B

A

 

POP()

C

B

 

PUSH(D)

D

C

B

 

POP(D,C)

B

[편집] 큐의 문제점

큐는 위의 그림에서 보듯이 제일 아래부분을 POP 시킬 경우 원래 자료가 있던 자리에는 저장을 할 수 없는 단점이 있다. 그렇다고 해서 지워진 공간으로 데이터를 모두 한칸씩 앞으로 당기는 것은 시간이 많이 소요되는 단점을 안고 있다.

[편집] 보완된 큐, 환형큐

큐의 문제점을 보환한 것이 원형으로 만들어 주는 환형큐 이다. PUSH 가 최대로 발생시 제일 앞으로 가서 빈 공간을 채워 나가는 방법이다.

환형 큐 의 구조

DATA : A B C D E

 

PUSH(A)

A

 

PUSH(B)

B

A

 

PUSH(C)

C

B

A

 

PUSH(D)

D

C

B

A

 

POP()

D

C

B

 

PUSH(E)

D

C

B

E

이 문서는 컴퓨터에 관한 토막글입니다. 서로의 지식을 모아 알차게 문서를 완성해 갑시다.