스택, 큐, 덱 ➡️ Restricted Structure: 특정 위치에서만 원소를 넣거나 뺄 수 있음

스택의 성질

1. 원소의 추가: O(1)
2. 원소의 제거: O(1)
3. 제일 상단의 원소 확인이 O(1)
4. 제일 상단이 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능❗️
   (cf. 배열로 스택을 구현할 경우 가능하기도 함)

스택의 구현

1) 배열

const int MX = 1000005;
int dat[MX];
int pos = 0; // 스택 내의 원소의 수를 의미하기도 함

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

void pop() {
	pos--;
    // 나중에 push가 발생하면 어차피 덮어씌워질 것이므로 추가적인 연산 불필요
}

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

2) 연결 리스트

STL stack

이왕이면 STL을 사용하는 것이 좋음

int main(void) {
  stack<int> S;
  S.push(10); // 10
  S.push(20); // 10 20
  S.push(30); // 10 20 30
  cout << S.size() << '\n'; // 3
  if(S.empty()) cout << "S is empty\n";
  else cout << "S is not empty\n"; // S is not empty
  S.pop(); // 10 20
  cout << S.top() << '\n'; // 20
  S.pop(); // 10
  cout << S.top() << '\n'; // 10
  S.pop(); // empty
  if(S.empty()) cout << "S is empty\n"; // S is empty
  cout << S.top() << '\n'; // runtime error 발생
}