[Data Structure] 스택(Stack)

롤 유저들은 나서스라는 챔프에 대해 알 것이다. 나서스는 q스킬이 스택을 쌓고 있다고 흔히들 표현하는데, 그 스택이라고 생각하면 기억하기 용이할 것이라고 생각한다.(데미지에 대한 데이터를 쌓는다)

 

스택

데이터가 논리적(물리적 x)으로 저장되어 있는 자료구조

LIFO(Last In First Out) 마지막에 들어온 데이터가 첫번째로 나가는 자료구조

 

두가지 연산

push : 데이터를 넣는 연산

pop : 데이터를 꺼내는 연산

 

 

시간복잡도

맨위에 있는 데이터를 접근(peek)	O(1)
i번째 데이터 접근	O(N)
x라는 데이터가 있는지 탐색	O(N)
push 연산	O(1)
pop 연산	O(1)

 

Error

Stack 메모리를 초과	Stack Overflow Error
Stack 데이터가 없을 때, pop을 수행할 경우,	Empty Stack Error

 

사용 사례

1. 프로세스의 메모리(코드, 데이터, 힙, 스택) 영역 중 하나에 사용된다.

스택 영역은 함수의 복귀 주소 및 지역 변수를 저장한다.

 

2. 실행 취소를 하는 기능을 구현할 때 가장 최근에 변경사항에 해당하는 데이터를 지워야하기 때문에 사용될 수 있다.