LinkedQueue

오랜만에 포스팅입니다.

오늘은 LinkedList로 만든 Queue입니다.

Queue는 우리 일상 생활에도 많이 존재합니다.

예를 들어서 은행에서 먼저 온사람이 먼저 서비스 받고, 나중에 온 사람이 나중에 서비스 받는 구조입니다.

즉, 선입선출의 특성을 지닙니다.(First - In - First - Out , FIFO)
먼저 들어온게 먼저 나가고, 나중에 들어온게 나중에 서비스를 받습니다.

Queue를 구현하는 방법은 많이 있습니다만, 저는 여기서 LinkedList를 가지고 구현해보도록 하겠습니다.(이유는 배열로 구현한 것은 미리 Queue의 크기를 정해야 하지만 LinkedList는 그럴 필요 없기 때문입니다. 또 한가지 이유는 제가 요즘 포인터에 대해서 좀 더 친숙해 질려고 노력중이기 때문입니다.)

Queue를 그림으로 표현하면 다음과 같이 표현합니다.

 Queue에는 포인터가 2개가 존재합니다. 맨 처음을 가르키는 포인터와 맨 끝을 가르키는 포인터

enQueue는 Data를 집어 넣는 것이고, deQueue는 Data를 빼는 것입니다.

enQueue시에는 rearNode를 한단계 증가시켜주면 되고,

deQueue에는 frontNode를 한단계 증가시키고 메모리를 해제하면 되겠습니다.

linkedQueue.h

1. #ifndef _LINKED_QUEUE_
2. #define _LINKED_QUEUE_
3.  
4. typedef struct QueueNodeType
5. {
6.     char data;
7.     struct QueueNodeType* pLink;
8. }QueueNode;  //큐노드 구조체
9.  
10. typedef struct LinkedQueueType
11. {
12.     int currentElementCount;
13.     QueueNode* pFrontQueue;
14.     QueueNode* pRearQueue;
15. }LinkedQueue; //큐 구조체
16.  
17. LinkedQueue* createLinkedQueue(); //큐 생성 함수
18. int edqueueLQ(LinkedQueue* pQueue, QueueNode element); //큐에 값을 넣는 함수
19. QueueNode* dequeueLQ(LinkedQueue* pQueue); //큐에 값을 빼는 함수
20. QueueNode* peekLQ(LinkedQueue* pQueue);    //큐의 맨 앞의 값, 즉 frontNode의 값을 가져온다
21. void deleteLinkedQueue(LinkedQueue* pQueue); //큐 삭제 함수
22. int isLinkedQueueFull(LinkedQueue* pQueue);  //큐가 다 찼는지 검사
23. int isLinkedQueueEmpty(LinkedQueue* pQueue); //큐가 비어있는지 검사
24.  
25.  
26. #endif
27.  
28. #ifndef _COMMON_QUEUE_DEF_
29. #define _COMMON_QUEUE_DEF_
30.  
31. #define TRUE 1
32. #define FALSE 0
33.  
34. #endif
35.  
36.  

linkedQueue.cpp

