Queue (큐) – 자료구조

지난 번에 작성했던 스택(stack)에 이어서 Queueu(큐) 자료구조에 대한 설명입니다.

목차

• 1. Queue 란?
• 2. Queue 큐에 대표적인 구현 2가지 방법
• 3. Queue 대표적인 함수

1. Queue 란?

• 메모리 안에 데이터들을 더욱 효과적으로 다루기 위해 만들어진 데이터 참조 방식이라고 합니다.
• First in First Out (FiFo)라고 부르며, 스택과 반대로 제일 먼저 들어왔던 값이 제일 먼저 나갑니다.

기존에 스택과 달리 수평으로 예시를 들었으며, 스택의 경우 뒤에 들어온 데이터부터 자료 제거가 되지만 Queue-큐 같은 경우에는 먼저 들어온 데이터부터 제가 되기 때문에 A, B 순으로 값이 제거 됩니다.

사진에서 볼 수 있듯이 First A 값이 진행되면 next는 B로 이동하며, 이후 -> C 이렇게 진행 됩니다. 옆으로 진행 중 A 값이 제거 되어도 next는 다시 처음으로 돌아가지 않고 4번째 칸에 머물러 있습니다.

Queue 실제 생활에서 사용되는 예로는 마트 같이 계산 하는 곳에서 먼저 온 사람이 빠지고, 프로세스 스케줄링, 대기열 관련해서 예시를 생각하면 쉽게 이해를 할 수 있습니다.

2. Queue 큐에 대표적인 구현 2가지 방법

• 정적인 어레이 특징은 구현이 쉽지만 고정된 Queue크기로 크기가 넘어갈 경우에는 에러가 발생할 수 있습니다.
• 동적인 어레이 특징은 자유로운 Queue 크기가 있지만 반대로 구현이 약간 어렵습니다.

3. Queue 대표적인 함수

• Enqueue : 큐에 값을 집어 넣는 함수 입니다. 스택으로 보면 push로 생각을 하면 됩니다.
• Dequeue : 큐에서 값을 빼내는 함수로 스택에서 보면 POP으로 보면 됩니다.
• 그 외에는 size를 확인활 수 있는 함수로 Queue의 크기를 확인 가능합니다. 그리고 Enpty로 큐가 비었는지 확인할 수 있습니다.

이외에도 순환을 하는 Circular Queue가 있으며, Priority Queue(우선순위 큐가 있습니다.) 우선순위 큐의 경우 원래는 먼저 들어온 순서로 값이 제거 되지만 우선순위가 있으면 다시 재배열 되어 우선 순위가 높은 순으로 값이 제거 된다고 합니다.

이전에 공부 했던 스택에 대한 내용이 궁금할 경우 링크 참고.