Queue (큐)

큐는 선형 구조이며, 삽입된 순서대로 값이 나오는 FIFO(First in First Out)로 되어 있습니다. 이때 삽입하는 과정을 enqueue라고 하며 값을 빼내는 과정을 dequeue라고 합니다.
예를 들면 a, b, c 순서로 enqueue하고 큐에 있는 값들을 모두 dequeue하면 a, b, c 순서로 나오게 됩니다.
또한 큐에는 size, front, empty라는 함수가 있으며 size는 큐에 들어있는 값들의 수를 반환하는 함수이고, front은 큐에서 가장 먼저 삽입된 값을 반환하는 함수, empty는 큐가 비어 있는지 여부를 반환하는 함수입니다.

<enqueue>                                                                                              <dequeue>

그리고 이러한 큐를 만드는 방법에는 2가지 방법이 있습니다. 하나는 배열을 이용한 방법이고, 다른 하나는 링크드 리스트를 이용한 방법입니다.

 배열을 이용한 방법에서는 삽입될 위치인 큐의 마지막 부분을 저장하는 변수 rear와 큐의 처음 부분을 저장하는 변수 front가 필요합니다. 또한 큐의 데이터 개수를 저장하는 변수 size를 이용하여 큐의 크기(큐에 들어있는 요소의 수)를 빠르게 알 수 있습니다. 또한 큐의 크기가 0일 경우 큐가 비어 있는 것이므로 비어 있는지 여부도 쉽게 알 수 있습니다. 따라서 배열로 구현하기 위해서는 값들을 담을 배열과 큐의 처음 위치와 마지막 위치(삽입될 위치)를 저장하는 변수가 필요합니다. 또한 enqueue과정과 dequeue과정에서 각각 rear index, front index가 점점 뒤로 밀려나기 때문에 이를 효율적으로 구성하려면 환형 배열로 구현해주어야 합니다.

<enqueue in list>                                                                                                      <dequeue in list>

 

  링크드 리스트를 이용한 방법에서는 값과 다음 노드의 위치를 저장하는 큐 노드들을 이용할 것이며 마지막으로 삽입된 노드의 위치를 저장하는 노드형 포인터 rear와 큐의 가장 앞 노드의 위치를 저장하는 노드형 포인터 front, 노드들의 수를 저장하는 변수 size가 필요합니다. front와 rear는 초기화시 처음에 널 값을 넣어주고, enqueue할 경우 이전에 rear의 next는 새로 삽입하는 노드가 되고, 새로 삽입되는 노드가 rear가 됩니다. dequeue할 경우 이전의 Head의 next가 Head가 되고, 이전의 head는 메모리 할당 해제 시킵니다.

euqueue and dequeue in linked list

다음은 C++ (배열) 로 나타낸 코드입니다.

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
struct queue {
    int *data;
    int front,rear;
    int maxsize;
    int size;
    queue(int sz = 16) {
        maxsize = sz;
        front = 0;
        rear = 0;
        size = 0;
        data = (int*)malloc(maxsize*sizeof(int));
    }
};

int queue_size(queue& q) {
    return q.size;
}
bool queue_empty(queue& q) {
    return queue_size(q) == 0;
}
bool queue_full(queue& q) {
    return q.size == q.maxsize;
}
void queue_push(queue& q, int val) {
    assert(!queue_full(q));
    q.data[q.rear] = val;
    q.rear = (q.rear + 1) % q.maxsize;
    q.size++;
}
void queue_pop(queue& q) {
    assert(!queue_empty(q));
    q.front = (q.front + 1) % q.maxsize;
    q.size--;
}
int queue_front(queue& q) {
    assert(!queue_empty(q));
    return q.data[q.front];
}
int main() {
    int val;
    queue q;

    for (int i = 0; i < 5; i++) {
        queue_push(q,i); // input : 0 1 2 3 4
    }
    printf("output : ");
    while(!queue_empty(q)) {
        printf("%d ", queue_front(q));
        queue_pop(q);
    }

    return 0;
}

다음은 C++ (링크드 리스트) 로 나타낸 코드입니다.

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
struct queue_node {
    int data;
    queue_node* next;
};

struct queue {
    queue_node* front;
    queue_node* rear;
    int sz;
    queue() {
        front=rear = NULL;
        sz = 0;
    }

};
int queue_size(queue &q) {
    return q.sz;
}
bool queue_empty(queue &q) {
    return queue_size(q) == 0;
}
void queue_enqueue(queue& q, int val) {
    queue_node *newNode = (queue_node*)malloc(sizeof(queue_node));
    newNode->data = val;
    newNode->next = 0;
    q.sz++;
    if (q.rear==NULL && q.front==NULL) {
        q.rear=q.front = newNode;
        return;
    }
    q.rear->next = newNode;
    q.rear = newNode;
}
void queue_dequeue(queue& q) {
    assert(!queue_empty(q));
    queue_node *nextHead = q.front->next;
    free(q.front);
    if (q.front == q.rear) q.front = q.rear = 0;
    q.front = nextHead;
    q.sz--;
}
int queue_front(queue& q) {
    assert(!queue_empty(q));
    return q.front->data;
}

int main() {
    int val;
    queue q;

    for (int i = 0; i < 5; i++) {
        queue_enqueue(q, i); // input : 0 1 2 3 4
    }
    printf("output : ");
    while(!queue_empty(q)) {
        printf("%d ", queue_front(q));
        queue_dequeue(q);
    }


    return 0;
}

다음은 C++ (라이브러리 활용)으로 나타낸 코드입니다.

#include <queue>
#include <iostream>
#include <string>
using namespace std;

int main() {
    int val,N;
    queue<int> q;
    string cmd;
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> cmd;
        if (cmd[0] == 's') {
            cout << q.size() << endl;
        } else if (cmd[0] == 'e') {
            cin >> val;
            q.push(val);
        } else if (cmd[0] == 'd') {
            q.pop();
        } else if (cmd[0] == 'f') {
            cout << q.front() << endl;
        }
    }
    return 0;
}

다음은 Java로 나타낸 코드입니다.

import java.util.*;

public class Main {
    public static void main(String[] args) {
        
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < N; i++) {
            String cmd = scanner.next();
            if (cmd.charAt(0) == 's') {
                System.out.println(q.size());
            }
            else if (cmd.charAt(0) == 'e') {
                int val = scanner.nextInt();
                q.add(val);
            }
            else if (cmd.charAt(0) == 'd') {
                q.remove();
            }
            else if (cmd.charAt(0) == 'f') {
                System.out.println(q.peek());
            }
        }
    }
}

다음 시간엔 스택에 대해 알아보겠습니다.