[바킹독]5. 스택

https://youtu.be/0DsyCXIN7Wg?si=bYuwMhwGlEmQFd4b

https://blog.encrypted.gg/933

[실전 알고리즘] 0x05강 - 스택

 

1. 정의와 성질
2. 기능과 구현
3. STL stack
4. 연습 문제 

 

1. 정의

스택 : 한쪽 끝에서만 원소를 넣거나 뺄 수 있는 자료구조

FILO(First In Last Out) : 구조적으로 먼저 들어간 원소가 제일 나중에 나옴 

cf. Restricted Structure : 특정 위치에서만 원소를 넣거나 뺄 수 있는 제한이 걸려있음 -> 스택, 큐, 덱 

 

2. 성질

1) 원소의 추가 : O(1)

2) 원소의 제거 : O(1)

3) 제일 상단의 원소 확인 : O(1)

4) 제일 상단이 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능 

 

3. 구현

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

 

1) push 함수

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

 

2) pop 함수

void pop(){
  pos--;
}

 

3) top 함수

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

 

4. STL 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 발생
}

 

5. 연습 문제 

BOJ 스택 (10828)

1) STL로 풀이

 

2) 배열로 직접 구현 

pos=0 : 스택이 비었음을 의미

-> pop, empty, top에 활용