스택

스택(Stack) = 한쪽 끝에서만 원소를 넣거나 뺄 수 있는 자료구조.

 

스택은 구조적으로 먼저 들어간 원소가 제일 나중에 오게되는데, 이런 의미로 FILO(First In Last Out) 자료구조 라고도 부른다. 참고로 큐나 덱도 스택처럼 특정 위치에서만 원소를 넣거나 뺄 수 있는 제한이 걸려있다. 그래서 스택, 큐, 덱을 묶어서 Restricted Strcture 라고 부른다.

 

스택의 성질

1. 원소의 추가가 O(1)

2. 원소의 제거가 O(1)

3. 제일 상단의 원소 확인이 O(1)

4. 제일 상단이 아닌 나머지 원소들의 확인/ 변경이 원칙적으로 불가능

 ㄴ 원래 스택이라는 자료구조는 원소의 추가/ 제거/ 제일 상단의 원소 확인이라는 기능만 제공하는 자료구조이다.

그래서 STL 에도 이 기능은 없다.

 

구현

스택은 배열 혹은 연결 리스트를 이용하여 구현이 가능하다.