배열로 구현한 Stack

arraystack.cpp

arraystack.h

main.cpp

오늘은 배열로 구현한 Stack을 포스팅 하려고 합니다. 

Stack : 자료를 한 방향으로만 쌓는 구조입니다. 앞에서 배운 리스트는 양방향으로 자료를 집어 넣고 , 뺄 수 있었지만 스택은 오직 한방향에서만 가능합니다. 

스택에서는 오직 맨 위에다가만 자료를 추가할 수 있습니다. 이를 Push라고 합니다. 

또한, 스택에서 자료를 꺼내는 것을 Pop라고 합니다.(현재 top에 있는 자료를 꺼내오겠죠!)

그래서 스택은 다른말로 LIFO(Last - In - First - Out) 맨 마지막에 들어와서 마지막 원소가 가장 먼저 나가는 특성을 지닙니다. 

기본적으로 배열로 구현한 Stack에서는 크기를 지정해줘야 합니다. 

배열로 구현한 스택의 단점은 크기를 미리 지정하고, 그 지정한 크기가 넘어가면 Overflow가 발생합니다. 

arraystack.h

1. #ifndef _ARRAYSTACK_
2. #define _ARRAYSTACK_
3.  
4. typedef struct ArrayStackNodeType
5. {
6.     int data;
7. }ArrayStackNode;                   //stackNode 구조체
8.  
9. typedef struct ArrayStackType
10. {
11.     int maxElementCount;           //최대 개수
12.     int currentElementCount;       //현재 개수
13.     ArrayStackNode* pElement;      //배열로 Node저장
14. }ArrayStack;                       //ArrayStack 구조체
15.  
16. ArrayStack* createArrayStack(int maxElementCount);       //stack만드는 함수
17. int pushAS(ArrayStack* pStack, ArrayStackNode element);  //push 함수
18. ArrayStackNode* popAS(ArrayStack* pStack);               //pop 함수
19. ArrayStackNode* peekAS(ArrayStack* pStack);              //현재 top에 있는 값 가져오는 함수
20. void deleteArrayStack(ArrayStack* pStack);               //stack을 삭제하는 함수
21. int isArrayStackFull(ArrayStack* pStack);                //stack이 full인지 검사
22. int isArrayStackEmpty(ArrayStack* pStack);               //stack이 empty인지 검사
23.  
24.  
25. #endif
26.  
27. #ifndef _COMMON_STACK_DEF
28. #define _COMMON_STACK_DEF
29.  
30. #define TRUE 1
31. #define FALSE 0
32.  
33. #endif
34.  

arraystack.cpp

