스택(Stack) 자료구조

스택(Stack)이란?

• 스택(Stack)은 LIFO (Last In, First Out) 원칙에 기반한 선형 자료구조입니다. 이는 가장 최근에 Stack에 추가된 항목이 가장 먼저 제거되는 순서를 따른다는 것을 의미합니다. 즉, 마지막으로 들어간 원소가 제일 먼저 나오게 됩니다.
• 스택의 주요 연산에는 Push (원소 추가), Pop (원소 제거), Top/Peek (맨 위 원소 조회), IsEmpty (비어 있는지 확인)가 있습니다.

스택의 사용 사례

• Undo / Redo: "Undo"와 "Redo" 기능을 구현하기 위해서는 주로 두 개의 스택(Stack)을 사용합니다. 사용자 작업을 역순으로 복구하거나 다시 수행할 수 있습니다.

• 백스페이스: 키보드 입력 중 백스페이스( ← ) 키를 누르면 최근에 입력한 글자를 지웁니다.

• 최근 작업 순서로 되돌아가기: 편집기 등에서 최근 작업을 되돌릴 때 스택을 활용합니다.

• 프로그램의 함수 호출 관리: 운영체제는 함수 호출을 스택을 사용하여 관리합니다. 이를 호출 스택 (Call Stack)이라고 하며, 함수 호출과 반환을 효과적으로 관리합니다.

• 그 외: 문자열 역순으로 바꾸기, 괄호의 짝 확인하기, 후위 표기법 변환 등 다양한 알고리즘에서 사용됩니다.

스택의 장점

• 상수 시간의 기본 연산: 스택의 기본 연산들 (Push, Pop, Peek 등)은 대부분 상수 시간 $O(1)$으로 매우 빠릅니다.

• 메모리 효율성: 스택은 필요한 만큼의 메모리만 사용하므로 메모리를 효율적으로 활용할 수 있습니다.

• 구현의 간결성: 스택은 간단한 자료구조로 구현이 쉽고 코드가 짧고 명확합니다.

• LIFO 특성 활용: LIFO 특성은 깊이 우선 탐색, 백트래킹 알고리즘 등에서 자연스럽게 활용됩니다.

스택의 연산 시간 복잡도

• Push (원소 추가): 배열 또는 연결 리스트를 이용한 스택 모두 $O(1)$
• Pop (원소 제거): 배열 또는 연결 리스트를 이용한 스택 모두 $O(1)$
• Peek (맨 위 원소 조회): 배열 또는 연결 리스트를 이용한 스택 모두 $O(1)$
• IsEmpty (비어 있는지 확인): $O(1)$
• Size (스택 크기 확인): 배열 또는 연결 리스트를 이용한 스택 모두 $O(1)$ (구현에 따라 $O(n)$ 가능)

Stack Overflow와 Underflow

Stack Overflow

• 스택 오버플로우(Stack Overflow)는 스택이 할당된 메모리 용량을 초과하여 아이템을 추가하려고 할 때 발생하는 현상입니다. 스택이 가득 찼을 때 더 많은 데이터를 푸시하려고 시도하면 스택 오버플로우가 발생합니다.

Stack Underflow

스택 언더플로우(Stack Underflow)는 스택이 비어 있을 때 아이템을 제거하려고 할 때 발생하는 현상입니다. 스택에서 아무것도 없는 상태에서 팝 연산을 수행하려고 시도하면 스택 언더플로우가 발생합니다.

영향과 방지

• 스택 오버플로우와 언더플로우가 발생하면 해당 스레드나 프로세스는 중단됩니다.
• 방지하기 위해서는 재귀 함수를 제한하거나, 예외 처리를 사용하여 오류를 처리하고, 스택이 비어 있는지 미리 확인하는 등의 방법을 사용할 수 있습니다.

중위 표현식 (Infix Notation)와 후위 표현식 (Reverse Polish Notation, RPN) 변환

중위 표현식(Infix Notation)이란?
중위 표현식은 일상적으로 사용하는 수학적 표현 방식입니다. 이 방식에서 연산자는 두 개의 피연산자 사이에 위치합니다.

