[스택]

스택

• 한쪽 끝에서만 자료를 넣거나 뺄 수 있는 자료구조
• FILO(First-In-Last-Out) 형식을 갖는 자료구조

---

스택의 성질

• 원소의 추가가 O(1)
• 원소의 삭제 O(1)
• 제일 상단의 원소의 확인 O(1)
• 제일 상단이 아닌 원소들의 확인 및 변경은 `불가능'

---

배열을 이용한 스택

#include <iostream>
using namespace std;

const int MX = 1000005;
int dat[MX];
int pos = 0;

void pop()
{
    pos--;
}

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

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

int empty()
{
    return pos==0? 1 : 0;
}

int size()
{
    return pos;
}

• pos를 인덱스로 둠으로써 스택을 구현
• pos가 최상단의 원소+1의 인덱스로 둠으로써 스택의 크기를 쉽게 구할 수 있도록함.

---

STL stack

#include <bits/stdc++.h>
using namespace std;

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 발생
}