티스토리 뷰

선형 자료구조

스택 ( Stack )

RiKang 2018.01.21 18:26

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)


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


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//code by RiKang, weeklyps.com
 
#include <stdio.h>
typedef int node_type; // 스택에 어떤 형태의 자료가 들어갈 지를 선택합니다.
const int stack_size_max = 1000000// 스택의 최대 사이즈
 
struct DS_stack{
    int stack_size=0// 현재 스택에 몇 개의 자료가 있는 지를 저장합니다.
    node_type arr[stack_size_max]; // 자료를 보관할 배열
    
    node_type top(){ return 0; } // 스택의 끝(top)에 있는 자료를 반환
    void push(node_type v){}     // 스택에 v를 삽입
    void pop(){}                 // 스택의 끝에 있는 자료를 삭제
};
 
int main() {
    return 0;
}
cs




3. 반환


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


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


1
2
3
4
5
//code by RiKang, weeklyps.com
node_type top(){ // 스택의 끝(top)에 있는 자료를 반환
    if(stack_size==0return -1// 스택이 비어있기 때문에 반환할 수 없음.
    return arr[stack_size-1];     // 스택 top에 있는 자료를 반환.
}
cs




4. 삽입


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


1
2
3
4
//code by RiKang, weeklyps.com
void push(node_type v){     // 스택에 v를 삽입
    arr[stack_size++= v;
}
cs




5. 삭제


 가장 위에 있는 arr[stack_size-1] 을 삭제하고 stack_size를 하나 줄여야 합니다. 그런데 사실 stack_size를 하나 줄이는 것만으로도 arr[stack_size-1]의 값으 무의미해지기 때문에 stack_size--;를 해주면 삭제가 완료됩니다.


1
2
3
4
5
//code by RiKang, weeklyps.com
void pop(){ // 스택의 끝에 있는 자료를 삭제
    if(stack_size!=0)
        stack_size--;
}
cs




6. 코드



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
//code by RiKang, weeklyps.com
 
#include <stdio.h>
typedef int node_type;
const int stack_size_max = 1000000;
 
struct DS_stack{
    int stack_size=0;
    node_type arr[stack_size_max];
    
    node_type top(){
        if(stack_size==0return -1;
        return arr[stack_size-1];
    }
    void push(node_type v){
        arr[stack_size++= v;
    }
    void pop(){
        if(stack_size!=0)
            stack_size--;
    }
};
 
int main() {
    DS_stack st;
    st.push(1);
    st.push(2);
    printf("%d\n",st.top());
    st.pop();
    printf("%d\n",st.top());
    return 0;
}
cs




7. 문제


 (0) [BOJ 10828] 스택


 (1) [BOJ 1874] 스택 수열


 (2) [BOJ 9012] 괄호


(0) ~ (2) 풀이 모음




8. C++ STL stack


 사실 C++ STL (standard library) 에 스택이 정의되어 있기 때문에 굳이 스택을 손수 구현하여 사용할 필요는 없습니다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//code by RiKang, weeklyps.com
 
#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;
}
cs
출력
2
1

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


※ 본문의 코드들은 C++ 14 환경으로 작성되었습니다.


'선형 자료구조' 카테고리의 다른 글

스택 ( Stack )  (0) 2018.01.21
동적 배열 ( dynamic array )  (0) 2017.12.21