[알고리즘] 스택 - 먼저하면 늦게, 늦게하면 먼저

스택(Stack)

먼저 들어간 요소가 가장 나중에 나온다

Last-In, First Out: LIFO 자료구조

 

비행기 캐리어처럼 먼저 실으면 늦게 나오고, 늦게 실으면 먼저 나온다.

 

• 스택의 삽입 연산: push
• 스택의 삭제 연산: pop

 

스택 응용 예시

예시1) 역순 문자열 만들기

[A] [B] [C] [D] 들어올 때 [D] [C] [B] [A]가 나오도록

 

배열에 push 사용하듯

push(stack, A)

push(stack, B)

push(stack, C)

push(stack, D)

 

꺼낼 때는 pop 이용

pop(stack) 하면 D

pop(stack) 하면 C

pop(stack) 하면 B

pop(stack) 하면 A

이 나온다.

 

 

예시2) 시스템 스택

함수 호출과 복귀를 보면 시스템 스택이다.

예를들면

B함수를 가지고 있는 A함수가 있다

1. A함수가 실행되면
2. B함수가 호출되고
3. B함수가 리턴하고
4. 마지막에 A함수가 리턴된다.

이런게 스택의 구조다

 

스택 알고리즘 구현

class Stack:
    def __init__(self):
        self.items = []


    def __str__(self):
        return str(self.items)

    def push(self, item):
        self.items.append(item)

    def pop(self):
        if len(self.items) == 0:
            return None
        else:
            return self.items.pop()


if __name__ == '__main__':
    s = Stack()
    print(s)           // []
    s.push(100)        
    s.push(200)
    print(s)           // [100, 200]
    print(s.pop())     // 200
    print(s)           // [100]
    print(s.pop())     // 100
    print(s.pop())     // None