큐(Queue)
큐(Queue)
스택과 더불어 매우 빈번하게 이용되는 자료 구조가 큐(queue)이다.
선형(linear)구조라는 점에서는 지금까지 배워온 선형 배열, 연결 리스트, 그리고 스택과 같은 성질을 가지고 있지만, 스택과는 어떻게 보면 반대인 특성을 가지고 있다.
- 큐는 선입선출(FIFO; First-In First-Out),
"파이포"라고도 많이 부른다.
환형 큐(Circular Queue)
큐(queue) 또한 스택과 마찬가지로 컴퓨터 시스템을 구성하는 많은 곳에서 이용된다.
ex) 어느 컴퓨터 시스템에서 서로 다른 응용 프로그램들이 프린터에 인쇄할 문서를 보낸다고 생각해보자. 시스템(보다 명확하게는 운영체제) 내에서는 프린팅 큐라는 자료 구조를 유지하여 프린터에 보내진 인쇄할 문서들을 유지할 수 있다.("대기열"이라는 말이 이런 모습을 잘 설명한다.)
또 다른 예로는, 네트워크 인터페이스를 통하여 도착하는 패킷(packet)들도 큐에 쌓여서 도착한 순서대로 적적한 응용 프로그램에게 데이터를 보내주는 기능을 운영체제 내에서는 구현하고 있을 수 있다.
큐에 담을 수 있는 데이터의 양이 무한할 수 없는데, 만약 큐에 담을 수 있는 원소의 개수의 상한을 미리 정하고 이를 지킬 수 있다면, 선형 배열을 이용해 큐를 효과적으로 구현할 수 있다. 한쪽 끝과 다른 쪽 끝이 서로 맞닿아 있는 모습으로 생각하고, 큐의 맨 앞과 맨 뒤를 가리키는(즉, 원소를 넣을 쪽의 배열 인덱스와 꺼낼 쪽의 배열 인덱스를) 기억해 두면, 저장소를 재활용하면서 큐를 관리할 수 있다.
우선순위 큐(Priority Queue)
큐에 원소를 추가하는 연산은 다른 점이 없되, 큐에서 원소를 꺼내는 원칙은 원소들 사이의 우선순위에 따르는 자료구조
ex) 운영체제에서 CPU 스케줄러를 구현할 때, 현재 실행할 수 있는 작업들 중 가장 우선순위가 높은 것을 골라 실행하는 알고리즘 같은 것들
먼저 구현하는 데에는 두 가지의 서로 다른 접근 방법을 생각할 수 있다.
- 큐에 원소를 넣을 때(enqueue 할 때) 우선순위 순서대로 정렬해 두는 방법
- 큐에서 원소를 꺼낼 때(dequeue 할 때) 우선순위가 가장 높은 것을 선택하는 방법
본 문서는 프로그래머스 어서와! 자료구조와 알고리즘 강의를 수강하고 정리했습니다.