이번에 다룰 스택(Stack)이라는 자료구조와 다음 포스팅에서 다룰 큐(Queue)라는 자료구조는 간단하면서도 유용한 특징 덕분에 자주 활용하는 자료구조에 속한다. 스택과 큐만 잘 이해하고 활용할 수 만 있어도 다른 자료구조나 알고리즘을 배울 때 적극적으로 활용할 수 있을 것이다.
스택(Stack)이란?
스택이라는 자료구조가 어떻게 이루어져 있는지는 책을 쌓아 올린 모습을 보면 편하게 이미지화할 수 있다. 차곡차곡 쌓아 올린 구조에 책이 무너지지 않게 하려면 위에서부터 차근차근 책을 제거해야 한다. (중간에 있는 책을 뽑으면 책이 무너지겠지) 스택이 이런 구조로 되어 있다. 밑에서부터 하나씩 차곡차곡 데이터를 쌓아 올리고 쌓아올린 데이터에 접근하려면 맨 위에 올려져 있는 데이터부터 꺼내 사용해야 한다. 이런 구조를 컴퓨터 과학에서는 LIFO(Last In First Out)이라고 한다. 나중에 들어온 것이 가장 먼저 나간다는 의미이다.
그럼 과연 스택이라고 하는 자료구조가 우리가 사용하는 프로그램 안에서 어떻게 사용되고 있을까? 대표적으로 “뒤로 가기”기능이 있다. 예를 들어 우리가 “네이버”에서 “구글”을 검색하여 “구글”로 이동했고, “구글”에서 “오르카의 IT 공방”을 검색해 들어왔다고 하자. 브라우저는 우리가 이동한 이동 경로를 기억하고 있으므로 뒤로 가기 버튼을 누르면 “오르카의 IT 공방”에서 “구글 검색결과 페이지”로 이동하게 될 것이다. 아래 그림을 참고해보자.
뒤로가기 버튼을 누르면 왼쪽에서 오른쪽으로 변한다 브라우저가 사용자의 페이지 이동기록을 차곡차곡 쌓아 두고 있기 때문에 뒤로 가기 버튼을 누르면 쌓아 놓은 히스토리 중 맨 위쪽 데이터를 가져와 현재 페이지로 보여주게 된다.
스택의 동작
스택은 간단한 구조만큼이나 간단한 동작들로 이루어져 있다. 크게 두 가지 동작으로 이루어져 있는데 스택에 자료를 집어넣는 푸시(Push)라는 동작과 스택에서 자료를 꺼내는 팝(Pop)이라는 동작이다.
동작은 연결리스트보다 간단하다. 간단해도 너무 간단하므로 추가적인 설명이 필요 없을 것으로 생각한다. 사실 스택을 배열을 기반으로 구현하느냐, 연결 리스트를 이용하여 구현하느냐에 따라서 스택 크기를 동적으로 늘리고 줄이는 기능이 추가될 수 있겠지만 기본적인 기능은 Push와 Pop이다.
소스 코드
저번 포스팅에서 언급했듯이 Stack과 Queue는 정말 간단하게 동작하기 때문에 직접 소스코드를 분석해보면 좋겠다. 추후 설명이 빈약하다고 생각되면 소스코드 주석을 통해 설명을 첨부하도록 할 예정이다.