정의와 성질

스택은 LIFO이다. 큐, 덱, 스택 같은 특정 위치에서만 원소를 넣거나 뺄 수 있는 제한된 자료구조를 Restricted Structure라고 부른다.

스택의 성질

원소의 추가 O(1)
원소의 제거 O(1)
제일 상단의 원소 확인 O(1)
나머지 원소들의 확인/변경 원칙적으로 불가능

기능과 구현

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

일단 여기서 원소를 담은 큰 배열과 인덱스를 저장할 변수 한 개만 있으면 구현이 가능하다. pos는 원소의 개수이자 추가할 때 삽입해야 하는 인덱스를 의미한다.

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

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

void push(int x){
    dat[pos]=x;
    pos++; //dat[pos++]=x;로 한 줄로 표현도 가능, 전치 후치 차이에 대해 알고 있기 
}

void pop(){
    pos--; //여기까지만 써도 됨 
    /* 어차피 아래 코드들은 나중에 push할 때 덮어쓸 공간
    cout<<dat[pos];
    dat[pos]=0; */
}

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

void test(){

}

int main(void){
    test();
}

음 연결 리스트 하다가 얘 하니까 구현은 쉽다. 그래도 바킹독 강의에서는 STL을 권장한다. STL stack을 썼으면 최소 스택 쪽에는 문제 없다는 걸 알 수 있으니 로직 개선에 신경 쓸 수 있다.

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

int main(void){
    stack<int> s;
    s.push(10);
    s.push(20);
    cout<<s.size()<<'\n'; // 2
    s.empty(); // bool 
    s.pop(); //10만 남을 것 
}

coding