정의와 성질

스택은 한쪽 끝에서만 원소를 넣거나 뺄 수 있는 자료구조. 프링글스 통을 생각하면 쉽다.
스택은 구조적으로 가장 먼저 들어간 원소가 마지막에 나오게 되는 FILO(First In Last Out) 자료구조이다.
참고로 큐나 덱도 스택처럼 특정 위치에서만 원소를 넣거나 뺄 수 있는 제한이 걸려있다. 스택, 큐, 덱을 묶어서 Restricted Structure라고 부르기도 함!

스택에는 원소의 추가 제거가 가장 상단에서만 이루어진다. 따라서 추가,제거, 상단의 원소 확인이 모두 O(1)의 시간복잡도를 갖게 됨.
스택에서는 상단이 아닌 나머지 원소들을 확인/변경하는 것이 원칙적으로는 불가능(배열로 직접 구현하여 확인하는 것이 가능하기는 함). 스택 활용 예시를 보면 최상단 이외의 원소를 다뤄야 할 필요가 없기도 하다.

기능과 구현

배열을 이용하여 구현해보자. 아주 간단함.

push 함수

pos가 가르키는 위치를 한 칸 옮긴 뒤 x를 대입하면 끝

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

pop 함수

그냥 pos의 위치를 한 칸 이전으로! 직접 값을 바꾸거나 삭제할 필요는 없다. 어차피 새롭게 push하면 변경 됨

void pop(){
	pos--;
}

top 함수

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

STL stack

stl의 스택에는 push, pop, top, empty, size 함수가 존재한다.
스택이 비어있을 때 pop이나 top함수를 호출하면 런타임 에러가 발생한다. 그렇기 때문에 코드를 다 짜고나서도 스택이 비어있을 경우를 항상 생각하기!

연습문제

백준10828 스택

STL stack을 이용한 방법과 직접 구현하는 방법 두 가지로 풀어보자.

풀이

내 코드

<stl 풀이>

#include <iostream>
#include <stack>

using namespace std;

int main()
{
    stack<int> st;
    int N,x;
    string order;
    cin >> N;
    while(N--){
        cin >> order;
        if(order == "push"){
            cin >> x;
            st.push(x);
        }
        else if(order == "pop"){
            if(!st.empty()){
                cout << st.top() << "\n";
                st.pop();
            }
            else cout << "-1\n";
        }
        else if(order == "size") cout << st.size() << "\n";
        else if(order == "empty") {
            if(!st.empty()) cout << "0\n";
            else cout << "1\n";
            
        }
        else {
            if(!st.empty()) cout << st.top() << "\n";
            else cout <<"-1\n";
        }
    }

    return 0;
}

<구현 풀이>

#include <iostream>

using namespace std;

int pos=0;
int stack_arr[100001];

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

void pop(){
    if(pos == 0) cout << "-1\n";
    else{
        cout << stack_arr[pos-1]<<"\n";
        pos--;
    }
}

void size(){
   cout << pos << "\n";
}

void empty(){
    if(pos == 0) cout << "1\n";
    else cout << "0\n";
}

void top(){
    if(pos == 0) cout << "-1\n";
    else{
        cout << stack_arr[pos-1]<<"\n";
    }
}

int main()
{
    int N,x;
    string order;
    cin >> N;
    while(N--){
        cin >> order;
        if(order == "push"){
            cin >> x;
            push(x);
        }
        else if(order == "pop") pop();
        else if(order == "size") size();
        else if(order == "empty") empty();
        else top();
    }

    return 0;
}