Stack 간단 정의, 시간복잡도

Stack 정의

스택은 대표적인 후입선출(LIFO) 방식의 자료 구조입니다.

가장 나중에 저장된 데이터가 가장 먼저 제거되는 구조입니다.

 

기본 함수로는 push, pop, empty, top, size이 있습니다

 

후입선출(LIFO) : Last In First Out

컨테이너

Stack는 컨테이너 어뎁터이다.

 

어뎁터 컨테이너는  다른 컨테이너 클래스들을 상속 받아서 다른 컨테이터 클래스의 객체에 특정한 인터페이스를 제공해주는 개념이다.

단, 반복자를 지원하지 않으므로 STL 알고리즘에서는 사용할 수 없다.

시간복잡도

1. 원소의 추가O(1)
2. 원소의 제거O(1)
3. 제일 상단의 원소 확인O(1)
4. 제일 상단이 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능

출처 : https://www.youtube.com/watch?v=0DsyCXIN7Wg (바킹독님 강의)