1. #include <stdio.h>
2. #include <stdlib.h>
3. #include <memory.h>
4. #include "arraystack.h"
5.  
6.  
7.  
8. ArrayStack* createArrayStack(int size)
9. {
10.     ArrayStack* pReturn = NULL;
11.     int i = 0;
12.  
13.     if(size > 0)
14.     {
15.         pReturn = (ArrayStack*) malloc(sizeof(ArrayStack));
16.  
17.         if(pReturn != NULL)
18.         {
19.             memset(pReturn , 0, sizeof(ArrayStack));
20.             pReturn ->maxElementCount = size;
21.         }
22.         else
23.         {
24.             printf("pReturn memory malloc error\n");
25.             return NULL;
26.         }
27.         pReturn->pElement = (ArrayStackNode*) malloc(sizeof(ArrayStackNode)*size);
28.  
29.         if(pReturn->pElement != NULL)
30.         {
31.             memset(pReturn->pElement, 0, sizeof(ArrayStackNode)*size);
32.         }
33.         else
34.         {
35.             printf("pReturn memory malloc error\n");
36.             free(pReturn);
37.             return NULL;
38.         }
39.     }
40.     else
41.     {
42.         printf("size is 0 over\n");
43.         return NULL;
44.     }
45.     return pReturn;
46. }
47.  
48.  
49. int pushAS(ArrayStack* pStack, ArrayStackNode element)
50. {
51.     int ret = FALSE;
52.     int i;
53.    
54.     if(isArrayStackFull(pStack))
55.     {
56.         printf("ArrayStack is full\n");
57.         return ret;
58.     }
59.     if(pStack != NULL)
60.     {
61.         pStack->pElement[pStack->currentElementCount] = element;
62.         pStack->currentElementCount++;
63.         ret = TRUE;
64.     }
65.     return ret;
66. }
67. ArrayStackNode* popAS(ArrayStack* pStack)
68. {
69.     ArrayStackNode* pReturn;
70.  
71.     pReturn = (ArrayStackNode*) malloc(sizeof(ArrayStack));
72.  
73.     if(isArrayStackEmpty(pStack))
74.     {
75.         printf("stack is empty\n");
76.         return NULL;
77.     }
78.  
79.     pReturn = &(pStack->pElement[pStack->currentElementCount-1]);
80.  
81.     pStack->currentElementCount--;
82.     return pReturn;
83.  
84. }
85. ArrayStackNode* peekAS(ArrayStack* pStack)
86. {
87.    
88.     ArrayStackNode* pReturn = NULL;
89.     if(isArrayStackEmpty(pStack))
90.     {
91.         printf("stack is empty\n");
92.         return NULL;
93.     }
94.  
95.     pReturn  = (ArrayStackNode*) malloc(sizeof(ArrayStackNode));
96.  
97.     pReturn = &(pStack->pElement[pStack->currentElementCount-1]);
98.     return pReturn;
99. }
100. void deleteArrayStack(ArrayStack* pStack)
101. {
102.     if(isArrayStackEmpty(pStack))
103.     {
104.         printf("stack is empty\n");
105.         return ;
106.     }
107.  
108.     if(pStack!=NULL)
109.     {
110.         if(pStack->pElement != NULL)
111.         {
112.             free(pStack->pElement);
113.         }
114.         free(pStack);
115.     }
116. }
117.  
118. int isArrayStackFull(ArrayStack* pStack)
119. {
120.     int ret = FALSE;
121.  
122.     if(pStack != NULL)
123.     {
124.         if(pStack->currentElementCount == pStack->maxElementCount)
125.             ret =TRUE;
126.     }
127.     return ret;
128. }
129. int isArrayStackEmpty(ArrayStack* pStack)
130. {
131.         int ret = FALSE;
132.  
133.     if(pStack != NULL)
134.     {
135.         if(pStack->currentElementCount == 0)
136.             ret =TRUE;
137.     }
138.     return ret;
139. }
140.  

main.cpp

1. #include <stdio.h>
2. #include <stdlib.h>
3. #include <string.h>
4. #include "arraystack.h"
5.  
6. void displayArrayStack(ArrayStack* pStack)
7. {
8.     int i = 0;
9.     if(pStack!=NULL)
10.     {
11.         int size = pStack->maxElementCount;
12.         int top = pStack->currentElementCount;
13.  
14.         printf("스택 크기  %d  , 현재 노드 갯수  %d \n", size, top);
15.  
16.         for(i = size - 1 ; i>=top; i--)
17.         {
18.             printf("[%d] - [empty]\n", i);
19.         }
20.         for(i = top - 1 ; i>=0; i--)
21.         {
22.             printf("location : [%d] - data : [%d]\n", i, pStack->pElement[i].data);
23.         }
24.     }
25. }
26. int main()
27. {
28.     int i;
29.     ArrayStack *stack = NULL;
30.     ArrayStackNode node;
31.     stack = createArrayStack(10);
32.  
33.  
34.     for(i = 1; i<11; i++)
35.     {
36.         node.data = i;
37.         pushAS(stack, node);
38.     }
39.    popAS(stack);   
40.     displayArrayStack(stack);
41.     return 0;
42. }

main파일에 몇가지 함수를 실행 안해봤는데요. 기본적으로 실행은 다 됩니다. 

제가 만든 소스도 같이 올립니다~

다음시간에는 연결리스트를 이용한 Stack를 만들께요~