[Algorithm-Basic] Stack

*유튜브 채널 "동빈나"의 실전 알고리즘 강좌(Algorithm Programming Tutorial) 영상을 시청한 후 작성한 글 입니다.*

Stack이란?

기본 데이터 구조 중 하나로, 데이터를 후입선출(LIFO, Last In First Out) 구조로 유지하는 추상 데이터형을 말한다.

(네이버 지식백과)

따라서 가장 마지막에 들어온 데이터가 가장 먼저 처리되며, 아래와 같이 입구와 출구가 하나밖에 없는 상태로 표현 가능하다.

 

 

입구와 출구가 좌측에 하나로 위치한다.

ㅡㅡㅡㅡㅡㅡㅡ

                      ㅣ

ㅡㅡㅡㅡㅡㅡㅡ

 

이곳에 다음과 같은 명령어를 수행한다고 하자.

 

1. 삽입(7)

ㅡㅡㅡㅡㅡㅡㅡ

                  7  ㅣ

ㅡㅡㅡㅡㅡㅡㅡ

 

2. 삽입(5)

ㅡㅡㅡㅡㅡㅡㅡ

              5   7 ㅣ

ㅡㅡㅡㅡㅡㅡㅡ

 

3. 삽입(4)

ㅡㅡㅡㅡㅡㅡㅡ

        4   5   7   ㅣ

ㅡㅡㅡㅡㅡㅡㅡ

 

4. 삭제()

ㅡㅡㅡㅡㅡㅡㅡ

             5   7  ㅣ

ㅡㅡㅡㅡㅡㅡㅡ

>>4가 가장 마지막에 들어온 데이터이므로 4가 삭제된다.

 

Stack에서 활용 가능한 명령어

1. push

: 데이터를 삽입하는 명령어.

 

s.push(7); //s 스택에 7 삽입

 

2. pop

: 데이터를 추출하는 명령어.

 

s.pop(); //가장 마지막에 들어온 데이터 추출

 

예제

백준 10828번

https://www.acmicpc.net/problem/10828

 

문제

정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

 

명령은 총 다섯 가지이다.

• push X: 정수 X를 스택에 넣는 연산이다.
• pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• size: 스택에 들어있는 정수의 개수를 출력한다.
• empty: 스택이 비어있으면 1, 아니면 0을 출력한다.
• top: 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.

입력

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

 

출력

출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.

 

예제 입력

7
pop
top
push 123
top
pop
top
pop

예제 출력

-1
-1
123
123
-1
-1

 

풀이

//c언어로 구현
#include<stdio.h>
#include<string.h>
 
#define TRUE 1            //1반환 
#define FALSE 0           //0반환 
#define MINUS -1          //-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){    //스택의 size 반환 
    return sp->top + 1;
}
 
 
int IsFull(Stack * sp){        //스택이 꽉 차있는지 확인 
    if(sp->top + 1 >= MAX_SIZE) return TRUE;
    
    return FALSE;
}
 
void Push(Stack * sp, int data){    //스택의 push 
    if(IsFull(sp)==TRUE) return;
    
    //top을 하나 올린 후 data 삽입
    sp->arr[++(sp->top)] = data;    
}
 
int Pop(Stack * sp){    //스택의 pop. 
    if(IsEmpty(sp) == TRUE) return MINUS;
 
    //top이 가리키는 값을 반환 후 top을 하나 내림.
    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);    //stack 초기화. 
    
    
    for(i=0; i<n; i++){
    
        scanf("%s", str);
        fgetc(stdin);    //버퍼 비우기. 
 
        if(!strcmp(str, "push")){    //push 인 경우 
            
            scanf("%d", &num);
            fgetc(stdin);    //버퍼 비우기. 
            Push(&stack, num);    
            
        }else if(!strcmp(str, "pop")){    //pop인 경우 
        
            printf("%d\n", Pop(&stack));
        
        }else if(!strcmp(str, "empty")){    //empty인경우 
            
            printf("%d\n", IsEmpty(&stack));
            
        }else if(!strcmp(str, "size")){        //size인 경우  
        
            printf("%d\n", Size(&stack));
        
        }else if(!strcmp(str, "top")){        //top인 경우 
        
            printf("%d\n", Peek(&stack));
        
        }
    }
    
    return 0;    
}