지혜의 개발공부로그

자료구조, Stack

16 Jul 2025 | Data Structure

개인공부 후 자료를 남기기 위한 목적임으로 내용 상에 오류가 있을 수 있습니다.

Stack

선형 자료구조 중에서도 동적 자료구조에 해당하는 Stack은 필요에 따라 메모리에 공간을 유연하게 할당하고 해제해 데이터를 저장할 수 있어 데이터의 추가, 삭제, 크기 변경등이 가능하다. 이때 스택의 가장 중요한 특징은 LIFO 개념이다.

LIFO: Last In First Out

  • 가장 마지막에 들어온 데이터가 가장 먼저 나가는 자료구조
  • 데이터는 한쪽 끝에서만 삽입, 삭제가 이루어짐
  • 중간에 대한 접근은 불가능 > 오직 맨 위(top) 데이터에만 접근 가능

주요 연산

  1. push(value): 스택의 맨 위에 값을 추가 > append개념
  2. pop: 스택의 맨 위 값만 제거하고 반환

Python으로 구현해보는 stack

class Stack:
    def __init__(self):
        # stack을 담아줄 빈 리스트 생성
        self.items = []

    def push(self, value):
        # 비어있는 stack에 값을 추가 
        self.items.append(value)

    def pop(self):
        try:
            # items이 빈리스트가 아니라면 (값이 있다면)
            return self.items.pop()
        except IndexError:
            # items에 아무것도 없다면 더이상 삭제할 아이템이 없으니까 indexError발생
            print('Stack is empty')
            return None

    def top(self):
        # 현재 스택 최상단 친구는 누구인지 묻는 함수
        try:
            return self.items[-1]
        except IndexError:
            # items에 아무것도 없다면 더이상 삭제할 아이템이 없으니까 indexError발생
            print('Stack is empty')
            return None

    # 이미 존재하는 함수인 len 접근
    def __len__(self):
        return len(self.items)

stack = Stack()
stack.push(12)
stack.push(3)
stack.push(2)
stack.push(1232)
stack.push(12123124)

stack.items
# 출력: [12, 3, 2, 1232, 12123124]
stack.pop()
# 출력: 12123124
stack.items
# 출력: [12, 3, 2, 1232]
stack.top()
# 출력: 1232
len(stack)
# 출력: 4

각 연산들의 시간 복잡도: O(1)인 것도 확인 가능하다.(push, pop, top, len)

스택 예제 > 괄호 맞추기

  • 문제 상황
    1. 왼쪽 괄호 ‘(‘ → 스택에 push
    2. 오른쪽 괄호 ‘)’ → 스택에서 pop
    3. 모든 괄호 처리 후 스택이 비어있으면 올바른 쌍
def check_parentheses(seq):
    # 위에서 만들어놓은 Stack 클래스를 통해 stack 객체 생성
    stack = Stack()
    
    for s in seq:
        # 들어온 seq에 s가 "(" 라면
        if s == "(":
            # stack에 ( 를 추가 (push)
            stack.push(s)

        # 들어온 seq에 ")"라면
        elif s == ")":
            # 현재 stack의 길이를 확인해서 
            # 길이가 0이면 현재 스택엔 아무것도 없다는 뜻이니까
            if len(stack) == 0:
                # 비어있다고 출력 
                # 근데 원래는 )가 있었어야해 ()이렇게가 쌍이니까! 
                # 그래서 다르게 표현해보면 > return False 이것도 맞다 
                return "empty stack"
            # 만약 stack이 비어있지 않다면? -> 길이가 0이 아니라면
            # (든 )든 둘중 뭐가 있다는 뜻이니까 일단 맨끝에 있는 애를 삭제해! (pop)
            stack.pop()

    # for문을 통해 들어온 seq에 대한 push, pop을 다 진행한 뒤에 stack의 길이를 확인
    # pop을 했는데 stack의 길이가 0보다 많다면 ()의 쌍이 맞지 않았다는 뜻이니까
    if len(stack) > 0:
        # 쌍이 잘 맞지 않았고, stack은 비어있지 않다는 의미!
        return "not empty"
    # len == 0이라는 의미는 쌍이 맞았다는 의미니까
    return "잘 넣으셨군요"

Related Posts