교수님께서 보여주신 스택의 아주 좋은 예시

스택이란

LIFO(Last-In First-Out) 원칙에 따라 삽입 및 제거되는 요소들의 모음

LIFO의 예시로 위의 컵 사진을 들 수 있다. 제일 마지막에 쌓인 것이 제일 먼저 나오는 구조인 것이다.

스택의 용어

• Top: 스택의 꼭대기 (기본값 = -1) (가장 마지막에 삽입된 원소)
• Push: 꼭대기에 요소를 삽입하는 것
• Pop: 꼭대기의 요소를 제거하는 것

스택의 작동

• Q. 꼭대기의 요소 외에 다른 요소에 접근할 수 있는가?
• A. 스택은 말 그대로 쌓는 것이기 때문에 정의에 따라서 불가능, 그건 스택이라고 할 수 없다.

스택에 접근할 때의 모든 동작은 꼭대기의 요소에 대해 실행한다.

작동 관련 함수들

• InitStack : 빈 스택 만들기
• IsFull : 스택이 꽉 찼는지 확인
• IsEmpty : 스택이 비어있는지 확인
• Peek : 꼭대기의 요소를 읽음
• Push : 꼭대기에 요소 삽입
• Pop : 꼭대기의 요소 제거

코드로 써보자

C를 기준으로 작성한 코드입니다.

스택 설정

#define MAX_STACK 100

typedef int Data;

typedef struct {
    Data items[MAX_STACK];
    int top;
} Stack;

스택 작동 관련 함수

InitStack - 빈 스택 만들기

void InitStack(Stack *pstack) {
    pstack->top = -1;
}

IsFull - 스택이 꽉 찼는가

bool IsFull(Stack *pstack) {
    return pstack->top == MAX_STACK - 1;
}

IsEmpty - 스택이 비어있는가

bool IsEmpty(Stack *pstack) {
    return pstack->top == -1;
}

Peek - 꼭대기 요소 읽기

Data Peek(Stack *pstack) {
    if (IsEmpty(pstack)) {
        exit(1);
    }
    return pstack->items[pstack->top];
}

Push - 꼭대기에 요소 삽입

void Push(Stack *pstack, Data item) {
    if (IsFull(pstack)) {
        exit(1);
    }
    pstack->items[++(pstack->top)] = item;
}

Pop - 꼭대기의 요소 제거

void Pop(Stack *pstack) {
    if (IsEmpty(pstack)) {
        exit(1);
    }
    --(pstack->top);
}