[프로그래머 면접 금 전] 면접 문제 03.03. 접시 쌓 기

제목.
접 시 를 쌓다.접시 한 무 더 기 를 상상 해 봐, 너무 높 게 쌓 으 면 넘 어 질 수도 있어.그래서 현실 생활 에서 접시 가 일정 높이 쌓 일 때 우 리 는 따로 접 시 를 쌓 아 놓는다.데이터 구조 SetOfStacks 를 실현 하여 이러한 행 위 를 모 의 하 십시오.SetOfStacks 는 여러 개의 스 택 으로 구성 되 어야 하 며, 이전 스 택 이 가득 찼 을 때 스 택 을 새로 만들어 야 합 니 다.또한, SetOfStacks. push () 와 SetOfStacks. pop () 은 일반 스 택 의 조작 방법 과 같 아야 합 니 다 (즉, pop () 가 되 돌아 오 는 값 은 하나의 스 택 만 있 을 때의 상황 과 같 아야 합 니 다).진급: popAt (int index) 방법 을 실현 하고 지정 한 하위 스 택 에 따라 pop 작업 을 수행 합 니 다.어떤 스 택 이 비어 있 을 때 이 스 택 을 삭제 해 야 합 니 다.스 택 에 요소 가 없 거나 이 스 택 이 존재 하지 않 을 때 pop, popat 돌아 가 야 지. - 1.
예시 1:

  ：
["StackOfPlates", "push", "push", "popAt", "pop", "pop"]
[[1], [1], [2], [1], [], []]
  ：
[null, null, null, 2, 1, -1]

예시 2:

  ：
["StackOfPlates", "push", "push", "push", "popAt", "popAt", "popAt"]
[[2], [1], [2], [3], [0], [0], [0]]
  ：
[null, null, null, null, 2, 1, 3]

사고의 방향
2 차원 배열 을 사용 하여 여러 개의 스 택 을 표시 하고 줄 마다 스 택 을 표시 합 니 다.
코드
시간 복잡 도: O (1) 공간 복잡 도: O (1)

class StackOfPlates {
    int size;
    vector> vec;
public:
    StackOfPlates(int cap) {
        size = cap;
        vec.push_back(vector());
    }
    
    void push(int val) {
        if (size > 0) {
            if (!vec.empty() && vec.back().size() < size) {
                vec.back().push_back(val);
            } else {
                vec.push_back(vector());  //      
                vec.back().push_back(val);
            }
        }
    }
    
    int pop() {
        if (size > 0) {
            if (vec.empty() || (vec.size() == 1 && vec.back().empty())) return -1;
            int val = vec.back().back();
            vec.back().pop_back();
            if (vec.back().empty()) vec.pop_back();  //      
            return val;
        }
        return -1;
    }
    
    int popAt(int index) {
        if (size > 0) {
            if (vec.empty() || index >= vec.size() || (vec.size() == 1 && vec.back().empty())) return -1;
            int val = vec[index].back();
            vec[index].pop_back();
            if (vec[index].empty()) vec.erase(vec.begin() + index);  //        
            return val;
        }
        return -1;
    }
};