CH7큐의 이해와 ADT정의(1)
큐(Queue)를 마지막으로 선형 자료구조는 끝이다.
만약 큐까지의 코드나 예제가 어렵다면 이를 마치고 복습하기 좋은 타이밍이다.
비선형자료구조는 포기하는 사람이 생기는 구간이다. 선형자료구조에 대한 이해를 확실히 하고 넘어가자.
스택보다 큐가 구현에 아주 약간… 어렵다. 하지만 큐는 활용적 측면에서는 스택만큼 어려운게 없다. 큐를 활용하는 영역 자체가 보다 단순하기 때문임.
우리 주변에서 큐 구조를 갖고 있는 대표적 현상은 줄서기이다. 줄서기는 선착순으로 먼저 온 사람이 서비스를 받는다. 즉 큐는 FIFO의 자료구조이다. 스택과 다르게 양쪽으로 뚫려있어서 먼저 들어온 데이터가 먼저 나간다.
큐의 기본 연산은 다음의 두가지이다.
큐는 OS에서 프로세스, 쓰레드 관리, 스케쥴링 등에 활용이 된다. 따라서 OS이해에는 자료구조에 대한 이해가 선행되어야 한다.
그러므로 enqueue와 dequeue의 구현에만 관심을 갖지 말고, OS의 관점에서도 큐 자료구조를 생각하면서 학습하면 후에 도움이 된다.
큐의 ADT정의를 보자. 이 ADT를 바탕으로 큐도 배열과 연결리스트 기반으로 구현가능하다.