큐는 줄이다. 여기서 줄은 다른 의미의 줄이 아니라 우리가 티켓을 구입하기 위하여, 혹은 편의점에서 담배를 사기 위하여 순서를 기다리는 의미로 즉, 줄을 선다라는 내용의 줄이다. 이 줄을 선다는 것은 사회적인 상식이 있는 사람이라면 당연히 알고 있으리라 생각이 되기 때문에 더 설명을 하기 어려울 정도이다.

위의 이미지는 아래의 링크에서 가져옴.
http://www.metro.co.uk/news/world/147125-slow-response-could-kill-1-5million-in-burma
미얀마에서 사람들이 물을 구하기 위해 줄을 서 있는 장면이다.

이들은 물을 구하기 위하여 줄을 서 있는다.

OS 카테고리에서 CPU 스케쥴링 이야기를 할 때, 프로세스들은 Ready 큐에서 자신이 프로세싱 되기를 기다렸다. 지금 여기서는 자료구조이기 때문에 프로세싱을 기다리는 것이 아니라 처리할 자료들을 줄을 세워놓는 것이라고 생각을 하면 된다.

큐와 같은 것을 다른 말로 FIFO라고 표현을 하기도 하는데, 이는 First In First Out의 의미로 가장 먼저 들어온 것이 가장 먼저 나간다는 뜻이다.

위의 사진을 예로 들자면 스택의 경우 오른쪽에서 세번째에 있는 파란 통을 들고있는 아이가 필요하면 뒤에 있는 2 사람을 먼저 밖으로 빼고, 꼬마 아이가 나온 다음 다시 두 사람이 줄을 서야 했다. 큐의 경우 같은 아이가 필요하다면, 아이 앞에있는 모든 사람을 빼고, 아이를 불러온 다음 다시 사람들을 순서대로 세워야 하는 것이다.

순수한 큐는 2가지 방식으로 생각을 해볼 수 있다.
다시 위의 사진을 예로 들자면... 자꾸 힘들었던 사람들 사진을 예로 들어서 미안하다. 앞에서 한명씩 물을 받아간다고 했을 때, 기존의 사람들이 현재 위치에 그대로 서서 기다리면서 자신의 차례가 되면 앞으로 빈 공간에 점점 길어지는 방식과 한명이 물을 받아가면, 다른 사람들도 한칸씩 앞으로 걸어 나오는 방식이 있다. 당연히 상식적으로 후자의 방법이 정상적이라 생각을 하겠지만, 이를 프로그래밍적으로 생각을 해보자.

보통 큐라는 것은 일정 메모리 공간을 잡아두고 시작을 한다. (하나의 배열이라고 생각을 해보자.)
a[0]~[9] 까지의 10개가 들어가는 배열이라고 가정을 한다면, 여기서 0번째의 자료가 밖으로 나가면 1번부터 9번까지 한칸씩 앞으로 이동을 해야한다. 그런데 그냥 한번에 한칸씩 툭! 하고 이동을 하는 것은 아니다.
1번이 0번으로 이동, 2번이 1번으로 이동, 이러한 방법을 이용하여 이동하여야 한다. 따라서 한칸 이동을 한다는 것이 연산적으로 제법 많은 일을 처리해야하는 문제점을 가지고 있는 것이다.

이 문제를 해결하는 방법으로 가장 쉽게 0번지를 가리키는 포인터를 하나가 진행이 될 때마다, 다음 배열을 가리키도록 메모리 번지수의 값을 더해주는 것이다. 하지만 그렇게 하여 생겨나는 문제점은 무엇인가? 시작번지를 가리키는 포인터가 0에서 1로 이동을 하는 순간 해당 배열은 1~9까지 사용이 가능한 배열이 되어버린 것이다. 하나의 데이터를 처리하고 나면, 빈 칸으로 다음 데이터가 들어올 수 있어야 하는데, 이 것이 불가능하게 되어버린 것이다.

이 문제점을 해결하기 위해 생긴 것이 순환 큐라는 것이다.

http://polisoftdesign.com/blog/
위의 이미지는 위의 링크에서 가져옴.

순환 큐의 특징은 Tail 이 가리키는 위치를 보자. Null인 곳이다. 추가와 삭제가 위의 이미지처럼 동작하는 것이다.

* 여기서 문제, 위의 이미지와 같이 고정된 크기의 순환 큐에서 아주 심각한 문제를 발생시킬 수 있는 것이 무엇인가?
* 고정된 크기를 가지는 큐에서 발생할 수 있는 문제점은 무엇이 있는가?



설명이 워낙 뛰어나서 질문은 없으리라 생각되지만 질문은 댓글로 남겨주세요.
저작자 표시 비영리 변경 금지
신고
by 가우초 2011.09.25 15:37
| 1 |