LinkedList로 구현한 Stack

linkedlistStack.cpp

linkedlistStack.h

배열로 구현한 Stack에 이어서 오늘은 LinkedList로 구현한 Stack을 구현하겠습니다~

배열로 구현한 Stack와 다른점은 maxElementcount가 없습니다. 즉, 링크 주소만 쭉 연결해주면 제한이 없다는 점입니다.

linkedlistStack.h

1. #ifndef _LINKED_STACK_
2. #define _LINKED_STACK_
3.  
4. typedef struct StackNodeType
5. {
6.     int data;
7.     struct StackNodeType* pLink;
8. }StackNode;
9.  
10. typedef struct LinkedListStack
11. {
12.     int currentElementCount;
13.     StackNode* pTopElement;
14. }LinkedStack;
15.  
16.  
17. LinkedStack* createLinkedStack();
18. int pushLS(LinkedStack* pStack, StackNode element);
19. StackNode* popLS(LinkedStack* pStack);
20. StackNode* peekLS(LinkedStack* pStack);
21. void deleteLinkedListStack(LinkedStack* pStack);
22. int isLinkedStackFull(LinkedStack* pStack);
23. int isLinkedStakEmpty(LinkedStack* pStack);
24. void displayLinkedStack(LinkedStack* pStack)
25.  
26. #endif
27.  
28. #ifndef _COMMON_STACK_DEF
29. #define _COMMON_STACK_DEF
30.  
31. #define TRUE 1
32. #define FALSE 0
33.  
34. #endif
35.  

linkedlistStack.cpp

1. #include <stdio.h>
2. #include <stdlib.h>
3. #include <memory.h>
4. #include "linkedlistStack.h"
5.  
6. LinkedStack* createLinkedStack()
7. {
8.     LinkedStack* pReturn = NULL;
9.  
10.     pReturn = (LinkedStack*) malloc(sizeof(LinkedStack));
11.    
12.     if(pReturn != NULL)
13.     {
14.         memset(pReturn, 0, sizeof(LinkedStack));
15.     }
16.     else
17.     {
18.         printf("pReturn memory malloc error\n");
19.         return NULL;
20.     }
21.     return pReturn;
22. }
23. int pushLS(LinkedStack* pStack, StackNode element)
24. {
25.     int ret = FALSE;
26.     int i;
27.     StackNode *pNode = NULL;
28.     if(pStack != NULL)
29.     {
30.         pNode = (StackNode*) malloc(sizeof(StackNode));
31.         if(pNode != NULL)
32.         {
33.             memset(pNode, 0, sizeof(StackNode));
34.             *pNode = element;
35.             pNode->pLink = pStack->pTopElement;
36.             pStack->pTopElement = pNode;
37.             pStack->currentElementCount++;
38.             ret = TRUE;
39.         }
40.         else
41.         {
42.             printf("메모리 할당 오류\n");
43.         }
44.     }
45.     return ret;
46. }
47. StackNode* popLS(LinkedStack* pStack)
48. {
49.     StackNode *pReturn = NULL;
50.    
51.     pReturn = (StackNode*) malloc(sizeof(StackNode));
52.     if(pStack != NULL)
53.     {
54.         if(!isLinkedStakEmpty(pStack))
55.         {
56.             pReturn  = pStack->pTopElement;
57.             pStack->pTopElement = pReturn->pLink;
58.             pReturn->pLink = NULL;
59.             pStack->currentElementCount --;
60.         }
61.     }
62. }
63. StackNode* peekLS(LinkedStack* pStack)
64. {
65.     StackNode *pReturn = NULL;
66.    
67.     pReturn = (StackNode*) malloc(sizeof(StackNode));
68.     if(pStack != NULL)
69.     {
70.         if(!isLinkedStakEmpty(pStack))
71.         {
72.             pReturn  = pStack->pTopElement;
73.         }
74.     }
75. }
76. void deleteLinkedListStack(LinkedStack* pStack)
77. {
78.     StackNode* pNode = NULL;
79.     StackNode* pDelNode = NULL;
80.  
81.     if(pStack!=NULL)
82.     {
83.         pNode = pStack->pTopElement;
84.  
85.         while(pNode != NULL)
86.         {
87.             pDelNode = pNode;
88.             pNode = pDelNode->pLink;
89.             free(pDelNode);
90.         }
91.         free(pStack);
92.     }
93. }
94. int isLinkedStackFull(LinkedStack* pStack)
95. {
96.     int ret = FALSE;
97.     return ret;
98. }
99. int isLinkedStakEmpty(LinkedStack* pStack)
100. {
101.     int ret = FALSE;
102.  
103.     if(pStack != NULL)
104.     {
105.         if(pStack->currentElementCount == 0)
106.         {
107.             ret = TRUE;
108.         }
109.     }
110.     return ret;
111. }
112.  
113. void displayLinkedStack(LinkedStack* pStack)
114. {
115.     StackNode* pNode = NULL;
116.     int i = 1;
117.  
118.     if(pStack != NULL)
119.     {
120.         printf("현재 노드 갯수 : %d\n", pStack->currentElementCount);
121.         pNode = pStack->pTopElement;
122.  
123.         while(pNode!= NULL)
124.         {
125.             printf("[%d] - [%d]\n", pStack->currentElementCount-i, pNode->data);
126.             pNode = pNode->pLink;
127.             i++;
128.         }
129.     }
130. }

main.cpp

1. #include <stdio.h>
2. #include <stdlib.h>
3. #include "linkedlistStack.h"
4.  
5. int main()
6. {
7.     LinkedStack* pStack = NULL;
8.     StackNode* pNode = NULL;
9.     int i;
10.     pStack = createLinkedStack();
11.  
12.     if(pStack!= NULL)
13.     {
14.         StackNode node;
15.         for(i=1; i<10; i++)
16.         {
17.             node.data = i;
18.             node.pLink = NULL;
19.             pushLS(pStack, node);
20.         }
21.         displayLinkedStack(pStack);
22.     }
23.    
24.     return 0;
25. }
26.  

충분히 이해가 가실껍니다~