Q.Stack과 Queue

Q. Stack?

Q. Queue?

Q. 스택과 큐의 차이점?

Q. 스택과 큐를 각각 언제 사용하는가?

Q. 스택에 숫자들이 계속 들어오고, O(1)만에 스택에 들어있는 숫자들중에 최소값 찾는 방법?
- A. 흔히 ‘Min 스택’이라고 부르는 보조 스택을 하나 만들어서 최소값만 따로 관리하는 방식을 씁니다. push할 때는 새 값이 최소값 스택의 top보다 작거나 같으면 그 스택에도 같이 넣고, pop할 때는 데이터 스택에서 꺼낸 값이 최소값 스택 top과 같으면 같이 꺼냅니다.
이렇게 하면 getMin 연산은 항상 최소값 스택 top을 바로 반환해서 O(1)로 처리할 수 있습니다.
공간은 최악의 경우 O(n) 들어가지만, push, pop, getMin 모두 O(1) 보장됩니다.