[알고리즘] Do it 자료구조와 알고리즘 4장 정리

연습문제_Q1 > IntStack.c에서 제공하는 함수를 모두 사용하여 프로그램을 만드세요.

 

[ IntStack.h ] 

//
//  Intstack.h
//  helloC
//
//  Created by Hevton on 2020/10/14.
//

/* int형 스택 IntStack 헤더 */
#ifndef Intstack_h
#define Intstack_h

typedef struct {
    int max; // 스택의 최대 용량
    int ptr; // 스택에 쌓여있는 데이터의 개수를 나타내는 스택 포인터. 포인터 변수를 의미하지 않으며, '스택의 인덱스를 가리킨다'라는 의미로 그렇게 부름
    int *stk; // 스택으로 사용할 배열을 가리키는 포인터
} IntStack;

// 스택 초기화
int Initialize(IntStack *s, int max);

// 스택에 데이터를 푸시
int Push(IntStack *s, int x);

// 스택에서 데이터를 팝
int Pop(IntStack *s, int *x);

// 스택에서 데이터를 피크(top에 위치하는 요소 확인)
int Peek(const IntStack *s, int *x);

// 스택 비우기
void Clear(IntStack *s);

// 스택의 최대 용량
int Capacity(const IntStack *s);

// 스택의 데이터 개수
int Size(const IntStack *s);

// 스택이 비어있나요?
int IsEmpty(const IntStack *s);

// 스택이 가득 찼나요?
int IsFull(const IntStack *s);

// 스택에서 검색
int Search(const IntStack *s, int x);

// 모든 데이터를 출력
void Print(const IntStack *s);

// 스택 종료
void Terminate(IntStack *s);


#endif /* Intstack_h */

 

[ IntStack.c ]

//
//  IntStack.c
//  helloC
//
//  Created by Hevton on 2020/10/14.
//
#include <stdio.h>
#include <stdlib.h>
#include "IntStack.h"

// 스택 초기화
int Initialize(IntStack *s, int max)
{
    s->ptr = 0;
    if((s->stk = calloc(max, sizeof(int))) == NULL) {
        s->max = 0; // 배열의 생성에 실패
        return -1;
    }
    
    s->max = max;
    return 0;
}

// 스택에 데이터를 푸시
// 스택이 가득 차서 푸시할 수 없는 경우 -1 반환, 스택에 푸시 성공하면 0을 반환
int Push(IntStack *s, int x)
{
    // == 연산자를 사용해도 되나, 프로그램의 오류나 사용자의 의도적인 잘못된 값 입력 등의 이유로 ptr 값이 잘못 입력되어 max값을 초과하는 경우가 생길 우려를 으레 막아놓음으로써, 프로그램의 안정성을 높일 수 있다.
    if(s->ptr >= s->max) // 스택이 가득 참
        return -1;
    
    s->stk[s->ptr++] = x;
    return 0;
}

// 스택에서 데이터를 팝
// 스택이 비어 있어 팝 할수 없는 경우 -1 반환, 팝에 성공할 경우 0을 반환
int Pop(IntStack *s, int *x)
{
    if(s->ptr <=0) // 스택이 비어 있음
        return -1;
    
    *x = s->stk[--s->ptr];
    return 0;
}

// 스택에서 데이터를 피크(top에 위치하고 있는 데이터를 열람)
// 스택이 비어 있으면 -1 반환, 피크에 성공하면 0을 반환
int Peek(const IntStack *s, int *x)
{
    if(s->ptr<=0) // 스택이 비어있음
        return -1;
    
    *x = s->stk[s->ptr-1];
    return 0;
}

// 스택 비우기
// 배열 요소들을 변경할 필요 없음. ptr을 0으로.
void Clear(IntStack *s)
{
    s->ptr = 0;
}

// 스택 용량
// max의 값 반환
int Capacity(const IntStack *s)
{
    return s->max;
}

// 스택에 쌓여 있는 데이터의 수
// ptr의 값 반환
int Size(const IntStack *s)
{
    return s->ptr;
}

// 스택이 비어 있는가?
// 스택이 비어 있으면 1, 그렇지 않으면 0 반환
int IsEmpty(const IntStack *s)
{
    return s->ptr <= 0;
}

// 스택이 가득 찼는가?
// 스택이 가득 찼으면 1, 그렇지 않으면 0 반환
int IsFull(const IntStack *s)
{
    return s->ptr >= s->max;
}

// 스택에서 검색
// 검색에 성공하면 찾은 요소의 인덱스를 반환, 실패하면 -1을 반환
int Search(const IntStack *s, int x)
{
    int i;
    for(i = s->ptr-1; i>=0; i--) { // top -> bottom 방향으로 선형 검색
        if(s->stk[i] == x)
            return i; // 검색 성공
    }
    return -1; // 검색 실패
}

// 모든 데이터를 출력
void Print(const IntStack *s)
{
    int i;
    for(i = 0; i < s->ptr; i++) // bottom -> top 방향으로 출력
        printf("%d ", s->stk[i]);

    putchar('\n');
}

// 스택 종료
void Terminate(IntStack *s)
{
    if(s->stk!=NULL)
        free(s->stk); // 배열을 삭제
    
    s->max = s->ptr = 0;
}

