728x90
반응형
원형 큐란?
- 원형 큐(Circle Queue)는 큐의 한 형태이다.
- 큐를 배열로 구현을 하게 될 경우, 데이터를 삭제하게 되면 삭제한 부분은 더 이상 사용할 수 없다.
- 이 경우 삭제를 배열 끝까지 하게 되면 그 큐는 더 이상 사용할 수 없게 된다.
- 이때 사용하는 것이 바로 원형 큐이다.
원형 큐의 특징
- 원형 큐의 경우, 일반적으로 배열로 구현한다.
- 원형 큐는 배열의 앞과 끝을 이어 배열에 끝에 도달했다면 다시 처음으로 되돌아오는 큐를 의미한다.
- 배열의 앞을 가리키는 변수(front)와 배열의 끝을 가리키는 변수(rear)를 통해 데이터를 삽입하고 삭제한다.
- 데이터를 삽입할 때마다 rear가 한 칸 증가한다.
- 데이터를 삭제하면 front가 한 칸 증가한다.
- 만일 rear가 배열의 끝에 도달했는데, 배열의 시작이 비어있다면 rear의 인덱스는 0을 가리킨다.
- 원형 큐는 큐의 특성을 지니고있어 선입선출을 유지한다.
- 원형 큐의 연산은 삽입, 삭제, 맨 앞의 값 읽기, 원형 큐가 꽉 차있는지, 원형 큐가 비어있는지 확인이 있다.
시간복잡도
- 삽입(Enqueue)
- 원형 큐에 값을 넣고 rear의 값을 1 증가한다.
- 따라서 시간복잡도는 O(1)이다.
- 삭제(Dequeue)
- 원형 큐의 값을 제거하고 front의 값을 1 증가한다.
- 따라서 시간복잡도는 O(1)이다.
- 맨 앞의 값 읽기(Peek)
- 원형 큐의 rear에 해당하는 값을 읽어온다.
- 따라서 시간복잡도는 O(1)이다.
- 배열이 꽉 차있는지(IsFull)
- rear와 front의 위치를 통해 배열이 꽉 차있는지 확인한다.
- 따라서 시간복잡도는 O(1)이다.
- 배열이 비어있는지(IsEmpty)
- rear와 front의 위치를 통해 배열이 비어있는지 확인한다.
- 따라서 시간복잡도는 O(1)이다.
원형 큐의 장단점
- 장점
- 큐를 활용하기에 선입선출 구조이며, 배열로 구현된 큐처럼 공간을 낭비하지 않아도 된다.
- front와 rear를 활용해 인덱스만을 관리해주면 되기에 비교적 구현이 쉽다.
- 단점
- 배열로 구현하기 때문에 크기가 고정되어 있어, 너무 크게 선언을 하게 되면 메모리를 낭비하게 된다.
- front와 rear를 통해 배열이 비어있는지, 꽉차있는지에 대한 추가적인 구현이 필요하다.
예제
package QueueExample
class CircleQueue(size: Int) {
private val queueSize: Int
private var circleQueue = emptyArray<Int>()
private var rear: Int = -1
private var front: Int = -1
init {
queueSize = size;
circleQueue = Array(queueSize) { -1 }
}
fun isEmpty(): Boolean {
return rear == front && circleQueue[rear] == -1
}
fun isFull(): Boolean {
if(rear == front -1 && circleQueue[front] == -1)
return false
return rear == front - 1 || (front == -1 && rear == queueSize - 1) || (rear == front && front != -1 && circleQueue[front] != -1)
}
fun enqueue(element: Int): Boolean {
return if(isFull())
false
else
{
rear = if(rear + 1 == queueSize) 0 else rear + 1
circleQueue[rear] = element
true
}
}
fun dequeue(): Int {
return if(isEmpty())
-1
else
{
front = if(front + 1 == queueSize) 0 else front + 1
var data = circleQueue[front]
circleQueue[front] = -1
data
}
}
}
fun main() {
var circleQueue = CircleQueue(5)
circleQueue.enqueue(1)
circleQueue.enqueue(2)
println(circleQueue.isFull())
circleQueue.enqueue(3)
circleQueue.enqueue(4)
circleQueue.enqueue(5)
println(circleQueue.isFull())
println("원형 큐에서 꺼낸 값 : ${circleQueue.dequeue()}")
println("원형 큐에서 꺼낸 값 : ${circleQueue.dequeue()}")
println("원형 큐에서 꺼낸 값 : ${circleQueue.dequeue()}")
println(circleQueue.isEmpty())
println("원형 큐에서 꺼낸 값 : ${circleQueue.dequeue()}")
println("원형 큐에서 꺼낸 값 : ${circleQueue.dequeue()}")
println(circleQueue.isEmpty())
}
728x90
반응형
'개념정리 > 자료구조' 카테고리의 다른 글
[자료구조] 연결리스트(Linked List)란? (0) | 2023.11.25 |
---|---|
[자료구조] 덱(Deque)이란? (1) | 2023.11.22 |
[자료구조] 큐(Queue)란? (0) | 2023.11.15 |
[자료구조] 스택(Stack)이란? (1) | 2023.10.30 |
[자료구조] 배열(Array)란? (2) | 2023.10.27 |