[자료구조] 스택 (Stack)

스택: 후입선출(LIFO)의 자료구조
출입구가 하나밖에 없는 일직선 통로와 같다.

 

스택이 사용되는 예시로는 아래를 들 수 있다.

• 되돌리기 기능 (Ctrl + Z)
• 브라우저의 이전 페이지로 이동
• 함수 호출 후 메인으로 복귀
• 괄호 닫기 프로그램
  등등에 사용된다.

 

스택의 기능

• isEmpty(): 스택이 비어있으면 True를, 아니면 False를 반환한다.
• push(e): 항목 e를 스택의 맨 위에 추가한다.
• pop(): 스택의 맨 위에 있는 항목을 꺼내 반환한다.
• peek(): 스택의 맨 위에 있는 항목을 반환한다. (꺼내지 않음)
• size(): 스택의 항목 개수를 반환한다.
• clear(): 스택을 전부 비운다.

---

스택의 구현

class Stack:
    def __init__(self):
        self.top = []
    def isEmpty(self):
        return len(self.top) == 0

    def size(self):
        return len(self.top)

    def clear(self):
        global top
        self.top=[]

    def push(self, item):
        self.top.append(item)

    def pop(self):
        if not self.isEmpty():
            return self.top.pop(-1)

    def peek(self):
        if not self.isEmpty():
            return self.top[-1]

스택은 기본 중에 기본이 되는 자료구조라서 그런지 구현도 쉽고 이해하기도 쉽다.
상단에서 넣고 빼는 게 모두 되는 자료구조!

 

스택의 시간복잡도
리스트의 맨 앞에서 삽입과 삭제를 일으키면 삽입과 삭제의 시간복잡도가 O(n)이 되고,
나머지 연산의 시간복잡도는 O(1).

---

스택의 예시 1) 괄호 검사기

def checkBrackets(statement):
    stack = Stack()

    for ch in statement:
        if ch in ('(', '{', '['):
            stack.push(ch)
        elif ch in (')', '}', ']'):
            if stack.isEmpty():
                return False
            else:
                left = stack.pop()
                if ch == ')' and left != '(': return False
                elif ch == '{' and left != '{': return False
                elif ch == '[' and left !='[': return False
    return stack.isEmpty()

str1 = "(괄호검사기 테스트"
print(checkBrackets(str1))

 

스택의 예시 2) 후위 표기식 계산기

def evalPostfix(expr):
    stack = Stack()

    for ch in expr:
        if ch == "+":
            b = stack.pop()
            a = stack.pop()
            stack.push(a + b)
        elif ch == "-":
            b = stack.pop()
            a = stack.pop()
            stack.push(a - b)
        elif ch == "*":
            b = stack.pop()
            a = stack.pop()
            stack.push(a * b)
        elif ch == "/":
            b = stack.pop()
            a = stack.pop()
            stack.push(a / b)
        else:
            stack.push(float(ch))

    return stack.pop()

################
# Drive Code
식 = input("후위표기식을 입력하세요: ")
print(식.split(' '))
print(evalPostfix(식))

 

스택의 예시 3) 중위 표기식 계산기

def precedence(op):
    if op in "()": return 0
    elif op in "+-": return 1
    elif op in "*/": return 2
    else: return -1

def Infix2Postfix(expr):
    stack = Stack()
    output = [] # 출력할 후위표기식
    
    for ch in expr:
        if ch == '(':
            stack.push(ch)
        elif ch == ')':
            while not stack.isEmpty():
                op = stack.pop()
                if op == '(': break
                else:
                    output.append(op)

        elif ch in "+-*/":
            while not stack.isEmpty():
                op = stack.peek()
                if (precedence(ch) <= precedence(op)):
                    output.append(op)
                    stack.pop()
                else: break
            stack.push(ch)

        else:
            output.append(ch)

    while not stack.isEmpty():
        output.append(stack.pop())

    return output

################
# Drive Code
식 = input("중위표기식을 입력하세요: ")
후위식 = Infix2Postfix(식)
print(후위식)
print(evalPostfix(후위식))

 

작성일자: 2023-03-04