Stack(스택)

개념

한 쪽 끝에서만 자료를 넣고 뺄 수 있는 LIFO(Last In First Out) 형식의 자료 구조

LIFO(Last In First Out)
가장 최근에 스택에 추가한 항목(top)이 가장 먼저 제거될 항목이다.

이는 알고리즘 구현시 임시 목록에 객체를 추가한 다음 나중에 목록에서 객체를 꺼내려고 할 때 필요하다.

연산

• push(item) : item 을 top에 추가한다.
• pop() : top을 제거한다.
• top() : top을 반환한다.
• empty() : 스택이 비어 있으면 true
• size() : 스택의 크기를 반환한다.

사용 사례

재귀 알고리즘을 사용하는 경우 스택이 유용하다.

• 재귀 알고리즘
  재귀적으로 함수를 호출해야 하는 경우에 임시 데이터를 스택에 넣어준다.
  재귀함수를 빠져 나와 퇴각 검색(backtrack)을 할 때는 스택에 넣어 두었던 임시 데이터를 빼 줘야 한다.
  스택은 이런 일련의 행위를 직관적으로 가능하게 해 준다.
  또한 스택은 재귀 알고리즘을 반복적 형태(iterative)를 통해서 구현할 수 있게 해준다.
• 웹 브라우저 방문기록 (뒤로가기)
• 실행 취소 (undo)
• 역순 문자열 만들기
• 수식의 괄호 검사 (연산자 우선순위 표현을 위한 괄호 검사)
  Ex) 올바른 괄호 문자열(VPS, Valid Parenthesis String) 판단하기
• 후위 표기법 계산

💡 참고 포스팅

[자료구조] 스택(Stack)이란
C++ 스택 자료구조