Problem1

An animal shelter holds only dogs and cats and operates on a strictly first in, first out basis. People must adopt either the oldest (based on arrival time) of all animals at the shelter, or they can select whether they would prefer a dog or a cat (and will receive the oldest animal of that type). They cannot select which specific animal they would like. Design the data structures to maintain this system.

동물 보호소는 개와 고양이만을 수용하며, 엄격한 선입선출(FIFO) 방식으로 운영됩니다. 사람들은 보호소에 있는 모든 동물 중 가장 오래된 동물을 입양하거나, 개 또는 고양이 중 하나를 선택할 수 있습니다(선택한 동물 유형에서 가장 오래된 동물을 입양하게 됩니다). 특정 동물을 선택할 수는 없습니다. 이 시스템을 유지하기 위한 데이터 구조를 설계하세요.

Problem2

항공 지도에서 도시 A에서 도시 B로 가는 경로가 있는지 탐색하세요.

Problem3

두 개의 stack을 사용하여 Queue를 구현하세요.

• 아이디어: 첫 번째 스택은 enqueue 용도로, 두 번째 스택은 dequeue 용도로 사용
• dequeue 요청을 받았을 때 두 번째 스택이 비어 있다면, 첫 번째 스택의 모든 요소를 pop하여 두 번째 스택에 push