Chapter 06. 스택(Stack)

2.1 스택 기본 코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <assert.h>

enum {
    FALSE = 0,
    TRUE = 1,
    INVALIED_INDEX = -1,
    MAX_COUNT = 100001
};

typedef struct stack {
    int nArray[MAX_COUNT];
    size_t uTop;
} stack_t;

void push(stack_t* _pStack, int _nData);
int isEmpty(stack_t* _pStack);
int pop(stack_t* _pStack);

int main(void)
{


    return 0;
}


void push(stack_t* _pStack, int _nData)
{
    assert(_pStack->uTop < MAX_COUNT);

    _pStack->nArray[_pStack->uTop++] = _nData;
}
int isEmpty(stack_t* _pStack)
{
    if (0 == _pStack->uTop)
    {
        return TRUE;
    }
    return FALSE;
}
int pop(stack_t* _pStack)
{
    assert(FALSE == isEmpty(_pStack));

    return _pStack->nArray[--_pStack->uTop];
}

 

2.2 CodeUp 문제 풀이

// 1402 거꾸로 출력하기3

#include <stdio.h>
#include <assert.h>

enum { ... };

typedef struct stack { ... } stack_t;

void push(stack_t* _stack, int _nData);
int is_empty(stack_t* _stack);
int pop(stack_t* _stack);

int main(void)
{
    int     ans;
    size_t  i, size;
    stack_t st;

    scanf("%zu", &size);
    for (i = 0; i < size; ++i)
    {
        scanf("%d", &ans);
        push(&st, ans);
    }

    for (i = 0; i < size; ++i)
    {
        printf("%d ", pop(&st));
    }

    return 0;
}

void push(stack_t* _stack, int _nData)
{
    ...
}

int is_empty(stack_t* _stack)
{
    ...
}

int pop(stack_t* _stack)
{
    ...
}

 

// 1714 숫자 거꾸로 출력하기

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <assert.h>

enum {
    ...
};

typedef struct stack {
    ...
} stack_t;

void push(stack_t* _stack, int _nData);
int is_empty(stack_t* _stack);
int pop(stack_t* _stack);

int main(void)
{
    int         answer;
    size_t      i = 0, j;
    stack_t     stOriginal = { 0, }, stReverse = { 0, };

    scanf("%d", &answer);

    if (0 == answer)
    {
        printf("0");
        return 0;
    }
    else
    {
        while (0 < answer)
        {
            push(&stOriginal, answer % 10);
            answer /= 10;
            ++i;
        }
    }

    for (j = i; j > 0; --j)
    {
        push(&stReverse, pop(&stOriginal));
    }

    for (j = i; j > 0; --j)
    {
        printf("%d", pop(&stReverse));
    }

    return 0;
}

void push(stack_t* _stack, int _nData)
{
    ...
}

int is_empty(stack_t* _stack)
{
    ...
}

int pop(stack_t* _stack)
{
    ...
}

 

이진수 만들기

...

enum {
    FALSE = 0,
    TRUE = 1,
    INVALIED_INDEX = -1,
    MAX_COUNT = 32
};

typedef struct stack {
    ...
} stack_t;

void push(stack_t* _pStack, int _nData);
int isEmpty(stack_t* _pStack);
int pop(stack_t* _pStack);

int main()
{
    stack_t st = {0,};
    int i, j, n, n_1;

    scanf("%d", &n);
    for (i = 0; ; ++i)
    {
        n_1 = n % 2;
        push(&st, n_1);
        n /= 2;
        if (n <= 0)
        {
            break;
        }
    }

    for (j = 0; j <= i; ++j)
    {
        printf("%d", pop(&st));
    }

    return 0;
}

...

 

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

enum
{
    FALSE = 0,
    TRUE = 1,
    INVALIED_INDEX = -1,
    MAX_COUNT = 32
};

typedef struct stack
{
    int nArray[MAX_COUNT];
    size_t uTop;
} stack_t;

void push(stack_t* _pStack, int _nData);
int isEmpty(stack_t* _pStack);
int pop(stack_t* _pStack);

int main()
{
    stack_t st = {0,};
    size_t i, n;
    int cnt = 1;
    int input[101] = {0,}, trash;

    scanf("%zu", &n);
    for (i = 0; i < n; ++i)
    {
        scanf("%d", &input[i]);
    }

    for (i = 0; i < n; ++i)
    {
        while (TRUE)
        {
            if (input[i] != st.nArray[st.uTop])
            {
                push(&st, cnt++);
                printf("+ ");
            }
            else
            {
                trash = pop(&st);
                printf("- ");
            }

            if (TRUE == isEmpty(&st))
            {
                break;
            }
        }
    }

    return 0;
}

void push(stack_t* _pStack, int _nData)
{
    assert(_pStack->uTop < MAX_COUNT);

    _pStack->nArray[_pStack->uTop++] = _nData;
}
int isEmpty(stack_t* _pStack)
{
    if (_pStack->uTop == 0)
    {
        return TRUE;
    }
    return FALSE;
}
int pop(stack_t* _pStack)
{
    assert(FALSE == isEmpty(_pStack));

    return _pStack->nArray[--_pStack->uTop];
}

 

2014 스택 수열

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <assert.h>
#include <string.h>

enum {
    FALSE = 0,
    TRUE = 1,
    INVALID_INDEX  = -1,
    MAX_COUNT = 100001
};

typedef struct stack {
    int nArray[MAX_COUNT];
    size_t uTop;
} stack_t;

