실전 알고리즘 0x05 스택

 스택

[ 정의와 성질 ]

- FILO( First In Last Out ) 자료구조

- 스택, 큐, 덱을 묶어서 Restricted Structure라고 부른다.

- 원소의 추가/제거 O(1)

- 제일 상단의 원소 확인이 O(1)

- 제일 상단이 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능하다. ( 배열을 이용하면 가능하게 할 수 있다 )

 

[ 기능과 구현 ]

- 배열, 연결 리스트로 구현 가능하다.

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

- push ( 원소 추가 )

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

- pop ( 원소 제거 )

void pop() {
	pos--;
}

- top ( 제일 상단의 원소 확인 )

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

 

[ STL stack ]

- reference : http://www.cplusplus.com/reference/stack/stack/

 

#include <bits/stdc++.h>
using namespace std;

int main(void) {
  stack<int> S;
  S.push(10); // 10
  S.push(20); // 10 20
  S.push(30); // 10 20 30
  cout << S.size() << '\n'; // 3
  if(S.empty()) cout << "S is empty\n";
  else cout << "S is not empty\n"; // S is not empty
  S.pop(); // 10 20
  cout << S.top() << '\n'; // 20
  S.pop(); // 10
  cout << S.top() << '\n'; // 10
  S.pop(); // empty
  if(S.empty()) cout << "S is empty\n"; // S is empty
  cout << S.top() << '\n'; // runtime error 발생
}

- stack이 비어있을 때 top()이나 pop()을 하면 런타임 에러가 발생한다.

 

[ 활용성 ]

- 수식의 괄호 쌍

- 전위/중위/후위 표기법 ( 코딩테스트에 나올 확률이 0에 가깝다 )

- DFS

- Flood Fill