1. #include <stdio.h>
2. #include <stdlib.h>
3. #include <memory.h>
4. #include "linkedqueue.h"
5.  
6.  
7. LinkedQueue* createLinkedQueue()
8. {
9.     LinkedQueue* pReturn = NULL;  //새로 LinkedQueue를 생성한다.
10.     int i = 0;
11.     pReturn = (LinkedQueue*) malloc(sizeof(LinkedQueue)); //메모리를 할당하고
12.        
13.     if(pReturn != NULL)
14.     {
15.         memset(pReturn, 0, sizeof(LinkedQueue)); //메모리가 제대로 할당 되었다면 메모리를 0으로 채운다.
16.     }
17.     else
18.     {
19.         printf("memory error, createLinkedQueue()\n");
20.     }
21.     return pReturn; //pReturn값이 NULL 혹은 제대로 메모리 할당 한 값을 반환한다.
22. }
23. int edqueueLQ(LinkedQueue* pQueue, QueueNode element)
24. { //큐에 데이터를 넣는 함수
25.     int ret =FALSE;
26.     QueueNode* pNode; //큐에서 연결할 수 있는 구조체
27.  
28.     if(pQueue!=NULL)
29.     {
30.         pNode = (QueueNode*) malloc(sizeof(QueueNode));  //메모리 할당하고
31.  
32.         if(pNode!=NULL)
33.         {
34.             *pNode = element; //할당이 잘 되었다면 element값을 넣어준다.
35.             //pNode = &(element); //이렇게 해줘도 상관없다.
36.             pNode->pLink = NULL;
37.  
38.             //만약 Queue가 비어있다면 FrontNode 와 RearNode가 같은 값을 가지고 있따.
39.             if(isLinkedQueueEmpty(pQueue) ==TRUE)
40.             {  
41.                 pQueue->pFrontQueue = pNode;
42.                 pQueue->pRearQueue = pNode;
43.             }
44.             else
45.             {
46.                 //그렇지 않으면 RearNode->pLink에만 pNode를 연결시켜준다
47.                 pQueue->pRearQueue->pLink = pNode;
48.                 pQueue->pRearQueue = pNode;
49.             }
50.             pQueue->currentElementCount++;
51.             ret = TRUE;
52.  
53.         }
54.         else
55.         {
56.             printf("memory error, enqueue()\n");
57.         }
58.     }
59.     return ret;
60. }
61. QueueNode* dequeueLQ(LinkedQueue* pQueue)
62. {//Queue의 FrontNode를 가져오는 함수
63.     QueueNode* pReturn = NULL;
64.  
65.     if(pQueue != NULL)
66.     {
67.         pReturn = (QueueNode*)malloc(sizeof(QueueNode));
68.         //Queue가 비었는지 검사를 하고
69.         if(isLinkedQueueEmpty(pQueue) ==FALSE)
70.         {
71.             //pReturn에 pQueue의 pFrontQueue를 넣어준다.
72.             //그리고 pQueue의 pFrontQueue에 다음 주소값을 대입해주고
73.             //pReturn을 삭제한다.
74.             pReturn = pQueue->pFrontQueue;
75.             pQueue->pFrontQueue = pQueue->pFrontQueue->pLink;
76.             pReturn->pLink = NULL;
77.             pQueue->currentElementCount--;
78.             if(isLinkedQueueEmpty(pQueue) == TRUE)
79.             {
80.                 pQueue->pRearQueue = NULL;
81.             }
82.         }
83.     }
84.     return pReturn;
85. }
86. QueueNode* peekLQ(LinkedQueue* pQueue)
87. {
88.     //현재 pQueue의 FrontNode를 가져오는 함수
89.     QueueNode* pReturn = NULL;
90.  
91.     if(pQueue != NULL)
92.     {
93.         if(isLinkedQueueEmpty(pQueue) == FALSE)
94.             pReturn = pQueue->pFrontQueue;
95.     }
96.     return pReturn;
97. }
98. void deleteLinkedQueue(LinkedQueue* pQueue)
99. {//pQueue를 삭제하는 함수
100.     QueueNode* pNode = NULL;
101.     QueueNode* pDelNode = NULL;
102.    
103.     while(pQueue != NULL)
104.     {
105.         pNode = pQueue->pFrontQueue;
106.  
107.         while(pNode != NULL)
108.         {
109.             pDelNode = pNode;
110.             pNode = pNode->pLink;
111.  
112.             free(pDelNode);
113.         }
114.         free(pQueue);
115.     }
116. }
117. int isLinkedQueueFull(LinkedQueue* pQueue)
118. {
119.     int ret = FALSE;
120.     return ret;
121. }
122. int isLinkedQueueEmpty(LinkedQueue* pQueue)
123. {
124.     int ret = FALSE;
125.  
126.     if(pQueue != NULL)
127.     {
128.         if(pQueue->currentElementCount == 0)
129.             ret = TRUE;
130.     }
131.     return ret;
132. }
133.  

main.cpp

1. #include <stdio.h>
2. #include <stdlib.h>
3. #include "linkedqueue.h"
4.  
5. void displayLinkedQueue(LinkedQueue *pQueue)
6. {
7.     QueueNode *pNode = NULL;
8.     int i = 0;
9.     if (pQueue != NULL) {
10.         printf("현재 노드 개수: %d\n",
11.                 pQueue->currentElementCount);
12.         pNode = pQueue->pFrontQueue;
13.         while(pNode != NULL) {
14.             printf("[%d]-[%c]\n", i, pNode->data);
15.             i++;
16.             pNode = pNode->pLink;
17.         }
18.     }
19. }
20. int enqueueLQChar(LinkedQueue* pQueue, char data)
21. {
22.     QueueNode node = {0,};
23.     node.data = data;
24.     return edqueueLQ(pQueue, node);
25. }
26.  
27. int main(int argc, char *argv[])
28. {
29.     LinkedQueue *pQueue = NULL;
30.     QueueNode *pNode = NULL;
31.     char value = 0;
32.  
33.     // 배열 큐 생성
34.     pQueue = createLinkedQueue();
35.     if (pQueue != NULL) {
36.         // 큐 초기화: 'A', 'B', 'C', 'D' 추가.
37.         enqueueLQChar(pQueue, 'A');
38.         enqueueLQChar(pQueue, 'B');
39.         enqueueLQChar(pQueue, 'C');
40.         enqueueLQChar(pQueue, 'D');
41.         displayLinkedQueue(pQueue);
42.  
43.         pNode = dequeueLQ(pQueue);
44.         if (pNode != NULL) {
45.             printf("Dequeue Value-[%c]\n", pNode->data);
46.             free( pNode );
47.         }
48.  
49.         pNode = dequeueLQ(pQueue);
50.         if (pNode != NULL) {
51.             printf("Dequeue Value-[%c]\n", pNode->data);
52.             free( pNode );
53.         }
54.         displayLinkedQueue(pQueue);
55.  
56.         pNode = peekLQ(pQueue);
57.         if (pNode != NULL) {
58.             printf("Peek Value-[%c]\n", pNode->data);
59.         }
60.         displayLinkedQueue(pQueue);
61.  
62.         // 큐에 'E', 'F' 추가.
63.         enqueueLQChar(pQueue, 'E');
64.  
65.         displayLinkedQueue(pQueue);
66.     }
67.     return 0;
68. }

linkedqueue.cpp

linkedqueue.h

main.cpp