|
STL에 있는 수많은 Data structure 들 중에
어떤 pointer들을 안에 저장하고 있는 리스트 비슷한 것으로,
아래의 설명을 만족하는 structure가 무엇인가요?(STL에서 그러한 데이타스트럭쳐를 구현한 클레스의 이름이 무엇인가요?)
1. push와 pop동작을 지원한다.
3. pop()은 그 안에서 포함된 포인터 하나를 제거한 후 그 포인터를 리턴하는 것, 즉 , 포인터 하나를 밖으로 빼내는 동작을 하되, 어떤 순서로 빼낸다는 것에 대한 제약상황은 (구하는 자가) 상관하지 않는다. 즉, 처음 들어간 것이 먼저 나오는 스트럭쳐여도 괜찮고, 늦게 들어간게 먼저 나오는 것이여도 괜찮고, 무작위로 나오는 것이라도 괜찮다. 그러나, pop의 time-complexity는 log N 이하이어야 한다. (N은 안에 저장된 포인터의 갯수)
2. push(i)는 포인터 i를 그 안에 넣는 동작을 하되, 그 안에 이미 같은 포인터(주소가 같은 포인터)가 들어있을 경우에는 넣지 않는다. push는 (이미 같은 포인터가 있는지를 확인하는 과정을 포함함에도 불구하고) time complexity가 log N 이하이다.
|