Language 자료구조 Part2. "큐"의 모든 것.

자료구조가 무엇인지는 본 블로그의 "자료구조알고리즘" 항목의
 
첫번째 글에 자료구조에 대한 설명이 대략 있음을 알린다.
 
 
Part2 큐
--------------------------------------
 
큐(Queue) 는 동적배열과 마찬가지로 상당히 구현이 쉬운 자료구조중 하나이다.
 
큐는 간단히 어떠 한 기억장소에 쓰고자 하는 데이타들을 차례로 기억 시킨 뒤,
 
그 데이타들을 입력 한 순서대로 차례로 다시 읽어오는 기법이다.
 
즉, 큐는 FIFO(First In First Out)의 원리대로 동작하는 자료 구조인데,
 
FIFO가 무슨뜻인가 하면, 먼저들어간 자료가 먼저나오고, 늦게들어간 자료가 늦게 나온다는 것이다.
 
필자는 맨처음 큐를 쇠파이프 라고 배웠다.
 
왜냐하면 쇠 파이프에 무언가를 넣고 쌓아두면 반대쪽 구멍으로 그 무언가 들이 내가 넣은 순서대로 나올 수 밖에 없기 때문이다.
 
이렇게 해 두면 이해가 쉬울 것이다.
 
넣은 순서대로 자료를 꺼내가므로 순서대로 처리해야 하는 자료를 임시적으로 저장하는 용도로 흔히 사용한다.
 
고속도로 톨게이트에 줄 서 있는 차들의 행렬이 큐의 대표적인 예인데 먼저 도착한 차가 먼저 빠져 나가고 늦게 도착한 차는 앞 차가 지나갈 때까지 기다려야 한다.
 
큐는 배열로 구현한 일자 큐( 선형 큐 라고 한다)와, 원형 큐 , 그리고 연결리스트로 구현 한 큐.
 
이렇게 크게 3가지로 나눌 수 있다.
(연결리스트로 구현 한 큐는 이 장에선 다루지 않고, 연결리스트의 강의 후 따로 다룰것이다.)
 
그리고 큐 에서 쓰이는 용어로는 front(앞, 전방) 과, rear(뒤, 후방)이 있으며,
 
이 둘은 배열의 데이타 들 중 다음으로 삭제될 위치와 다음으로 삽입될 위치를 가리키는 역활을 하며,
 
당연히 포인터로 구현 할 수 있겠지만, 배열을 이용한 큐 에서는 간단히 정수형변수로도 구현이 가능하다.
 
ex) front = 7 -> 배열[7] -> 8번째 방에서 다음으로 삭제된다.
 
보통 front는 자료들 중 맨 앞을, rear는 맨 뒤 자료의 다음칸을 가리킨다.
 
 
또다른 용어로 삽입을 put, 출력(빼내기)을 get 이라 한며,
 
init 를 초기화(시작 전 셋팅정도)로 정의한다.
(init는 큐 뿐만 아니라 스택외 다른 자료구조에서도 시작전 셋팅정도의 초기화의 의미로 쓰인다.)
 
------참고로 사람마다 front 와 rear를 head(머리)와 tail(꼬리)로,
put과 get을 insert(삽입)과 delete(삭제)로 부르기도 한다.-----------
 
용어들은 아래를 참고하면 충분히 이해를 할 수 있을 것이다.
 
 
당연히 선형 큐가 구현하기 가장 쉬운 듯 보이므로, 선형 큐 부터 보도록 하자.
 
 
1. 선형 큐
 
