알고리즘-스택 (C언어 배열로 구현한 스택, STL stack)

스택이란 ‘쌓아올린 더미’를 말합니다.

책을 쌓아서 탑을 만들면 스택이고, 편의점 냉장고에 캔음료수가 일렬로 줄 서 있는 것도 스택입니다. 이렇듯 스택은 마지막으로 들어온 것부터 나가는 특징을 가지고 있습니다. 책 탑에서 맨 아래 책을 빼면 무너지고, 편의점에서 음료수를 앞에서부터 빼지 못 하는 점을 생각하면 됩니다. 그런 현실의 개념을 추상화한 것이 바로 스택입니다.

 

스택을 가지고 주로 삽입, 삭제, 검색 작업을 하는데, 스택의 특징에 따라 가장 최근에 들어온 데이터를 빼고, 아니면 그 뒤에 새로운 데이터를 넣게 됩니다.

스택의 특징을 영어로는 LIFO(Last In First Out), 한자로는 후입선출이라 합니다. 여기서 중요한 건, 편의점의 캔음료를 중간에 있는 것부터 뺄 수 없듯 이 스택에서도 스택 중간이나 처음 데이터를 바로 뺄 수가 없습니다. 뺀다기보다는 접근 자체가 불가능합니다. 맨 마지막 데이터부터 차례대로 접근해야 합니다.

 

*위키백과

 

스택을 구현하려면 필요한 작업은 뭐가 있을까요?

스택으로 삽입, 삭제, 검색 작업을 한다고 했습니다. 스택을 하나의 통이라 생각하고, 삽입은 통에 값을 넣는 것이니까 push, 삭제는 빼니까 pop 라고 합니다. 검색은 맨 마지막 데이터를 검색한다는 의미로 top이라고 합니다.

그 외에도 스택에 작업을 하려면 스택 저체가 있어야 하니까 스택을 만드는 create, 스택이 비어있는지 확인하는 empty.작업도 필요합니다.

 

이 글에서는 스택을 C 언어 배열로 구현해보고, STL stack 사용법에 대해서 다루겠습니다. 구현에는 포인터가 잔뜩 나오지만 이렇게 하나보다~는 느낌으로 읽어주세요. 실제 문제 풀이에서는 스택 형식으로 배열을 쓰거나, 라이브러리에서 이미 구현된 스택을 가져와 사용합니다.

 

 

C언어 배열로 구현한 스택

Init: 스택을 만드는 함수

Push: 스택에 데이터 넣기

Pop: 스택의 맨 마지막 데이터 반환하고 삭제

Peek: 스택의 맨 마지막 데이터 반환

isEmpty: 스택이 비어있나?

isFull: 스택이 꽉차있나?

Display: 스택의 모든 데이터 출력

 

#include <stdio.h>
#define MAX 30
 
typedef struct _ArrayStack {
    int top; //스택 맨 위의 인덱스
    int data[MAX]; //스택 데이터 공간
}ArrayStack;
 
typedef ArrayStack Stack; //배열로 구현한 스택
 
 
void Init(Stack* s) { //스택 초기화 top 값을 -1로
    s->top = -1; //top 초기값은 -1
}
 
int isEmpty(Stack* s) { //스택이 비었나?
    return s->top == -1; //top이 -1일 때 스택은 비어있음
}
 
int isFull(Stack* s) {  //스택이 꽉 찼나?
    return s->top == MAX - 1;
}
 
void Push(Stack* s, int item) { //스택의 맨 위에 데이터 삽입
    if (isFull(s)) printf("stack empty die");
    else {
        s->top++;
        s->data[s->top] = item;
    }
}
 
int Peek(Stack* s) { //스택 최상단의 데이터 검색, 찾은 데이터 반환
    int d;
    if (isEmpty(s)) {
        printf("stack full dis");
        return -1;
    }
    else {
        d = s->data[s->top];
        return d;
    }
}
 
int Pop(Stack* s) { //스택 최상단의 데이터 삭제, 삭제되는 데이터 반환
    int t = Peek(s);
    s->top--;
    return t;
}
 
void Display(Stack* s) { //스택 데이터 표시
    if (isEmpty(s)) printf("stack empty die");
    else {
        printf("bottom [ ");
        for (int i = 0; i <= s->top; i++) {
            printf("%d ", s->data[i]);
        }
        printf(" ] top \n\n");
    }
}
 
int main() {
    Stack s1;
    Init(&s1);
    for (int i = 1; i <= 5; i++) {
        printf("Push(%d)\n", i);
        Push(&s1, i);
        Display(&s1);
    }
 
    printf("Pop() : %d\n", Pop(&s1));
    Display(&s1);
 
    printf("Pop() : %d\n", Pop(&s1));
    Display(&s1);
 
    printf("Peek() : %d\n", Peek(&s1));
    Display(&s1);
 
    printf("\n\n");
    return 0;
}

 

