Stack

특징

데이터를 후입선출(LIFO) 기반으로 관리하는 자료구조입니다. 즉, 최근에 추가된 데이터의 우선순위가 가장 높음을 의미합니다. 이때, 데이터 추가(Push)와 삭제(Pop) 연산은 O(1)의 시간복잡도를 가지고 있습니다.

Stack은 아래 그림처럼 세로 형태의 긴 막대로 표현합니다.

이제, 그림을 통해 Stack에서 연산이 어떻게 수행되는지 알아보겠습니다.

Push 연산을 수행하면 가장 위에 데이터를 쌓고, Top 포인터를 위로 한 칸 이동합니다.

Pop 연산을 수행하면 가장 맨 위에 있는 데이터를 삭제한 후 Top 포인터를 아래로 한 칸 이동합니다.

활용

Stack이 활용되는 경우는 다음과 같습니다.

• 후위 표기법 연산
• 괄호 유효성 검사
• 웹 브라우저 방문 기록 (뒤로가기)
• DFS

예상 질문

Stack은 어떤 자료구조인가요?

후입선출을 기반으로 데이터를 관리하는 자료구조입니다.

Queue와 차이점은 무엇인가요?

Queue는 처음에 들어온 데이터의 우선 순위가 높지만, Stack은 가장 최근에 들어온 데이터의 우선 순위가 높습니다.

어디에 활용할 수 있나요?

후위 표기법 연산, 괄호 유효성 검사, 브라우저 방문 기록(뒤로가기), DFS 등에 사용할 수 있습니다.