void push(stack_t* _pStack, int _nData);
int isEmpty(stack_t* _pStack);
int pop(stack_t* _pStack);
int top(stack_t* _pStack);
size_t size(stack_t* _pStack);
void print(stack_t* _pStack);

int main(void)
{
    stack_t st = {0,};
    int i, nNumCnt, nInputArrCnt = 1, nStrCnt = 1;
    int arrInput[MAX_COUNT] = {0,};
    char str[MAX_COUNT] = {0,};

    scanf("%d", &nNumCnt);
    for (i = 1; i <= nNumCnt; ++i)
    {
        scanf("%d", &arrInput[i]);
    }

    for (i = 1; i <= nNumCnt; ++i)
    {
        push(&st, i);
        str[nStrCnt++] = '+';
        while (FALSE == isEmpty(&st) && arrInput[nInputArrCnt] == top(&st))
        {
            pop(&st);
            ++nInputArrCnt;
            str[nStrCnt++] = '-';
        }
    }

    if (FALSE == isEmpty(&st))
    {
        printf("NO");
        return 0;
    }
    for (i = 1; i < nStrCnt; ++i)
    {
        printf("%c\n", str[i]);
    }

    return 0;
}

void push(stack_t* _pStack, int _nData)
{
    assert(_pStack->uTop < MAX_COUNT);

    _pStack->nArray[_pStack->uTop++] = _nData;
}
int isEmpty(stack_t* _pStack)
{
    if (_pStack->uTop == 0)
    {
        return TRUE;
    }
    return FALSE;
}
int pop(stack_t* _pStack)
{
    /* assert(FALSE == isEmpty(_pStack)); */
    if (TRUE == isEmpty(_pStack))
    {
        return -1;
    }

    return _pStack->nArray[--_pStack->uTop];
}
int top(stack_t* _pStack)
{
    if (TRUE == isEmpty(_pStack))
    {
        return -1;
    }
    return _pStack->nArray[_pStack->uTop-1];
}
size_t size(stack_t* _pStack)
{
    return _pStack->uTop;
}

void print(stack_t* _pStack)
{
    size_t i;
    for (i = 0; i < _pStack->uTop; ++i)
    {
        printf("%c", _pStack->nArray[i]);
    }
    printf("\n");
}

 

2010 탑(반대로)

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <assert.h>
#include <string.h>

enum {
    FALSE = 0,
    TRUE = 1,
    INVALID_INDEX = -1,
    MAX_COUNT = 101
};

typedef struct stack {
    int nArray[MAX_COUNT];
    size_t uTop;
} stack_t;

void push(stack_t* _pStack, int _nData);
int isEmpty(stack_t* _pStack);
int pop(stack_t* _pStack);
int top(stack_t* _pStack);
size_t size(stack_t* _pStack);
void print(stack_t* _pStack);

int main(void)
{

    stack_t st = { 0, };
    int i, nNumCnt;
    int arrInput[MAX_COUNT] = { 0, };
    int arrReceive[MAX_COUNT] = { 0, };
    int cnt = 1;


    scanf("%d", &nNumCnt);
    for (i = 1; i <= nNumCnt; ++i)
    {
        scanf("%d", &arrInput[i]);
    }

    for (i = nNumCnt; i >= 1; --i)
    {
        if (TRUE == isEmpty(&st))
        {
            push(&st, arrInput[i]);
            continue;
        }

        if (top(&st) < arrInput[i])
        {
            while (FALSE == isEmpty(&st) && top(&st) < arrInput[i])
            {
                arrReceive[i + cnt] = i;
                ++cnt;
                pop(&st);
            }
            push(&st, arrInput[i]);
        }
        else
        {
            push(&st, arrInput[i]);
        }
        cnt = 1;
    }

    for (i = 1; i <= nNumCnt; ++i)
    {
        printf("%d ", arrReceive[i]);
    }


    return 0;
}

void push(stack_t* _pStack, int _nData)
{
    assert(_pStack->uTop < MAX_COUNT);

    _pStack->nArray[_pStack->uTop++] = _nData;
}
int isEmpty(stack_t* _pStack)
{
    if (_pStack->uTop == 0)
    {
        return TRUE;
    }
    return FALSE;
}
int pop(stack_t* _pStack)
{
    /* assert(FALSE == isEmpty(_pStack)); */
    if (TRUE == isEmpty(_pStack))
    {
        return -1;
    }

    return _pStack->nArray[--_pStack->uTop];
}
int top(stack_t* _pStack)
{
    if (TRUE == isEmpty(_pStack))
    {
        return -1;
    }
    return _pStack->nArray[_pStack->uTop - 1];
}
size_t size(stack_t* _pStack)
{
    return _pStack->uTop;
}

void print(stack_t* _pStack)
{
    size_t i;
    for (i = 0; i < _pStack->uTop; ++i)
    {
        printf("%c", _pStack->nArray[i]);
    }
    printf("\n");
}

 

탑 C++ 버전

#include <bits/stdc++.h>

using namespace std;

stack< pair<int, int> > st;

int main(void)
{
    int nTopCount, nTopHeight;

    scanf("%d", &nTopCount);
    for (int i = 1; i <= nTopCount; i++)
    {
        scanf("%d", &nTopHeight);
        while (false == st.empty())
        {
            if (st.top().second < nTopHeight)
            {
                st.pop();
            }
            else
            {
                printf("%d ", st.top().first);
                break;
            }
        }

        if (true == st.empty())
        {
            printf("0 ");
        }

        st.push(make_pair(i, nTopHeight));
    }

    return 0;
}