표준 라이브러리에서 가져와 사용한 스택

코드 길이를 보면 느껴지겠지만 문제 하나를 풀 때마다 이렇게 긴 코드를 매번 구현하기는 힘듭니다. 그래서 보통 배열을 스택 느낌으로 쓰거나, 라이브러리에서 이미 구현된 스택을 가져와 사용합니다. 배열을 쓰는 것은 일반적인 배열 사용법과 같으므로 여기서는 STL에서 스택을 가져와서 사용해보겠습니다.

 

C++에서 제공하는 표준 라이브러리 중에는 기본 템플릿 라이브러리(Standard Template Library, STL)가 있습니다. 라이브러리란 스택같이 자주 쓰는 함수를 묶어 놓은 파일이라고 생각하시면 됩니다. STL에는 스택뿐만 아니라 큐, 덱, 벡터 등 다양한 자료구조들이 들어있습니다.

사실 이런 기본적인 자료 구조들은 C++뿐만 아니라 거의 모든 언어의 표준 라이브러리에서 제공하고 있습니다. 하지만 C언어에서는 제공하지 않기 때문에 C++ 라이브러리에서 살짝 가져와 사용하는 것입니다.

 

예시 문제를 하나 풀어보겠습니다.

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

10828번: 스택

 

먼저 배열을 스택처럼 사용하여 푼 코드입니다.

#include <stdio.h>
#include <string.h>
int n, tmp, stack[10001], i = 0;
char what[10];
 
int main() {
    scanf("%d", &n);
    while (n--) {
        scanf("%s", what);
        if (strcmp(what, "push") == 0) {
            scanf("%d", &tmp);
            stack[i++] = tmp;
        }
        else if (strcmp(what, "top") == 0) {
            if (i <= 0) printf("-1\n");
            else printf("%d\n", stack[i-1]);
        }
        else if (strcmp(what, "size") == 0) {
            printf("%d\n", i);
        }
        else if (strcmp(what, "empty") == 0) {
            if (i <= 0) printf("1\n");
            else printf("0\n");
        }
        else if (strcmp(what, "pop") == 0) {
            if (i <= 0) printf("-1\n");
            else printf("%d\n", stack[--i]);
        }
    }
}

2열) strcmp를 위한 string.h 헤더를 가져옵니다.

3열) 스택으로 사용할 배열입니다. i는 스택의 인덱스

12열) 이건 숏코딩을 위한 기술인데, stack[i++] = tmp는 stack[i] = tmp; i++과 같은 의미입니다. 코드는 취향껏 쓰시면 됩니다. 스택의 i번째 자리에 값을 넣고 i를 한 칸 앞으로 옮겨줍니다.

16열) top은 맨 마지막 값을 출력합니다. i가 0이라는 것은 스택에 아무 것도 없다는 의미이기 때문에 -1를 출력하고(문제 조건) 스택 인덱스는 0부터 시작했기 때문에 출력할 때는 i-1로 출력해줘야 합니다.

27열) stack[--i]는 i--; stack[i]; 와 같습니다. 실제로 배열에 값은 있지만, i를 하나 줄여주는 것으로 삭제한듯 동작합니다.

 

 

같은 문제를 라이브러리에서 가져온 stack으로 구현하면 이렇게 됩니다

#include <stdio.h>
#include <string.h>
#include <stack>
using namespace std;
 
int n, tmp;
char what[10];
stack<int> s;
 
int main() {
    scanf("%d", &n);
    while (n--) {
        scanf("%s", what);
        if (strcmp(what, "push") == 0) {
            scanf("%d", &tmp);
            s.push(tmp); //삽입
        }
        else if (strcmp(what, "top") == 0) {
            if (s.empty()) printf("-1\n"); //empty-비어있으면 1 아니면 0
            else printf("%d\n", s.top()); //맨 마지막 데이터
        }
        else if (strcmp(what, "size") == 0) {
            printf("%d\n", s.size()); //사이즈 출력
        }
        else if (strcmp(what, "empty") == 0) {
            if (s.empty()) printf("1\n");
            else printf("0\n");
        }
        else if (strcmp(what, "pop") == 0) {
            if (s.empty()) printf("-1\n");
            else printf("%d\n", s.top()), s.pop(); //top은 출력만, 삭제는 pop
        }
    }
}

배열 부분이 라이브러리 제공 stack으로 바뀌면서 함수가 pop(), push() 같이 더 직관적으로 바뀌었습니다.

함수는 작업의 이름 그대로 쓰는데 앞에 스택 이름을 점(.)으로 붙여주고 뒤에는 괄호()를 붙여줍니다.

스택을 사용하려면 먼저 라이브러리를 가져와야 하며(#include <stack>), int형 스택을 선언하는 부분(stack<int> s)을 추가해주는 부분만 추가해주면 됩니다.