자료구조 스택 (stack)

스택은 선입 후출(First In Last Out : FILO) 형태의 자료구조이다.

 

스택은 직전 단계로 돌아가는 기능이 필요한 경우 적절하게 사용할 수 있다.

 

인터넷 브라우저의 뒤로 가기 기능이 좋은 예시이다.

인터넷을 이용하는 과정에서 1번 페이지에서 2번 페이지로, 2번에서 3번, 3번에서 4번 페이지 순으로 이동했다고 가정해보자.

 

4번 페이지에서 뒤로 가기 버튼을 누르면 3번 페이지로 이동해야 한다.

마찬가지로 3번 페이지에서 한번 더 뒤로 가기 버튼을 누르면 2번 페이지로 이동해야 한다.

 

위의 예시처럼 이전 상황을 복원해야 하는 상황에서 스택은 좋은 선택이 될 수 있다.

스택의 동작 예시

 

 

 

 스택은 대부분의 프로그래밍 언어에서 라이브러리로 지원되고 있다.

C++ / Java의 경우 push(삽입), pop(삭제), top(현재 값)의 메소드를 이용해 조작할 수 있다.

python의 경우 기본 자료형인 list를 이용하여 append(삽입), pop(삭제), [-1](현재 값)을 이용한다.

 

 

만약 배열 등을 이용하여 직접 스택의 기능을 구현한다면 아래와 같이 

현재 스택의 가장 위를 가리키는 top index와 삽입, 삭제, 현재 값 확인 기능을 구현하여 스택의 최소 기능을 만들 수 있다.

 

스택의 최소 기능

여기에 추가로

• 현재 스택 내의 원소 개수를 반환하는 size
• 현재 스택이 비어 있는지 확인하는 empty

등의 기능을 구현한다면 라이브러리에서 제공하는 스택 대부분을 구현하게 되는 것이다.

 

 

 

실제로 스택을 이용하여 구현 가능한 기능으로는

• 깊이 우선 탐색(DFS)
• 재귀 함수
• 뒤집기(reverse)

등이 있다.