c++ 알고리즘 공부 5 - 스택

자료구조에서의 스택은 뭐냐하면, 바로 한쪽 끝에서만 원소를 넣거나 뺄 수 있는 자료구조입니다. 대충 프링글스 통을 생각하면 이해가 쉬울 것입니다. 아니면 엘리베이터를 생각해도 되겠습니다.

 

스택은 구조적으로 먼저 들어간 원소가 제일 나중에 나오게 되는데, 이런 의미로 FILO(First In Last Out) 자료구조라고 부르기도 합니다. 참고로 큐나 덱도 스택처럼 특정 위치에서만 원소를 넣거나 뺄 수 있는 제한이 걸려있습니다. 그래서 스택, 큐, 덱을 묶어서 Restricted Structure라고 부르기도 합니다.

 

스택은 특정 위치에서만 원소를 넣거나 뺄 수 있게 제한을 둔 대신에 원소의 추가와 제거가 모두 O(1)입니다. 나중에 구현을 같이 해보겠지만 우리가 배열의 끝에서 원소를 추가/제거할 때 시간복잡도가 O(1)이었던 것과 완전 상황이 똑같습니다. 그리고 제일 상단의 원소 확인 또한 O(1)입니다.

 

대신 스택에서는 제일 상단이 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능합니다. 원칙적으로 불가능하다는 뜻을 잘 이해할 필요가 있는데, 원래 스택이라는 자료구조는 원소의 추가/제거/제일 상단의 원소 확인이라는 기능만 제공하는 자료구조입니다. 그래서 제일 상단이 아닌 나머지 원소들의 확인/변경은 스택에서 제공하는 기능이 아닙니다. 구현을 할 때 배열을 기반으로 구현해서 해당 기능이 가능하도록 만들 수는 있지만, 나중에 스택의 응용 사례들을 보시면 모두 원소의 추가/원소의 제거/제일 상단의 원소 확인 기능만을 필요로 합니다.

 

그래서 정리를 하면, 스택에서는 제일 상단이 아닌 나머지 원소들의 확인/변경 기능이 제공되지 않습니다. STL stack에서도 이 기능은 없습니다. 그리고 스택을 활용하는 예시들을 보면 애초에 제일 상단이 아닌 나머지 원소들의 확인/변경이 필요하지 않습니다. 하지만 배열을 이용해 스택을 구현하면 기본적인 스택의 기능 이외에도 제일 상단이 아닌 나머지 원소들의 확인/변경을 가능하도록 만들 수는 있습니다.

 

 

스택에서 제공되는 연산들을 살펴봤으니 그 다음으로 스택을 어떻게 구현하면 될지 알아보겠습니다. 스택은 배열 혹은 연결 리스트를 이용해서 구현할 수 있습니다. 그리고 둘 중에서 배열을 이용하는게 구현이 더 쉽습니다.

 

스택을 배열로 구현할 때에는 단지 원소를 담은 큰 배열 한 개와 인덱스를 저장할 변수 한 개만 필요합니다. 이들이 실제 스택에 어떻게 대응되는 방식을 확인해보면 오른쪽 그림과 같습니다.