개요
스택이란 대표적인 후입선출(Last In First Out, LIFO)형 자료구조이다. 후입선출이란 나중에 들어온 것이 먼저 나간다는 것을 뜻한다.
스택은 데이터를 입력한 순서대로가 아닌, 반대의 순서로 처리해야 할 때 사용된다. 마치 반복문 안의 반복문 안의 반복문에서 가장 나중에 쓴 반복문이 먼저 돌아가듯 스택이 그렇다. 프링글스를 먹을 때처럼, 가장 나중에 있는 것부터 역순으로 데이터를 취하게 되는 것이다.
주요 메소드
기본적으로 다음과 같은 기능을 가진다.
Push()
스택에 데이터를 추가하는 것을 의미한다. 데이터는 항상 스택의 마지막 위치에 추가된다.
항상 마지막 위치에 추가되므로, 복잡한 연산이 필요없다. 따라서 항상 O(1)의 시간복잡도를 가진다.
Pop()
스택에서 데이터를 꺼내는 것을 의미한다. 데이터는 항상 스택의 마지막 위치에서 꺼낸다.
Push와 마찬가지로 항상 마지막 위치의 데이터를 꺼내므로 복잡한 연산이 필요없다. 그렇기에 Pop도 O(1)의 시간복잡도를 가진다.
Peek() 또는 Top()
스택의 가장 마지막 위치에 존재하는 데이터를 조회한다. Pop과 달리 데이터가 꺼내지진 않는다.
A, B, C, D의 데이터가 들어있는 스택에서, Pop과 Push를 차례대로 연산하면 다음과 같은 그림이 나온다.
먼저 들어간 A, B, C는 그대로 보존되며, 가장 나중에 들어갔던 D가 방출되고 새로 E가 들어와 최종적으로는 A, B, C, E의 구조가 되는 것이다.
어떤 때에 쓰이나
웹 브라우저의 뒤로 가기 기능이나, 프로그램의 실행 취소 기능에 스택을 사용할 수 있다. 사용자의 입력을 하나의 데이터로 만든 다음, 스택에 저장했다가 실행 취소를 눌렀을 때 역순으로 돌아가도록 실행시키는 것이다.
위에서는 반복문으로 소개했지만, 함수에서 함수를 부르고, 거기서 또 함수를 부르는 과정 자체가 스택 자료구조를 사용한다고 볼 수 있다.
문자열의 괄호가 제대로 열고 닫혔는지 확인하는데에도 사용할 수 있다. '('가 나온만큼 스택을 더하고, ')'가 나온만큼 스택을 꺼내서 최종적으로 0의 크기가 되면 괄호를 제대로 쓴 것이 되는 것이다.
전/후위 표기식 연산에도 스택을 쓰기 좋다. 여기서 후위 표기식이란 수식을 3 + 4 처럼 쓰지 않고, 3 4 + 로 적어 컴퓨터가 연산하기 좋게 만든 수식을 뜻한다.
