Stack 면접 문제

 스택은 무엇인지 설명해주세요.

 

FILO(First In Last Out)구조로 처음 들어간 요소가 가장 마지막에 나오는 자료구조이다.

스택은 (배열이나, 연결리스트, 동적배열)등을 통해 구현할수있으며 데이터가 선입 후출인 사용 한다.

예시) 

 1. 자바의 메소드 호출은(stack)으로 구성, 

 2. 모바일 앱의 화면은 stack구조로 화면 이동을 관리,

 3. 웹 브라우저의 뒤로가기 앞으로가기 또한 stack 구조로 이루어짐

 4. 텍스트에디터의 undo, redo또한 stack

 

---

스택을 구현하는 두 가지 방법은 무엇이고 장단점은 무엇인가요?

 1. (배열이나, 연결리스트, 동적배열)등을 통해 구현할수있으며 
     배열의 경우 메모리 장점은 있으나 고정 크기로 인해
     지정된 배열크기를 넘어설때 stack over flow가 발생할수있으며 

 2. 연결리스트의 경우 node를 구성할때 추가적인 메모리를 사용하기에 메모리 효율성에서는 떨어진다. 

 3. 동적배열은 배열크기가 넘어서면 배열을 추가하여 stack over flow는 방지 가능하나 배열 확장시 o(n)의 시간이 든다

---

스택 오버플로우가 발생하는 이유를 설명해주세요.

스택이 정해진 크기를 지닌 경우 발생하는데, 스택이 지닌크기를 벗어나면서 메모리 할당도 안했는데

왜 할당 안된 메모리 건드리니? 라고 에러를 발생하는 것이다. 

자바에서는 할당된 스택 메모리가 오버 될정도의 메소드 호출로 많이 발생 하는데

이는 아래와 같은 경우일때 주로 발생함

 

1) 재귀함수 잘못씀 

2) 스택 메모리가 적게 할당됬는데 해당 애플리케이션의 이용자가 급증해서 터짐 

3) Lombok에서 ToString의 순환 참조 

@Data
public class Parent {
    private Child child;
}

@Data
public class Child {
    private Parent parent;
}

이와 같이 서로 참조할때 toString을 사용하면 서로 참조를 멈추지 않다가 터집니다.

 4) Jackson이 동작할때 순환참조라면 참조를 멈추지 않다가 터짐

---

브라우저의 뒤로가기와 앞으로가기 기능은 어떻게 스택을 활용하나요?

 1) 브라우저의 뒤로가기는 유저가 이동하는 웹사이트의 히스토리를 아이템으로 push하고 뒤로가기를 누를때마다 pop 합니다.

 2) 브라우저의 앞으로가기는 유저가 뒤로가기로 pop한 아이템을 push합니다.
    이때 앞으로가기를 누르면 해당 stack의 아이템을 pop하고 
    유저가 다른 링크를 눌러 이동시 해당 스택을 clean합니다.

---

스택을 사용할 때 발생할 수 있는 주요 제약은 무엇인가요?

 1) 음... 메모리 제약? 많이 쓰면 메모리관점에서 많은 공간을 차지하니 안정적인 서비스가 힘듬

 2) 배열기반 스택은 고정적 크기가 제약

---

함수 호출 스택과 힙 메모리의 차이점을 설명해주세요.

스택 영역

• 함수는 스택영역을 사용해서 호출하기에 재귀함수나 과도한 함수호출은 스택영역의 stack over flow를 발생 시킬 수 있음
• 메서드, 메서드가 돌아갈 리턴 주소, 메서드 내부의 변수들이 보관됩니다.
• GC 대상이 아닙니다.

힙 영역

• 힙 메모리는 객체, 클래스 변수, 동적 생성 배열, 객체에서 참조하고있는 상수 등이 생성됩니다
• 힙영역은 GC 대상으로 사용 빈도에 따라 GC할지 안할지 결정 대상에 들어가며 자주 사용하는 힙 요소들은 오래살아남습니다.

---

가비지 컬렉터가 스택 메모리와 힙 메모리를 관리하는 방식에 대해 설명해주세요.

스택

X (GC 대상이 아님) 메소드 호출 끝나면 메모리 바로 정리되기때문에 따로 관리가 필요없음

힙

Parallel GC ,Serial GC, CMS GC, G1 GC, ZGC, Shenandoah GC, Epsilon GC 등 관리 방식이 다양함

G1GC 기준으로 설명하면 Young Generation과 Old Generation을 논리적인 Region으로 나누어 관리

GC가 가장 많은 Garbage가 있는 Region부터 우선적으로 처리