2021-06-03 · 3분

스택(Stack)

algorithm

이 글은 작성된 지 2년이 넘었어요. 내용이 오래됐을 수 있어요.

백준 10828번 스택 문제 : https://www.acmicpc.net/problem/10828

스택이란?

스택(Stack)은 제한적으로 접근할 수 있는 나열 구조이다. 한쪽 끝에서만 자료를 넣고 뺄 수 있는 LIFO(Last In First Out) 형식의 자료 구조이다.

스택의 기능

여러 가지가 있지만 가장 많이 사용하는 것들이다.

pop(): 스택에서 가장 위에 있는 항목을 제거한다.
push(input): input이란 변수를 스택의 가장 윗부분에 추가한다.
size(): 스택에 들어가 있는 크기를 알려준다.
top(): 스택의 가장 윗 부분를 반환해준다.(삭제하지 않는다)
empty(): 스택이 비어 있을때에 true를 반환해준다.

왜 스택을 사용할까?

문제의 종류에 따라 배열보다 스택에 데이터를 저장하는 것이 더 적합한 방법일 수 있다.

배열과는 달리 해당 위치에 접근할 수 없다.
스택에서 데이터를 추가하거나 삭제하는 연산은 상수 시간에 가능하다.
배열을 스택처럼 사용하려면 배열에서 원소를 뺄 때마다 옆으로 밀어줘야 하는데 스택에서는 그럴 필요가 없다.

스택의 구현

백준 10828번 스택문제

#include<stdio.h>
#include<string.h>
 
#define TRUE 1            
#define FALSE 0           
#define MINUS -1          
#define MAX_SIZE 10000    
 
typedef struct _stack{    
    int arr[MAX_SIZE];
    int top;
} Stack;
 
void StackInit(Stack * sp){    
    sp->top = -1;
}
 
int IsEmpty(Stack * sp){    
    if(sp->top == -1) return TRUE;
        
    return FALSE;
}
 
int Size(Stack *sp){    
    return sp->top + 1;
}
 
 
int IsFull(Stack * sp){        
    if(sp->top + 1 >= MAX_SIZE) return TRUE;
    
    return FALSE;
}
 
void Push(Stack * sp, int data){    
    if(IsFull(sp)==TRUE) return;
    
    sp->arr[++(sp->top)] = data;    
}
 
int Pop(Stack * sp){    
    if(IsEmpty(sp) == TRUE) return MINUS;
 
    return sp->arr[(sp->top)--];
}
 
int Peek(Stack *sp){    
    if(IsEmpty(sp) == TRUE) return MINUS;
    
    return sp->arr[sp->top];
}
 
 
int main(void){
    int i;
    char str[6];
    Stack stack;
    int n, num;
    
    scanf("%d", &n);
    fgetc(stdin);    
    StackInit(&stack);    
    
    
    for(i=0; i<n; i++){
    
        scanf("%s", str);
        fgetc(stdin);    
 
        if(!strcmp(str, "push")){    
            
            scanf("%d", &num);
            fgetc(stdin);    
            Push(&stack, num);    
            
        }else if(!strcmp(str, "pop")){    
        
            printf("%d\n", Pop(&stack));
        
        }else if(!strcmp(str, "empty")){    
            
            printf("%d\n", IsEmpty(&stack));
            
        }else if(!strcmp(str, "size")){        
        
            printf("%d\n", Size(&stack));
        
        }else if(!strcmp(str, "top")){        
        
            printf("%d\n", Peek(&stack));
        
        }
    }
    
    
    return 0;    
}

직접 이런 식으로 만들어서 사용할 수도 있지만 c++ 에는 stack이라는 헤더가 존재한다.

이건 위 문제의 답이 아니고 stack이라는 헤더를 사용할 때 이런 식으로 할 수 있는 것이다.

#include <stdio.h>
#include <string.h>
#include <stack>

using namespace std;

stack<int> Stack;

int main()
{
    int i;
    char str[7];
    int n, num;

    scanf("%d", &n);
    fgetc(stdin);

    for (int i = 0; i < n; i++)
    {
        scanf("%s", str);
        fgetc(stdin);

        if(!strcmp(str, "push")) {
            scanf("%d", &num);
            fgetc(stdin);
            Stack.push(num);
        }else if(!strcmp(str, "pop")) {
            if(Stack.empty()) printf("-1\n");
            else {
                printf("%d\n", Stack.top());
                Stack.pop();
            }
        }else if(!strcmp(str, "empty")) {
            if(Stack.empty()) printf("1\n");
            else printf("0\n");
        }else if(!strcmp(str, "size")) {
            printf("%ld\n", Stack.size());
        }else if(!strcmp(str, "top")) {
            printf("%d\n", Stack.top());
        }
    }
    
}

STL stack의 사용법

// stack헤더 추가
#include <stack>

// 비어 있는 stack를 생성
stack<int> Stack;

// {1, 2, 3, 4, 5}로 초기화 된 stack 생성
stack<int> Stack({ 1, 2, 3, 4, 5 });

stack의 함수들

stack<int> Stack를 기준으로 하여

Stack.push(n) : 맨 위에 n를 추가
Stack.pop() : 맨 위의 원소를 제거
Stack.top() : 맨 위의 원소 리턴
Stack.size() : 스택의 크기를 반환
Stack.empty() : 비어있는지 확인

스택을 이용한 문제 풀이 :

**[알고리즘] - 백준 9012번 괄호**](https://gmlwjd9405.github.io/2018/08/03/data-structure-stack.html) 참조 : https://ko.wikipedia.org/wiki/%EC%8A%A4%ED%83%9D https://velog.io/@choiiis/C-STL-stack-%ED%81%B4%EB%9E%98%EC%8A%A4-%EC%A0%95%EB%A6%AC [https://gmlwjd9405.g — data-structure-stack.html

사진 : http://www.incodom.kr/%EC%8A%A4%ED%83%9D