[ main.c ]

 #include <stdio.h>
 #include "IntStack.h"

 int main() {
     IntStack s;
     
     if(Initialize(&s, 64) == -1) {
         puts("스택 생성에 실패했습니다.");
         return 1;
     }
     
     while(1) {
         int menu, x;
         printf("현재 데이터 수 : %d / %d\n", Size(&s), Capacity(&s));
         printf("(1)푸시 (2)팝 (3)피크 (4)클리어 (5)최대 용량 (6)데이터 개수 (7)스택이 비어있는지 (8)스택이 가득 찼는지 (9)검색 (10)출력 (0)종료 : ");
         scanf("%d", &menu);
         
         if(menu == 0) break;
         switch(menu) {
             case 1: // 푸시
                 printf("데이터 : ");
                 scanf("%d", &x);
                 
                 if(Push(&s, x) == -1)
                     puts("\a오류 : 푸시에 실패했습니다.");
                 break;
                 
             case 2: // 팝
                 if(Pop(&s, &x) == -1)
                     puts("\a오류 : 팝에 실패했습니다.");
                 else
                     printf("팝 데이터는 %d입니다.\n", x);
                 break;
                 
             case 3: // 피크
                 if(Peek(&s, &x) == -1)
                     puts("\a오류 : 피크에 실패했습니다.");
                 else
                     printf("피크 데이터는 %d입니다\n", x);
                 break;
                 
             case 4: // 클리어
                 Clear(&s);
                 break;
                 
             case 5: // 최대 용량
                 printf("스택의 최대 용량은 %d입니다.\n", Capacity(&s));
                 break;
                 
             case 6: // 데이터 개수
                 printf("현재 스택의 데이터 개수는 %d개 입니다.\n", Size(&s));
                 break;
                 
             case 7: // 스택이 비어있는지
                 if(IsEmpty(&s))
                     puts("스택이 비어있습니다.");
                 else
                     puts("스택이 비어있지 않습니다.");
                 break;
                 
             case 8: // 스택이 가득 찼는지
                 if(IsFull(&s))
                     puts("스택이 가득 차 있습니다.");
                 else
                     puts("스택이 가득 차 있지 않습니다.");
                 break;
                 
             case 9: // 검색
                 printf("검색할 데이터 : ");
                 scanf("%d", &x);
                 int data = Search(&s, x);
                 if(data!= -1)
                     printf("검색한 데이터는 s[%d]에 있습니다.\n", data);
                 else
                     puts("데이터가 존재하지 않습니다.");
                 break;
                 
             case 10: // 출력
                 Print(&s);
                 break;
         }
     }
     Terminate(&s);
     return 0;
 }

 

연습문제_Q2 > 다중 스택을 구현하세요.

 

[ IntDoubleStack.h ]

//
//  IntDoubleStack.h
//  helloC
//
//  Created by Hevton on 2020/10/14.
//

/* int형 스택 Int_DounbleStack 헤더 */
#ifndef Int_DoubleStack_h
#define Int_DoubleStack_h

enum { stackA, stackB }; //열거형으로 상수 키 정의(값은 할당하지 않은 상태)

typedef struct {
    int max; // 스택의 최대 용량
    int ptrA; // 스택 포인터A.
    int ptrB; // 스택 포인터B. 기본적으로 스택 포인터는 스택에 쌓여 있는 데이터의 개수를 나타낸다고 할 수 있는데, 이렇게 하나의 배열 안에서 두 개의 스택을 이용하는 경우, 데이터의 개수를 나타낸다고 생각하기 보단 다음 데이터를 삽입할 인덱스를 기억하는 용도라고 생각.
    int *stk; // 스택으로 사용할 배열을 가리키는 포인터
} IntDoubleStack;

// 스택 초기화
int Initialize(IntDoubleStack *s, int max);

// 스택에 데이터를 푸시
int Push(IntDoubleStack *s, int sw, int x);

// 스택에서 데이터를 팝
int Pop(IntDoubleStack *s, int sw, int *x);

// 스택에서 데이터를 피크(top에 위치하는 요소 확인)
int Peek(const IntDoubleStack *s, int sw, int *x);

// 스택 비우기
void Clear(IntDoubleStack *s, int sw);

// 스택의 최대 용량
int Capacity(const IntDoubleStack *s);

// 스택의 데이터 개수
int Size(const IntDoubleStack *s, int sw);

// 스택이 비어있나요?
int IsEmpty(const IntDoubleStack *s, int sw);

// 스택이 가득 찼나요?
int IsFull(const IntDoubleStack *s);

// 스택에서 검색
int Search(const IntDoubleStack *s, int sw, int x);

// 모든 데이터를 출력
void Print(const IntDoubleStack *s, int sw);

// 스택 종료
void Terminate(IntDoubleStack *s);


#endif /* IntDoubleStack_h */

 

[ IntDoubleStack.c ]

//
//  IntDoubleStack.c
//  helloC
//
//  Created by Hevton on 2020/10/14.
//
#include <stdio.h>
#include <stdlib.h>
#include "IntDoubleStack.h"

// 스택 초기화
int Initialize(IntDoubleStack *s, int max)
{
    s->ptrA = 0;
    if((s->stk = calloc(max, sizeof(int))) == NULL) {
        s->max = 0; // 배열의 생성에 실패
        s->ptrB = 0;
        return -1;
    }
    
    s->ptrB = max - 1;
    s->max = max;
    return 0;
}

