04. 스택

4.1 스택이란?

스택

• 데이터를 차곡 차곡 쌓아올린 형태로 데이터를 추상화하여 자료구조로 정의한 것
• 연탄을 쌓아올린 모습, 뷔페 접시가 차곡차곡 쌓아올린 모습 과 비슷하다.
• 특징
  • 같은 구조와 같은 크기의 데이터를 정해진 방향으로만 쌓을 수 있다. 
  • top으로 정한 한 곳만 접근 가능하다
  • 후입선출(LIFO) 의 동작구조를 갖는다
    : 가장 마지막에 삽입된 데이터가 가장 먼저 삭제 된다
• 예제 - 시스템 스택을 이용한 함수호출
  : 함수는 실행이 끝나면 자신을 호출한 함수로 되돌아 가야하는데, 이때 스택을 사용한다. → 복귀할 주소를 기억하는 데 사용

🤷‍♀️ 왜 일까요? 함수는 호출된 역순으로 돌아가야 하기 때문! 

void func2() {
	return;
}

void func1() {
	func2();
}

int main(void) {
	func1();
    return 0;
}

이렇게 함수를 호출한다고 가정하였을 때,

스택의 형식으로 활성 레코드가 만들어졌다가 없어집니다.

 

4.2 스택의 구현

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

#define MAX_STACK_SIZE 100

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

// 스택 초기화 함수
void init_stack(StackType *s) {
    s->top = -1; // s 안에 있는 top에 -1로 초기화
}

// 공백 상태 검출
int is_empty(StackType *s) {
    return s->top == -1;
}

// 스택 포화상태 검출
int is_full(StackType *s) {
    return s -> top == (MAX_STACK_SIZE - 1); // index는 0부터 시작하기 때문에 -1을 해준다.
}

// 스택 삽입 함수
void push(StackType *s, element item) {
    if (is_full(s)) {
        fprintf(stderr, "스택이 포화상태입니다. ");
        return;
    }
    else s->data[++(s->top)] = item; // 먼저 스택의 top을 증가시키고, 그 데이터에 아이템을 넣겠다. -> 스택은 위로 쌓아올리는 구조이기 때문에
} 

// 스택 삭제 함수
element pop(StackType *s) {
    if (is_empty(s)) {
        fprintf(stderr, "스택이 비어있습니다. ");
        exit(1);
    } 
    else return s->data[(s->top)--]; // 데이터에서 탑을 꺼낸 후 스택의 크기를 줄인다 
}

// 스택 피크 함수
element peek(StackType *s) {
    if (is_empty(s)) {
        fprintf(stderr, "스택이 비어있습니다. ");
        exit(1);
    } 
    else return s->data[s->top]; // 단순히 스택에서 꺼내오는 함수
}

int main(void) {
    StackType s;

    init_stack(&s);
    push(&s, 1);
    push(&s, 2);
    push(&s, 3);

    printf("%d\n", pop(&s));
    printf("%d\n", pop(&s));
    printf("%d\n", pop(&s));
}

넣을 땐 1, 2, 3 순서로 넣었지만 후입선출이라는 특징을 가지고 있기때문에 

출력은 3, 2, 1 로 이루어진다.