Stack

 

Stack

• 한 쪽 끝에서만 데이터의 추가(push)와 삭제(pop)가 일어나는 선형 자료구조
• 이러한 구조로 인해 Last In First Out의 형태로 동작

 

시간복잡도

최상단 원소를 제외한 나머지 원소들의 접근 및 변경은 원칙적으로 불가능

추가 (Push)	O(1)
제거 (Pop)	O(1)
최상단 원소 확인 (Top)	O(1)

 

구현

• 배열이나 연결리스트 등으로 구현이 가능
• ex) 배열을 이용한 구현

struct Stack<T> {
    private var array: [T] = []
    
    var size: Int { array.count }
    var isEmpty: Boot { array.isEmpty }
    var top: T? { array.last }
    
    mutating func push(_ newElement: T) { array.append(newElement) }
    mutating func pop() -> T { array.removeLast() } 
}

 

활용

괄호 쌍 판별

• 표현식의 괄호 쌍이 올바른지 판단하기 위해 스택을 사용
• e.g.
  • {10 * (3+7)} / 10 → { ( ) } = O
  • {10 * (3+7) / 10 → { ( ) = X

 

로직

• 닫는 괄호는 가장 최근에 들어온 여는 괄호를 없앤다는 개념으로 접근

func isBalanced() -> Bool {
    var isValid = true
    
    for char in 표현식 {
        if char == "(" {
            stack.push(char)
        } else if char == ")" {
            if stack.isEmpty || stack.top() != "(" {  // 짝이 맞는 여는 괄호 없음
                isValid = false
                break
            }
            
            stack.pop()  // 짝이 맞는 여는 괄호 제거
        }
    }
    
    if !stack.isEmpty { isValid = false }  // 짝지어지지 못한 여는 괄호 존재
    return isValid
}

 

표현식 표기법 변환

Infix

• 연산자가 피연산자 사이에 위치
• e.g. A + B
• 연산자 우선순위를 처리하기 위해 괄호가 필요할 수 있다.

 

prefix

• 연산자가 피연산자 앞에 위치
• e.g. + AB
• 괄호 없이도 연산의 순서가 명확함

 

postfix

• 연산자가 피연산자 뒤에 위치
• e.g. AB + 
• 괄호 없이도 연산의 순서가 명확함
• 컴퓨터는 우리가 작성한 중위 표현식을 컴파일 단계에 내부적으로 후위 표현으로 변환
  • 변환한 표현식은 스택을 사용하여 쉽게 계산 가능

 

•  

변환법

1. 연산자 우선순위에 맞게 괄호치기

2. 우선순위에 따라 연산자 pre, post로 옮기기

 

주어진 infix 표현식 X = A / B * (C + D) + E 에 대해 다음의 문제들을 해결하세요.

• prefix로 변환
• postfix로 변환
• 1번의 정답을 다시 infix로 변환
• 3번의 정답을 다시 infix로 변환

정답

• + * / AB + CDE
• AB / CD + * E +

 

프로세스 스택

• 프로세스 스택은 런타임에 함수 호출과 관련된 정보를 저장하는 메모리 영역
• 스택 자료구조의 작동 방식(LIFO)을 따름
• 일반적으로 컴파일 타임에 스택의 크기를 결정 (e.g. 4MB, 8MB)

 

스택 프레임

• 함수에 대한 정보를 담은 블럭
• 함수 호출의 컨텍스트(파라미터, 지역 변수, 복귀 주소 등)를 저장
• 스택 포인터는 현재 스택의 가장 최근에 push된 스택 프레임의 주소를 갖는 포인터

 

함수 호출 작동 방식

1. 코드 영역에서 instruction을 실행 중 함수 호출 instruction을 만남

2. 스택 프레임을 생성해 현재 실행 중인 instruction의 주소(복귀 주소)와 함수 호출에 필요한 정보를 저장(지역변수, 매개변수 등)하고 스택에 push

• 이 때, 스택 영역에 높은 주소에서 낮은 주소 순으로 할당됨

3. 호출 할 함수의 instruction이 있는 코드 영역으로 점프한 후 instuction 실행

4. 함수 호출이 완료되면, 스택에서 스택 프레임을 pop하여 복귀 주소를 얻고, 이 주소로 돌아가 원래의 instruction 실행을 계속함

 

예제

1. 스택 영역에 메모리를 할당/해제하는 속도가 힙 영역에 메모리를 할당/해제하는 속도보다 빠른 이유를 서술하세요.

 

정답

• 스택은 스택 포인터의 값만 증감시키면 되기 때문에 복잡한 계산이나 탐색이 필요 없다. 따라서 할당과 해제가 상대적으로 빠르다. 
• 힙은 메모리 할당을 위해, 할당이 가능한 메모리 영역을 탐색하고, 해제 과정에서도 메모리 릭을 방지하기 위한 복잡한 연산을 필요로 하기 때문에 스택에 비해 할당과 해제가 느리다.

 

스택 유형

스택은 요소들이 한 쪽 끝에서만 추가되고, 제거되는 순서가 있는 컬렉션 입니다. 스택의 예로는 주방의 접시를 탑처럼 쌓아올린 것이 있겠져? 접시는 탑의 맨 위에서 추가되거나 제거됩니다. 소프트웨어 상에서는 브라우저 탭의 히스토리가 있습니다.

 

스택은 매우 간단하게 구현할 수 있습니다. 자바와 같은 일부 언어는 내장 스택을 가지고 있고, 파이썬에서는 리스트 stack = [] 를 사용하여 append와 pop을 사용할 수 있습니다.

• 스택에 삽입은 push
• 스택에서 제거는 pop
• 스택의 맨 위 요소에 접근은 peek

 

스택의 시간복잡도는 구현에 따라 다릅니다. 일반적으로 배열을 사용하면 시간 복잡도는 배열과 동일합니다.

push, pop 그리고 random access는 O(1), 검색은 O(n)입니다. 때로 스택은 꼬리 포인터가 있는 연결 리스트로 구현될 수 있습니다.

 

스택과 재귀는 유사합니다. 이는 재귀가 실제로 스택을 사용하기 때문인데요.

함수 호출은 스택에 push됩니다. return 문이나 함수의 끝에 도달하면 현재 호출은 스택에서 pop됩니다.

 

알고리즘 문제에서는 LIFO 패턴을 인식할 수 있을 때, 스택을 사용하는 것이 적절합니다. 일반적으로 입력값의 요소들이 서로 상호작용하는 것이 있습니다. 예를 들어, "다음으로 큰 요소가 얼마나 먼지" 와 같은 속성 쿼리, 문자열로 주어진 수학적 식을 평가하기 등이 있습니다. 하지만 때로는 LIFO 특성이 보이지 않을 수도 있습니다.

 

스택 연산들

// Declaration: we will use an array
var stack: [Int] = []

// pushing elements
stack.append(1)
stack.append(2)
stack.append(3)

// Popping elements
stack.removeLast()  // 3
stack.removeLast()  // 2

// Check if empty
stack.isEmpty  // false

// Check element at top
stack.last  // 1

// Get Size
stack.count  // 1

 

 

Reference:

- https://leetcode.com/