// 스택에 데이터를 푸시
// 스택이 가득 차서 푸시할 수 없는 경우 -1 반환, 스택에 푸시 성공하면 0을 반환
int Push(IntDoubleStack *s, int sw, int x)
{
    if(s->ptrA >= s->ptrB+1) // 스택이 가득 참
        return -1;
    
    switch(sw) {
        case stackA:
            s->stk[s->ptrA++] = x;
            break;
            
        case stackB:
            s->stk[s->ptrB--] = x;
            break;
    }
    return 0;
}

// 스택에서 데이터를 팝
// 스택이 비어 있어 팝 할수 없는 경우 -1 반환, 팝에 성공할 경우 0을 반환
int Pop(IntDoubleStack *s, int sw, int *x)
{
    
    switch(sw) {
        case stackA:
            if(s->ptrA <= 0)
                return -1;
            *x = s->stk[--s->ptrA];
            break;
            
        case stackB:
            if(s->ptrB >= s->max -1)
                return -1;
            *x = s->stk[++s->ptrB];
            break;
    }

    return 0;
}

// 스택에서 데이터를 피크(top에 위치하고 있는 데이터를 열람)
// 스택이 비어 있으면 -1 반환, 피크에 성공하면 0을 반환
int Peek(const IntDoubleStack *s, int sw, int *x)
{
    switch(sw) {
        case stackA:
            if(s->ptrA <= 0)
                return -1;
            *x = s->stk[s->ptrA - 1];
            break;
            
        case stackB:
            if(s->ptrB >= s->max -1)
                return -1;
            *x = s->stk[s->ptrB + 1];
            break;
    }

    
    return 0;
}

// 스택 비우기
// 배열 요소들을 변경할 필요 없음. ptr을 0으로.
void Clear(IntDoubleStack *s, int sw)
{
    switch(sw) {
        case stackA:
            s->ptrA = 0;
            break;
            
        case stackB:
            s->ptrB = s->max-1;
            break;
    }
}

// 스택 용량
// max의 값 반환. IntDoubleStack이여도 그대로.
int Capacity(const IntDoubleStack *s)
{
    return s->max;
}

// 스택에 쌓여 있는 데이터의 수
// stackB의 경우 ptrB를 이용한 간단한 연산 필요 (ptrA와는 다르게 ptrB는 데이터의 수를 의미하진 못하므로)
// 이럴 때를 대비하여, 스택포인터가 스택에 쌓여 있는 데이터의 개수를 나타낸다기보다, 다음 데이터를 삽입할 인덱스를 기억한다고 생각하면 좋음.
int Size(const IntDoubleStack *s, int sw)
{
    return (sw==stackA) ? s->ptrA : s->max - s->ptrB - 1;
}

// 스택이 비어 있는가?
// 스택이 비어 있으면 1, 그렇지 않으면 0 반환
int IsEmpty(const IntDoubleStack *s, int sw)
{
    return (sw==stackA) ? (s->ptrA<=0) : (s->ptrB >= s->max -1);
}

// 스택이 가득 찼는가?
// 스택이 가득 찼으면 1, 그렇지 않으면 0 반환
int IsFull(const IntDoubleStack *s)
{
    return s->ptrA >= s->ptrB +1;
}

// 스택에서 검색
// 검색에 성공하면 찾은 요소의 인덱스를 반환, 실패하면 -1을 반환
int Search(const IntDoubleStack *s, int sw, int x)
{
    int i;
    
    switch(sw) {
        case stackA:
            for(i = s->ptrA - 1; i >=0; i--) {
                if(s->stk[i] == x)
                    return i;
            }
            break;
            
        case stackB:
            for(i = s->ptrB + 1; i<s->max; i++) {
                if(s->stk[i] == x)
                    return i;
            }
            break;
    }

    return -1; // 검색 실패
}

// 모든 데이터를 출력
void Print(const IntDoubleStack *s, int sw)
{
    int i;
    switch(sw)
    {
        case stackA:
            for(i = 0; i < s->ptrA; i++) // bottom -> top 방향으로 출력
                printf("%d ", s->stk[i]);
            break;
            
        case stackB:
            for(i = s->max - 1; i > s->ptrB ; i--) // bottom -> top 방향으로 출력
                printf("%d ", s->stk[i]);
            break;
    }
    putchar('\n');
}

// 스택 종료
void Terminate(IntDoubleStack *s)
{
    if(s->stk!=NULL)
        free(s->stk); // 배열을 삭제
    
    s->max = s->ptrA = s->ptrB = 0;
}

[ main.c ]

#include <stdio.h>
#include "IntDoubleStack.h"

