스택

생활 속 자료구조와 알고리즘

초콜릿맛, 바닐라맛, 딸기맛이 차례대로 쌓여 있는 아이스크림 콘을 만드는 과정을 생각해 보자.

아이스크림 콘을 만들 때 우선 가장 아래쪽에 초콜릿을 녹여 넣은 후 그 위에 커피맛을, 그 위에 바닐라맛을, 그 위에 딸기맛을 쌓았을 것이다. 즉, 아이스크림을 쌓은 차례는 초콜릿->커피->바닐라->딸기 순이다.
그런데 철수는 아이스크림 맨 아래쪽에 있는 초콜릿을 좋아한다. 좋아하는 초콜릿을 먹으려면 어떻게 해야 할까? 순서대로 쌓여 있는 딸기->바닐라->커피를 차례대로 먹어야 초콜릿을 먹을 수 있다. 즉, 아이스크림 콘을 쌓았던 순서와 반대로 먹어야 한다. 이렇게 가장 먼저 넣은 초콜릿을 가장 나중에 먹을 수 있는 구조가 스택 구조다.

스택의 기본

1.스택의 개념

스택 자료구조는 한쪽 끝이 막힌 형태다. 스택 예로 한쪽 끝이 막힌 주차장, 프링글스 과자통, 종이컵 수거함, 연탄 화로, 동전통 등이 있다. 입구 겸 출구를 공통으로 사용하는 모든 형태를 스택 예로 볼 수 있다.

스택의 가장 큰 특징은 입구가 하나뿐이기 때문에 먼저 들어간 것이 가장 나중에 나오는 구조다. 이를 선입후출(First In Last Out,FIFO)이라고 하거나 반대로 후입선출(Last In First Out, LIFO)이라고 한다.

스택 구조에서 주의할 점은 수거함에 넣을 때는 사용자가 커피, 녹차, 꿀물 등 종이컵을 지정해서 넣을 수 있지만, 빼낼 때는 특정 종이컵을 선택할 수 없다는 것이다. 빼낼 때는 항상 수거함(=스택)의 맨 위에 있는 종이컵이 나올 수 밖에 없는 구조다. 그래서 '꿀물 종이컵 빼기'가 아닌 그냥 '종이컵 빼기'작동으로 제한된다.

2.스택 원리

스택은 한쪽만 뚫려 있는 구조이기 때문에 삽입과 추출이 한쪽에서만 진행된다. 스택에 데이터를 삽입하는 작동을 push라고 하며, 반대로 데이터를 추출하는 작동을 pop이라고 한다. 스택에서는 top이라는 용어가 중요한데, 현재 스택에 들어 있는 가장 위의 데이터 위치를 가리키는 개념이다. 스택은 입구가 1개뿐이므로 push와 pop이 모두 한쪽에서만 작동한다.

데이터 삽입: push
스택에 데이터를 삽입하는 push 과정을 알아보자. 스택 5칸이 모두 빈 상태, 즉 top 값이 비어 있다는 의미로 -1인 상태에서 커피 종이컵을 삽입(push)하면 1단계에서 top을 증가시킨다. 그리고 2단계에서 증가시킨 top위치인 0번 칸에 데이터(커피 종이컵)을 삽입한다.

데이터 추출: pop
스택에서 데이터를 추출(pop)하는 것은 맨 위에 있는 데이터를 꺼내는 과정이다. 입구가 하나뿐이므로 맨 위에 있는 것을 꺼낼 수밖에 없으며, 중간에 있는 데이터는 꺼낼 수 없다. 그래서 데이터를 추출할 때는 어떤 값을 지정해서 꺼낼 수 없고, 그냥 추출 과정만 전달하면 된다.

즉, 현재 녹차와 커피가 들어 있다고 가정한 상태에서 녹차를 지정해서 꺼내는 것이 아니라 그냥 pop을 하면 자연스럽게 맨 위에 있는 녹차가 추출된다.

커피와 녹차 데이터가 들어 있는 스택에서 녹차를 지정해서 꺼내는 것이 아니라 그냥 pop하면 1단계에서 top이 가리키는 위치의 데이터(녹차 종이컵)를 꺼내고, 2단계에서 top을 1 감소시킨다.

스택의 응용

1. 웹 서핑에서 이전 페이지 돌아가기
2. 괄호의 매칭 검사