큐의 정의
큐는 앞뒤가 뚫린 긴 통.
입력과 출구가 다르다. 뒤에서 뭔가를 집어 넣고 앞에서 그것을 빼낸다.
먼저 들어온 것이 먼저 나온다.
->> FIFO (First IN First OUT)
구현 방법:
배열을 이용하는 방법, 연결 리스트를 이용하는 방법
조작 방법:
put동작, get동작
- put 동작 : 자료를 집어 넣는 동작 - 뒤(rear)에서
- get 동작 : 자료를 얻는 동작 - 앞(front)에서
배열을 이용한 큐의 구현
1. 자료를 저장하기 위한 배열
2. 앞과 뒤를 가리키는 변수
#define MAX 10
int queue[MAX];
int front, rear;
3. put 연산과 get 연산
int put(int k)
{
rear가 한계를 넘었는지 검사, 넘었다면 오버플로우 처리
queue[++rear] = k;
}
int get(void)
{
큐가 비어있지 않은가? 비어 있으면 언더플로우 에러 처리
return queue[front++];
}
배열로 구현한 큐의 문제점
put 연산과 get 연산을 계속하다 보면 rear와 front는 계속 증가하게 되고, 결국에는 큐가 전체적으로 배열 속을 이동하게 된다. 이는, 실제로 저장된 자료가 몇 개 되지 않지만, rear가 배열의 한계를 넘어서서 오버플로우 에러를 발생할 수 있다.
그래서, rear가 배열 끝에 이르렀는지를 점검하기 위해서 배열의 끝에 닿았을 경우, 큐의 내용 전체를 복사해서 배열의 앞부분으로 옮기는 동작이 필요하게 된다.
문제점 해결 방법 : 원형 큐(Circular Queue)를 이용
원형 큐는 배열의 첫 요소와 마지막 요소가 붙어서 마치 뱀의 머리가 꼬리를 물고 있는 듯한 모양이다.
제일 처음 요소의 앞 요소는 제일 마지막 요소이고, 제일 마지막 요소의 뒷 요소는 제일 앞 요소로 조작하게 된다. 이 조작은 나머지 연산(%)을 이용하여 간단하게 구현된다.
원형의 자료 구조는 끝이라는 개념이 없다. 계속 돌기만 할 뿐이다. 그래서 배열을 이용할 때의 큐처럼 이동하여서 한계를 넘는 경우는 없다. 계속 회전만 할 뿐이다.
댓글