스택 ( Stack )

Table of Contents

 

개요

기본 구조

반환

삽입

삭제

코드

문제

C++ STL stack

 

 

 

1. 개요

 

 스택은 선형 자료구조 중 하나로서 추상화에 큰 도움을 주는 자료구조입니다. 요약하면 선형 구조의 양 끝 중에서 한쪽에서만 자료를 삽입하고 삭제할 수 있는 자료구조를 뜻합니다. 이 요약의 의미는 이후의 '기본 구조'란에서 자세히 설명하겠습니다.

 

 스택은 간단한 선형 자료구조인 만큼, 배열만을 활용해도 간단히 구현할 수 있습니다. 굳이 스택이라는 새로운 이름을 붙여야 하나 싶을 정도로 간단하지요. 게다가 배열보다 자유도도 낮기 때문에 오히려 할 수 있는 일은 더 줄어들게 됩니다.

 

 하지만 스택은 선형 자료구조를 공부할 때 빼놓지 않고 등장하는 주제로서, 꽤 중요한 자료구조 취급을 받습니다. 이는 스택의 효율성이 배열 혹은 리스트보다 딱히 좋을 것이 없을지라도, 추상화에는 큰 도움이 되기 때문입니다. 모든 장소에 자료를 삽입할 수 있었던 배열 대신에 한쪽 끝에서만 자료를 삽입, 삭제할 수 있는 스택을 사용함으로써 프로그램을 좀 더 직관적이고 이해하기 쉽도록 바꾸어 줄 수 있습니다. 또한, 추상화의 간편함은 결국 프로그램의 설계에도 도움을 줄 수 있습니다.

 

 

 

2. 기본 구조

 

 스택은 한쪽 끝에서만 자료의 삽입, 삭제를 할 수 있는 선형 자료구조입니다. 이러한 스택의 특성을 가장 잘 나타내는 단어는 후입선출(LIFO, Last In First Out)입니다. 말 그대로 나중에 들어온 자료가 먼저 빠져나간다는 의미이지요. 이는 아래의 그림을 통해 이해할 수 있습니다.

 

 이 그림은 스택을 시각화한 것으로서 스택의 한쪽 끝, 즉, 위쪽으로만 자료가 삽입되고 삭제된다고 보시면 됩니다. (현실 상황을 예로 들면, 박스 안에 책을 차례로 쌓아놓는 상황을 생각해 볼 수 있습니다.)

 

 왼쪽 상황에서 자료4가 삽입된다고 생각해보면 오른쪽처럼 자료3 위에 자료4가 쌓이게 됩니다. 이제, 이 상황에서 자료가 삭제될 때를 생각해보면 후입선출의 의미를 알 수 있습니다. 자료4에게 막혀서 자료1, 2, 3을 꺼낼 수 없기 때문이지요. 스택은 한쪽으로만 삽입, 삭제를 할 수 있기 때문에 결국 가장 나중에 넣은 자료를 가장 먼저 꺼내게 됩니다. (Last In First Out)

 

 자료4를 삭제하면 이제 자료1, 2, 3만 남게 되고, 더 이상 삽입이 없는 상태에서 삭제를 해야 하면 자료3이 삭제될 것입니다.

 

 이제 스택을 구현해보도록 하겠습니다. 보통 스택은 아래의 3가지 연산을 수행할 수 있도록 구현합니다.

 

연산 1) 끝에 있는 자료를 반환. (가장 위에 있다는 의미로 top이라고도 합니다.)

연산 2) 자료 삽입 (push)

연산 3) 자료 삭제 (pop)

 

 따라서 아래와 같이 자료구조의 기본 구조를 잡을 수 있습니다.

 

const int maxStackSize = 1000000; // 스택의 최대 사이즈
 
struct intStack {
    int stackSize = 0;            // 현재 스택에 들어가 있는 자료의 갯수
    int repository[maxStackSize]; // 자료를 보관할 배열
 
    int top();               // 스택의 끝(top)에 있는 자료를 반환
    void push(int pushData); // 스택에 pushData를 삽입
    void pop();              // 스택의 끝에 있는 자료를 삭제
};

 

 

 

3. 반환

 

 현재 스택에 몇 개의 자료가 있는 지를 저장하는 변수, stackSize를 저장하면 top() 함수는 쉽게 구현할 수 있습니다. repository 배열에 자료를 repository[0], repository[1], repository[2], ... 순서대로 저장하면 repository[stackSize-1] 이 스택의 끝에 있는 자료가 되기 때문입니다. 

 

 이 그림에서 왼쪽 상황을 예시로 들면 repository[0] = 자료1, repository[1] = 자료2, repository[2] = 자료3, repository[3] = 자료4를 저장해 놓은 것입니다. 이 때 stackSize=4 이므로 repository[stackSize-1]을 하면 스택의 끝에 있는 자료를 얻을 수 있습니다.

 stackSize==0 인 경우엔, 스택이 비어있는 것이므로 예외처리를 해주어야 합니다.

 

int top() {
    if(stackSize == 0) return -1;
    return repository[stackSize-1];
}

 

 

 

4. 삽입

 

 repository[0] ~ repository[stackSize-1] 이 채워져 있으므로, 새로운 값이 들어갈 자리는 repository[stackSize]입니다. 따라서 repository[stackSize]에 값을 넣어준 후, stackSize 를 하나 증가시켜주면 삽입이 완료됩니다.

 

void push(int pushData) {
    repository[stackSize++] = pushData;
}

 

 

 

5. 삭제

 

 개념상으로는 가장 위에 있는 repository[stackSize-1] 을 삭제하고 stackSize를 하나 줄여야 합니다. 하지만 배열을 통한 구현에서는 stackSize를 하나 줄이는 것만으로도 repository[stackSize-1]의 값이 무의미해지기 때문에 stackSize--;만 해주면 삭제가 완료됩니다.

 

void pop() {
    if(stackSize != 0)
        stackSize--;
}

 

 

 

6. 코드

 

#include <stdio.h>
 
const int maxStackSize = 1000000;
 
struct intStack {
    int stackSize = 0;
    int repository[maxStackSize];
    
    int top() {
        if(stackSize == 0) return -1;
        return repository[stackSize-1];
    }
    void push(int pushData) {
        repository[stackSize++] = pushData;
    }
    void pop() {
        if(stackSize != 0)
            stackSize--;
    }
};
 
int main() {
    intStack st;
    st.push(1);
    st.push(2);
    printf("%d\n",st.top());
    st.pop();
    printf("%d\n",st.top());
    return 0;
}

 

 

 

7. 문제

 

 (0) [BOJ 10828] 스택

 

 (1) [BOJ 1874] 스택 수열

 

 (2) [BOJ 9012] 괄호

 

(0) ~ (2) 풀이 모음

 

 

 

8. C++ STL stack

 

 C++ STL (standard library) 에 스택이 정의되어 있기 때문에 스택을 손수 구현하지 않아도 사용할 수 있습니다.

 

#include <stdio.h>
#include <stack>
 
using namespace::std;
 
stack<int> st;
 
int main() {
    st.push(1);
    st.push(2);
    printf("%d\n",st.top());
    st.pop();
    printf("%d\n",st.top());
    return 0;
}

 위의 형식처럼 #include<stack>과 using namespace::std; 를 해준다면 stack<자료형>의 형식으로 스택을 선언 및 사용할 수 있습니다. push, top, pop 연산 모두 가능합니다.

 

※ 본문의 코드들은 C++ 17 환경에서 작성되었습니다.

※ 문의 : rikang93@gmail.com