스택(Stack)
- LIFO(Last In, First Out) 원리에 따라 작동하는 선형 자료구조
- 가장 마지막에 추가된 요소가 가장 먼저 제거됨.
- 주요 연산
push: 스택의 맨 위에 요소를 추가함
pop: 스택의 맨 위에서 요소를 제거하고 그 요소를 반환함
peek: 스택의 맨 위 요소를 반환하지만 제거하지는 않음
isEmpty: 스택이 비어있는지 확인함
struct Stack<Element> {
private var storage: [Element] = []
mutating func push(_ element: Element) {
storage.append(element)
}
mutating func pop() -> Element? {
return storage.popLast()
}
func peek() -> Element? {
return storage.last
}
var isEmpty: Bool {
return storage.isEmpty
}
}
// 사용 예시
var stack = Stack<Int>()
stack.push(1)
stack.push(2)
stack.push(3)
print(stack.peek() ?? "스택이 비어있습니다.") // 3 출력
print(stack.pop() ?? "스택에서 꺼낼 요소가 없습니다.") // 3 출력
print(stack.pop() ?? "스택에서 꺼낼 요소가 없습니다.") // 2 출력스택(Stack)이 사용되는 경우
- 역순 문자열 생성
문자열의 각 문자를 차례대로 스택에 넣고, 이후에 하나씩 꺼내면 문자열이 역순으로 정렬됨.
- 괄호 검사
여는 괄호를 만날 때마다 스택에 넣고, 닫는 괄호를 만나면 스택에서 꺼내어 짝이 맞는지 확인함.
- 함수 호출
프로그램에서 함수를 호출할 때 호출 스택을 사용하여 호출된 함수의 주소를 저장하고, 함수가 종료되면 스택에서 해당 함수의 주소를 꺼내어 제어를 반환함.
- 웹 브라우저 방문 기록 관리
사용자가 방문한 페이지를 스택에 넣고, 사용자가 뒤로 가기를 할 때 스택에서 꺼내어 이전 페이지로 돌아감.
큐(Queue)
- FIFO(First In, First Out) 원리에 따라 작동하는 선형 자료구조
- 가장 먼저 추가된 요소가 가장 먼저 제거됨.
- 주요 연산
enqueue: 큐의 뒤쪽에 요소를 추가함
dequeue: 큐의 앞쪽에서 요소를 제거하고 그 요소를 반환함
peek: 큐의 맨 앞 요소를 반환하지만 제거하지는 않음
isEmpty: 큐가 비어있는지 확인함- 대기열 관리, 프린터의 인쇄 작업 스케줄링, 네트워크 요청 처리 등에 사용됨.
struct Queue<Element> {
private var storage: [Element] = []
mutating func enqueue(_ element: Element) {
storage.append(element)
}
mutating func dequeue() -> Element? {
guard !storage.isEmpty else { return nil }
return storage.removeFirst()
}
func peek() -> Element? {
return storage.first
}
var isEmpty: Bool {
return storage.isEmpty
}
}
// 사용 예시
var queue = Queue<String>()
queue.enqueue("A")
queue.enqueue("B")
queue.enqueue("C")
print(queue.peek() ?? "큐가 비어있습니다.") // "A" 출력
print(queue.dequeue() ?? "큐에서 꺼낼 요소가 없습니다.") // "A" 출력
print(queue.dequeue() ?? "큐에서 꺼낼 요소가 없습니다.") // "B" 출력큐(Queue)가 사용되는 경우
- 데이터 처리 순서 유지
문서 인쇄, 작업 스케줄링 등 순서대로 처리해야 하는 작업에 큐를 사용함.
- 대기열 관리
은행, 티켓 카운터, 콜센터 등에서 서비스를 기다리는 대기열을 관리할 때 큐를 사용함.
- 너비 우선 탐색(BFS)
그래프나 트리에서 너비 우선 탐색을 수행할 때 큐를 사용하여 방문할 노드를 관리함.
- 버퍼(buffer)
데이터를 전송하거나 받는 동안 일시적으로 데이터를 저장하는 버퍼에 큐를 사용할 수 있음.
- 캐시 구현
최근에 사용된 항목을 기억하고 오래된 항목부터 제거하는 캐시 알고리즘에 사용됨.
덱(Duque)
- 양쪽 끝에서 삽입과 삭제가 가능한 자료구조
- 스택과 큐의 일반화된 형태
- 주요 연산
pushFront: 덱의 앞쪽에 요소를 추가함
pushBack: 덱의 뒤쪽에 요소를 추가함
popFront: 덱의 앞쪽에서 요소를 제거하고 그 요소를 반환함
popBack: 덱의 뒤쪽에서 요소를 제거하고 그 요소를 반환함
peekFront: 덱의 맨 앞 요소를 반환하지만 제거하지는 않음
peekBack: 덱의 맨 뒤 요소를 반환하지만 제거하지는 않음
isEmpty: 덱이 비어있는지 확인함- 스크롤, 스테핑 기능이 있는 웹 페이지나 앱 인터페이스, 양방향 대기열 등에 사용됨.
struct Deque<Element> {
private var storage: [Element] = []
mutating func pushBack(_ element: Element) {
storage.append(element)
}
mutating func pushFront(_ element: Element) {
storage.insert(element, at: 0)
}
mutating func popBack() -> Element? {
return storage.popLast()
}
mutating func popFront() -> Element? {
guard !storage.isEmpty else { return nil }
return storage.removeFirst()
}
func peekFront() -> Element? {
return storage.first
}
func peekBack() -> Element? {
return storage.last
}
var isEmpty: Bool {
return storage.isEmpty
}
}
// 사용 예시
var deque = Deque<Int>()
deque.pushBack(1)
deque.pushFront(2)
deque.pushBack(3)
print(deque.peekFront() ?? "덱이 비어있습니다.") // 2 출력
print(deque.peekBack() ?? "덱이 비어있습니다.") // 3 출력
print(deque.popFront() ?? "덱에서 꺼낼 요소가 없습니다.") // 2 출력
print(deque.popBack() ?? "덱에서 꺼낼 요소가 없습니다.") // 3 출력덱(Deque)이 사용되는 경우
- 양방향 큐
데이터가 양쪽 끝에서 추가되거나 제거되어야 할 때 덱을 사용함.
ex) 스크롤 기능이 있는 사용자 인터페이스에서 최근 항목을 양쪽 끝에 추가할 수 있음.
- 양방향 탐색
리스트의 양쪽 끝에서 동시에 탐색을 시작해야 할 경우 덱을 사용하여 효율적으로 탐색할 수 있음.
iOS Developer