[바킹독의 실전 알고리즘] 0x05강 - 스택

정의와 성질

스택은 한쪽 끝에서만 원소를 넣거나 뺄 수 있는 자료구조이다.

구조적으로 먼저 들어간 원소가 제일 나중에 나오게 된다.

이를 FILO(First In Last Out) 자료구조라고 부르기도 한다.

 

큐와 덱도 스택처럼 특정 위치에서만 원소를 넣거나 뺄 수 있다.

그래서 스택, 큐, 덱을 묶어서  Restricted Structure라고 부르기도 한다.

 

스택의 성질

• 원소의 추가/제거의 시간 복잡도는 O(1)이다.
• 제일 상단의 원소 확인의 시간 복잡도는 O(1)이다.
• 제일 상단이 아닌 나머지 원소들의 확인 및 변경이 원칙적으로 불가능하다.

스택은 원소의 추가/제거, 그리고 제일 상단의 원소 확인 기능만 제공한다.

그래서 제일 상단이 아닌 나머지 원소들의 확인/변경은 스택에서 제공하는 기능이 아니다.

 

배열을 기반으로 구현하여 해당 기능이 가능하도록 만들 수는 있지만,

스택의 응용 사례를 보면 원소의 추가/제거, 최상단의 원소 확인 기능만 필요로 한다.

 

기능과 구현

배열을 기반으로 구현한 스택에서 push, pop, top 함수를 구현해보았다.

 

STL stack

stack이 비어있을 때 pop, top을 호출하지 않도록 주의해야 한다.

 

출처: 바킹독님 블로그