[자료구조]큐(queue), 큐의 구현

큐(queue)란?

가장 처음에 삽입한 데이터가 가장 처음 꺼낼 수 있는 자료구조.

아래는 동적할당으로 구현하는 방법으로 template을 사용하지 않고, 데이터는 int를 가진 큐 구현 코드이다.

#include<cstdio>
 
class queue {
private:
    struct node {
        int data;
        node* after;
        node() {
            after = NULL;
        }
        node(int input): data(input){
            after = NULL;
        }
    };
    node* pfront;
    node* pend;
    int element;
public:
    queue() {
        pfront = pend = NULL;
    }
    ~queue() {
        while (!empty()) {
            pop();
        }
    }
    void push(int input) {
        node* new_node = new node(input);
        if (empty()) {
            pfront = pend = new_node;
        }
        else {
            pend->after = new_node;
            pend = new_node;
        }
        printf("push data %d\n", input);
    }
    bool pop() {
        if (empty()) return false;
        node* del_node = pfront;
        pfront = pfront->after;
        printf("pop data %d\n", del_node->data);
        delete del_node;
        if (pfront == NULL) pend = NULL;
        return true;
    }
    bool empty() {
        if (pfront == NULL && pend == NULL) return true;
        return false;
    }
    int front() {
        if (empty()) return -1;
        return pfront->data;
    }    
};
 
int main() {
    queue* Q = new queue();
    for (int i = 1; i < 20; i++) {
        Q->push(3 * i + 1);
        printf("front %d\n", Q->front());
    }
    while (!Q->empty()) {
        Q->pop();
    }
    printf("empty Queue\n");
    for (int i = 1; i < 20; i++) {
        Q->push(3 * i + 1);
        printf("front %d\n", Q->front());
    }
    delete Q;
    return 0;
}

큐의 크기를 1<<18 만큼 정해두고 작성한 코드이다.

template<class T>
struct my_queue {
    T d[1 << 18];
    int s, e;
    my_queue() { s = e = 0; }
    bool full() { return (e + 1) == s; }
    bool empty() { return s == e; }
    void push(T input) {
        if (full()) return;
        T[e++] = input;
        e %= (1 << 18);
    }
    void pop() {
        if (empty()) return;
        s = (s + 1) % (1 << 18);
    }
    T front() {
        T ret;
        if (empty()) return ret;
        return d[s];
    }
};