그냥 게임개발자
stack 본문
스택은 가장 마지막으로 들어간 데이터가 가장 첫 번째로 나오는 성질인 LIFO(Last in First Out)을 가진 자료구조
그 유명한 후입선출이다.
마지막으로 들어온 애들이 처음으로 나온다.
재귀적인 함수, 알고리즘에 사용되며 웹 브라우저 방문 기록 등에 쓰인다.
삽입 및 삭제에 O(1), 탐색에 O(n)이 걸립니다.
탐색에 O(n)이 걸리는 이유는 n번째 요소를 찾는다고 하면 그 이전에 들어있던 요소들을 거쳐서 찾아야 하기 때문이다.
순회를 하는거죠.
그 과정을 n번 반복해야 찾을 수 있기 때문에 O(n)이 걸립니다.
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()
스택의 크기를 반환하는 함수
'내 개인적인 공부 > 자료구조' 카테고리의 다른 글
deque (0) | 2024.04.14 |
---|---|
queue (0) | 2024.04.14 |
set? unique? (0) | 2024.04.14 |
set (0) | 2024.04.13 |
unordered_map (0) | 2024.04.13 |