이번에는 스택에 이어서 큐(Queue)에 대해 정리해보려고 합니다.
Queue(큐)
- 기억나실지 모르겠지만 iOS의 셀의 재사용 내용에서 간단하게 큐를 설명하긴 했었는데요! 이번에는 큐에 대해서 본격적으로 정리해보도록 하겠습니다.
- 큐란 스택(Stack)과 마찬가지로 컴퓨터의 기본 자료구조 중 하나로 먼저 들어온 데이터가 먼저 나가는 구조로 되어 있습니다. 즉, FIFO(First-In First-Out) 선입선출입니다.
- 이해하기 쉽게 예를 들어 보자면 매표소에서 표를 사기 위해 줄을 선 사람들을 생각하시면 됩니다. (먼저 줄을 선 사람이 먼저 표를 살 수 있으니까요!)
- 큐는 한쪽에서는 데이터가 추가되고 한쪽에서는 데이터가 삭제되는 구조를 가지고 있습니다.
- 스택과 다른점은 스택의 경우 삽입과 삭제가 한쪽 에서 일어나지만 큐의 경우는 삽입과 삭제가 다른 쪽 에서 일어난다는 점입니다!
- 큐에서 삽입(Enqueue) 이 일어나는 곳을 Rear 라고 하며 삭제(Dequeue) 가 일어나는 곳을 Front 라고 합니다.
- Enqueue 연산은 큐의 맨 뒤에서 새로운 요소를 추가하고 Dequeue는 큐의 맨 앞에 있는 요소를 꺼내게 됩니다.
- 위에서 말씀드렸다시피 스택(Stack) 에서는 삽입 / 삭제가 한 곳에서 일어나 Top 이라는 변수가 한 개 필요했다면 큐의 경우 2개의 변수가 필요합니다!
- 큐를 사용하는 분야를 생각해보면 보통 컴퓨터를 이용한 현실 세계를 시뮬레이션할때 자주 사용된다고 합니다. (예를 들어서 은행에서의 사람들, 공항에서 이륙하는 비행기들 등이 있습니다!)
선형 큐
- 선형 큐는 제가 위에서 보여드렸던 큐를 생각하시면 되는데요!!
- 1차원 배열 이라고 생각하면 편하겠죠??
- 데이터가 증가하면 Rear의 값이 증하고 그 위치에 데이터를 저장하게 됩니다. 삭제할 때는 Front의 값을 하나 증가하고 Front의 위치에 있는 데이터를 삭제하게 됩니다!
- 하지만 선형큐의 문제점 이 있습니다 !
- Front와 Rear의 값이 계속 증가 하기 때문에 언젠가는 배열의 끝에 도달하게 될 거고 그렇게 되면 배열의 앞부분이 비어 있더라도 사용하지를 못합니다! 이를 해결하기 위해서는 배열의 요소들을 주기적으로 왼쪽으로 이동시켜야 하는데요. 그렇게 되면 시간도 걸리고 코딩이 복잡해지게 되겠죠??
- 위에서처럼 큐의 경우 가득 차게 되면 더 이상 데이터를 추가하는 것이 불가능해집니다!
원형큐
- 위에서 말씀드렸던 선형큐의 문제점을 보완하기 위한 것이 바로 원형큐 입니다!
- 큐를 원형으로 생각하여 Front와 Rear의 값이 배열의 끝에 도달하면 다음에 증가되는 값은 0이 되도록 하는 것입니다!
- 배열의 처음과 끝이 연결되어 있다고 생각하면 좋을 것 같습니다!! :)
- 하지막 공백 상태와 포화 상태를 구분할 수 없기 때문에 하나의 자리는 비워두는 것이 좋습니다.
큐(Queue) 구현해보기
Swift를 사용하여 이번에는 큐를 구현해보았습니다!
import Foundation
class Queue {
var arr: [Int] = []
func enqueue(_ element: Int) {
arr.append(element)
}
@discardableResult func dequeue() -> Int {
guard !arr.isEmpty else {
print("Queue가 비었기 때문에 dequeue가 불가능합니다.")
return 0
}
return arr.removeFirst()
}
func clear() {
arr.removeAll()
}
func sumOfQueueItems() -> Int {
let sum = arr.reduce(0){$0 + $1}
print("큐의 모든 값의 합은 : \(sum)")
return sum
}
func printSelf() {
print(" 현재 큐 ")
print("--- rear ---")
arr.forEach{ print($0) }
print("------------")
print("")
}
}
var queue = Queue()
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
queue.dequeue()
queue.printSelf()
queue.sumOfQueueItems()
이렇게 하면 어떠한 출력 값이 나오게 될까요??!!
큐는 스택과 반대로 먼저 들어온 값이 먼저 삭제되게 됩니다!
읽어주셔서 감사합니다!!
오늘은.. 여기까지..
'자료구조' 카테고리의 다른 글
| 자료구조(1) - 스택(Stack)이란 무엇일까? (0) | 2020.02.20 |
|---|
