0x05강 - 스택

목차

0x00 정의와 성질

0x01 기능과 구현

0x02 STL stack

0x03 연습문제 

---

0x00 정의와 성질

원소의 추가가 O(1)
원소의 제거가 O(1)
제일 상단의 원소 확인이 O(1)

 

stack은 상단에서만 데이터를 push pop 할 수 있는 자료구조다.

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

push() : 상단에 x를 추가 
pop()   : 최상단의 데이터를 제거 
top()   : 최상단의 데이터를 조회(확인)

---

0x01 기능과 구현

배열을 이용해 직접 스택을 구현해봤다.  기본 코드는 바킹독 github 를 가져왔고, 직접 push, pop, top 함수를 채웠다. 

 내가 작성한 코드 

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

const int MX = 1000005;
int dat[MX];
int pos = 0; // 삽입할 수 있는 인덱스

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

void pop(){
    if(pos != 0) 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) {
    ios_base::sync_with_stdio(0);
    cin.ignore(0);

    test();
    return 0;
}

 

아래는 바킹독님이 제공한 정답 코드

내코드보다 짧게 처리된 부분이 많았다. 

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

void pop(){
  pos--;
}

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

---

0x02 STL stack

STL에서 stack을 제공하니깐 코테에서는 이것을 이용하자. 

직접 stack을 구현하는 것 보다는, 실수를 줄일 수 있기 때문이다. 

스택이 비어있는데 top()을 호출하면 런타임 에러가 발생하니까 주의하자. 
스택이 비어있는데 pop()을 호출해도 마찬가지로 런타임 에러가 난다. 

#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 (최근에 넣은 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

    cout << s.top() << '\n'; // <--- runtime error 발생 !

    return 0;
}

 

0x03 연습문제 

스택 문제집 BOJ

백준 문제	내가 푼 코드
스택
제로	내 코드
스택 수열
탑	내 코드
옥상 정원 꾸미기
오큰수
오아시스 재결합

 

---

다음 시간에는 큐를 공부한다. 

공부 내용 출처  바킹독 알고리즘 스택