[☆운영체제를 만들어보자☆][Chapter 01] 2. 스택이 뭘까? 스택을 만들어보자. [※연습 문제, 요약 추가]

이번 글에서는 스택이 어떤 자료구조인지 알아보고, 스택을 한 번 만들어보겠습니다.

다음 강좌에서는 프로세스의 메모리 구조와 함께 스택이 어떻게 사용되는지 알아볼겁니다.

※연습문제와 강좌 요약을 넣는다고 해놓고 깜빡했네요. 추가했습니다. (2018-02-15 01:06)

스택 (Stack)

스택이란 단어는 말 그대로 쌓아올린다는 의미가 있는데요, 스택이라는 자료구조도 비슷한 의미입니다.

사전적으로는 다음과 같은 의미가 있습니다.

"스택(stack)은 제한적으로 접근할 수 있는 나열 구조이다. 그 접근 방법은 언제나 목록의 끝에서만 일어난다. 끝먼저내기 목록(Pushdown list)이라고도 한다.

스택은 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 구조(LIFO - Last In First Out)으로 되어 있다. 자료를 넣는 것을 '밀어넣는다' 하여 푸시(push)라고 하고 반대로 넣어둔 자료를 꺼내는 것을 팝(pop)이라고 하는데, 이때 꺼내지는 자료는 가장 최근에 보관한 자료부터 나오게 된다. 이처럼 나중에 넣은 값이 먼저 나오는 것을 LIFO 구조라고 한다." - 출처 : 위키백과(링크)

하지만 사전은 정확하고 논리적이긴 하지만 우리가 이해하기는 쉽지가 않죠. 따라서 우리는 스택이 무엇인지 쉽게 풀어서 이야기를 해보려고 합니다.

스택이란 자료구조를 그냥 하나의 프링글스 과자 통이라고 해보겠습니다. 

