[자료구조][알고리즘] 스택

스택

한 쪽 끝에서만 재료를 넣고 뺄 수 있는 LIFO, FILO 형식의 자료구조

스택 메서드

• push
• pop
• peek: 가장 뒷단, 혹은 상단에 있는 자료를 확인하는 메소드
• isEmpty
• count

struct Stack<T> {
	private var elements: [T] = []
    init() {}
    
    mutating func push(_ element: T) {
    	elements.append(element)	// O(1)
    }
    mutating func pop() -> T? {
    	elements.popLast()	// O(1)
    }
    
    func peek() -> T? {
    	elements.last	// O(1)
    }
    var isEmpty : Bool {
    	elements.isEmpty	// O(1)
    }
}

var stack = Stack<Int>([1,2,3,4,5])

popLast와 removeLast는 다르다. popLast는 배열 값이 비어있어도 런타임에러가 안 나지만, removeLast는 난다. 이 경우를 stack underflow라고 한다.

백준

let testCase = Int(readLine()!)!

for _ in 0..<testCase {
    // 앞에 있는 친구가? ( 라면 push하고 )라면 pop을 한다.
    // 짝이 안 맞으면 바로  No
    
    let line = readLine()!
    var stack: [Character] = []
    var answer = true
    
    for char in line {
        if char == "(" {
            stack.append(char)
        } else {
            if stack.isEmpty {
                answer = false
                break
            } else {
                stack.removeLast()
            }
        }
    }
    
    if answer == false {
        print("NO")
    } else {
        if stack.isEmpty {
            print ("YES")
        } else {
            print("NO")
        }
    }
    
    
}

출처

SeSAC 메모리스