FILO(First In Last Out)의 구조를 가짐.

특정 위치에서만 원소를 넣거나 뺄 수 있는 제한이 걸려있음.

스택, 큐 덱을 묶어서 Restricted Structure라고 부름.

스택의 성질

1. 원소의 추가 O(1)
2. 원소의 제거 O(1)
3. 제일 상단의 원소 확인 O(1)
4. 제일 상단이 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능
   • 배열을 통해 stack을 구현하면 제일 상단이 아닌 나머지 원소들도 확인/변경이 가능하도록 만들 수는 있음.

스택의 구현

• 배열을 이용한 구현

const int MX = 1000005;
int dat[MX];
int pos = 0; // 스택의 길이, 스택 내의 원소의 갯수

void StackBasic::push(int x) {
    dat[pos++] = x;
}

void StackBasic::pop() {
    pos--;
}

int StackBasic::top() {
    return dat[pos-1];
}

stack의 STL

• stack<int> S
• S.push(element) element를 Stack에 추가
• S.pop() Stack의 제일 상단 값을 제거
• S.empty() Stack이 비었는 지 확인
• S.top() Stack의 제일 상단 원소 확인
• 주의점: 스택이 비어있을 때, pop, top을 호출하면 런타임에러가 발생하니 이점 주의할 것!