[바킹독 알고리즘]0x05강 - 스택

0x00 정의와 성질

정의

마치 프링글스 통과 비슷하다

 

자료구조에서의 스택이란, 한쪽 같에서만 원소를 넣거나 뺼 수 있는 자료구조이다.

 

스택은 구조적으로 먼저 들어간 원소가 제일 나중에 나오게 되는데, 이런 의미로 FILO(First in Last Out) 자료구조라고 부르기도 한다. 참고로 큐나 덱도 스택처럼 특정위치에서만 원소를 넣거나 뺼 수 있는 제한이 걸려있다. 그래서 스택, 큐, 덱을 묶어서 Restricted Structure라고 부르기도 한다.

 

 

 

성질

 

스택에서는 제일 상단이 아닌 나머지 원소들의 확인/변경 기능이 제공되지 않는다. STL stack에서도 이 기능은 없다. 그리고 스택을 활용하는 예시들을 보면 애초에 제일 상단이 아닌 나머지 원소들의 확인/변경이 필요하지 않다. 하지만 배열을 이용해 스택을 구현하면 기본적인 스택의 기능 이외에도 제일 상단이 아닌 나머지 원소들의 확인/변경을 가능하도록 만들 수는 있다.

 

 

0x01 기능과 구현

기본 틀 (예시로 13, 21, 30이 들어있다)

 

 

push 함수는 스택에 x를 추가하는 함수이고, pop 함수는 스택의 꼭대기에 위치한 원소를 제거하는 함수이고, top 함수는 스택의 꼭대기에 위치한 원소의 값을 확인하는 함수이다.  구현을 해보자.

 

 

 

 

 

완성코드

#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();
}

 

 

0x02 STL stack

 

stack STL을 사용하기 위해서는 #include <stack> 헤더파일을 포함해야 한다.

stack <데이터 타입>이름;    으로 선언한다.

#include <stack>
stack<int> stack;

 

 

스택의 기본함수에는 push, pop, top, size, empty, swap 등이 있다.

 

여기서 empty는 스택이 비어있는지 확인하는 기능이고, swap은 스택1과 스택2의 내용을 바꾸는 기능을 한다.

swap(stack1 , stack2)

 

 

주의점으로는,   스택이 비어있는데 top이나 pop을 호출하면 에러가 발생한다. 

 

 

 

 

 

0x03 연습문제

BOJ 10828번:스택

#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--){
        string op;
        cin >> op;
        if(op == "push") {
            int a;
            cin >> a;
            s.push(a);
        }
        else if(op == "pop"){
            if(s.empty()) cout << -1 << '\n';
            else {
                cout << s.top() <<'\n';
                s.pop();
            }
        }
        else if(op == "size") cout << s.size() << '\n';
        else if(op == "empty") {
            if(s.empty()) cout << 1 << '\n';
            else cout << 0 << '\n';
        }
        else {
            if(s.empty()) cout << -1 << '\n';
            else cout << s.top() << '\n';
        }
     }
}