int main() {
    IntDoubleStack s;
    
    if(Initialize(&s, 12) == -1) {
        puts("스택 생성 실패");
        return 1;
    }
    
    while(1) {
        int menu, x;
        int idx;
        
        printf("현재 데이터 개수 : A : %d B : %d / %d\n", Size(&s, stackA), Size(&s, stackB), Capacity(&s));
        printf("1) A에 Push 2) A에서 Pop 3) A에서 Peek 4) A를 출력 5) A에서 검색 6) A를 초기화\n"
                        "7) B에 Push 8) B에서 Pop 9) B에서 Peek 10) B를 출력 11) B에서 검색 12) B를 초기화\n""13) 빈 상태 / 가득 찬 상태 0) 종료 : ");
        
        scanf("%d", &menu);
        
        if(menu == 0) break;
        
        switch(menu) {
            case 1: // A에 푸시
                printf("데이터 : ");
                scanf("%d", &x);
                if(Push(&s, stackA, x) == -1)
                    puts("\a오류 : 푸시 실패");
                break;
                
            case 2: // A에서 팝
                if(Pop(&s, stackA, &x) == -1)
                    puts("\a오류 : 팝 실패");
                else
                    printf("팝한 데이터는 %d입니다.\n", x);
                break;
                
            case 3: // A에서 피크
                if(Peek(&s, stackA, &x) == -1)
                    puts("\a오류 : 피크 실패");
                else
                    printf("피크한 데이터는 %d입니다.\n", x);
                break;
                
            case 4: // A 출력
                Print(&s, stackA);
                break;
                
            case 5: // A에서 검색
                printf("검색 데이터 : ");
                scanf("%d", &x);
                if((idx = Search(&s, stackA, x) == -1))
                    puts("\a오류 : 검색 실패");
                else
                    printf("데이터는 인덱스 %d에 있습니다.\n", idx);
                break;
                
            case 6: // A 초기화
                Clear(&s, stackA);
                break;
                
            case 7: // B에 푸시
                printf("데이터 : ");
                scanf("%d", &x);
                if(Push(&s, stackB, x) == -1)
                    puts("\a오류 : 푸시 실패");
                break;
                
            case 8: // B에서 팝
                if(Pop(&s, stackB, &x) == -1)
                    puts("\a오류 : 팝 실패");
                else
                    printf("팝한 데이터는 %d입니다.\n", x);
                break;
                
            case 9: // B에서 피크
                if(Peek(&s, stackB, &x) == -1)
                    puts("\a오류 : 피크 실패");
                else
                    printf("피크한 데이터는 %d입니다.\n", x);
                break;
                
            case 10: // B 출력
                Print(&s, stackB);
                break;
                
            case 11: // B에서 검색
                printf("검색 데이터 : ");
                scanf("%d", &x);
                if((idx = Search(&s, stackB, x) == -1))
                    puts("\a오류 : 검색 실패");
                else
                    printf("데이터는 인덱스 %d에 있습니다.\n", idx);
                break;
                
            case 12: // B 초기화
                Clear(&s, stackB);
                break;
               
            case 13: // 빈 상태 / 가득 찬 상태 판단
                printf("스택 A는 비어 %s.\n", IsEmpty(&s, stackA)? "있습니다" : "있지 않습니다");
                printf("스택 B는 비어 %s.\n", IsEmpty(&s, stackB)? "있습니다" : "있지 않습니다");
                printf("스택은 가득 %s.\n", IsFull(&s)? "찼습니다" : "차지 않았습니다");
                break;
        }

    }
    Terminate(&s);
    
    return 0;
}

 

연습문제_Q3 > 배열을 기반으로 간단하게 큐를 구성해보세요.

typedef struct { int max; int num; int *que; }ArrayIntQueue;

 

[ IntQueue.h ] 

//
//  IntQueue.h
//  helloC
//
//  Created by Hevton on 2020/10/14.
//

#ifndef IntQueue_h
#define IntQueue_h

typedef struct {
    int max; //  큐의 용량
    int num; // 현재 데이터 수, 큐 포인터. 스택포인터 같은 개념.
    int *que; // 큐의 첫 요소에 대한 포인터
} ArrayIntQueue;

int Initialize(ArrayIntQueue *q, int max);

int enqueue(ArrayIntQueue *q, int x);

int dequeue(ArrayIntQueue *q, int *x);

int Capacity(ArrayIntQueue *q);

int Size(ArrayIntQueue *q);

void Print(ArrayIntQueue *q);

int IsFull(ArrayIntQueue *q);

int IsEmpty(ArrayIntQueue *q);

int Search(const ArrayIntQueue *q, int x);

void Terminate(ArrayIntQueue *q);

#endif /* IntQueue_h */

 

[ IntQueue.c ] 

//
//  IntQueue.c
//  helloC
//
//  Created by Hevton on 2020/10/14.
//

#include <stdio.h>
#include <stdlib.h>
#include "IntQueue.h"

int Initialize(ArrayIntQueue *q, int max) {
    q->num = 0;
    if((q->que = calloc(max, sizeof(int))) == NULL ) {
        q->max = 0;
        return -1;
    }
    
    q-> max = max;
    return 0;
}


int enqueue(ArrayIntQueue *q, int x) {
    if(q->num >= q->max)
        return -1;
    
    q->que[q->num++] = x;
    return 0;
}

int dequeue(ArrayIntQueue *q, int *x) {
    if(q->num <= 0)
        return -1;
    
    *x = q->que[0];
    
    for(int i=1; i<q->num; i++) {
        q->que[i-1] = q->que[i];
    }
    q->num--;
    
    return 0;
}

int Capacity(ArrayIntQueue *q) {
    return q->max;
}

int Size(ArrayIntQueue *q) {
    return q->num;
}

void Print(ArrayIntQueue *q) {
    
    for(int i = 0; i<q->num; i++) {
        printf("%d ", q->que[i]);
    }
    putchar('\n');
}

int IsFull(ArrayIntQueue *q) {
    return (q->num >= q->max);
}

int IsEmpty(ArrayIntQueue *q) {
    return (q->num <= 0);
}

int Search(const ArrayIntQueue *q, int x) {
    int i;
    
    for(i = 0; i<q->num; i++) {
        if(q->que[i] == x)
            return i;
    }
    return -1;
}

void Terminate(ArrayIntQueue *q) {
    if(q->que != NULL)
        free(q->que);
    
    q->max = q->num = 0;
}

 

[ main.c ]

#include <stdio.h>
#include "IntQueue.h"

