[코딩인터뷰 완전정복] 3.3 접시 무더기

Q : 자료구조 SetOfStacks를 구현해 보라. SetOfStacks는 여러 개의 스택으로 구성되어 있으며, 이전 스택이 지정된 용량을 초과하는 경우 새로운 스택을 생성해야 한다. SetOfStacks.push()와 SetOfStacks.pop()은 스택이 하나인 경우와 동일하게 동작해야 한다.

#include <iostream>

template<typename T>
class Stack {
private:
    T *start;
    int nOfE;
    int size;
public:

    Stack() {
        start = new T[10];
        nOfE = 0;
        size = 10;
    }

    Stack(int N) {
        start = new T[N];
        nOfE = 0;
        size = N;
    }

    void push(T n) {
        if (nOfE == size) {
            T *sizeIncreaseStack = new T[size * 2];
            sizeIncreaseStack = start;
            for (int i = 0; i < size; i++) {
                sizeIncreaseStack[i] = start[i];
            }
            start = sizeIncreaseStack;
            size *= 2;
        }
        start[nOfE] = n;

        nOfE++;
    }

    T pop() {
        if (nOfE == 0) return NULL;
        nOfE--;

        return start[nOfE];
    }

    T top() {
        if (nOfE == 0) return NULL;
        return start[nOfE - 1];
    }

    int Size() {
        return nOfE;
    }
};

#include <iostream>
#include "Stack.h"

template <typename T>
class SetOfStack {
private :
    Stack<Stack<T>*> stackStack;
    int index;
    int stackSize;
public :
    SetOfStack() {
        stackSize = 8;
        index = stackSize;
    }

    SetOfStack(int size) {
        stackSize = size;
        index = stackSize;
    }

    void push(T n) {
        if (stackSize <= index) {
            stackStack.push(new Stack<T>(stackSize));
            index = 1;
        }
        else {
            index++;
        }
        (*stackStack.top()).push(n);
    }

    T pop() {
        if (stackStack.Size() == 0) return NULL;
        T value = (*stackStack.top()).pop();
        if (index <= 1) {
            stackStack.pop();
            index = stackSize;
        }
        else {
            index--;
        }
        return value;
    }
};

Stack을 담는 Stack을 만들고 내부 스택이 꽉 차면 새로운 스택을 추가한다.