그리고 프링글스 통 안에 과자가 아래와 같은 순서대로 '쌓여있다고'해볼까요? (물론 뚜껑은 이미 뜯었습니다.

[  바베큐맛 ]

[   양파맛   ]

[오리지널맛]

----바닥----

저는 개인적으로 바베큐, 양파맛은 좋아하지만 오리지널맛은 저한텐 좀 밋밋해서 별로네요.

오리지널맛은 다른사람한테 줘야겠습니다. 그럼 오리지널맛을 꺼내보죠.

하지만 오리지널맛 부터 꺼낼 수 있나요? 불가능합니다. 오리지널맛이 가장 바닥 쪽에 있으니까요.

그래서 하나씩 차근차근 꺼내보겠습니다.

[  바베큐맛 ]

[    양파맛   ]      --->  [   양파맛   ]     --->                         --->

[ 오리지널맛 ]             [ 오리지널맛 ]           [ 오리지널맛 ]

---- 바닥 ----              ---- 바닥 ----           ---- 바닥 ----             ---- 바닥 ----

위의 그림처럼 위에 있는 것 부터 차례대로 프링글스 과자를 모두 꺼냈습니다.

바로 이런 연산을 스택에서는 POP 연산이라고 합니다. 한 방향에서만, 그리고 한 번에 하나씩만 데이터를 꺼낼 수 있죠.

또, 위의 그림에서 진한 색으로 칠한 과자는 맨 위에 있는 과자 입니다. 스택에서도 맨 위에 있는 것을 많이 중요하게 생각하는데,

그래서 맨 위에 있는 것을 가리키는 포인터에 TOP(다른 말로는 SP: Stack Pointer)이라는 이름을 붙여주었습니다.

이제 오리지널맛을 설 연휴로 내려온 작은 누나에게 주었습니다. 이제 저는 남은 과자들을 다시 통에 넣어서

하나씩 음미하려고 합니다. 아래 그림의 순서대로 과자를 다시 집어넣었습니다.

                                                     [  바베큐맛 ]

                ---> [   양파맛   ]     --->   [   양파맛   ]

----바닥----        ---- 바닥 ----             ---- 바닥 ----

이렇게 밑에서 부터 자료를 하나씩 추가하는걸 스택에서는 POP 연산이라고 합니다.

이제 저는 다시 남은 과자를 하나씩 음미하면서 먹을겁니다. 아마 다음 그림처럼 되겠죠?

[  바베큐맛 ]                       

[   양파맛   ]     --->   [   양파맛 >

---- 바닥 ----             ---- 바닥 ----        ---- 바닥 ----

여기서 스택의 특징을 하나 더 볼 수 있습니다. 바로 LIFO(Last-in, FIrst-Out, 후입선출)이라는 특징인데요,

말 그대로 나중에 넣은 자료를 가장 먼저 꺼낼 수 있다는 말입니다.

우리가 양파맛 먼저 넣고 바베큐맛을 넣었지만, 먹을 때는 반대로

바베큐맛을 먹고 양파맛을 먹은 것 처럼 말이죠.

C언어로 스택을 구현해보자

이제 스택이 무엇인지 알아보았으니, 스택을 직접 만들어볼까요??

하지만 앞에서 말씀드렸듯, 코드를 복붙하거나 코드를 그냥 보고 따라쓰는 것은 별로 도움이 되지 않습니다. 

아래의 소스코드 없이 직접 스택을 구현해보고, 어떤 형태로 코드를 짜야할지 직접 고민해보고

다른 사람의 코드를 보시는게 훨씬 공부에 도움이 됩니다.

#include <stdio.h>
#include <stdlib.h>

typedef struct stack{

    int data[5];
    int top;

}STACK;

int init_stack(STACK *); //스택 구조 초기화
int push(STACK *, int); //스택의 PUSH연산
int pop(STACK *);       //스택의 POP연산
void showstack(STACK *);//STACK 자료구조 출력


int main(){
    STACK stack;
    init_stack(&stack);
    push(&stack, 10);
    push(&stack, 20);
    push(&stack, 30);
    pop(&stack);
    showstack(&stack);
    for(;;);
}

int push(STACK *stack, int data){
    if(stack->top >= 4) // 스택이 꽉차있다면
        exit(0);
    else{
        stack->top++;
        stack->data[stack->top] = data;
    }

}

int pop(STACK *stack){

    if(stack->top == -1) //스택이 비어있다면
       exit(0);
    else{
        int pop_data = stack->data[stack->top];
        stack->top--;
        return pop_data;
    }
}
void showstack(STACK *stack){
    printf("     STACK !!       \n");
    for(int i = 4; i > stack->top; i--){
        printf("====================\n");
        printf("      %d :  NULL     \n", i);
        printf("====================\n");
    }
    for(int i = stack->top; i > -1; i--){
        printf("====================\n");
        printf("      %d :  %d     \n", i, stack->data[i]);
        printf("====================\n");
    }


}

int init_stack(STACK * stack){
    for(int i = 0; i < 5 ; i++)
        stack->data[i] = 0;
    stack->top = -1;

}

이번 시간에 배운 것

1. 스택의 두 가지 연산 : PUSH, POP

2. 스택의 가장 윗부분 자료를 가리키는 포인터 : TOP or SP: Stack Pointer

3. 스택의 특징 : LIFO : Last-in, FIrst-out (후입선출)

연습문제

1. 만약 스택을 이용해 함수의 파라미터(매개변수)를 전달한다면, 어떤 식으로 이를 전달하고 호출된 함수에서 이용할지

오늘 배운 PUSH, POP 연산과 TOP 포인터를 이용하여 의사 코드를 작성해보시오. (또는 프로그래밍 언어로)

※만약 잘 모르시겠다면, 함수의 프롤로그와 에필로그에 관해 찾아보시는 것도 좋습니다.

더 공부할 만한 것들

http://ehpub.co.kr/c언어-소스-스택을-연결리스트로-구현/

http://effort4137.tistory.com/entry/Multiple-Stack