int main() {
    ArrayIntQueue q;
    
    if(Initialize(&q, 64) == -1) {
        puts("큐 생성에 실패했습니다.");
        return 1;
    }
    
    while(1) {
        int menu, x;
        printf("현재 데이터 수 : %d / %d\n", Size(&q), Capacity(&q));
        
        printf("(1)인큐 (2)디큐 (3)empty? (4)full? (5)검색 (6)출력 (0)종료: ");
        scanf("%d", &menu);
        
        if(menu == 0) break;
        
        switch(menu) {
                
            case 1: // enqueue
                printf("데이터 : ");
                scanf("%d", &x);
                
                if(enqueue(&q, x)== -1)
                    puts("인큐 실패");
                else
                break;
                
            case 2: // dequeue
                if(dequeue(&q, &x)== -1)
                    puts("디큐 실패");
                else
                    printf("디큐한 데이터는 %d입니다.\n", x);
                break;
                
            case 3:
                printf("큐가 %s.\n", (IsEmpty(&q)==1)?"비어있습니다":"비어있지 않습니다");
                break;
                
            case 4:
                printf("큐가 %s.\n", (IsFull(&q)==1)?"꽉 차있습니다":"꽉 차있지 않습니다");
                break;
                
            case 5:
                printf("검색 데이터 : ");
                scanf("%d", &x);
                int idx = Search(&q, x);
                if(idx==-1)
                    puts("데이터를 찾을 수 없습니다.");
                else
                    printf("해당 값은 %d 인덱스에 있습니다.\n", idx);
                break;
                
            case 6: // print
                Print(&q);
                break;
                
        }
    }
    Terminate(&q);
}

 

연습문제_Q4 > 링 버퍼 기반 int형 큐를 사용하는 프로그램에 아래 함수를 추가하세요.

int Search2(const IntQueue *q, int x);

-> 찾은 데이터가 맨 앞의 요소로부터 상대적으로 몇 번째 위치에 있는지 값 반환

int Search2(const IntQueue *q, int x) {
    int i;
    
    for(i=0; i< q->num; i++) {
        if(q->que[(q->front+i)%q->max] == x) // 검색 성공
            return i;
    }
    return -1;

}

 

연습문제_Q5 > Q4의 함수도 포함하여, IntQueue 함수 전체를 기능하는 프로그램 작성( = 큐 구현)

 

[ IntQueue.h ]

//
//  IntQueue.h
//  helloC
//
//  Created by Hevton on 2020/10/14.
//

#ifndef IntQueue_h
#define IntQueue_h

// 링 버퍼 구조로 큐를 구현
typedef struct {
    int max; //  큐의 용량
    int num; // 현재 데이터 수. front와 rear의 값이 같은 경우 큐가 비어있는지, 가득찼는지 구별할 수 없는 상황을 피하기 위해 사용.
    int front; // 프런트. 첫 번째 요소의 인덱스를 저장
    int rear; // 리어. 맨 나중에 넣은 요소의 하나 뒤의 인덱스를 저장 (다음 인큐 시에 데이터가 저장될 요소의 인덱스를 미리 준비하는 것)
    int *que; // 큐의 첫 요소에 대한 포인터
} IntQueue;

// 큐 초기화
int Initialize(IntQueue *q, int max);

// 큐에 데이터를 인큐
int enqueue(IntQueue *q, int x);

// 큐에서 데이터를 디큐
int dequeue(IntQueue *q, int *x);

// 큐에서 데이터를 피크
int Peek3(const IntQueue *q, int *x);

// 모든 데이터 삭제
void Clear(IntQueue *q);

// 큐의 최대용량
int Capacity(const IntQueue *q);

// 큐에 저장된 데이터의 개수
int Size(const IntQueue *q);

// 모든 데이터 출력
void Print(const IntQueue *q);

// 큐가 가득 찼는가?
int IsFull(const IntQueue *q);

// 큐가 비어 있는가?
int IsEmpty(const IntQueue *q);

// 큐에서 검색
int Search(const IntQueue *q, int x);

// 연습문제_Q4번을 위한 함수.
// 찾은 요소가 맨 앞 요소로부터 상대적으로 몇 번째 위치에 있는지에 대한 인덱스 값 반환하는 함수.
int Search2(const IntQueue *q, int x);

// 큐 종료
void Terminate(IntQueue *q);

#endif /* IntQueue_h */

 

[ IntQueue.c ]

//
//  IntQueue.c
//  helloC
//
//  Created by Hevton on 2020/10/14.
//

#include <stdio.h>
#include <stdlib.h>
#include "IntQueue.h"


// 큐 초기화
// num, front, rear 값을 모두 초기화
int Initialize(IntQueue *q, int max) {
    q->num = q->front = q->rear = 0;
    if((q->que = calloc(max, sizeof(int))) == NULL ) {
        q->max = 0;
        return -1;
    }
    
    q-> max = max;
    return 0;
}

// 큐에 데이터를 인큐
// 인큐에 성공하면 0을 반환, 실패하면 -1을 반환
int enqueue(IntQueue *q, int x) {
    if(q->num >= q->max) // 큐가 가득 참
        return -1;
    
    else {
        q->num++;
        q->que[q->rear++] = x;
        if(q->rear == q->max)
            q->rear = 0;
        return 0;
    }
}

// 큐에 데이터를 디큐
int dequeue(IntQueue *q, int *x) {
    if(q->num <= 0) // 큐가 비어있음
        return -1;
    
    else {
        q->num--;
        *x = q->que[q->front++];
        if(q->front == q->max)
            q->front = 0;
        return 0;
    }
}

