문법 기초 공부 (스택&큐)

스택,큐

• 큐와 스택은 데이터에 대한 개념이다. Swift에서는 따로 큐와 스택을 지원하지 않는데, Array 등을 이용해 직접 구현할 수 있다.

-> Queue

큐

• First - In - First - Out(FIFO)
• 먼저 들어온 값을 먼저 내보내는 구조이다.

Swift Queue 구현

struct Queue<T> {
	private var queue: [T] = []
    
    public var count: Int {
    	return queue.count
    }
    
    public var isEmpty: Bool{
    	return queue.isEmpty
    }
    
    public mutating func enqueue(_ element: T){
    	queue.append(element)
    }
    
    public mutating func dequeue() -> T? {
    	return isEmpty ? nil : queue.removeFirst()
    }
}

var queue = Queue<Int>()
queue.enqueue(10)
queue.enqueue(20)
queue.dequeue() // 10

 

큐 사용 알고리즘 예시

1) 그래프의 BFS 탐색 함수

// 그래프의 BFS 탐색 함수
func bfs(start: Int, graph: [Int: [Int]]) {
    var visited = Set<Int>()       // 방문한 노드를 기록
    let queue = Queue<Int>()       // BFS를 위한 큐
    
    // 시작 노드를 큐에 추가하고 방문 표시
    queue.enqueue(start)
    visited.insert(start)
    
    while !queue.isEmpty {
        // 큐에서 노드를 꺼내서 처리
        let node = queue.dequeue()!
        print("Visited node: \(node)")
        
        // 현재 노드의 인접 노드들을 탐색
        if let neighbors = graph[node] {
            for neighbor in neighbors {
                if !visited.contains(neighbor) {
                    queue.enqueue(neighbor)
                    visited.insert(neighbor)
                }
            }
        }
    }
}

// 그래프 표현 (인접 리스트)
let graph: [Int: [Int]] = [
    1: [2, 3],
    2: [4, 5],
    3: [6, 7],
    4: [],
    5: [],
    6: [],
    7: []
]

// BFS 탐색 시작
bfs(start: 1, graph: graph)

 

 

 

-> Stack

스택

• Last-In-First-Out (LIFO)
• 먼저 들어온 값을 가장 마지막에 내보내는 구조이다.

스택은 다양한 부분에서 사용 가능하다. 함수 호출 스택, 실행 취소 스택, 메모리 관리 등 다양한 컴퓨팅 문제에서 적용되며, 괄호 짝 맞추기, 히스토리 관리, 트리 또는 그래프 데이터 구조의 깊이 우선 탐색(DFS)등 다양한 알고리즘에서도 사용된다.

Swift 스택 구현

struct Stack<T>{
	private var stack: [T] = []
    
    public var count: Int {
    	return stack.isEmpty
    }
    
    public mutating func push(_ element: T){
    	stack.append(element)
    }
    
    public mutating func pop() -> T? {
    	return isEmpty ? nil : stack.popLast()
    }
}

var stack = Stack<Int>()
stack.push(10)
stack.push(20)
stack.pop() // 20

 

스택 사용 알고리즘 예시

1) 괄호 유효성 검사

func isValid(_ s: String) -> Bool {
    var stack = [Character]()
    let matching: [Character: Character] = [")": "(", "}": "{", "]": "["]
    
    for char in s {
        if matching.values.contains(char) {
            stack.append(char)
        } else if let match = matching[char], !stack.isEmpty, stack.last == match {
            stack.removeLast()
        } else {
            return false
        }
    }
    
    return stack.isEmpty
}