자료구조 - 스택 (Stack)

1. 스택이란?

Stack의 사전적 정의는 '쌓다', '더미'로 나중에 들어간 것이 먼저 나오는 Last In First Out 형태이다. 아래 Reference Code처럼 배열로 스택을 구현해도 되지만, 표준 라이브러리에 정의되어 있기 때문에 include하여 사용하면 편리하다.

맨 위 요소는 top이라고 하며, 이 요소만 접근할 수 있다. 자료가 없을 때 pop을 하는 오류를 stack underflow, 스택의 크기 이상의 자료를 push하려고 할 때의 오류를 stack overflow라고 한다.

 

선언

stack<자료형> 스택 이름; 형태로 선언한다.

#include <stack>

stack<int> s1;

stack<float> s2;

stack<char> s3;

 

기본 메소드

1. push() : 현재 스택 최상위에 데이터 추가

2. pop() : 현재 스택 최상위의 데이터 제거

3. top() : 현재 스택 최상위의 데이터 반환

4. size() : 현재 스택에 저장된 데이터 갯수 반환

5. empty() : 현재 스택이 비어있으면 true, 아닐 경우 false를 반환

스택명.메소드() 형태로 사용한다.

 

2. 시간복잡도

1) 삽입 / 삭제

- 원소를 삽입 / 삭제하는 경우 : O(1)

 

3. 장단점

1) 장점

- 데이터의 삽입과 삭제가 빠르다. (맨 위 원소 접근 O(1))

 

2) 단점

- 탐색을 하려면 원소를 하나하나 꺼내 옮겨가면서 해야한다.

- 맨 위의 원소만 접근 가능하다.

 

4. 응용

그래프의 깊이 우선 탐색 (DFS)에서 사용되고, 재귀적 함수 호출에도 사용된다.

 

[예시문제]

주어진 N(2<= N <=100)개의 수를 순서대로 Stack에 넣은 후 하나씩 꺼내 화면에 출력하시오.

 

[입력]

케이스 개수

스택 크기

데이터

 

[Reference Code]

#include <stdio.h>
 
#define MAX_N 100
 
int top;
int stack[MAX_N];
 
void stackInit(void) //스택 초기화
{
    top = 0; //top 초기값은 0
}
 
int stackIsEmpty(void) //스택이 비었나?
{
    return (top == 0); //top이 0일 때 스택은 비어있음
}
 
int stackIsFull(void) //스택이 꽉 찼나?
{
    return (top == MAX_N);
}
 
int stackPush(int value) //스택의 맨 위에 데이터 삽입
{
    if (stackIsFull()) //스택이 꽉 찼나?
    {
        printf("stack overflow!");
        return 0; //삽입 못하게 리턴
    }
    stack[top] = value; //값 삽입
    top++;
 
    return 1;
}
 
int stackPop(int *value) //스택 최상단의 데이터 삭제
{
    if (stackIsEmpty())
    {
        printf("stack is empty!");
        return 0;
    }
    top--;
    *value = stack[top];
 
    return 1;
}
 
int main(int argc, char* argv[])
{
    int T, N;
 
    scanf("%d", &T);
 
    for (int test_case = 1; test_case <= T; test_case++)
    {
        scanf("%d", &N);
        stackInit();
        for (int i = 0; i < N; i++) 
        {
            int value;
            scanf("%d", &value);
            stackPush(value);
        }
 
        printf("#%d ", test_case);
 
        while (!stackIsEmpty())
        {
            int value;
            if (stackPop(&value) == 1)
            {
                printf("%d ", value);
            }
        }
        printf("\n");
    }
    return 0;
}