[자료구조] 스택(Stack)

스택(Stack)이란?

영어 그대로 쌓아놓은 것이라고 생각하면 편함

스택의 핵심은 후입선출, 즉 가장 최근에 들어온 데이터가 가장 먼저 나감

 

 

스택의 연산

• push: 삽입, 저장소에 자료를 저장
• pop: 삭제, 저장소에서 자료를 꺼냄, 순서는 최근에 삽입한 자료 부터
• isEmpty: 공백인지 아닌지를 확인
• peek: 스택의 top에 있는 원소를 반환

 

 

스택의 구현

1. push

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

print(pop())

if top > -1:
    top -= 1
    print(stack[top + 1])

2. pop

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

print(pop())

if top > -1:
    top -= 1
    print(stack[top + 1])

 

스택의 응용

1. 괄호검사

조건

• 왼쪽 괄호의 개수와 오른쪽 괄호의 개수가 같아야 한다.
• 같은 괄호에서 왼쪽 괄호는 오른쪽 괄호보다 먼저 나와야 한다.
• 괄호 사이에는 포함관계만 존재한다.

스택을 이용해서 괄호검사를 진행

• 여는 괄호('(')를 만나면 push, 닫는 괄호(')')를 만나면 pop
• 마지막에 스택이 비어있지 않으면 오류
  (swea1218, 백준 괄호)

 

2. Function Call

main() → F1() → F2() 순서대로 함수를 쌓아놓으면, F2 → F1 → main 순서대로 함수가 끝남
= 프로그램에서의 함수 호출과 복귀에 따른 수행 순서를 관리함

 

---

재귀호출

: 자기 자신을 호출하여 순환 수행되는 것

• 예시1: 팩토리얼
  • n! = n * (n - 1)!
  • f(n) = n * f(n - 1)
• 예시2: 피보나치 수

여기서 만약 중복되는 값들이 존재하면 Memoization을 사용

Memoization

: 이전에 계산한 값을 메모리에 저장해서 다시 계산하지 않도록 하는 것 → 동적계산법(DP)참고