// 큐에서 데이터를 피크
// 맨 앞의 데이터(디큐에서 꺼낼 데이터), que[front]의 값을 출력.
// 피크에 성공하면 0, 실패하면 -1 반환
int Peek(const IntQueue *q, int *x)
{
    if(q->num <= 0) // 큐가 비어있음
        return -1;
    
    else {
        *x = q->que[q->front];
        return 0;
    }
}

// 모든 데이터 삭제
void Clear(IntQueue *q)
{
    q->num = q->front = q->rear = 0;
}

// 큐의 최대용량
int Capacity(const IntQueue *q) {
    return q->max;
}

// 큐에 쌓여 있는 데이터 개수
int Size(const IntQueue *q) {
    return q->num;
}

// 큐가 비어 있나요?
// 비어 있으면 1, 그렇지 않으면 0 반환
int IsEmpty(const IntQueue *q) {
    return (q->num <= 0);
}

// 큐가 가득 찼나요?
// 가득 찼으면 1, 그렇지 않으면 0 반환
int IsFull(const IntQueue *q) {
    return q->num >= q->max;
}

// 큐에서 검색
// 맨 앞(front부분)부터 선형 검색 수행
// 찾으면 해당 인덱스, 실패하면 -1 반환
int Search(const IntQueue *q, int x) {
    int i, idx;
    
    for(i=0; i< q->num; i++) {
        if(q->que[idx = (q->front+i)%q->max] == x) // 검색 성공
            return idx;
    }
    return -1;
}

// 연습문제_Q4번을 위한 함수
int Search2(const IntQueue *q, int x) {
    int i;
    
    for(i=0; i< q->num; i++) {
        if(q->que[(q->front+i)%q->max] == x) // 검색 성공
            return i;
    }
    return -1;

}

// 모든 데이터 출력
// 맨 앞(front부분)부터
void Print(const IntQueue *q) {
    
    for(int i = 0; i<q->num; i++) {
        printf("%d ", q->que[(q->front+i)%q->max]);
    }
    putchar('\n');
}

// 큐의 종료
void Terminate(IntQueue *q) {
    if(q->que != NULL)
        free(q->que);
    
    q->max = q->num = q->front = q->rear = 0;
}

 

[ main.c ]

#include <stdio.h>
#include "IntQueue.h"

int main() {
    IntQueue q;
    
    if(Initialize(&q, 64) == -1) {
        puts("큐 생성에 실패했습니다.");
        return 1;
    }
    
    while(1) {
        int menu, x;
        printf("현재 데이터 수 : %d / %d\n", Size(&q), Capacity(&q));
        
        printf("(1)인큐 (2)디큐 (3)Peek (4)Clear (5)empty? (6)full? (7)검색 (8)검색2 (9)출력 (0)종료: ");
        scanf("%d", &menu);
        
        if(menu == 0) break;
        
        switch(menu) {
                
            case 1: // enqueue
                printf("데이터 : ");
                scanf("%d", &x);
                
                if(enqueue(&q, x)== -1)
                    puts("인큐 실패");
                else
                break;
                
            case 2: // dequeue
                if(dequeue(&q, &x)== -1)
                    puts("디큐 실패");
                else
                    printf("디큐한 데이터는 %d입니다.\n", x);
                break;
                
            case 3: // peek
                if(Peek(&q, &x)== -1)
                    puts("피크 실패");
                else
                    printf("Peek : %d\n", x);
                break;
                
            case 4: // Clear
                Clear(&q);
                break;
                
                
            case 5:
                printf("큐가 %s.\n", (IsEmpty(&q)==1)?"비어있습니다":"비어있지 않습니다");
                break;
                
            case 6:
                printf("큐가 %s.\n", (IsFull(&q)==1)?"꽉 차있습니다":"꽉 차있지 않습니다");
                break;
                
            case 7:
                printf("검색 데이터 : ");
                scanf("%d", &x);
                int idx = Search(&q, x);
                if(idx==-1)
                    puts("데이터를 찾을 수 없습니다.");
                else
                    printf("해당 값은 %d 인덱스에 있습니다.\n", idx);
                break;
                
            case 8: // 연습문제_Q4번을 위한 함수
                printf("검색 데이터 : ");
                scanf("%d", &x);
                int idz = Search2(&q, x);
                if(idz==-1)
                    puts("데이터를 찾을 수 없습니다.");
                else
                    printf("해당 값은 상대적 %d 에 있습니다.\n", idz);
                break;

                
            case 9: // print
                Print(&q);
                break;
                
        }
    }
    Terminate(&q);
}

 

연습문제_Q6 > deck이라고 하는 양방향 대기열(deque/double ended queue) 구현

 

[ double_ended_queue.h ]

//
//  double_ended_queue.h
//  helloC
//
//  Created by Hevton on 2020/10/15.
//

#ifndef double_ended_queue_h
#define double_ended_queue_h
// 이 또한 링 버퍼 기반
typedef struct {
    int max; // 큐의 최대 용량
    int num; // 현재 요소 개수
    int front; // 맨 앞 요소
    int rear; // 링 버퍼 기반에선, 맨 뒤 요소 + 1임. 정답소스 오타인듯..
    int *que; // 큐를 가리키는 포인터
} IntDequeue;

int Initialize(IntDequeue *q, int max);

int EnqueFront(IntDequeue *q, int x);

