스택

스택(Stack)의 개념

한 쪽 끝에서만 자료를 넣고 뺄 수 있는 자료구조
LIFO : Last In First Out 방식이다.

스택(Stack)의 연산

• push : 스택에 자료를 넣는 연산
• pop : 스택에서 자료를 빼는 연산
• top : 스택의 가장 위에 있는 자료를 반환하는 연산
• empty : 스택이 비어있는지 여부를 반환하는 연산, 비어있다면 1, 아니면 0을 반환한다.

스택(Stack)의 구현

파이썬에서는 스택을 리스트 또는 연결리스트로 구현한다.

class Stack:
    def __init__(self) :
        #자료를 저장할 공간(배열) myStack을 만듭니다.
        self.myStack = []

    def push(self, n) :
        #stack에 정수 n을 넣는다.
        self.myStack.append(n)

    def pop(self) :
        #stack에서 가장 위에 있는 정수를 제거하고, stack에 아무 원소가 없다면 아무 일도 하지 않는다.
        if self.empty() == 1:
            return
        else:
            self.myStack.pop()

    def size(self) :
        #stack에 들어 있는 정수의 개수를 return 한다.
        return len(self.myStack)

    def empty(self) :
        #stack이 비어있다면 1, 아니면 0을 return 합니다.
        if self.size() == 0:
            return 1
        else:
            return 0

    def top(self) :
        #stack의 가장 위에 있는 정수를 return 하고, stack에 들어있는 값이 없을 경우에는 -1을 return 한다.
        if self.empty() == 1:
            return -1
        else:
            return self.myStack[-1]

스택(Stack)이 활용되는 대표 예시

콜 스택(Call Stack)

컴퓨터 프로그램에서 현재 실행 중인 함수(서브루틴)를 저장하는 역할을 한다.

def a(v) :
	n = b(v)
    return n
    
def b(v) :
	m = c(v) * 2
    return m
    
def c(v) :
    return v ** 2
    
print(a(5)) #50출력

return이 실행되면 Stack에서 실행된 함수를 pop 한다.

사진 출처

1. https://medium.com/@songjaeyoung92/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-javascript-stack-%EC%9D%B4%EB%9E%80-31f9bbb84897
2. 엘리스 AI 트랙