Queue(큐)의 사전적 의미는 무언가를 기다리는 사람들이나 물건등의 줄을 의미합니다.
컴퓨터 프로그래밍에서 Queue(큐)는 Stack(스택)과 함께 대표적인 자료구조 중의 하나로 데이터가 들어간 순서대로 제거되는 선입선출(FIFO) 형태의 자료구조를 의미합니다.

쉬운 예로 버스를 기다리는 사람들의 줄을 생각할 수 있으며 가장 먼저 줄을 선 사람이 가장먼저 버스에 올라타는 구조로 이해하면 됩니다.
컴퓨터 프로그래밍에서 Queue 자료구조는 프로세스가 요청한 작업들을 순서대로 처리하는 작업 스케쥴러등을 구현할때 흔히 쓰이곤 합니다.

일반적으로 큐를 구현할 경우 배열을 사용하여 구현할 수 있으나 크기가 결정된 배열안에서 데이터 추가작업이 계속될 경우 배열의 크기를 초과하게되는 시점에 오버플로우가 발생하게 됩니다.
이를 방지하기 위해 충분히 큰 크기의 배열을 선언해서 용량을 확보하거나 배열의 처음과끝을 연결하여 배열의 크기가 초과되었을 경우 배열의 처음부터 다시 데이터를 삽입하는 환형큐 형태의 구조로 구현을 해야 합니다.

하지만 배열의 특성상 배열로 구현한 큐는 메모리공간 낭비를 초래할 수 밖에 없습니다.
큐에 데이터가 삽입되면서 큐의 끝을 가리키는 배열의 인덱스가 증가하는 반면 데이터가 삭제되면서 큐의 처음을 가리키는 배열의 인덱스 또한 증가하여 배열의 앞부분에 버려진 공간이 늘어나게 됩니다.
또한 환형큐로 구현하더라도 배열의 빈공간이 남는 낭비를 초래할 수 밖에 없으며 배열의 처음부터 쌓이는 데이터가 큐의 끝인지 처음인지, 혹은 큐가 가득찬 경우인지 빈 경우인지를 알려주는 플래그를 사용하는 등 복잡한 프로그래밍 기법이 동원되어야 합니다.

하지만 연결리스트로 구현하면 위의 나열한 불편한 점을 해소할 수 있습니다.
큐에 삽입되는 모든 데이터 노드는 데이터와 링크(포인터)로 구성하여 데이터가 삽입될때마다 노드에 포함되어 있는 링크(포인터)에 연결시켜 주는 방식으로 데이터의 저장이 가능하며 이는 시스템 메모리가 허용하는 범위까지 저장이 가능합니다. 또한 삭제도 마찬가지로 메모리에서 데이터를 삭제하고 링크(포인터)를 해제하는 방식으로 구현이 가능합니다.

아래는 연결리스트로 구현한 Queue 자료구조 예시코드입니다.

1. 선언.


2. 구현.
(1) 생성자 및 소멸자.

(2) Queue에 데이터 존재여부 판별.

(3) Queue에 데이터 삽입.

(4) Queue에서 데이터 삭제.

(5) Queue안의 모든 항목 삭제.


3. 사용 예시
Posted by 루시엔시엘

댓글을 달아 주세요