stack

스택은 가장 마지막으로 들어간 데이터가 가장 첫 번째로 나오는 성질인 LIFO(Last in First Out)을 가진 자료구조

그 유명한 후입선출이다.

마지막으로 들어온 애들이 처음으로 나온다.

 

재귀적인 함수, 알고리즘에 사용되며 웹 브라우저 방문 기록 등에 쓰인다.

 

삽입 및 삭제에 O(1), 탐색에 O(n)이 걸립니다.

 

탐색에 O(n)이 걸리는 이유는 n번째 요소를 찾는다고 하면 그 이전에 들어있던 요소들을 거쳐서 찾아야 하기 때문이다.

순회를 하는거죠.

그 과정을 n번 반복해야 찾을 수 있기 때문에 O(n)이 걸립니다.

 

LIFO 그림

LIFO, 가장 마지막으로 들어간 데이터가 가장 첫번째로 나오는 구조를 지녔습니다.

 

코드로 확인해볼까요?

 

#include <iostream>
#include <stack>

using namespace std;

stack<int> stk;

int main()
{
    for (int i = 0; i < 10; ++i)
    {
        stk.push(i);
    }
    
    while (stk.size())
    {
        cout << stk.top() << '\n';
        stk.pop();
    }
}

 

 

 

분명 push했을때는 0, 1, 2 순서대로 넣었는데, 출력할 때는 거꾸로 나오는 것을 볼 수 가 있다.

스택에서 코딩테스트 문제가 자주 나오는 것들은 주로 '문자열 폭발', '아름다운 괄호만들기', '짝찾기 키워드'를 기반으로 이루어진 문제에서 쓰일 수 있다.

 

스택 함수들을 알아보자.

 

push(value)

해당 value를 스택에 추가합니다.

 

pop()

가장 마지막에 추가한 요소를 지운다. 또는 가장 위에 있는 요소를 지운다.

 

 

top()

가장 마지막에 있는 요소를 참조합니다.(가장 위에 있는 요소를 참조한다고 보면 될 것 같습니다.)
실제 데이터는 꺼내지 않습니다.

 

size()

스택의 크기를 반환하는 함수