int EnqueRear(IntDequeue *q, int x);

int DequeFront(IntDequeue *q, int *x);

int DequeRear(IntDequeue *q, int *x);

int PeekFront(const IntDequeue *q, int *x);

int PeekRear(const IntDequeue *q, int *x);

void Clear(IntDequeue *q);

int Capacity(const IntDequeue *q);

int Size(const IntDequeue *q);

int IsEmpty(const IntDequeue *q);

int IsFull(const IntDequeue *q);

int Search(const IntDequeue *q, int x);

int Search2(const IntDequeue *q, int x);

void Print(const IntDequeue *q);

void Terminate(IntDequeue *q);

#endif /* double_ended_queue_h */

 

[ double_ended_queue.c ] 

//
//  double_ended_queue.c
//  helloC
//
//  Created by Hevton on 2020/10/15.
//

#include <stdio.h>
#include <stdlib.h>
#include "double_ended_queue.h"
// 이것도 링 버퍼 기반.
// 덱 = dequeue = double_ended_queue 초기화
int Initialize(IntDequeue *q, int max) {
    
    q->num = q->front = q->rear = 0;
    if((q->que = calloc(max, sizeof(int))) == NULL) {
        q->max = 0;
        return -1;
    }
    q->max = max;
    return 0;
    
}

// 맨 앞의 데이터를 인큐
int EnqueFront(IntDequeue *q, int x) {
    if(q->num >= q->max)
        return -1;
    else {
        q->num++;
        if(--q->front <0)
            q->front = q->max - 1;
        q->que[q->front] = x;
        return 0;
    }
}

// 맨 뒤의 데이터를 인큐
int EnqueRear(IntDequeue *q, int x) {
    if(q->num >= q->max)
        return -1;
    else {
        q->num++;
        q->que[q->rear++] = x;
        if(q->rear == q->max)
            q->rear = 0;
        return 0;
    }
}

// 맨 앞의 데이터를 디큐
int DequeFront(IntDequeue *q, int *x) {
    if(q->num <=0)
        return -1;
    
    else {
        q->num --;
        *x = q->que[q->front++];
        if(q->front==q->max)
            q->front=0;
        return 0;
    }
}

// 맨 뒤의 데이터를 디큐
int DequeRear(IntDequeue *q, int *x) {
    if(q->num <=0)
        return -1;
    else {
        q->num--;
        if(--q->rear <0)
            q->rear = q->max - 1;
        *x = q->que[q->rear];
        return 0;
    }
}

// 맨 앞의 데이터를 피크
int PeekFront(const IntDequeue *q, int *x) {
    if(q->num <= 0)
        return -1;
    else {
        *x = q->que[q->front];
        return 0;
    }
}

// 맨 뒤의 데이터를 피크 2021.03.10 오류 수정.
int PeekRear(const IntDequeue *q, int *x) {
    int temp;
    
    if(d->num <= 0)
        return -1;
    
    if((temp = q->rear - 1) < 0)
        temp = q->max - 1;
    
    *v = q->que[temp];
    return 0;
}


// 모든 데이터 삭제
void Clear(IntDequeue *q) {
    q->num = q-> front = q->rear = 0;
}

// 큐의 최대 용량
int Capacity(const IntDequeue *q) {
    return q->max;
}

// 큐에 저장된 데이터의 수
int Size(const IntDequeue *q) {
    return q->num;
}

// 큐가 비어있는지 확인
int IsEmpty(const IntDequeue *q) {
    return q->num <=0;
}

// 큐가 가득 찼는지 확인
int IsFull(const IntDequeue *q) {
    return q->num >= q->max;
}

// 큐 검색
int Search(const IntDequeue *q, int x) {
    int i, idx;
    
    for(i=0; i< q->num; i++) {
        if(q->que[idx = (i+q->front)%q->max] == x)
            return idx;
    }
    return -1;
}

// 큐 검색(논리적 검색)
int Search2(const IntDequeue *q, int x) {
    int i;
    
    for(i=0; i< q->num; i++) {
        if(q->que[(i+q->front)%q->max] == x)
            return i;
    }
    return -1;
}

// 전체 데이터 출력
void Print(const IntDequeue *q) {
    int i;
    
    for(i=0; i< q->num; i++) {
        printf("%d ", q->que[(i+q->front)%q->max]);
    }
    putchar('\n');
}

// 큐 삭제
void Terminate(IntDequeue *q) {
    if(q->que !=NULL)
        free(q->que);
    
    q->max = q->num = q->front = q->rear = 0;
}

 

[ main.c ]

#include <stdio.h>
#include "double_ended_queue.h"

