스택(Stack)이란?
stack = 쌓다, 쌓이다, 채우다
개념
스택(Stack)는 LIFO(Last In First Out) 를 따른다.
즉, 가장 최근에 스택에 추가한 항목이 가장 먼저 제거될 항목이다.
구멍이 하나밖에 없는 병이라고 생각하면 된다.
기능
- pop(): 스택에서 가장 위에 있는 항목을 제거한다.
- push(item): item 하나를 스택의 가장 윗 부분에 추가한다.
- peek(): 스택의 가장 위에 있는 항목을 반환한다.
- isEmpty(): 스택이 비어 있을 때에 true를 반환한다.
구현
문제의 종류에 따라 배열보다 스택에 데이터를 저장하는 것이 더 적합한 방법일 수 있다.
배열과 달리 스택은 상수 시간에 i번째 항목에 접근할 수 없다.
하지만 스택에서 데이터를 추가하거나 삭제하는 연산은 상수 시간에 가능하다.
배열처럼 원소들을 하나씩 옆으로 밀어 줄 필요가 없다.
스택(Stack)은 연결리스트로 구현할 수 있다. 연결리스트의 같은 방향에서 아이템을 추가하고 삭제하도록 구현한다.
파이썬에서의 스택 = list를 사용
파이썬은 스택 자료구조는 따로 제공하지 않는다. 다만 기본 클래스인 list를 통해 스택을 흉내 낼 수 있다.
사용 사례
-> 재귀 알고리즘을 사용하는 경우 스택이 유용하다.
재귀 알고리즘
인형 안에 더 작은 인형이 나오는 러시아 인형처럼 어떤 문제를 해결하기 위해 알고리즘을 설계할 때 동일한 문제의 조금 더 작은 경우를 해결함으로써 그 문제를 해결하는 것입니다. 문제가 간단해져서 바로 풀 수 있는 문제로 작아질 때까지 말이죠. 이런 테크닉을 재귀라고 합니다.
재귀적으로 함수를 호출해야 하는 경우에 임시 데이터를 스택에 넣어준다.
재귀함수를 빠져 나와 퇴각 검색(backtrack)을 할 때는 스택에 넣어 두었던 임시 데이터를 빼 줘야 한다.
스택은 이런 일련의 행위를 직관적으로 가능하게 해 준다.
또한 스택은 재귀 알고리즘을 반복적 형태(iterative)를 통해서 구현할 수 있게 해준다.
- 웹 브라우저 방문기록 (뒤로가기)
- 실행 취소 (undo)
- 역순 문자열 만들기
- 수식의 괄호 검사 (연산자 우선순위 표현을 위한 괄호 검사)
Ex) 올바른 괄호 문자열(VPS, Valid Parenthesis String) 판단하기 - 후위 표기법 계산
참고 문서 : https://gmlwjd9405.github.io/2018/08/03/data-structure-stack.html
