JArchive 프로그래밍 일기

목차

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

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

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