[실전 알고리즘] 스택

1. 정의와 성질

자료구조에서의 스택은 한쪽 끝에서 원소를 넣거나 뺄 수 있는 자료 구조이다.

 

스택은 구조적으로 먼저 들어간 원소가 제일 마지막에 나오는데, 이런 의미로 FILO(First In Last Out) 자료구조라고 부르기도 한다.

참고로 큐나 덱도 스택처럼 특정 위치에서만 원소를 넣거나 뺄 수 있는 제한이 걸려있다.

 

스택의 성질

1. 원소의 추가가 O(1)
2. 원소의 제거가 O(1)
3. 제일 상단의 원소 확인 O(1)
4. 제일 상단이 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능

스택에서는 제일 상단이 아닌 나머지 원소들의 확인/변경 기능이 제공되지 않는다. STL stack에서도 이 기능은 없다. 

---

2. 기능과 구현

const int MX = 1000005;
int dat[MX];
int pos = 0;

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

 

스택을 배열로 구현할 때에는 단지 원소를 담은 큰 배열 한 개와 인덱스를 저장할 변수 한 개만 필요하다.

이들이 실제 스택에 어떻게 대응되는 방식을 확인해보면 다음과 같다.

{13,21,30}이 담겨있는 스택을 나타내기 위해 dat[0], dat[1], dat[2] 각각에 13, 21, 30 썻고 pos는 3이란느 값을 가진다.

이와 같이 스택의 값들은 dat의 0번지부터 저장되고 pos는 다음에 원소가 추가될 때 삽입해야하는 곳을 가리키고 있다.

그리고 잘 생각해보면 pos의 값이 스택의 길이, 즉 스택 내의 원소의 수를 의미한다는 것을 알 수 있다.

 

구현

push 함수

void push(int x){
	dat[pos++] = x;
}

 

 

pop 함수

void pop(){
	pos--;
}

 

 

top 함수

int top(){
	return dat[pos-1];
}

---

스택부터는  본격적으로 활용할 수 있는 방법이 굉장히 많아진다. 대표적인 사례로 수식의 괄호 쌍이랑 전위/중위/후위 표기법, DFS, Flood Fill 등이 있다.