12일차
게일 라크만 맥도웰의 코딩 인터뷰 완전 분석 p.144 ~ p.146, 3.1, 3.2
내용 정리
9 면접 문제
03 스택과 큐
스택 구현하기
- 스택 자료구조는 데이터를 쌓아 올린다(stack)는 의미이다.
- LIFO(Last-In-Fisrt-Out)에 따라 자료를 배열한다.
- 연산은 다음과 같다.
pop(): 가장 위에 있는 항목을 제거한다.push(item):item하나를 가장 윗 부분에 추가한다.peek(): 가장 위에 있는 항목을 반환한다.isEmpty(): 스택이 비어 있을 때에 true를 반환한다.
- 배열과 달리 상수 시간에 i번째 항목에 접근할 수 없다.
- 데이터를 추가하거나 삭제하는 연산은 상수시간에 가능하다.
- 재귀함수에서 많이 사용한다.
큐 구현하기
- FIFO(First-In-First-Out) 순서를 따른다.
- 연산은 다음과 같다.
add(item):item을 리스트의 끝부분에 추가한다.remove(): 리스트의 첫 번째 항목을 제거한다.peak(): 큐에서 가장 위에 있는 항목을 반환한다.isEmpty(): 큐가 비어 있을 때에 true를 반환한다.
- 큐를 연결리스트로 구현할 수 있다.
- BFS나 캐시를 구현할 떄 종종 사용한다.
면접 문제
3.1 한 개로 세 개
배열 한 개로 스택 세 개를 어떻게 구현할지 설명하라.
답
배열을 같은 크기의 세 부분으로 나누어 각각의 스택이 그 크기 내에서만 사용되도록 한다. 아래에서 []는 끝점을 포함, ()는 미포함이다.
1번 스택은 [0, n/3)
2번 스택은 [n/3,2n/3)]
3번 스택은 [2n/3, n)
에 할당한다.
3.2 스택 Min
기본적인 push와 pop 기능이 구현된 스택에서 최솟값을 반환하는 min함수를 추가하려고 한다. 어떻게 설계할 수 있겠는가? push, pop, min 연산은 모두 O(1) 시간에 동작해야 한다.
답
스택을 두개 유지 한다. 스택 A에 숫자를 넣고, 다음 숫자와 비교하여 큰 것을 스택 B에 넣는다. 스택 A에는 가장 작은 수만 유지되고, 그 외의 수는 스택 B에 쌓는다.
읽고 나서
큐는 bfs 덕에 어느정도 익숙해졌는데 사실 스택은 조금은 낯설다. 이참에 둘 모두 알아두자.
