06. 스택

🧩 <코딩테스트 합격자 되기: 파이썬 편> 1독 스터디 기록입니다.

 

 

스택(Stack)

먼저 입력한 데이터는 가장 나중에 꺼낼 수 있는 선입후출(FILO, First-In-Last-Out) 자료구조이다. '가장 최근의 값'이 필요할 때 활용할 수 있다.

스택 개요

 

파이썬에서는 스택 자료구조를 지원하지 않기 때문에 리스트로 구현해서 이용할 수 있다.

 

---

스택 ADT

연산

• boolean isFull(): 스택에 들어있는 데이터 개수가 max_size인지 확인하여 boolean 값을 반환한다. 즉, 스택에 데이터가 가득 차 있으면 True, 그렇지 않다면 False를 반환한다.
• boolean isEmpty(): 스택이 비어있는지 확인하여 boolean 값을 반환한다. 즉, 데이터가 하나라도 있으면 False, 완전히 비어있으면 True를 반환한다.
• void push(ItemType item): 스택에 데이터를 삽입한다.
• ItemType pop(): 스택의 최상단에 있는 데이터를 꺼내어 반환한다. 즉, 가장 최근에 푸시한 데이터를 꺼내어 반환한다.

상태

• int top: 스택의 최상단에 있는 데이터, 즉 최근에 푸시한 데이터의 위치를 기록한다. 스택이 비어 있으면 -1로 기록할 수 있다.
• ItemType data[max_size]: 스택에서 데이터를 관리하는 배열이다.

 

구현

stack = [ ]    # 스택 리스트 초기화
max_size = 100  # 스택의 최대 크기

def isFull(stack):
  # 스택이 가득 찼는지 확인하는 함수
  # 스택의 현재 크기가 최대 크기와 같으면 스택이 가득 찬 것이다.
  return len(stack) == max_size    

def isEmpty(stack):
  # 스택이 비어 있는지 확인하는 함수
  return len(stack) == 0

def push(stack, item):
  # 스택에 데이터를 추가하는 함수
  if isFull(stack):
    print("Stack is full.")
  else:
    stack.append(item)

def pop(stack):
  # 스택에서 데이터를 꺼내는 함수
  if isEmpty(stack):
    print("Stack is empty.")
    return None
  else:
    return stack.pop( )

파이썬으로 구현할 때는 push()나 pop()은 따로 구현하지 않고 각각 append()와 pop() 함수를 이용하면 되겠다.

 

 

스택이 활용되는 경우

함수의 호출

함수가 호출되면 메모리의 스택 영역에 그 함수의 호출 정보가 차례대로 저장된다. 이때 저장되는 함수의 호출 정보에는 함수의 매개변수, 호출이 끝나고 돌아갈 반환 주소값, 함수에서 선언된 지역 변수 등이 있다. 이러한 호출 정보를 스택 프레임이라고 한다.

 

스택 영역은 함수의 호출과 함께 할당되고 호출이 완료되면 반환된다.

 

다음의 코드를 실행해본다고 하자.

def main():
    first()

def first():
    print("첫 번째 함수입니다.")
    second()

def second():
    print("두 번째 함수입니다.")

if __name__ == "__main__":
    main()

 

first()는 main()에서 호출되며, second()는 first()에서 호출되고 있다.

main()이 가장 먼저 호출되므로, 스택 영역에 main()의 스택 프레임이 저장된다.

main() 실행중 first()가 호출되어 main() 위에 first()의 스택 프레임이 저장된다.

first() 실행중 second()가 호출되어 first() 위에 second()의 스택 프레임이 저장된다.

 

이를 정리하면 다음의 그림과 같다.

 

이를 통해 다음과 같은 사실도 알 수 있다.

• 현재 실행되고 있는 함수는 스택 영역의 최상단에 위치한 함수이다.
• 각 함수를 호출한 함수, 즉 각 함수가 호출된 위치는 해당 함수의 아래에 위치한 함수이다.

 

재귀

재귀(recursion)이란 자신을 정의할 때 자기 자신을 재참조하는 방법이다. 재귀 함수는 실행 과정에서 자기 자신을 호출하게 된다.

 

재귀 함수에 대해 스택 영역은 다음과 같은 모습을 할 것이다.

 

스택 영역은 한정되어 있기 때문에 스택 영역이 가득 찰 때까지 함수가 계속 호출되면 런타임 에러가 발생한다. 따라서 재귀 함수를 정의할 때는 다음을 고려해야 한다.

• 바로 풀 수 있거나 종료 조건을 포함한 base case가 한 개 이상 존재해야 한다.
• 문제를 좀 더 작게(simpler&smaller) 만드는 방식으로 동작해야 한다.

 ※ base case란 더이상 재귀 호출을 하지 않고도 직접 문제를 해결할 수 있는 사례를 뜻한다.

 

 

---

📕 Reference

코딩 테스트 합격자 되기: 파이썬 편, 박경록, 골든래빗.

코딩 테스트 합격자 되기: 파이썬 편 | 박경록 - 교보문고