[자료구조] Queue

배열로 구현한 예시

요소는 int형

 

+ 링 버퍼 구조 기반 예시

 

[ 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);
}