본문 바로가기
C/자료구조와 알고리듬

Chapter 06. 스택(Stack)

by GameStudy 2021. 11. 10.

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;
}
저작자표시 비영리 변경금지

'C > 자료구조와 알고리듬' 카테고리의 다른 글

Chapter 08. 연결 리스트(Linked List)  (0) 2021.11.12
Chapter 07. 큐(Queue)  (0) 2021.11.10
Chapter 05. 가변 길이 배열(Variadic Array)  (0) 2021.11.10
Chapter 04. 배열(Array)  (0) 2021.11.01
Chapter 03. 정렬  (0) 2021.06.18

관련글

댓글

티스토리툴바