자료구조 - 스택, 큐, 덱

C언어로 쉽게 풀어쓴 자료구조를 읽으며 정리

---

스택

정의

• 후입선출(LIFO)구조로 모든 원소들의 삽입, 삭제가 리스트의 한쪽 끝에서만 수행되는 선형구조.

구현

struct Stack<Element> {
    private var _stack: [Element] = []
    
    var count: Int { self._stack.count }
    
    var isEmpty: Bool { self._stack.isEmpty }
    
    mutating func push(_ element: Element) {
        self._stack.append(element)
    }
    
    mutating func pop() -> Element? {
        return self.isEmpty ? nil : self._stack.removeLast()
    }
}

 

활용

• 왔던 곳을 다시 되돌아가는 상황이 필요한 곳에서 주로 사용
• ex. 시스템 함수 호출

괄호 검사

프로그램에서 문자열의 괄호가 적절한지 검사하는 로직을 작성해보자.

 

조건

• 사용되는 괄호는 대괄호 [], 중괄호 {} 소괄호 () 이다.
• 왼쪽 괄호의 개수와 오른쪽 괄호의 개수는 항상 같다.
• 같은 타입의 괄호에서 왼쪽 괄호는 오른쪽 괄호보다 먼저 나온다.
• 서로 다른 타입의 왼쪽 괄호와 오른쪽 괄호 쌍은 서로를 교차할 수 없다.

 

문제 해결 방법

 

• 열리는 괄호가 들어오면 스택에 push하고, 닫히는 괄호가 들어올 때 스택에서 pop한다.
• 아래 케이스의 경우 올바르지 못한 식이 된다.

1. pop한 괄호와 닫히는 괄호가 짝이 맞지 않음

2. pop할 element가 없거나 모든 괄호를 확인했는데 스택에 값이 남아있음.

 

구현

func checkMatchingBrackets(from expression: String) -> Bool {
    var stack = Stack<Character>()
    
    for ch in expression {
        switch ch {
        case "(", "{", "[":
            stack.push(ch)
        case ")", "}", "]":
            guard let bracket = stack.pop(), bracket.isMatchingBracket(with: ch) else {
                return false
            }
        default:
            continue
        }
    }
    
    return stack.isEmpty
}

extension Character {
    func isMatchingBracket(with other: Character) -> Bool {
        switch self {
        case "(": return other == ")"
        case ")": return other == "("
        case "{": return other == "}"
        case "}": return other == "{"
        case "[": return other == "]"
        case "]": return other == "["
        default: return false
        }
    }
}

let testCasesForSucceed: [String] = [
    "[{()}]",
    "([]){}",
    "({[]})",
    "[()]{[()()]}"
]

let testCasesForFailure: [String] = [
    "[(])",
    "([)]",
    "[{]}",
    "[()",
    "{[)]}",
    "[(])"
]

for exp in testCasesForSucceed {
    print(checkMatchingBrackets(from: exp))
}

for exp in testCasesForFailure {
    print(checkMatchingBrackets(from: exp))
}

 

후위 표기식 계산

수식을 표현하는 방법에는 중위(infix), 후위(postfix), 전위(prefix) 3가지 방법이 있다.

(와.. 너무 오랜만)

• 중위(infix) : 연산자가 피연산자 사이에 있음. ex) 2+3*4
• 전위(prefix) : 연산자가 피연산자 앞에 있음. ex) +2*34
• 후위(postfix) : 연산자가 피연사산자 뒤에 있음. ex) 234*+

 

프로그래머가 수식을 중위 표기법으로 작성하면 컴파일러는 이것을 후위 표기법으로 변환한 후에 스택을 이용하여 계산한다.

 

why? 후위 표기식은

• 괄호를 쓰지 않고, 우선 계산할 내용을 알 수 있음. (1+2)*7 ==> 12+7*
• 연산자의 우선순위도 이미 식 자체에 포함됨.
• 수식을 읽으면서 바로 계산 가능

문제 해결 방법

• 수식을 왼쪽에서 오른쪽으로 스캔
• 피연산자이면 스택에 저장
• 연산자이면 필요한 수 만큼 스택에서 꺼내 연산을 실행하고 연산의 결과를 다시 스택에 저장

구현

