1. 배열을 이용한 큐 구현


단순히 스택과 같이 큐를 배열을 이요하여 구현하면 아래와 같다.

문제점은 큐의 크기를 한번 다 사용하고 나면 큐는 실제로는 비어있지만 더이상 데이터를 삽입할 수가없다.

그렇기 때문에 배열을 이요할 때에는 원형 큐를 구현하게된다.




init: 큐 초기화

isEmpty: 큐가 비어있으면 1반환, 데이터가 있으면 0 반환

isFull: 큐가 가득 차있으면 1반환, 빈공간이 있으면 0반환

enqueue: 큐에 데이터 삽입

dequeue: 큐에서 데이터 추출


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
#include <stdio.h>
 
#define MAX_SIZE 10
 
typedef struct _queue {
    int data[MAX_SIZE];
    int front;
    int rear;
}queue;
 
void init(queue* q)
{
    q->front = 0;
    q->rear = 0;
}
int isEmpty(queue* q)
{
    if (q->front == q->rear)
        return 1;
    else
        return 0;
}
int isFull(queue* q)
{
    if (q->rear == MAX_SIZE)
        return 1;
    else
        return 0;
}
void enqueue(queue* q, int data)
{
    if (isFull(q))
    {
        printf("queue is full\n");
        return;
    }
 
    q->data[q->rear] = data;
    q->rear++;
}
int dequeue(queue* q)
{
    if (isEmpty(q))
    {
        printf("queue is empty\n");
        return -1;
    }
    
    return q->data[q->front++];
}
int seek(queue* q)
{
    if (isEmpty(q))
    {
        printf("queue is empty\n");
        return -1;
    }
    return q->data[q->front];
}
int main(void)
{
    queue q;
    init(&q);
    for (int i = 1; i <= 11; i++)
    {
        enqueue(&q, i * 10);
        printf("queue front : %d\n", seek(&q));
    }
    while (!isEmpty(&q))
        printf("dequeue data : %d \n", dequeue(&q));
    printf("queue front : %d\n", seek(&q));
    return 0;
}
 
cs


2. 배열을 이용한 원형 큐 구현


원형 큐의 경우, 배열을 지속적으로 사용할 수 있는 장점이 있다.

배열이 비어있는상태, 꽉차있는 상태를 구분하기 위해, 배열의 크기 - 1 만큼을 큐에서 사용한다.

front==rear인 경우 큐가 비어있는 상태이며, front-1 = rear인 경우 큐가 가득차 있는 상태이다.


isNext: 다음 인덱스를 가져오는 함수이다.


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
#include <stdio.h>
 
#define MAX_SIZE 10
 
typedef struct _queue {
    int data[MAX_SIZE];
    int front;
    int rear;
}queue;
 
void init(queue* q)
{
    q->front = 0;
    q->rear = 0;
}
int isEmpty(queue* q)
{
    if (q->front == q->rear)
        return 1;
    else
        return 0;
}
int isNext(int pos)
{
    if ( pos == MAX_SIZE-1)//마지막 인덱스면 첫번째로 돌아간다.
        return 0;
    else
        return pos + 1;
}
void enqueue(queue* q, int data)
{
    if (isNext(q->rear)==q->front)
    {
        printf("queue is full\n");
        return;
    }
    q->rear = isNext(q->rear);
    q->data[q->rear] = data;
}
int dequeue(queue* q)
{
    if (isEmpty(q))
    {
        printf("queue is empty\n");
        return -1;
    }
    q->front = isNext(q->front);
    return q->data[q->front];
}
int seek(queue* q)
{
    if (isEmpty(q))
    {
        printf("queue is empty\n");
        return -1;
    }
    return q->data[isNext(q->front)];
}
int main(void)
{
    queue q;
    init(&q);
    for (int i = 1; i <= 11; i++)
    {
        enqueue(&q, i * 10);
        printf("queue front : %d\n", seek(&q));
    }
    while (!isEmpty(&q))
        printf("dequeue data : %d \n", dequeue(&q));
    printf("queue front : %d\n", seek(&q));
    return 0;
}
 
cs


위 코드를 실행하면 아래와 같은 값이 나온다.

큐의 크기는 10이지만, 실제로 사용하는 영역은 9칸 이기 때문에, 11개의 데이터를 삽입하려고 시도하면 2번의 에러가 발생한다.




3. 리스트를 이용한 큐 구현


리스트를 사용할 경우, 데이터 삽입을 위해 리스트의 가장 마지막을 노드를 가르키는 포인터(여기서는 Tail)이 필요하다.

큐에서 데이터 삽입시 Tail 위치에 삽입하며, 삭제시 Head가 가르키는 노드를 삭제한다.




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
#include <stdio.h>
#include <stdlib.h>
 