---

a + b
c - d
e * f
g / h

후위 표현식(Reverse Polish Notation, RPN)이란?
후위 표현식은 연산자를 두 피연산자의 뒤에 위치시키는 표기법입니다.

---

a b +
c d -
e f *
g h /

후위 표현식의 장점

• 컴퓨터가 후위 표현식을 처리하기 매우 쉽습니다. 연산의 우선순위를 고려할 필요가 없으며, 괄호 없이도 표현식을 명확하게 나타낼 수 있습니다.
• 후위 표현식 계산의 일반적인 방법으로 스택을 사용합니다.
  • 피연산자가 나오면 스택에 푸시하고, 연산자가 나오면 스택에서 피연산자를 팝하여 연산을 수행한 후 결과를 다시 스택에 푸시합니다.
  • 표현식의 끝까지 이 과정을 반복한 후, 스택의 맨 위에 있는 값이 최종 결과값이 됩니다.

중위 표현식 → 후위 표현식 변환

# 중위 표현식 (Infix Notation) → 후위 표현식 (Reverse Polish Notation, RPN) 변환

# 연산자의 우선순위를 판단하는 메서드
def get_priority(operator):
    # 숫자가 높을수록 우선순위가 높다는 의미
    if operator in ['+', '-']:
        return 1
    elif operator in ['*', '/']:
        return 2
    else:
        return 0

# 피연산자인지 확인하는 함수
def is_operand(token):
    # 입력된 문자가 '0'부터 '9' 사이의 값인지 확인하여 피연산자인지 판단합니다.
    if '0' <= token <= '9':
        return True
    return False

# 연산자인지 확인하는 함수
def is_operator(token):
    return token in ['+', '-', '*', '/']

# 중위 표현식을 후위 표현식으로 변환하는 함수
def infix_to_postfix(infix_expression):
    operator_stack = []  # 연산자를 저장할 스택
    postfix_result = ""  # 변환된 후위 표현식을 저장할 변수

    # 중위 표현식을 왼쪽에서 오른쪽으로 순회하며 각 문자를 확인합니다.
    for token in infix_expression:
        if is_operand(token):
            # 피연산자(숫자)일 경우, postfix_result에 추가합니다.
            postfix_result += " " + token
        elif token == "(":
            # 여는 괄호 '('를 만나면, operator_stack에 추가합니다.
            operator_stack.append(token)
        elif token == ")":
            # 닫는 괄호 ')'를 만나면, operator_stack에서 여는 괄호 '('가 나올 때까지 스택의 상단에 있는 연산자를 postfix_result에 추가하고, 스택에서 제거합니다.
            while operator_stack and operator_stack[-1] != "(":
                postfix_result += " " + operator_stack.pop()
            # 여는 괄호 '('도 스택에서 제거합니다.
            if operator_stack and operator_stack[-1] == "(":
                operator_stack.pop()
        elif is_operator(token):
            # 연산자의 우선순위를 비교하면서, operator_stack의 맨 위에 있는 연산자의 우선순위가 현재 연산자와 같거나 높으면, operator_stack에서 해당 연산자를 팝(pop)하여 postfix_result에 추가합니다.
            while operator_stack and get_priority(token) <= get_priority(
                operator_stack[-1]
            ):
                postfix_result += " " + operator_stack.pop()
            # 현재 연산자를 operator_stack에 푸시합니다.
            operator_stack.append(token)

    # operator_stack에 남은 모든 연산자를 postfix_result에 추가합니다.
    while operator_stack:
        postfix_result += " " + operator_stack.pop()

    # 후위 표현식 결과를 반환합니다.
    return postfix_result

# 예제
infix_expression = "(1+3-1)*4"
postfix_expression = infix_to_postfix(infix_expression)
print("중위 표현식:", infix_expression)
print("후위 표현식:", postfix_expression)

출력 결과

중위 표현식: (1+3-1)*4
후위 표현식:  1 3 + 1 - 4 *