[바킹독 실전 알고리즘 0x05] 스택

정의와 성질

• LIFO(선입선출) 구조이다.
• 특정 위치에서만 원소의 추가나 제거가 이루어진다. 이 성질 덕분에 원소의 추가나 제거는 O(1)이다.
• 제일 상단의 원소를 확인하는 시간복잡도는 O(1)이다.
• 제일 상단이 아닌 나머지 원소들의 확인이나 변경은 원칙적으로 불가능하다. 원칙적으로 불가능해서 배열의 성질을 사용해 나머지 원소들의 확인이 가능하도록 구현할 수는 있지만, 스택의 응용 사례에는 제일 상단의 원소만을 다룬다.

 

기능과 구현

스택은 배열 혹은 연결 리스트를 사용해 구현할 수 있다. 그리고 둘 중 배열을 이용하는 구현 방법이 더 쉽다. 

배열을 사용해 스택을 구현하는 방법은 생각보다 간단한데, 원소들을 모두 담을 큰 배열 하나와 인덱스를 저장할 변수 하나만을 필요로 한다. 

const int MAX = 10000000;
int data[MAX];
int pos = 0;

인덱스를 붙인 스택의 모습은 다음과 같다. pos는 다음 원소가 추가될 때 삽입될 위치를 가리킨다. pos의 값은 stack의 길이, 즉 원소의 개수를 의미하기도 한다.

 

push(): stack에 원소를 추가하는 함수. pos가 가리키는 자리에 원소를 추가한 후, pos를 1 증가하면 된다.

pop(): stack의 꼭대기에 위치한 원소를 제거하는 함수. 단순히 pos를 1 줄이면 된다. 

top(): stack의 가장 위에 있는 원소를 반환하는 함수. data[pos-1]을 리턴하면 된다.

 

 

 

STL stack

스택은 구현이 매우 간단하지만, 그래도 STL을 쓸 수 있다면 쓰는 것이 좋다. STL스택을 사용하면 코드의 로직 내에서 최소 스택 부분에서는 오류가 없음을 확신할 수 있기 때문이다.

STL stack에서는 주로 push, pop, top, empty, size 멤버 함수를 쓴다. push, pop, top은 앞서 구현한 함수와 똑같은 것이다.

스택이 비어있는데 pop이나 top함수를 쓰면 런타임 에러가 발생한다. 따라서 빈 스택일 경우 pop이나 top을 호출하지 않도록 해야 한다.