Stack 자료 구조 이해

Stack

: 물건을 쌓아 올리듯 자료를 쌓아 올린 형태의 자료구조

• 대표적인 선형 자료구조 중 하나
• 스택에 자료를 삽입하거나, 스택에서 자료를 꺼낼 수 있음
• 후입선출 (LIFO, Last-In-First-Out)
  • 가장 마지막에 넣은 자료가 가장 먼저 나오는 것

스택의 기본 연산

• 배열을 사용해 구현 가능

  • 파이썬에서는 리스트를 사용하여 구현 가능

• 저장소 자체를 스택이라 부르기도 함

• 스택에서 마지막 삽입된 원소의 위치

  • 스택 포인터, top으로 부르며 데이터를 넣거나 뺄 때 기준이 되는 위치

• 스택의 연산

  • 삽입(Push)
    • 저장소에 자료를 저장하는 연산, 보통 push라고 부름
  • 삭제(Pop)
    • 저장소에서 삽입한 자료를 역순으로 꺼내는 연산, 보통 pop이라고 부름
  • 스택이 공백인지 확인하는 연산(isEmpty)
    • 스택이 비어있으면 True, 아니면 False 반환
  • 스택의 top에 있는 item(원소)을 반환하는 연산(peek)
    • 삭제는 하지 않음

• 스택의 삽입/삭제 과정

  • 빈 스택에 원소 A, B, C를 차례로 삽입(push) 후 한번 삭제(pop)하는 연산 과정

  

• 스택 구현

  • push 연산

    • append 메소드를 통해 리스트의 마지막에 데이터를 삽입

      def my_push(item):
          s.append(item)
      

    • 인덱스 연산을 활용한 구현

      def my_push(item, size):
          global top
          top += 1
          if top == size:
              print('overflow!')
          else:
              stack[top] = item
      

    • 단순한 push 연산 (크기가 정해진 리스트와 인덱스 연산 활용)

      size = 10
      stack = [0] * size
      top = -1
      
      push(10, size)
      top += 1   # push(20)
      stack[top] = 20
      

  • pop 연산

    • 남은 데이터 중 가장 늦게 저장된 데이터를 삭제하는 연산

      def my_pop():
          if len(s) == 0:
              # underflow
              return
          else:
              return s.pop()  # 리스트 s의 마지막 원소 삭제
      

    • 인덱스 연산을 이용한 연산

      def my_pop():
          global top
          if top == -1:
              print('underflow')
              return 0
          else:
              top -= 1
              return stack[top+1]
      
      print(pop())
      
      if top > -1:  # pop()
          top -= 1
          print(stack[top+1])
      

• 스택 구현 고려 사항

  • 1차원 배열을 사용하여 구현할 경우

    • 장점 : 구현이 용이함
    • 단점 : 스택의 크기를 변경하기 어려움

  • 해결 방법 : 저장소를 동적으로 할당하여 스택을 구현하는 방법

    (동적 연결리스트를 이용하여 구현하는 방법)

    • 장점 : 메모리를 효율적으로 사용
    • 단점 : 구현이 복잡함

  <aside> 💡

  • 동적 메모리 할당

    : 필요한 만큼 메모리를 할당하고 해제하여 유연하게 크기를 조절 가능

  • 연결리스트

    : 데이터와 다음 노드의 주소를 함께 저장하여 요소들이 순차적으로 연결된 자료구조

  • 메모리

    : 컴퓨터에서 데이터를 저장하고 처리하기 위해 사용하는 일시적인 저장 공간

  </aside>

Stack 응용

괄호 검사

• 괄호 종류

  • 대괄호 [ ]
  • 중괄호 { }
  • 소괄호 ( )

• 조건

  ① 왼쪽 괄호의 개수와 오른쪽 괄호의 개수가 같아야 함

  ② 같은 괄호에서 왼쪽 괄호는 오른쪽 괄호보다 먼저 나와야 함

  ③ 괄호 사이에는 포함 관계만 존재함

• 스택을 이용한 괄호 검사

  

  1. 문자열의 괄호를 차례대로 확인하면서 왼쪽 괄호를 만나면 스택에 삽입,

     오른쪽 괄호를 만나면 스택의 top 괄호를 삭제하고 오른쪽 괄호와 짝이 맞는지 검사함

  2. 스택이 비어 있으면 조건 ① 또는 조건 ②에 해당, 괄호의 짝이 맞지 않으면 조건 ③에 해당함

  3. 마지막 괄호까지 조사한 후 스택에 괄호가 남아 있으면 조건 ①에 해당함