int main() {
    IntDequeue que;
    
    if(Initialize(&que, 64) == -1) {
        puts("큐 생성 실패");
        return -1;
    }
    
    while(1) {
        int m, x;
        int idx;
        
        printf("현재 데이터의 수 : %d / %d\n", Size(&que), Capacity(&que));
        printf("(1)맨 앞에 데이터 인큐 (2)맨 앞의 데이터 디큐 (3)맨 앞 피크 (4)출력\n"
               "(5)맨 뒤에 데이터 인큐 (6)맨 뒤의 데이터 디큐 (7)맨 뒤 피크 (8)검색\n"
               "(9)초기화 (10)비어 있는 상태 / 가득 찬 상태 (0)종료 : ");
        scanf("%d", &m);
        
        if(m == 0) break;
        
        switch(m) {
            case 1: // 맨 앞에 데이터 인큐
                printf("데이터 : "); scanf("%d", &x);
                if(EnqueFront(&que, x) == -1)
                    puts("\a오류 : 인큐 실패");
                break;
                
            case 2: // 맨 앞의 데이터 디큐
                if(DequeFront(&que, &x) == -1)
                    puts("\a오류 : 디큐 실패");
                else
                    printf("디큐한 데이터는 %d입니다.\n", x);
                break;
                
            case 3: // 맨 앞 피크
                if(PeekFront(&que, &x) == -1)
                    puts("\a오류 : 피크 실패");
                else
                    printf("피크한 데이터는 %d입니다.\n", x);
                break;
                
            case 4: // 덱 출력
                Print(&que);
                break;
                
            case 5: // 맨 뒤에 데이터 인큐
                printf("데이터 : "); scanf("%d", &x);
                if(EnqueRear(&que, x) == -1)
                    puts("\a오류 : 인큐 실패");
                break;
                
            case 6: // 맨 뒤의 데이터 디큐
                if(DequeRear(&que, &x) == -1)
                    puts("\a오류 : 디큐 실패");
                else
                    printf("디큐한 데이터는 %d입니다.\n", x);
                break;
                
            case 7: // 맨 뒤 피크
                if(PeekRear(&que, &x) == -1)
                    puts("\a오류 : 피크 실패");
                printf("피크한 데이터는 %d입니다.\n", x);
                break;
                
            case 8: // 검색
                printf("검색 데이터 : ");
                scanf("%d", &x);
                if((idx=Search(&que, x)) == -1)
                    puts("\a오류 : 검색 실패");
                else {
                    printf("데이터는 인덱스 %d 위치에 있습니다.\n", idx);
                    printf("큐의 맨 앞에서 %d만큼 뒤에 위치합니다.\n", Search2(&que, x));
                }
                break;
                
            case 9: // 초기화
                Clear(&que);
                break;
                
            case 10: //  빈 상태 / 가득 찬 상태 판단
                printf("큐가 비어 있%s.\n", IsEmpty(&que)?"습니다":"지 않습니다");
                printf("큐가 가득 %s.\n", IsEmpty(&que)?"찼습니다":"차지 않았습니다");
                break;
        }
    }
    Terminate(&que);
    return 0;
}

 

 

공부 내용 정리

 

스택

LIFO 구조 : Last In First Out (후입선출)
가장 나중에 넣은 데이터를 가장 먼저 꺼내는 자료구조.

스택에 데이터를 넣는 작업을 push라 하고,
스택에서 데이터를 꺼내는 작업을 pop이라 한다.

스택의 가장 윗부분(push, pop을 하는 위치)을 top이라고 하고, 스택의 가장 밑바닥 부분을 bottom이라고 한다. (EBP , ESP같은 개념)
Top : 스택의 맨위를 가리킴
Bottom : 스택의 맨아래를 가리킴

C언어 프로그램에서 함수를 호출하고 실행할 때 프로그램 내부에서는 스택을 사용한다.




큐

FIFO 구조 : First In First Out (선입선출)
가장 먼저 넣은 데이터를 가장 먼저 꺼내는 자료구조.

큐에 데이터를 넣는 작업을 인큐(enqueue)라 하고, 데이터를 꺼내는 작업을 디큐(dequeue)라 한다.
인큐의 시간복잡도 : O(1)
디큐의 시간복잡도 : O(n)

데이터를 꺼내는 쪽을 프런트(front)라 하고, 데이터를 넣는 쪽을 리어(rear)라고 한다. 스택의 top bottom같은 개념


링 버퍼

배열 기반 선형 큐의 경우 디큐의 시간복잡도가 O(n)이나 된다. 프런트에 해당하는 데이터를 꺼낸 다음 남은 데이터들을 모두 앞으로 밀어넣어야 하기 때문이다. 이런 번거로움을 보완하기 위해 등장한 자료구조가 '링 버퍼'다.

 

링 버퍼를 이용해 큐를 구현함으로써, 디큐 작업 시 배열 요소를 앞쪽으로 옮기지 않아도 된다.

링 버퍼는 배열의 처음이 끝과 연결되어있다고 보는 자료구조다. 논리적으로 어떤 요소가 첫 번째 요소이고 어떤 요소가 마지막 요소인지 식별하기 위한 변수가 프런트와 리어다.

프런트(front) : 맨 처음 요소의 인덱스
리어(rear) : 맨 끝 요소의 하나 뒤의 인덱스 (다음 요소를 인큐할 위치를 미리 지정)

Ps. 링 버퍼에서의 rear는 위의 선형 큐와는 조금 다르다. 선형 큐에서는 rear가 맨 끝 요소의 인덱스를 담고 있으나, 링 버퍼에서의 rear는 맨끝요소의 하나 뒤의 인덱스를 담고 있다(스택의 스택포인터와 같은역할).

링 버퍼 구조를 사용한 큐를 구성하면 인큐와 디큐의 시간복잡도가 모두 O(1)이다.


∙ 링 버퍼의 활용

링 버퍼는 오래된 데이터를 버리는 용도로 사용할 수 있습니다. 요소의 개수가 n인 배열에 계속해서 데이터가 입력될 때 가장 최근에 들어온 데이터 n개만 저장하고 오래된 데이터는 버려지는(덮어씌워지는)것.

 

 

출처 - 'Do it 자료구조와 함께 공부하는 알고리즘 C언어편' 도서