선형 큐는 구현이 가장 쉽다. 동작 원리로는 아래의 그림과 같다.
-------------------------------
f,r
[　][　][　][　][　] (배열을 초기화 했다. - 비어있다 (front와 rear가 선두인 0을 가리킨다.)
　　　　 ↓
 f　 　 　r
[ 1 ][ 2 ][　][　][　] (1과 2를 삽입했다 (1과 2를 put 했다))
　　　　 ↓
 　　 f  　r
[　][ 2 ][　][　][　] (1을 삭제했다(빼내서 사용했다) (1을 get했다))
　　　　 ↓
 　　 f  　　　　　r
[　][ 2 ][ 3 ][ 4 ][　]　　(3, 4를 삽입했다 (3, 4 put))
　　　　 ↓
 　　　　　　 f   r
[　][　][　][ 4 ][　]　　(2, 3을 삭제했다 (빼내서 사용했다) (2, 3 get))
　　　　 ↓
 　　 　　　　f  　　　r
[　][　][　][ 4 ][ 5 ]　　(5를 삽입했다 (5 put))
-------------------------------------
보다시피 삽입을 할 때에는 r이 한칸씩 오른쪽으로,
 
삭제를 할 때에는 f가 한칸씩 오른쪽으로 간다는 걸 알 수 있다.
 
이렇게 계속 삽입, 삭제를 반복하다보면 금새 배열의 뒤쪽 공간이 부족해 진다는 걸 알 수 있다.
 
위 그림에선 5가 삽입 된 후 rear 가 배열의 경계를 넘어서며, 다음 삽입 동작을 할 수 없게 된다.
 
배열의 크기만큼 자료가 들어 있지도 않은데 기억 공간이 부족해진 것이다.
 
큐의 자료는 빈번하게 삽입, 삭제되므로 배열 크기를 늘리는 것으로는 이 문제를 근본적으로 해결할 수 없다.
 
하지만 rear가 경계를 넘어서면 4, 5 를 복사하여 앞으로 보내도록 구현하면
 
[ 4 ][ 5 ][　][　][　] 로 다시 나타 낼 수 있는데,
 
큐가 찰 때마다 이런 식으로 매번 복사를 한다면 느리고 비효율적이다.
 
그래서 이 방법 대신 포인터가 배열의 끝에 닿았을 때 앞쪽으로 보내어 배열을 원형(Circular)으로 연결하는 방법을 많이 사용하는데 이는 % 연산자로 간단하게 구현할 수 있다.
 
2. 원형 큐
 
원형큐의 front와 rear는 원형의 큐를 빙글 빙글 돌아가면서 자료를 삽입하고 삭제한다.

그림과 같다.
 
//시작--------------------이 줄은 소스에 포함되지 않습니다.
 

·미리보기 | 소스복사·

1. #include<stdio.h>   
2. #define MAX 10   
3. int queue[MAX];   
4. int front, rear;   
5. int put(int k)   
6. {   
7.  if((rear+1)%MAX == front)   
8.  {   
9.   printf("nQueue Overflow.");   
10.   return -1;   
11.  }   
12.  queue[rear] = k;   
13.  rear = ++rear % MAX;   
14.  return k;   
15. }   
16. int get(void)   
17. {   
18.  int i;   
19.  if(front == rear)   
20.  {   
21.   printf("nQueue Underflow.");   
22.   return -1;   
23.  }   
24.  i = queue[front];   
25.  front = ++front % MAX;   
26.  return i;   
27. }   
28. void print_queue()   
29. {   
30.  int i;   
31.  for(i = front; i!=rear; i= ++i%MAX)   
32.  {   
33.   printf("%3d",queue[i]);   
34.  }   
35.  printf("n");   
36. }   
37. void init_queue()   
38. {   
39.  front = rear = 0;   
40. }   
41. void clear_queue()   
42. {   
43.  front = rear;   
44. }   
45. void main()   
46. {   
47.  init_queue();   
48.  put(1);      // 자료 입력   
49.  put(2);   
50.  put(3);   
51.  put(4);   
52.  put(5);   
53.  put(6);   
54.  put(7);   
55.  put(8);   
56.  put(9);   
57.  put(10);   
58. }  

 
//끝--------------------이 줄은 소스에 포함되지 않습니다.
init_queue 는 큐를 초기화 하며(시작시 셋팅의 의미가 있다),
 
clear_queue 도 큐를 초기화 한다(사용 도중 데이타를 초기화 하는 의미가 있다).
 
오버플로우(overflow)는 큐가 꽉 찬 상태에서 더 입력을 하려 했을 경우 나오며,
 
언더플로우(underflow)는 큐가 비어있는 상태에서 더 출력을 하려 했을 경우에 나온다.
 
큐가 꽉 찬 상태는 그림과 같다.


그림처럼 (rear+1)%갯수 == front 일 때 큐가 꽉 찬 상태이며,
 
front == rear 일 때 비어있는 큐가 된다.
(맨 처음엔 front == rear == 0 이다)
 
head가 tail과 같은 상태는 큐가 빈 상태와 같으므로 두 포인터의 값만 비교해서는 큐의 정확한 상태를 알 수 없다.
 
그래서 head 바로 앞의 한 칸은 미사용으로 남겨 두어 tail이 head의 바로 앞쪽에 있을 때,
즉 tail이 head-1일 때를 큐가 가득찬 것으로 정의한다.
 
이렇게 하면 기억 장소 하나를 쓰지 못하는 약간의 낭비가 발생하기는 하지만 상태를 정확하게 판별할 수 있다.
 
-------------------------------------------
하지만, 배열로 큐를 구현하는 것에는 한계가 있으며, 상당히 불편하다.
 
이유인 즉, 배열의 크기보다 더 많은 데이타가 삽입되면 큐가 가득차게 되어 쓸 수 없다는 점.
(오버플로우 라 한다)인데, 이를 고치기 위해 최대크기를 충분히 할당 한다해도, 무한히 커지지는 않기 때문에 언제든지 부족한 상황이 나올 수 있다.
 
물론 동적 배열을 쓸 수도 있겠지만 여러 가지 상황으로 볼 때 어울리지 않는다.
 
또한 배열은 연속적인 메모리 공간을 차지하는 직선적인 구조를 가지기 때문에 최대 크기만큼 충분한 용량을 확보했더라도 삽입점이 금방 배열 끝에 이르게 된다.
 
그래서 처음과 끝을 인위적으로 연결하여 원형으로 만들어 직선의 기억 공간을 재사용해야 하는 불편함이 있다.
 
뿐만 아니라 원형 구조이다 보니 가득찬 경우와 빈 경우가 잘 구분되지 않아 한칸을 버리거나 별도의 플래그를 도입하는 기법도 동원되어야 한다.
 
이러한 이유들 때문에 연결리스트로 구현한 큐를 선보이는데,
 
이는 이러한 불편함을 해결 할 수 있다.
 
연결리스트로 구현 한 큐는 차후 연결리스트를 배운 후 또 다시 공부 해 보도록 하자.
 
-----------------------------------
07.09.04
written by 선린인고 20420 전호근.