Stack
✍ 막무가내로 알고리즘 문제를 풀다가 깨달았다.
✍ 내가 스택 이라는 자료구조를 많이 써보지 않았다는 것.
그래서 정리하고 넘어가려고 한다.
✍ 왜 정리하고 알고리즘 문제를 풀려고 하는가?
✍ 여러 자료구조와 알고리즘은 관련성이 크다.
✍ 문제를 풀고싶다? --> 고민한다 --> 무슨 방법으로 풀까 ? --> 이런 컬렉션을 쓰면 좋겠다!
✍ 를 생각하게된다.
✍ 하지만 그냥 구현 할 때 습관적으로 ArrayList를 쓰거나 대충 HashMap을 쓰거나..
✍ 아닌 경우 TreeMap을 쓰거나 밖에 없다.. 부끄럽다....
오늘은 크게 나누고 좀 더 세세한 정리를 기록하는 게 낫다고 본다.
크게 보자.
선형 - 비선형이 있다.
선형 : 리스트(llist) / 큐(queue) / 덱(deque)
비선형 : 그래프(graph) / tree (트리)
☁ 스택을 보자.
☁ LAST IN FIRST OUT ( LIFO )이 기본이다. 즉 나중에 들어가면 먼저 나오게된다.
☁ 상자를 쌓고, 상자를 쌓고.... 반복하다가 하나의 상자를 꺼내려면 맨 나중에 올린 상자부터 꺼내야 한다.
중간 부터 꺼낸다면 무너지니까.
리스트 - 벡터 아래에 스택이 있다.
☁ 생각보다 스택을 사용하는 곳이 많다.
☁ 뒤로가기 버튼, 최근에 검색한 단어 , 장기, 체스등의 게임 중에 수를 무른다거나.. 등등.
☁ 스택 메모리 구조 자체도 스택 자료 구조 형식과 동일하다고 한다.
함수를 호출하면, 스택 메모리에 지역 변수가 생성 - 이 때 함수를 호출하면 호출된 함수가 끝날 때까지 해당 함수의 메모리 공간은 계속 남아있게 된다. -- 따라서 가장 나중에 호출된 함수와 그 함수의 지역 변수가 사용하는 메모리는 스택 자료 구조와 같은 방식으로 운영된다.
