0x05. 스택(Stack) - LIFO 자료구조

0x05 스택

0x00 정의와 성질

정의

스택 : FILO (First In Last Out) , Restricted Structure ( 특정 위치에서만 원소를 넣거나 뺄 수 있는 제한 )

성질

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

0x01 기능과 구현

구현

Push 함수

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

Pop 함수

void pop(){
    pos--;
}

Top 함수

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

0x02 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 발생
}

→ 스택이 비어있을 경우 top, pop 함수 호출하면 런타임 에러 발생!!

0x03 연습문제

BOJ 10828 : 스택

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

int main() {
    stack<int> stack;
    int n;
    cin >> n;

    string s;
    while(n--) {
        cin >> s;
        if(s == "push") {
            int buffer;
            cin >> buffer;
            stack.push(buffer);
        } else if(s == "pop") {
            if(!stack.empty()) {
                cout << stack.top() << "\n";
                stack.pop();
          } else {
              cout << -1 << endl;
          }
        } else if(s= "size") {
              cout << stack.size() << "\n";
        } else if(s= "empty") {
              cout << stack.empty() << "\n";
        } else if(s= "top") {
              if(!stack.empty()) {
                cout << stack.top() << "\n";
              } else {
                cout << -1 << "\n";
              }
        }
    }
}

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

int main() {
    int n;
    string s;

    cin >> n;
    while(n--) {
        cin >> s;
        if(s == "push") {
            int buffer;
            cin >> buffer;
            push(buffer);
        } else if(s == "pop") {
            if(pos != 0) {
                cout << top() << "\n";
                pop();
          } else {
              cout << -1 << endl;
          }
        } else if(s= "size") {
              cout << pos << "\n";
        } else if(s= "empty") {
            if(pos= 0) cout << 1 << "\n";
              else cout << 0 << "\n";
        } else if(s= "top") {
              if(pos = 0) {
                cout << top() << "\n";
              } else {
                cout << -1 << "\n";
              }
        }
    }
}

문제 풀이

이번 강의에 해당하는 문제는 총 7개였다. 하지만 전 문제들과 달리 기본문제는 하나였고 나머지는 응용문제였다.

기본문제도 풀어본 문제여서 이번 강의에 해당하는 문제는 스킵하고 진도를 나간 후에 풀어보도록 할 예정이다.

Note_ 1874번 스택 수열 : 스택의 push, pop을 이용해서 만들 수 있는 수열인지 판단, 만들 수 있다면 +(push), -(pop)을 순서대로 출력

int buffer;
cin >> buffer;

while(cnt <= buffer) {
    S.push(cnt++);
    res += "+\n";
}

if(S.top() != buffer) {
    cout << "NO\n";
    return 0;
}

S.pop();
res += "-\n";

→ 로직이 잘 생각나지 않았던 문제. 기억해두기 - !!

2493번 탑 : 탑의 전파가 왼쪽으로 전파된다. 높이가 더 높은 첫번째 탑이 수신

stack<pair<int, int>> tower;
tower.push({100000001, 0});
for(int i=1; i<=n; i++) {
     int height;
     cin >> height;

     while(tower.top().first < height)
            tower.pop();

     cout << tower.top().second << " ";
     tower.push({height, i});
}

→ pair로 스택을 만들어서 스택을 사용해 시간복잡도를 낮출 수 있었다.

Note_ 나중에 풀기

6198번 : 옥상 정원 꾸미기
17298번 : 오큰수
3015번 : 오아시스 재결합
6549번 : 히스토그램에서 가장 큰 직사각형

리뷰

스택은 많이 만들어 보기도 했고 완벽하게 알고 있다고 자신할 수 있는 자료구조라서 별로 어렵게 다가 오지도 않았고 강의도 짧고 전반적으로 가장 쉽게 진도가 나가지는 강의였다.

잘 아는 파트는 복습하는 느낌으로 빠르게 스킵하도록 하겠다.

다음은 0x06강 큐로 돌아오겠다.

출처: 바킹독님의 실전알고리즘 강의