211122, 자료구조 Ch.06-1

저번주 금요일에 복습을 까먹고 안 한 내 죗값..

Ch.05 복습을 끝냈으니, 이번엔 Ch.06 복습을 진행해보겠다. 아마 계산기 구현 전까지 하지 않을까 싶다.

Ch 06. STACK

06-1

STACK. 일단 단어부터 "쌓다"라는 의미를 가지고 있다.

어느정도의 정형화된 정의를 보자.

메모리에 새로 들어오는 데이터의 위치가 메모리 말단이고, 써먹기 위해 내보내는 데이터 역시 메모리 말단을 거친다. - 출처 : 꺼무위키 -

이걸 쉽게 말하면, 그냥 쌓여있는 박스라고 생각하면 된다.

박스 세개가 이미 쌓여있다 가정하자. 우리가 새로운 박스를 쌓아올리려면, 바닥에 있는 다른 박스 하나를 이 세개의 박스 위에 올려서 네개가 된다. 이게 "매모리에 새로 들어오는 데이터의 위치가 메모리 말단이고," 의 설명.

그리고 이 네개가 쌓여있는 박스에서, 밑에서 두번째에 있는 박스를 빼려면?

바로 두번째 박스를 뺄 수는 없고, 위에서부터 차곡차곡 하나씩 꺼내야 한다. 이게 "써먹기 위해 내보내는 데이터 역시 메모리 말단을 거친다." 의 설명이다.

그냥 이걸 한줄로 말하면 쌓여 올려져 있는 박스들, 쟁반 위에 쌓여있는 접시들을 생각하면 된다. 아니면 "후입선출(後入先出)".

그리고 주의해야 할게, 스택의 의미를 말할 때, Heap 영역 메모리에서 일반적인 데이터를 저장하는 스택 / 스택 영역 메모리에서 프로그램에 정보를 저장하기 위한 스택 두가지를 잘 구분 하자. 지금 우리가 다룰건 후자다.

그러면 스택 자료구조의 ADT를 정의해보자.

필요한 기능은 총 네개다.

"넣기" / "빼기" / "뭐가 들어있나 확인하기" / "비었는지 확인하기". 앞에서부터 세개를 각각 Push / Pop / Peek 이라고 하고, 맨 마지막 하나는 그냥 ADT를 정의할때 Empty라고 하겠다.

아 그리고, 너무 당연하지만 Stack도 초기화를 해줘야 하니 Init 함수도 포함된다.

/* stack의 ADT*/

void StackInit (Stack *pstack);

int SIsEmpty(Stack *pstack);

void SPush(Stack *pstack, Data data);

Data SPop(Stack *pstack);

Data SPeek(Stack *pstack);

이렇게 다섯가지다. 위의 함수들이 뭘 의미하는지는 방금 코드 위에 적어놓은 말들과 비교하며 보자.

그리고 스택도 배열 / 연결리스트 등 자료구조를 활용해서 새로운 자료구조의 구현에 써먹을 수 있는데, 일단 배열을 기반으로 한 스택 구현을 보자.

06-2

이 배열 기반 스택 구현에선 List처럼 뭐 복잡하게 여기 잇고 저기 잇고 그런게 없이, 그냥 넣고 빼는데에만 신경쓰면 된다.

그림은 생략하겠지만, 앞서 예를 들었던 "박스 쌓기"를 생각해라.

여기서 중요한 포인트 두개는,

1. 인덱스 0 의 배열 요소가, 스택의 바닥으로 정의된다.
2. 마지막에 저장된 데이터 위치를 기억해야 한다.

1번은 만약 ch[3] = {1, 2, 3} 이라는 배열이 있으면, 여기서 가장 첫 요소는 ch[0]인 1이다. 그래서 인덱스 0의 배열 요소라고 말을 했고, 이 요소가 가장 먼저 Stack에 들어가게 되므로 스택의 바닥으로 정의되는 것이다.

2번은 앞서 박스 예시처럼 넣고 빼야하고, 몇개의 데이터가 저장되어있는지 알 수 있게 저장된 데이터 위치를 기억한다. 이를 topIndex라고 하겠다.

그러면 각 함수들은 어떻게 구현이 될까?

push, topIndex를 한 칸 올리고, 그 올라가있는 칸에 데이터를 추가.

pop. topIndex에 있는 데이터를 빼내고, topIndex를 한 칸 내린다.

/* ABS.h */

#ifndef __A_B_S_H__
#define __A_B_S_H__

#define TRUE		1
#define FALSE		0
#define STACK_LEN	100

typedef int Data;

typedef struct _arrayStack {
    Data stackArr[STACK_LEN];
    int topIndex;
} ArrayStack;

typedef ArrayStack Stack;

void StackInit (Stack *pstack);

int SIsEmpty(Stack *pstack);

void SPush(Stack *pstack, Data data);
Data SPop(Stack *pstack);

Data SPeek(Stack *pstack);

#endif

이걸 대충 ADT와 함께 헤더파일을 정의해주면 요렇게 된다.

이제 이 ADT에 정의된 함수들을 구현해보자.

/* ABS.c */

void StackInit (Stack *pstack) {
    pstack->topIndex = -1;
} // -1인 이유는, Index의 바닥이 0부터 시작되니까.

int SIsEmpty(Stack *pstack) {
    if(pstack->topIndex == -1) { // 비어있다면, TRUE 반환
        return TRUE;
    } else { // 뭔가 있다면, FALSE 반환
        return FALSE;
    }
}

void SPush(Stack *pstack, Data data) {    
    (pstack->topIndex)++; // topIndex를 한 칸 올리고
    pstack->stackArr[pstack->topIndex] = data; // 데이터넣기
}

Data SPop(Stack *pstack) {
    
    int rIdx;
    
    if(SIsEmpty(pstack)) { // 들어있는 데이터가 없다면
         printf("뽑을 데이터가 없는데요\n");
         exit(-1);
    }
    
    rIdx = pstack->topIndex; 
    pstack->topIndex -= 1;
    // 데이터는 꺼냈으니 삭제됨. 그냥 topIndex를 -1 하기만 해도 데이터 소멸 끝.
    
    return pstack->stackArr[rIdx];
}

Data SPeek(Stack *pstack) { // 맨 위에 뭐가있나 보기만 할게요!
	
    if(SIsEmpty(pstack)) {
        printf("볼게 없어요\n");
        exit(-1);
    }
    
    return pstack->stackArr[pstack->topIndex];
}

뭐, 요정도다.

오늘은 복습만 하고, 진도는 내일부터 다시 나가야지.

나머지 Stack은 내일 복습하도록 하겠다.