Data Structure 10 - Queue(3)

앞서 큐는 FIFO(First In First Out, 선입선출)을 따르는 자료구조라고 했다. 이것의 응용으로 양방향 삽입, 삭제가 가능하게 만든 큐는 Double-Ended Queue, Deque라고 부른다. 

이 경우, 삽입과 삭제가 front와 rear 모두 에서 가능하므로 front_enqueue, front_dequeue, rear_enqueue, rear_dequeue 의 총 4가지 operation이 가능하다.

Deque는 양방향 삽입 삭제가 가능하다는 특성 때문에 연결리스트로 구현하는 것이 일반적이다. 물론 배열로도 구현할 수 있다.

아래는 배열로 구현한 Deque ADT이다. struct를 사용하지 않고 배열과, front/rear를 가리키는 변수를 포인터로 이용하였다.

#include<stdio.h>
#define MAX_SIZE 100

int deque[MAX_SIZE];
int front = -1;
int rear = -1;

void push_front(int data) {
    if ((front == 0 && rear == MAX_SIZE - 1) || front == rear + 1) {
        printf("Deque is full\n"); return;
    }
    if (front == -1) {
        front = 0;
        rear = 0;
    }
    else if (front == 0) {
        front = MAX_SIZE - 1;
    }
    else front--;
    deque[front] = data;
    printf("push_front : %d\n", data);
}

void push_back(int data) {
    if ((front == 0 && rear == MAX_SIZE - 1) || front == rear + 1) {
        printf("Deque is full\n"); return;
    }
    if (front == -1) {
        front = 0;
        rear = 0;
    }
    else if (rear == MAX_SIZE-1) {
        rear = 0;
    }
    else rear++;
    deque[rear] = data;
    printf("push_back : %d\n", data);
}

void pop_front() {
    if (front == -1) {
        printf("Deque is empty\n");
        return;
    }
    printf("pop_front : %d\n", deque[front]);
    if (front == rear) {
        front = -1;
        rear = -1;
    }
    else if (front == MAX_SIZE - 1) front = 0;
    else front++;
}

void pop_back() {
    if (front == -1) {
        printf("Deque is empty\n");
        return;
    }
    printf("pop_back : %d\n", deque[rear]);
    if (front == rear) {
        front = -1;
        rear = -1;
    }
    else if (rear==0) rear = MAX_SIZE-1;
    else rear--;
}