[자료구조] Double ended queue

양방향 대기열 = deck = deque = double ended queue

시작과 끝 지점에서 양쪽으로 데이터를 인큐하거나 디큐하는 자료구조

 

 

배열로 구현한 예시

요소는 int형

 

+ 링 버퍼 구조 기반 예시

 

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