[ 자료구조 ] 스택 (Stack)

1. 스택의 이해

스택 ( stack ) 은 후입 선출 ( LIFO - Last In First Out )의 특성을 가지는 자료구조이다. 

쉽게 생각하면 한쪽 끝은 막혀있고 한쪽은 뚫려 있는 모습이다.

한쪽 끝이 막혀있는 구조이기 때문에 뚫린 한쪽에서 자료의 삽입과 삭제가 일어난다.

 

2. 스택의 동작

1) 삽입 - push

스택에 새로운 데이터를 삽입하는 작업을 push라고 한다. 이는 top 값을 하나 증가시킨 후 새로운 데이터를 삽입하도록 구현한다.

 

2) 삭제 - pop

스택에서 데이터를 제거하는 작업을 pop이라고 하며 이는 top이 가리키고 있는 자료를 삭제한 후 top 값을 하나 감소시키도록 구현한다.

 

3) 읽기 - peek

스택에서 top이 가리키는 데이터를 읽는 작업을 peek라고 한다.

 

3. 스택의 구현

스택의 구현은 선입선출인 큐보다 쉽다.

스택의 구현은 배열과 연결 리스트 등으로 구현할 수 있다.

 

https://www.acmicpc.net/problem/10828

10828번: 스택

 

배열 구현

#include <iostream>
#include <string>

using namespace std;

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

    //input + solve
    int n,x,idx = -1;
    string s;
    int stack[10001];

    cin >> n;

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


    return 0;
}

 

4. 배열 기반 구현과 연결 리스트 기반 구현의 장단점

사실 Stack STL을 사용하는 게 제일 편하다.

 

 

5. 언더플로우, 오버플로우 ( underflow, overflow )

• overflow: 자료를 꽉 찬 경우 데이터를 삽입하려고 할 때 일어나는 오류
• underflow: 자료가 빈 경우 데이터를 삭제하려고 할 때 일어나는 오류