스택 Stack

: 데이터를 쌓아서 관리하는 방식 혹은 저장소

• 특징
  • 후입선출 (Last-In-First-Out)
  • 선형구조 (자료 간의 관계가 1대 1)

cf) 함수 호출 시 스택 메모리 사용

 

💡 Java의 스택 클래스

import java.util.Stack;

선언

// Stack<래퍼클래스> 변수명 = new Stack<>();
Stack<Integer> stack = new Stack<>();

값 추가

stack.push(1);
stack.push(10);

상단의 값 삭제 및 반환

stack.pop();		// 10 삭제 -> return 10

상단의 값 반환

stack.peek();		// return 1

기타 메소드

stack.get(0);		// 인덱스로 조회 -> return 1
stack.size();		// 1
stack.empty();		// false
stack.contains(1);	// true

 

💡 Python에서의 스택

list로 스택 구현

# 생성
stack = []

# 값 추가
stack.append(1)

# 상단의 값 삭제 및 반환
stack.pop()

# 상단의 값 반환
stack[-1]

deque로 스택 구현

deque (double-ended queue) : 앞뒤에서 삽입, 삭제가 가능한 큐
→ stack, queue 등으로 사용 가능

from collections import deque

# 생성
stack = deque()

# 값 추가
stack.append(1)			# deque([1])

# 상단의 값 삭제 및 반환
stack.pop()

# 상단의 값 반환
stack[-1]

 

---

재귀 Recursion

: 자기 자신을 재참조

재귀 함수 Recursive Function

: 자기 자신을 호출하는 함수

→ 재귀 함수 호출 시 이름만 같은 다른 메소드가 스택 메모리에 계속 쌓이므로,
반복문에 비해 메모리 및 속도 성능저하 발생 가능

Call stack : 함수가 끝나면 돌아갈 위치를 기록해두는 곳
→ call stack이 너무 많이 쌓이면 Stack Over Flow Error 발생

• 구조
  • Base case : 재귀 호출에서 빠져나가는 경우
  • Recursive case : subproblem(같은 형태의 작은 문제)으로 이루어진 재귀 함수 호출

예시

→ 출력 : 5 4 3 2 1 0 1 2 3 4 5

public void main(String[] args) {
	recur(5, 0);
}

void recur(int level, int end) {
	// base case
    if(level == end) {
    	System.out.println(level);
        return;		// 함수 끝!
    }
    
    // recursive case
    System.out.println(level);
    recur(level - 1, end);
    System.out.println(level);
}

 

메모이제이션 Memoization

: 동일한 계산을 다시 수행하지 않도록 메모리에 저장하는 방식

→ Dynamic Programming (한 번 계산한 결과 재활용)