정의
- 먼저 들어간 원소가 가장 마지막에 나오는 FILO 구조를 가진다.
- 특정 위치에서만 원소를 넣거나 뺄 수 있다.
성질
- 원소의 추가/제거 : O(1)
- 제일 상단의 원소 확인 : O(1)
- 제일 상단이 아닌 나머지 원소들의 확인/변경은 원칙적으로 불가능하기 때문에 STL stack에서는 해당 기능을 제공하지 않는다.
구현
배열을 이용하여 스택을 직접 구현해보자.
const int MX = 1000005;
int dat[MX]; // 원소 저장 배열
int pos = 0; // 인덱스 저장 변수
void push(int x) { dat[pos++] = x; }
void pop() { pos--; }
int top() { return dat[pos - 1]; }
// 배열 속 원소들을 가리키며 이동하면서 데이터를 변경/삭제하지 않고도 해당 기능을 구현할 수 있다.- 스택의 값들은 dat[0]부터 저장된다.
- pos는 원소가 다음에 추가될 때 삽입해야 하는 곳이므로 pos의 값은 스택의 길이 즉, 스택 내의 원소의 개수를 의미한다.
- top : 원소가 추가/제거되는 곳
- 스택이 비어있을 때 pop(), top() 연산 시 런타임 에러가 발생할 수 있다.
STL stack