typedef struct _node {
    int data;
    struct _node* next;
}node;
 
typedef struct _queue {
    node* head;
    node* tail;
}queue;
 
void init(queue* q)
{
    q->head = NULL;
    q->tail = NULL;
}
 
int isEmpty(queue* q)
{
    if (q->head == NULL)
        return 1;
    else
        return 0;
}
 
void enqueue(queue* q, int data)
{
    node* newnode = (node*)malloc(sizeof(node));
 
    newnode->data = data;
    newnode->next = NULL;
    
    if (isEmpty(q))
    {
        q->head = newnode;
        q->tail = newnode;
    }
    else
    {
        q->tail->next = newnode;
        q->tail = newnode;
    }
}
 
int dequeue(queue* q)
{
    if (isEmpty(q))
    {
        printf("queue is empty\n");
        return -1;
    }
 
    int ret = q->head->data;
    node* temp = q->head;
 
    q->head = temp->next;
    free(temp);
 
    return ret;
}
 
int seek(queue* q)
{
    if (isEmpty(q))
    {
        printf("queue is empty\n");
        return -1;
    }
    return q->head->data;
}
 
int main(void)
{
    queue q;
    init(&q);
 
    for (int i = 1; i <= 11; i++)
    {
        enqueue(&q, i * 10);
        printf("queue front : %d\n", seek(&q));
    }
 
    while(!isEmpty(&q))
        printf("dequeue data : %d \n", dequeue(&q));
 
    printf("queue front : %d\n", seek(&q));
 
    return 0;
}
 
 
cs


'컴퓨터공학 > 자료구조' 카테고리의 다른 글

스택(stack)  (0) 2018.08.09
1.2 포인터와 동적 메모리 할당  (0) 2015.07.19
1.1 시스템 생명 주기(System Life Cycle)  (0) 2015.07.19
C로 쓴 자료구조론  (0) 2015.07.19

1. 배열을 이용한 스택 구현


정해진 크기의 배열에서, 배열의 크기에 여유가 있으면 데이터를 하나씩 추가한다.



init: 스택을 초기화 하는 함수. top을 가르키는 변수를 -1로 초기화 한다.

isEmpty: 스택이 비어있는지 체크하는 함수. 비어있으면 1, 비어있지 않으면 0을 반환한다.

push: 스택에 데이터를 삽입하는 함수. 스택이 가득차 있으면 더이상 추가하지 않는다.

pop: 스택에서 데이터를 추출하는 함수. 스택의 top에 에있는 데이터를 반환한다. 스택이 비어있으면 꺼내지 않는다.

seek: 스택의 top에 저장된 데이터를 반환하는 함수. 없어도 되지만 책에 있어서 추가해봤다.


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
#include <stdio.h>
 
#define MAX_SIZE 10
 
typedef struct _stack {
    int data[MAX_SIZE];
    int top;
}stack;
 
void init(stack* st)
{
    st->top = -1;
}
 
int isEmpty(stack* st)
{
    if (st->top == -1)
        return 1;
    else
        return 0;
}
 
void push(stack* st, int data)
{
    if (st->top == MAX_SIZE-1)
    {
        printf("stack is full\n");
        return;
    }
 
    st->data[++st->top] = data;
}
 
int pop(stack* st)
{
    if (isEmpty(st))
    {
        printf("stack is empty\n");
        return -1;
    }
    return st->data[st->top--];
}
 
int seek(stack* st)
{
    if (isEmpty(st))
    {
        printf("stack is empty\n");
        return -1;
    }
    return st->data[st->top];
}
 
int main(void)
{
    stack st;
    init(&st);
 
    for (int i = 1; i <= 11; i++)
    {
        push(&st, i * 10);
        printf("stack top : %d\n", seek(&st));
    }
 
    while(!isEmpty(&st))
        printf("pop data : %d \n", pop(&st));
 
    printf("stack top : %d\n", seek(&st));
 
    return 0;
}
 
 
cs

예전에 TOP을 초기화할 땐 -1로 했던 것 같은데 요즘엔 0이 대세인 것 같기도하다.
하지만 큰 차이없으니 개인의 취향대로 구현하면 될 것이다.

2. 리스트를 이용한 스택 구현

리스트를 이용할 경우, 배열과 다른점은 top이라는 변수가 따로 없는 것이다. Head가 top과 유사한 역할을 수행한다.
또, 리스트는 제한된 크기가 없기때문에, 메모리가 허용하는 만큼의 데이터를 삽입할 수 있다.
데이터 삽입시 새로운 노드를 생성하고, 새로운 노드에 데이터 할당, NEXT는 HEAD가 가르키고 있던 노드를 할당한다.
그다음 HEAD는 새로운 노드를 가르키게 하면된다.




