[실전 알고리즘] 스택

정의와 성질

 

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

스택의 성질

1. 원소의 추가와 제거가 모두 O(1)

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

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

 

 

기능과 구현

 

1. 코드로 직접 구현

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

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

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

void pop(){
  pos--;
}

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

void test(){
  push(5); push(4); push(3);
  cout << top() << '\n'; // 3
  pop(); pop();
  cout << top() << '\n'; // 5
  push(10); push(12);
  cout << top() << '\n'; // 12
  pop();
  cout << top() << '\n'; // 10
}

int main(void) {
	test();
}

 

2. STL로 구현

#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 발생
}

 

연습 문제

 

정답풀이

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

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin >> n;
  stack<int> S;
  while(n--){ // n번 반복
    string c;
    cin >> c;
    if(c=="push"){
      int t;
      cin >> t;
      S.push(t);
    }
    else if(c=="pop"){
      if(S.empty()) cout << -1 << '\n';
      else{
        cout << S.top() << '\n';
        S.pop();
      }
    }
    else if(c=="size")
      cout << S.size() << '\n';
    else if(c=="empty")
      cout << (int)S.empty() << '\n';
    else{ // top
      if(S.empty()) cout << -1 << '\n';
      else cout << S.top() << '\n';
    }
  }
}

10828번: 스택 (acmicpc.net)

 

 

출처

BaaaaaaaarkingDog | [실전 알고리즘] 0x05강 - 스택 (encrypted.gg)