[Data Structure] 스택(stack)

---

스택

 

 

스택이란 스택은 후입선출(LIFO, Last In First Out) 방식으로 동작하는 자료구조이다. 즉 마지막에 삽입된 데이터가 가장 먼저 삭제된다는 뜻이다. 무엇인가를 쌓고 나서 치우려고 하면 가장 나중에 쌓은 것인 가장 위부터 치워야 하는 것과 같다. 웹 브라우저의 뒤로 가기 기능이나 프로그램에서 괄호가 제대로 열고 닫혔는지 검사할 때 사용되기도 한다.

이러한 성질 때문에 스택은 가장 상위 데이터에만 접근할 수 있다. 상위 데이터를 삭제하거나, 확인하는 것은 가능하지만, 그 아래 데이터에 접근하려면 상위 데이터를 제거해 나가면서 접근해야 한다. 최상위 데이터에만 접근할 수 있다는 것은 최상위 데이터만 관리하면 된다는 뜻이기에 데이터를 관리하는 데에 드는 자원을 적게 소모한다는 뜻이기도 하다.

 

---

ADT

 

객체 (Object)

• 0 개 이상의 원소를 가지는 유한 선형 리스트

연산 (Operation)

• create(size) ::= 최대 크기가 size 인 공백 스택을 생성한다.
• is_full() ::= 스택의 원소 개수가 size 와 같다면 true 를, 아니라면 false 를 반환한다.
• is_empty() ::= 스택의 원소 개수가 0 이라면 true 를, 아니라면 false 를 반환한다.
• push(item) ::= 스택이 가득 차 있지 않다면 스택의 가장 위에 item 을 추가한다.
• pop() ::= 스택이 비어있지 않다면 스택의 가장 위 원소를 제거해서 반환한다.
• top() 혹은 peek() ::= 스택이 비어있지 않다면 스택의 가장 위 원소를 제거하지 않고 반환한다.
• size() ::= 스택의 원소  개수를 반환한다.

 

---

구현 | C

 

간단하게 C 를 통해 정적으로 구현하였다. 아래 코드는 main 함수를 제외한 스택 선언과 스택을 관리하는 코드이다. element 는 임의로 int 로 설정하였다. pop 이나 top 에서 스택이 비어있을 때 에러도 임의로 -1 을 반환하도록 하였다.

#include <stdio.h>
#define MAX_STACK_SIZE 10000

typedef int element;
typedef struct {
    element data[MAX_STACK_SIZE];
    int top;
} Stack;

void init_stack(Stack* s) {
    s->top = -1;
}

int is_empty(Stack* s) {
    return (s->top == -1);
}

int is_full(Stack* s) {
    return (s->top == MAX_STACK_SIZE - 1);
}

void push(Stack* s, element item) {
    if (is_full(s)) {
        printf("Stack is full\n");
    } else {
        s->data[++(s->top)] = item;
    }
}

element pop(Stack* s) {
    if (is_empty(s)) {
        printf("Stack is empty\n");
        return -1;
    } else {
        return s->data[(s->top)--];
    }
}

element top(Stack* s) {
    if (is_empty(s)) {
        printf("Stack is empty\n");
        return -1;
    } else {
        return s->data[s->top];
    }
}

int size(Stack* s) {
    if (is_empty(s)) {
        return 0;
    } else {
        return s->top + 1;
    }
}

main 함수를 구현하고, 예시로 1, 2, 3, 4 를 push 하고, pop 으로 꺼내보자. main 함수는 아래와 같다.

int main()
{
    Stack s;
    init_stack(&s);
    push(&s, 1);
    push(&s, 2);
    push(&s, 3);
    push(&s, 4);
    printf("%d\n", pop(&s));
    printf("%d\n", pop(&s));
    printf("%d\n", pop(&s));
    printf("%d\n", pop(&s));
    return 0;
}

결과는 아래와 같다.

4
3
2
1

push 로 넣은 순서와 반대로 출력된 것을 알 수 있다.

한 번 더 pop 을 해보면 아래와 같은 문구가 출력된다.

Stack is empty

pop 함수에서 미리 stack 이 비어있을 때를 예외처리 해놨기 때문에 'Stack is empty'가 잘 출력되었다.

 

스택의 크기를 동적으로도 구현 가능하고, 연결 리스트를 이용해서 구현도 가능하다. C 에서는 따로 stack 라이브러리가 존재하지 않지만, C++, Java 등에서는 별도의 라이브러리가 존재하고, Python 에서는 list 가 stack 을 대체할 수 있다.

백준의 스택 문제(링크)를 활용하여 스택을 구현하고 연습해볼 수 있다.