함수는 배열을 이용한 스택과 같다.


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
#include <stdio.h>
#include <stdlib.h>
 
typedef struct _node {
    int data;
    struct _node* next;
}node;
 
typedef struct _stack {
    node* head;
}stack;
 
void init(stack* st)
{
    st->head = NULL;
}
 
int isEmpty(stack* st)
{
    if (st->head == NULL)
        return 1;
    else
        return 0;
}
 
void push(stack* st, int data)
{
    node* newnode = (node*)malloc(sizeof(node));
    newnode->data = data;
    newnode->next = st->head;
    
    st->head = newnode;
}
 
int pop(stack* st)
{
    if (isEmpty(st))
    {
        printf("stack is empty\n");
        return -1;
    }
 
    int ret = st->head->data;
    node* temp = st->head;
 
    st->head = temp->next;
    free(temp);
 
    return ret;
}
 
int seek(stack* st)
{
    if (isEmpty(st))
    {
        printf("stack is empty\n");
        return -1;
    }
    return st->head->data;
}
 
int main(void)
{
    stack st;
    init(&st);
 
    for (int i = 1; i <= 11; i++)
    {
        push(&st, i * 10);
        printf("stack top : %d\n", seek(&st));
    }
 
    while(!isEmpty(&st))
        printf("pop data : %d \n", pop(&st));
 
    printf("stack top : %d\n", seek(&st));
 
    return 0;
}
 
 
cs


'컴퓨터공학 > 자료구조' 카테고리의 다른 글

큐(queue)  (0) 2018.08.09
1.2 포인터와 동적 메모리 할당  (0) 2015.07.19
1.1 시스템 생명 주기(System Life Cycle)  (0) 2015.07.19
C로 쓴 자료구조론  (0) 2015.07.19

1.2 포인터와 동적 메모리 할당


C언어 에서는 어떤 타입 T에 대해서 T의 포인터 타입이 존재한다. 포인터 타입의 실제 값은 메모리의 주소가 된다.


● & : 주소 연산자

● * : 역참조 연산자


ex)

'컴퓨터공학 > 자료구조' 카테고리의 다른 글

큐(queue)  (0) 2018.08.09
스택(stack)  (0) 2018.08.09
1.1 시스템 생명 주기(System Life Cycle)  (0) 2015.07.19
C로 쓴 자료구조론  (0) 2015.07.19

1.1 시스템 생명 주기(System Life Cycle)


(1) 요구사항(requirement) : 모든 경우에 대한 입력과 출력의 기술은 정밀하게 작성되어야 함

(2) 분석(analysis) : 문제들을 실제 다룰 수 있을 정도의 작은 단위로 나눔

 가) 상향식(bottom-up) 

 나) 하향식(top-down) 

(3) 설계(design) : 프로그램이 필요로 하는 자료 객체들과 이들 위에서 수행될 연산들의 관점에서 시스템에 접근

(4) 정제(refinement) and 코딩(coding) : 자료 객체에 대한 표현을 선택하고 그들 위에 수행되는 연산에 대한 알고리즘을 작성

(5) 검증(verification) : 프로그램의 정확성 증명, 다양한 입력 데이터를 이용한 프로그램의 테스트, 오류 제거로 구성

 가) 정확성 증명(correctness proof) : 수학에서 사용하는 기법들을 이용해서 프로그램들의 정확성을 증명 가능

 나) 테스팅(testing) : 테스트 데이터와 실제로 수행 가능한 코드를 필요로 함

 다) 오류 제거(error removal) : 이전 단계가 적절히 수행되고 나면 정확성 증명과 시스템 테스트 오류가 발생한 코드를 알려줌

'컴퓨터공학 > 자료구조' 카테고리의 다른 글

큐(queue)  (0) 2018.08.09
스택(stack)  (0) 2018.08.09
1.2 포인터와 동적 메모리 할당  (0) 2015.07.19
C로 쓴 자료구조론  (0) 2015.07.19

이 카테고리는

C로 쓴 자료구조론 책을 바탕으로 공부하고 작성한 자료구조 카테고리 입니다.

제목 : C로 쓴 자료구조론(Fundamentals of Data Structures in C)

옮긴이 : 이석호

저자 : HOROWITZ, SAHNI, ANDERSON-FREED

출판사 : 교보문고(SILICON PRESS) 

'컴퓨터공학 > 자료구조' 카테고리의 다른 글

큐(queue)  (0) 2018.08.09
스택(stack)  (0) 2018.08.09
1.2 포인터와 동적 메모리 할당  (0) 2015.07.19
1.1 시스템 생명 주기(System Life Cycle)  (0) 2015.07.19

+ Recent posts

티스토리툴바