func evaluatePostfix(expression: String) -> Int? {
    var stack = Stack<Int>()
    
    for ch in expression {
        if let num = Int(String(ch)) {
            stack.push(num)
            continue
        }
        
        guard let operand2 = stack.pop(),
              let operand1 = stack.pop() else {
            return nil
        }
        
        switch ch {
        case "+":
            stack.push(operand1 + operand2)
        case "-":
            stack.push(operand1 - operand2)
        case "*":
            stack.push(operand1 * operand2)
        case "/":
            stack.push(operand1 / operand2)
        default:
            return nil
        }
    }
    
    return stack.count == 1 ? stack.pop() : nil
}

evaluatePostfix(expression: "53+82-*") // 48

 

큐

정의

• 선입선출(FIFO)구조로 원소의 삽입은 큐의 후단(rear)에서 삭제는 전단(front)에서 이뤄지는 선형 자료구조.

활용

큐를 이용한 버퍼

큐는 서로 다른 속도로 실행되는 두 프로세스 간의 상호작용을 조화시키는 버퍼 역할을 담당한다.

• Ex. CPU와 프린터 사이의 프린팅 버퍼
• Ex. CPU와 키보드 사이의 키보드 버퍼

 

일반적으로 데이터를 생산하는 생산자 프로세스가 있고, 데이터를 소비하는 소비자 프로세스가 있으면, 이 사이에 큐로 구성되는 버퍼가 존재한다.

선형 큐

 

 

• 배열을 선형으로 사용하여 큐를 구현하는 방식이다.
• 큐의 전단과 후단이 연결되어 있지 않기 때문에 삽입을 계속하기 위해서는 데이터를 계속해서 이동시켜야 한다.

 

구현

struct LinearQueue<Element> {
    private var _queue: [Element] = []

    var isEmpty: Bool { return self._queue.isEmpty }
    var count: Int { return self._queue.count }

    mutating func enqueue(_ element: Element) {
        self._queue.append(element)
    }

    mutating func dequeue() -> Element? {
        return self.isEmpty ? nil : self._queue.removeFirst()
    }
}

 

원형 큐

배열의 전단과 후단을 연결하여 원형으로 사용하는 방식이다.

• 이 연결은 나머지 연산을 이용하여 구현할 수 있다.
• front를 전단보다 하나 작은 인덱스로 지정하고, rear를 마지막 요소의 인덱스로 지정하여 큐를 관리한다.
• 일반적으로 선형 큐와 비교했을 때 enqueue, dequeue 모두 모든 케이스에서 시간 복잡도가 개선된다. O(n) -> O(1)

 

 

• 공백 상태와 포화 상태를 구별하기 위하여 하나의 공간은 항상 비워둔다.

구현

• 삽입 시에 rear를 1 증가, 삭제 시에는 front를 1 증가 시켜주는 방식으로 구현.
• 공백상태 : front == rear
• 포화상태 : front % M == (rear + 1) % M

struct CircularQueue<Element> {
    private let maxSize: Int
    
    private var _queue: [Element?]
    
    private var front = 0
    private var rear = 0
    
    init(size: Int) {
        let maxSize = size + 1
        self.maxSize = maxSize
        self._queue = Array(repeating: nil, count: maxSize)
    }
    
    var isEmpty: Bool {
        return self.front == self.rear
    }

    var isFull: Bool {
        return self.front % self.maxSize == (self.rear + 1) % self.maxSize
    }
    
    mutating func enqueue(_ element: Element) -> Bool {
        guard !self.isFull else { return false }
        
        self._queue[self.rear] = element
        
        self.rear = (self.rear + 1) % self.maxSize
        
        return true
    }

    mutating func dequeue() -> Element? {
        guard !self.isEmpty else { return nil }
        
        let element = self._queue[self.front]
        self._queue[self.front] = nil
        self.front = (self.front + 1) % maxSize
        return element
    }
}

 

덱(deque)

• 전단과 후단에 모두 삽입과 삭제가 가능한 큐
• double ended queue의 줄말
• 배열을 이용해서 원형 큐와 유사하게 구현
• 원형 큐와 동일하고 front에서 데이터를 삽입하는 기능, rear에서 데이터를 삭제하는 기능을 추가로 구현

 

구현은 생략