가자미의 개발이야기

[자료구조] C언어로 배열 스택 구현하기 본문

Computer Science/자료구조

[자료구조] C언어로 배열 스택 구현하기

가자미 2021. 2. 10. 11:25

개념

-자료를 쌓아두는 의미

-LIFO(Last In First Out). 리포, 후입선출

-푸시(Push) 스택에 자료를 추가하는 것

-팝(Pop) 스택에서 자료를 꺼내는 것

-피크(Peek) 자료를 꺼내지 않고 스택의 가장 최상위에 있는 자료에 접근

-오버플로우(넘침) 스택 크기를 초과하여 새로운 자료 추가

-언더플로우(부족) 원소가 없는데 자료를 꺼내려 함

-배열로 구현 시 복잡도는 낮지만, 스택 크기를 미리 고정.

 

arraystack.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#ifndef _ARRAY_STACK_
#define _ARRAY_STACK_
 
typedef struct ArrayStackNodeType {
    char data;
}ArrayStackNode;
 
typedef struct ArrayStackType {
    int maxElementCount;
    int currentElementCount;
    ArrayStackNode* pElement;    //노드 저장을 위한 1차원 배열
}ArrayStack;
 
ArrayStack* createArrayStack(int maxElementCount);
int pushAS(ArrayStack* pStack, ArrayStackNode element);
ArrayStackNode* popAS(ArrayStack* pStack);
ArrayStackNode* peekAS(ArrayStack* pStack);
void deleteArrayStack(ArrayStack* pStack);
int isArrayStackFull(ArrayStack* pStack);
int isArrayStackEmpty(ArrayStack* pStack);
#endif
 
#ifndef _COMMON_STACK_DEF_
#define _COMMON_STACK_DEF_
 
#define TRUE    1
#define FALSE    0
#endif
 cs

"

 

 

arraystack.c

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "arraystack.h"
 
ArrayStack* createArrayStack(int size)
{
    ArrayStack* pReturn = NULL;
    int i = 0;
 
    if (size > 0) {
        pReturn = (ArrayStack*)malloc(sizeof(ArrayStack));    //메모리 할당
        if (pReturn != NULL) {
            memset(pReturn, 0, sizeof(ArrayStack));    //메모리 초기화
            pReturn->maxElementCount = size;    //최대 저장공간 설정
        }
        else {
            printf("오류, 메모리 할당, createArrayStack()\n");
            return NULL;
        }
 
        //배열 메모리 할당
        pReturn->pElement = (ArrayStackNode*)malloc(sizeof(ArrayStackNode) * size);
        if (pReturn->pElement != NULL) {
            memset(pReturn->pElement, 0, sizeof(ArrayStackNode) * size);//배열 초기화
        }
        else {
            printf("오류, 메모리 할당2, createArrayStack()\n");
            free(pReturn);
            return NULL;
        }
    }
    else {
        pritnf("오류, 스택의 크기는 0 이상이어야 합니다.\n");
        return NULL;
    }
    return pReturn;
}
int pushAS(ArrayStack* pStack, ArrayStackNode element)
{
    int ret = FALSE, i = 0;
 
    if (pStack != NULL) {
        if (isArrayStackFull(pStack) == FALSE) {
            pStack->pElement[pStack->currentElementCount] = element;
            pStack->currentElementCount++;
            ret = TRUE;
        }
        else {
            printf("오류, 스택이 가득 찼습니다. pushAS()\n");
        }
    }
    else {
        printf("메모리 할당 오류, pushAS()\n");
    }
    return ret;
}
ArrayStackNode* popAS(ArrayStack* pStack)
{
    ArrayStackNode* pReturn = NULL;
    if (pStack != NULL) {
        if (isArrayStackEmpty == FALSE) {
            pReturn = (ArrayStackNode*)malloc(sizeof(ArrayStackNode));
            if (pReturn != NULL) {
                *pReturn = pStack->pElement[pStack->currentElementCount - 1];
                pStack->currentElementCount--;
            }
            else {
                printf("오류, 메모리 할당, popAS()\n");
            }
        }
        else {
            printf("스택이 비었습니다. popAS()\n");
        }
    }
    else {
        printf("오류, 메모리 할당2, popAS()\n");
    }
    return pReturn;
}
ArrayStackNode* peekAS(ArrayStack* pStack)
{
    ArrayStackNode* pReturn = NULL;
    if (pStack != NULL) {
        if (isArrayStackEmpty == FALSE) {
            pReturn = &(pStack->pElement[pStack->currentElementCount - 1]);
            //peek은 포인터만 반환
        }
        else {
            printf("스택이 비었습니다. peekAS()\n");
        }
 
    }
    else {
        printf("오류, 메모리 할당, peekAS()\n");
    }
    return pReturn;
}
void deleteArrayStack(ArrayStack* pStack) {
    if (pStack != NULL) {
        if (pStack->pElement != NULL) {
            free(pStack->pElement);
        }
        free(pStack);
    }
}
int isArrayStackFull(ArrayStack* pStack) {
    int ret = FALSE;
    if (pStack != NULL) {
        if (pStack->pElement != NULL) {
            if (pStack->currentElementCount == pStack->maxElementCount) {
                ret = TRUE;
            }
        }
    }
    return ret;
}
int isArrayStackEmpty(ArrayStack* pStack) {
    int ret = FALSE;
    if (pStack != NULL) {
        if (pStack->pElement != NULL) {
            if (pStack->currentElementCount == 0) {
                ret = TRUE;
            }
        }
    }
    return ret;
}
 cs

 

 

 

만난 오류들

ifndef를 ifdef로 작성해서 구조체 자료형을 인식하지 못하는 오류가 있었다.

'Computer Science > 자료구조' 카테고리의 다른 글

[자료구조] 스택  (0) 2021.07.05
[자료구조] 배열과 리스트  (0) 2021.07.05
[자료구조] 연결리스트로 다항식 구현하기  (0) 2021.02.10
C언어로 원형 연결 리스트 만들기  (0) 2021.02.09
C언어로 링크드리스트(연결리스트) 만들기  (0) 2021.02.04
'Computer Science/자료구조' Related Articles more