[코딩인터뷰 완전정복] 3.5 스택 정렬

Q : 가장 작은 값이 위로 오도록 스택을 정렬하는 프로그램을 작성하라. 추가적으로 하나 정도의 스택은 사용해도 괜찮지만, 스택에 보관된 요소를 배열 등의 다른 자료구조로 복사할 수는 없다. 스택은 push, pop, peek, isEmpty의 네가지 연산을 제공해야 한다.

#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 peak() {
        if (nOfE == 0) return NULL;
        return start[nOfE - 1];
    }

    int Size() {
        return nOfE;
    }

    bool isEmpty() {
        return nOfE == 0;
    }
};

#include "Stack.h"

void StackSort(Stack<int> stack) {
    Stack<int> buffer;

    while (!stack.isEmpty()) {
        int temp = stack.pop();
        int count = 0;

        while (!buffer.isEmpty() && buffer.peak() > temp) {
            stack.push(buffer.pop());
            count++;
        }

        buffer.push(temp);

        for (int i = 0; i < count; i++) {
            buffer.push(stack.pop());
        }
    }

    while (!buffer.isEmpty()) {
        stack.push(buffer.pop());
    }
}

int main() {
    Stack<int> stack;
    stack.push(2);
    stack.push(1);
    stack.push(4);
    stack.push(6);
    stack.push(12);
    stack.push(2);
    stack.push(66);
    stack.push(7);
    stack.push(8);
    stack.push(10);
    stack.push(4);

    StackSort(stack);

    while(!stack.isEmpty()) {
        printf("%d\n", stack.pop());
    }
}

1. 인풋 스택에서 1개의 원소를 뺀 뒤 버퍼 스택의 제일 위에 있는 값과 비교한다.

2. 만약 원소가 버퍼 스택의 peak 값보다 크거나 같다면 버퍼스택에 넣는다.

3. 원소가 버퍼 스택에 peak값보다 작다면 원소가 들어갈 위치를 찾아야 한다.

   버퍼 스택이 비거나 원소보다 작은값이 나올 때 까지 버퍼 스택을 pop하여 인풋 스택에 넣어주고 그 숫자를 저장한다.

   그 다음 버퍼 스택에 원소를 집어넣고 버퍼 스택에서 꺼냈던 원소들을 다시 돌려준다.

4. 인풋 스택이 빌때 까지 1부터 반복한다.

5. 버퍼 스택의 모든 원소를 pop해서 인풋 스택에 push해준다.