큐의 이해
오늘 정리해볼 내용은 큐 이다
우리는 앞서 스택에 대해 정리해 보았다
스택이 후입선출 자료구조라면 큐는 선입선출 (FIFO)형 자료구조 이다
흔히 우리가 일상애서 보는 "줄서기"와 유사하다고 볼수있다
우리가 놀이기구 줄서기를 할떄 당연히 1번 으로 줄을 선사람은 1번으로 놀이기구를 탈것이다
이것이 큐의 기본적인 구조이다
그러면 이재 큐의 ADT를 정의해보자
큐의 ADT
큐 자료구조의 ADT룰 살펴보자
void QueueInit(Queue * pq)
-큐의 초기화를 진행
-큐 생성후 제일 먼저 호출되어야함
int QIsEmpty(Queue * pq)
-큐가 빈 경우 1 아니면 0을 반환한다
void Enqueue(Queue * pq, Data data)
-큐에 데이터를 저장한다
-매개변수 data로 저장된 값을 저장
int Dequeue(Queue * pq)
-저장순서가 가장 앞선 데이터를 삭제한다 (처음으로 줄선 사람을 입장시킨다)
-삭제된 데이터는 반환한다
-본 함수의 호출을 위해 데이터가 1개 이상임을 보장한다
int QPeek(Queue * pq)
-저장순서가 가장 앞선 데이터를 반환하되 삭제하지 않는다 (처음으로 줄선 사람의 값만 확인)
-본 함수의 호출을 위해 데이터가 1개 이상임을 보장한다
ADT구현에 앞서 큐의 2가지 형태에 대해 알고가자
큐는 크게 2가지 형태로 나뉘게 된다
1.배열 큐
2.연결 리스트 큐
그러면 각각의 큐가 어떻게 형성되는지에 대해 알아보자
배열 기반 큐
그림을 통해 천천히 정리해 나가보자
먼저 배열을 선언했다 배열을 줄서는 라인이라고 생각해보자
F,R은 줄에서 각각 처음과 마지막을 나타내는 역활을 한다
먼저 줄에 데이터 1개가 들어왔다고 생각해보자
지금 줄을 서고 있는 데이터는 A혼자이니 F,R모두 A를 가리킬 것이다
이상황 에서 줄에 데이터 1개가 더왔다고 생각해보자
F는 여전히 첫번쨰인 A를 가리키고 있다 하지만 R은 줄에 맨마지막인 B를 가리키고 있다
여기서 A가 반환되면 어떻게 될까?
그림처럼 F가 뒤로 1칸이동되고 배열의 처음칸이 비어버렸다
우리는 데이터가 추가 되거나 삭제될떄 F,R에 이동에 대해 알아보았다
그러면 이제 1가지 상황을 놓고 이야기 해볼건데 먼저 1가지 사실에 대해 이야기 하고 가자
우리는 포인터나 배열을 공부할떄 비어있는 값은 어떤 재앙을 불러올지 모르니
0이나 NULL값으로 초기화 시킨다고 공부했다 하지만 여기서는 빈 배열 이나 포인터를 그냥
비어있는 상태로 나둘것이다 이것은 실무에서도 코드를 구성할떄 사용하기에 비어있는 포인터나 배열에 예민하게 반응할 필요가 없음을 기억하자
그러면 그림을 통해 계속 정리해 가보자
이처럼 배열을 만들고 계속해서 데이터를 추가하다 보면 언제가 그림처럼 더이상 데이터를 담을 공간이
부족해 지는 순간이 올것이다 그렇다면 우리는 어떻게 이문제를 해결할수 있을까?
답은 우리가 앞서 비워놨던 배열들을 재사용 하는거다.
그렇다면 어떻게 우리는 앞에 빈배열들을 활용할수 있는지는 다음장에서 정리해 보겠다
