[실전 알고리즘] 0x05강 - 스택

1. 정의와 성질

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

먼저 들어간 원소가 제일 나중에 나오는 FILO(First In Last Out) 자료구조이다.

 

+) 참고로 큐나 덱도 스택처럼 특정 위치에서만 원소를 넣거나 뺄 수 있는 제한이 걸려있어 스택, 큐, 덱을 묶어서 Restricted Structure라고 부르기도 한다.

 

스택의 성질

1. 원소의 추가 - O(1)

2. 원소의 제거 - O(1)

3. 제일 상단의 원소 확인 - O(1)

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

 

원칙적으로 불가능하다는 뜻을 잘 이해할 필요가 있는데, 원래 스택이라는 자료구조는 원소의 추가/제거/제일 상단의 원소 확인이라는 기능만 제공하는 자료구조이다. 제일 상단이 아닌 나머지 원소들의 확인/변경은 스택에서 제공하는 기능이 아니다. 구현을 할 때 배열을 기반으로 구현해서 해당 기능이 가능하도록 만들 수는 있지만, 스택의 응용 사례들을 보면 모두 원소의 추가/원소의 제거/제일 상단의 원소 확인 기능만을 필요로 한다.

 

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

 

---

2. 기능과 구현

스택은 배열이나 연결 리스트를 이용해서 구현 가능하다. 배열을 이용하는 게 더 쉽다. 배열로 구현 시 단지 원소를 담은 큰 배열 한 개와 인덱스를 저장할 변수 한 개만 필요하다. 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();
}

 

---

3. 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 발생
}

주로 push, pop, top, empty, size 멤버 함수를 쓰게 될 것이다. 스택이 비어있는데 top이나 pop을 호출하면 런타임 에러가 발생한다. 그렇기 때문에 스택이 비어있을 때에는 top이나 pop을 호출하지 않도록 해야한다.

---

4. 연습문제

BOJ 10828번: 스택

10828번: 스택

 

STL stack 이용

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

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    stack<int> stack;
    int n, x;
    string s;
    cin >> n;
    for (int i = 0; i < n; i++)
    {

        cin >> s;

        if (s == "push")
        {
            cin >> x;
            stack.push(x);
        }
        else if (s == "pop")
        {
            if (stack.empty())
            {
                cout << -1 << "\n";
            }
            else
            {
                int tmp = stack.top();
                stack.pop();
                cout << tmp << "\n";
            }
        }
        else if (s == "size")
        {
            cout << stack.size() << "\n";
        }
        else if (s == "empty")
        {
            if (stack.empty())
            {
                cout << 1 << "\n";
            }
            else
            {
                cout << 0 << "\n";
            }
        }
        else if (s == "top")
        {
            if (stack.empty())
            {
                cout << -1 << "\n";
            }
            else
            {
                cout << stack.top() << "\n";
            }
        }
    }

    return 0;
}

STL 이용 X

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

int dat[100000];
unsigned int pos;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n, x;
    string s;
    cin >> n;
    for (int i = 0; i < n; i++)
    {

        cin >> s;

        if (s == "push")
        {
            cin >> x;
            dat[pos++] = x;
        }
        else if (s == "pop")
        {
            if (!pos)
            {
                cout << -1 << "\n";
            }
            else
            {
                cout << dat[--pos] << "\n";
            }
        }
        else if (s == "size")
        {
            cout << pos << "\n";
        }
        else if (s == "empty")
        {
            if (!pos)
            {
                cout << 1 << "\n";
            }
            else
            {
                cout << 0 << "\n";
            }
        }
        else if (s == "top")
        {
            if (!pos)
            {
                cout << -1 << "\n";
            }
            else
            {
                cout << dat[pos - 1] << "\n";
            }
        }
    }

    return 0;
}

 

---

참고자료

[실전 알고리즘] 0x05강 - 스택

[실전 알고리즘] 0x05강 - 스택