2011
연재 차례
1. C언어 소개
2. 형태, 연산자, 표현
3. 제어 흐름
4. 함수와 프로그램 구조
5. 포인터와 배열
6. 구조체
7. 알고리즘 소개
8. 소팅을 통한 알고리즘 분석
9. 스택(Stack) 실습
10. 큐(Queue) 실습
11. 리스트(List) 실습
12. 트리(Tree) 실습
13. 해싱(Hash) 실습
14. 알고리즘 설계 및 분석기법
15. 진보된 알고리즘 소개
컴
퓨팅에서 일반적인 프로그래밍 패턴은 생산(입력)과 소비(출력)이다. 생산자는 데이터를 생성하고 소비자는 데이터를 읽고 처리한다.
이러한 패턴을 구현하기 위한 가장 쉬운 방법은 큐를 사용하는 것이다. 생산자는 큐에 데이터를 입력(enqueue)하고 소비자는
큐에서 데이터를 가져(dequeue)온다. Queue는 선행적인 자료구조로서 뒷(rear) 부분에서 입력된 데이터가
앞(front) 부분에서 출력되는 FIFO(First In First Out)로 동작한다. Queue의 FIFO에서는 첫 번째로
입력된 데이터가 첫 번째로 출력된다. Queue에 저장되는 데이터 노드들은 스택처럼 Linked list로 연결되지만 동작위치가
스택과는 다르다. 스택은 입력과 출력이 top 위치 한군데에서 발생하지만, Queue는 입력과 출력이 앞과 뒤 양쪽에서 발생한다.
Queue는 처리하고자 하는 데이터들을 일렬로 줄지어 보관하는 대기열과 같은 자료구조로서 컴퓨팅에서 많이 활용된다. 예를 들면,
버스를 타기 위해서 정거장에 줄 서있는 사람들의 대기열과 같은 구조로서 제일 먼저 줄을 선 사람이 제일 처음으로 버스에 타는
동작 방식이 Queue이다.
Queue의 동작은 enqueue와 dequeue로 구분한다. enqueue는 큐의 뒷(rear) 부분에서 데이터를 입력하는 동작이고, dequeue는 큐의 앞(front) 부분에서 데이터를 출력하는 동작이다.
Queue를 구현하기 위해서 먼저 아래와 같이 노드 구조체와 큐 구조체를 선언한다.
{
void* data;
struct node* link;
} NODE;
노 드 구조체는 스택처럼 데이터를 저장하는 포인터(*data)와 Linked list로 노드를 연결하는 포인터(*link)로 구성된다. 큐가 스택과 달라지는 부분은 아래와 같이 큐의 구조체에 앞(front)과 뒤(rear) 노드 포인터가 있다는 것이다.
typedef struct
{
NODE* front;
NODE* rear;
int count;
} QUEUE;
위의 구조체들을 C언어로 코딩하여 queue.h 헤더 파일로 저장한다.
(실습 소스) queue.h
//
// Source: queue.h written by Jung,JaeJoon at the www.kernel.bz
// Compiler: Standard C
// Copyright(C): 2010, Jung,JaeJoon (rgbi3307@nate.com )
//
//boolean 데이터타입(gcc: #include <stdbool.h>) -
typedef enum {
true = 1,
TRUE = 1,
false = 0,
FALSE = 0
} bool;
//큐구조체선언-
//단방향노드(일반적인스택, 큐, 리스트)
typedef struct node
{
void* data;
struct node* link;
} NODE;
typedef struct
{
NODE* front;
NODE* rear;
int count;
} QUEUE;
//큐함수들선언-
QUEUE* que_create (void);
QUEUE* que_destroy (QUEUE* queue);
bool que_dequeue (QUEUE* queue, void** data_out);
bool que_enqueue (QUEUE* queue, void* data_in);
bool que_front (QUEUE* queue, void** data_out);
bool que_rear (QUEUE* queue, void** data_out);
int que_count (QUEUE* queue);
bool que_is_empty (QUEUE* queue);
bool que_is_full (QUEUE* queue);
아래는 큐의 rear 포인터에 노드를 enqueue하는 과정을 그림으로 설명하는 것이다.
위의 큐의 동작들을 queue.c 파일로 코딩한다.
(실습 소스) queue.c
-
//
// Source: queue.c written by Jung,JaeJoon at the www.kernel.bz
// Compiler: Standard C
// Copyright(C): 2010, Jung,JaeJoon (rgbi3307@nate.com )
//
#include <stdlib.h>
//#include <malloc.h>
#include "queue.h"
QUEUE* que_create (void)
{
QUEUE* queue;
queue = (QUEUE*) malloc(sizeof(QUEUE));
if (queue) {
queue->front = NULL;
queue->rear = NULL;
queue->count = 0;
}
return queue;
}
QUEUE* que_destroy (QUEUE* queue)
{
NODE* node_temp;
if (queue) {
while (queue->front != NULL) {
free (queue->front->data);
node_temp = queue->front;
queue->front = queue->front->link;
free (node_temp);
} //while
free (queue);
} //if
return NULL;
}
//큐의뒤(rear)에노드를입력한다.
bool que_enqueue (QUEUE* queue, void* data_in)
{
NODE* node_new;
if (!(node_new = (NODE*) malloc (sizeof(NODE)) ) )
return false;
node_new->data = data_in;
node_new->link = NULL;
if (queue->count == 0) queue->front = node_new;
else queue->rear ->link = node_new;
(queue->count)++;
queue->rear = node_new;
return true;
}
//큐의앞(front)에서노드를가져온후제거한다.
bool que_dequeue (QUEUE* queue, void** data_out)
{
NODE* node_del;
if (!queue->count) return false;
*data_out = queue->front->data;
node_del = queue->front;
if (queue->count == 1) queue->rear = queue->front = NULL;
else queue->front = queue->front->link ;
(queue->count);
free (node_del);
return true;
}
bool que_front (QUEUE* queue, void** data_out)
{
if (!queue->count) return false;
else {
*data_out = queue->front->data ;
return true;
}
}
bool que_rear (QUEUE* queue, void** data_out)
{
if (!queue->count) return false;
else {
*data_out = queue->rear->data ;
return true;
}
}
bool que_is_empty (QUEUE* queue)
{
return (queue->count == 0);
}
bool que_is_full (QUEUE* queue)
{
NODE* node_temp;
node_temp = (NODE*) malloc (sizeof(*(queue->rear)));
if (node_temp) {
free (node_temp);
return false;
}
return true;
}
int que_count (QUEUE* queue)
{
return queue->count;
}
queue.c 파일에 코딩한 큐의 동작들(enqueue, dequeue)을 main 함수에서 테스트 해보도록 하자.
먼저, while 루프에서 정수형 데이터를 scanf() 함수를 통하여 입력 받은 후 이것을 que_enqueue() 함수를 통하여 큐에 입력한다. 숫자가 아닌 문자를 입력하면 while 루프를 빠져 나온다.
while (!done)
{
data_temp = (int*)malloc (sizeof(int));
printf("Enter a number: <!digit> to stop: ");
if (((scanf("%d", data_temp)) == 0) || que_is_full (queue))
done = true; else
que_enqueue (queue, data_temp);
}
que_enqueue() 함수를 통하여 큐에 순서대로 저장된 데이터를 que_dequeue() 함수를 통하여 출력한다. while 루프는 큐에 저장된 데이터가 모두 dequeue되고 없을 때 빠져 나온다.
-
while (!que_is_empty (queue))
{
que_dequeue (queue, &data_temp);
printf("%3dn", *data_temp);
free (data_temp);
}
-
위와 같이 큐에 데이터를 순서대로 enqueue하고 저장된 순서대로 dequeue하는 과정을 main 함수로 모두 코딩하면 아래와 같다.
(실습 소스) main.c
//
// Source: main.c written by Jung,JaeJoon at the www.kernel.bz
// Compiler: Standard C
// Copyright(C): 2010, Jung,JaeJoon (rgbi3307@nate.com )
//
#include <stdlib.h>
#include <stdio.h>
#include "queue.h"
int main (void)
{
bool done = false;
int* data_temp;
QUEUE* queue;
queue = que_create ();
while (!done)
{
data_temp = (int*)malloc (sizeof(int));
printf("Enter a number: <!digit> to stop: ");
if (((scanf("%d", data_temp)) == 0) || que_is_full (queue))
done = true;
else
que_enqueue (queue, data_temp);
}
printf("nnThe List of numbers:n");
while (!que_is_empty (queue))
{
que_dequeue (queue, &data_temp);
printf("%3dn", *data_temp);
free (data_temp);
}
que_destroy (queue);
printf("nPress any key to end...");
getchar();
return 0;
}
(실행 결과) main.c
-
Enter a number: <!digit> to stop: 10
Enter a number: <!digit> to stop: 20
Enter a number: <!digit> to stop: 30
Enter a number: <!digit> to stop: 40
Enter a number: <!digit> to stop: 50
Enter a number: <!digit> to stop: q
The List of numbers:
10
20
30
40
50
Press any key to end...
지금까지 큐의 데이터 포인터에 정수형의 데이터를 메모리 할당하여 정수를 enqueue 및 dequeue하는 코드를 작성했지만, 큐의 데이터 포인터에는 다양한 종류의 데이터 타입을 메모리 할당하여 연결할 수 있다.
int* data_temp;
data_temp = (int*)malloc (sizeof(int));
위의 형태뿐만 아니라, 아래와 같이 구조체를 데이터 포인터에 할당할 수 있다.
//개인주소록 구조체
typedef struct
{
int pno; //개인번호
char name [30]; //성명
char phone [20]; //전화번호
} PERSON;
PERSON* person_data;
person_data = (PERSON*)malloc (sizeof(PERSON));
개인주소록(개인번호, 성명, 전화번호) 구조체를 메모리 할당하여 큐의 데이터 포인터에 enqueue하여 입력하고 dequeue로 출력하는 예제 프로그램을 작성하면 아래와 같다.
(실습 소스) main.c
//
// Source: main.c written by Jung,JaeJoon at the www.kernel.bz
// Compiler: Standard C
// Copyright(C): 2010, Jung,JaeJoon (rgbi3307@nate.com )
//
#include <stdlib.h>
#include <stdio.h>
#include "queue.h"
//개인주소록구조체
typedef struct
{
int pno; //개인번호
char name [30]; //성명
char phone [20]; //전화번호
} PERSON;
int main (void)
{
bool done = false;
PERSON* person_data;
QUEUE* queue;
queue = que_create ();
while (!done)
{
if (que_is_full (queue)) break;
person_data = (PERSON*)malloc (sizeof(PERSON));
printf("Enter a person number: ");
if (scanf("%d", &(person_data->pno)) == 0) break;
printf("Enter a person name: ");
if (scanf("%s", person_data->name) == 0) break;
printf("Enter a person phone: ");
if (scanf("%s", person_data->phone) == 0) break;
que_enqueue (queue, person_data);
printf("n");
}
printf("nnThe List of persons:n");
while (!que_is_empty (queue))
{
que_dequeue (queue, (void*)&person_data);
printf("%d, %s, %sn", person_data->pno, person_data->name, person_data->phone);
free (person_data);
}
que_destroy (queue);
printf("nPress any key to end...");
getchar();
return 0;
}
(실행 결과) main.c
-
Enter a person number: 1
Enter a person name: Kim
Enter a person phone: 010-123-1234
Enter a person number: 2
Enter a person name: Lee
Enter a person phone: 010-255-1357
Enter a person number: 3
Enter a person name: Jung
Enter a person phone: 010-255-3737
Enter a person number: q
The List of persons:
1, Kim, 010-123-1234
2, Lee, 010-255-1357
3, Jung, 010-255-3737
Press any key to end...
위와 같은 응용은 실제 프로그래밍에서 많이 활용되는 것이므로 잘 익혀 두도록 하자. 큐의 노드에 있는 데이터와 개인 주소록 구조체 PERSON과의 연결관계를 그림으로 나타내면 다음과 같다.
Queue 는 FIFO(First In First Out) 방식으로 동작하는 선형적인 자료구조로서 데이터가 입력되는 순서대로 대기열에 입력(enqueue)해 두었다가, 입력한 순서대로 처리(dequeue)하는 방식이다. Queue는 스택과 마찬가지로 노드를 Linked List 형태로 연결하지만 enqueue와 dequeue가 Queue의 양쪽 끝(rear, front)에서 발생한다는 점이 스택과 다르다. Queue는 실제 컴퓨팅에서 많이 활용되는 자료구조이므로 활용법을 잘 이해해 두도록 하자.
필 / 자 / 소 / 개
※ 본 내용은 (주)테크월드(http://www.embeddedworld.co.kr)의 저작권 동의에 의해 공유되고 있습니다.
Copyright ⓒ Techworld, Inc. 무단전재 및 재배포 금지
| 번호 | 제목 | 작성 | 조회수 |
|---|---|---|---|
| 394 | [C언어와 알고리즘] 진보된 알고리즘 소개- 인공지능 ② (15) | 2012-08-17 | 2005 |
| 393 | [C언어와 알고리즘] 진보된 알고리즘 소개- 인공지능 ① (14) | 2012-08-17 | 2251 |
| 392 | [C언어와 알고리즘] 해싱(Hash) 실습 (13) | 2012-08-17 | 2864 |
| 391 | [C언어와 알고리즘] 트리(Tree) 실습 (12) | 2012-08-17 | 3915 |
| 390 | [C언어와 알고리즘] 리스트(List) 실습 (11) | 2012-08-17 | 5524 |
| 389 | [C언어와 알고리즘] 큐(Queue) 실습 (10) | 2012-08-17 | 4774 |
| 388 | [C언어와 알고리즘] 스택(Stack) 실습 (9) | 2012-08-17 | 3980 |
| 387 | [C언어와 알고리즘] 소팅을 통한 알고리즘 분석 (8) | 2012-08-17 | 2416 |
| 386 | [C언어와 알고리즘] 알고리즘 소개 (7) | 2012-08-17 | 2058 |
| 385 | [C언어와 알고리즘] 구조체 (6) | 2012-08-17 | 3906 |
0개 댓글