스택(Stack)
struct Stack<T> {
private var array = [T]()
var isEmpty: Bool {
return array.isEmpty
}
var count: Int {
return array.count
}
mutating func push(_ element: T) {
array.append(element)
}
mutating func pop() -> T? {
return array.popLast()
}
var top: T? {
return array.last
}
}
큐(Queue)
- First In First Out
- 배열 2개를 이용한 큐(enqueue용과 dequeue용 2개)
- removeFirst()는 시간복잡도가 O(n)이므로, 시간복잡도가 O(1)인 reversed() 사용한 후 popLast()로 원소를 가져온다.
import Foundation
struct Queue<T> {
private var enqueueArray: [T] = []
private var dequeueArray: [T] = []
var isEmpty: Bool {
return enqueueArray.isEmpty && dequeueArray.isEmpty
}
var count: Int {
return enqueueArray.count + dequeueArray.count
}
mutating func enqueue(_ element: T) {
enqueueArray.append(element)
}
mutating func dequeue() -> T? {
if dequeueArray.isEmpty {
dequeueArray = enqueueArray.reversed()
enqueueArray.removeAll()
}
return dequeueArray.popLast()
}
var front: T? {
return dequeueArray.last ?? enqueueArray.last
}
}
덱(Deque)
- 덱(Deck) 이라고 읽는다
- 양방향 삽입, 삭제가 가능한 자료구조
- 위에 큐와 비슷하게 배열 2개를 이용해서 구현한 덱
import Foundation
struct Dequeue<T> {
private var enqueueArray: [T] = []
private var dequeueArray: [T] = []
var isEmpty: Bool {
return enqueueArray.isEmpty && dequeueArray.isEmpty
}
var count: Int {
return enqueueArray.count + dequeueArray.count
}
mutating func enqueueFront(_ element: T) {
dequeueArray.append(element)
}
mutating func enqueue(_ element: T) {
enqueueArray.append(element)
}
mutating func dequeue() -> T? {
if dequeueArray.isEmpty {
dequeueArray = enqueueArray.reversed()
enqueueArray.removeAll()
}
return dequeueArray.popLast()
}
mutating func dequeueBack() -> T? {
if enqueueArray.isEmpty {
enqueueArray = dequeueArray.reversed()
dequeueArray.removeAll()
}
return enqueueArray.popLast()
}
var front: T? {
return dequeueArray.last ?? enqueueArray.last
}
var back: T? {
return enqueueArray.last ?? enqueueArray.last
}
}
출처