Stack

Stack

정의와 성질

• FILO(Fisrt 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 push(int x){
    dat[pos]=x;
    pos++;
  }
  void pop(){
    pos--;
  }
  int top(){
    if(pos>=1){
        return dat[pos-1];
    }
    else{
        return -1;
    }
  }
  void test(){
    push(5);
    push(4);
    push(3);
    cout<<top()<<'\n';
    pop();
    pop();
  }
  int main(void){
    test();
    return 0;
  }
  

  STL Stack

  #include<iostream>
  #include<stack>
  using namespace std;
  int main(void){
    stack<int> S;
    S.push(10); // 10
    S.push(20); // 10 20
    cout<<S.size()<<'\n'; // 2
    S.pop(); // 10
    S.pop(); //
    if(S.empty()){
        cout<<"empty\n";
    }
    return 0;
  }