Stack

Stack은 위에만 구멍이 뚫린 박스라고 생각하면 된다.

이 그림이 Stack 구조이다.

먼저 들어간 데이터가 가장 마지막에 나온다.

가장 마지막에 들어간 데이터가 가장 먼저 나온다. LIFO.

 

Stack은 중간에 데이터를 넣는것도 불가능하고 맨위에 데이터를 새로 넣거나 맨위에 있는 데이터를 빼거나해야 한다.

 

코드적으로 접근해보기

Stack은 보통 이러한 메서드들을 가지고 있다.

• pop(): 가장 최근에 추가된 데이터 빼기
• push(item): 데이터 새로 추가하기
• peek(): 가장 최근에 추가된 데이터 읽기
• isEmpty(): Stack이 비어있는지 확인하기

다음 그림과 같이 사이즈가 7인 Stack이 있다고 해보자.

 

1. 이 상태에서 push(8)을 하면 다음 그림이 된다.

2. 이 상태에서 또 push(10)을 하면 다음 그림이 된다.

3. 이 상태에서 peek() 메서드를 호출하면 10을 반환한다. 가장 마지막에 넣은 녀석을 가져오는 메서드니까.

4. 이 상태에서 isEmpty() 메서드를 호출하면 false를 반환한다.

5. 이 상태에서 pop()을 호출하면 10이 나온다.

6. 이 상태에서 pop()을 한번 더 호출하면 8이 나온다.

7. 여기서 isEmpty()를 호출하면 true가 나온다.

 

그래서 Stack의 특징은 맨 위(가장 마지막)만 알면 모든 처리가 가능하다.

 

Stack의 예시 코드

#define MAX_SIZE 100

typedef struct {
	int stack[MAX_SIZE];
    int pop;
} Stack;

void initialize(Stack* s) {
	s->top = -1; // 최초에는 아무 데이터도 들어가지 않으니까 -1
}

int pop(Stack* s) {
	if (isEmpty(s)) {
    	printf("Stack Underflow: Cannot pop element from the stack.\n");
        return -1;
    }
    
    int item = s->stack[s->top--];
    return item;
}

void push(Stack* s, int item) {
	if (s->top == MAX_SIZE -1) {
    	printf("Stack Overflow: Cannot push element onto the stack.\n");
        return;
    }
    
    s->stack[++s->top] = item;
    printf("%d pushed onto the stack.\n", item);
}

int peek(Stack* s) {
	if (isEmpty(s)) {
    	printf("Stack is empty.\n");
        return -1;
    }
    
    return s->stack[s->top];
}

bool isEmpty(Stack* s) {
	return (s->top == -1);
}

 

Stack test

int main() {
    Stack stack;
    initialize(&stack);
    ...
}

여기까지 하면 이런 그림이 된다.

 

int main() {
    Stack stack;
    initialize(&stack);
    push(&stack, 10);
    ...
}

여기까지 하면 이런 그림이 된다.

int main() {
    Stack stack;
    initialize(&stack);
    push(&stack, 10);
    push(&stack, 20);
    push(&stack, 30);
    ...
}

여기까지 하면 이런 그림이 된다.

이 상태에서 peek()메서드를 호출하면? 30을 반환한다.

 

다음과 같이 pop()메서드를 호출하면 어떻게 될까?

int main() {
    Stack stack;
    initialize(&stack);
    push(&stack, 10);
    push(&stack, 20);
    push(&stack, 30);
    
    pop(&stack);
    ...
}

이런 그림이 된다.

 

정리

이런 자료구조를 Stack이라고 한다. 그럼 자주 들어봤던 Stack Overflow는 어떤 순간에 발생하는걸까?

일단 Overflow니까 꽉 차서 더 못넣는다는 얘기인데, 자바 메모리 구조를 생각해보면 항상 실행하는 메서드를 순차적으로 Stack에 집어넣게 되어 있다.

 

최초의 main() 메서드가 실행되고 main()에서 A()라는 메서드를 호출하고 A()메서드가 B()라는 메서드를 호출하면 처리하는 순서는 B -> A -> main이 된다. 이게 정확하게 Stack의 구조다.

 

그래서 이 Stack에 계속해서 쌓이는 무언가가 Stack Overflow를 일으키는데 대표적인 예시가 자기 자신을 무한하게 호출하는 경우가 그렇다. 자기가 자기 자신을 계속 호출 호출 호출 무한루프에 빠지는거지. 그럴때 이제 더 이상 Stack에 넣을 자리가 없어서 Stack Overflow가 발생한다.