C++ Queue(큐) 배열, 연결 리스트로 구현

Queue

스택이 top에 쌓는 것이었다면 queue는 줄을 세우는 것이다.

지하철역에서 줄을 서면 먼저 온 사람이 앞(front)쪽에 서고 나중에 온 사람은 그 사람 뒤(rear)에 선다.

그리고 지하철에 탈 때는 먼저 온 사람이 먼저 들어간다.

즉, front와 rear가 필요하다.

1. implementation using array

#include <iostream>
 
using namespace std;
int queue[100];
int n = 100, front = -1, rear = -1;
 
void insert(int data) {
    if (rear == n - 1) {
        cout << "queue overflow";
    }
    else {
        if (front == -1) {
            front = 0;
        }
 
        cout << "insert : " << data;
        rear++;
        queue[rear] = data;//끝에 추가
    }
    cout << endl;
}
 
void del() {
    if (front == -1 || front > rear) {
        cout << "queue underflow";
    }
    else {
        cout << "delete : " << queue[front];
        front++;//먼저 들어온 사람 나감
        //즉 프론트 증가, rear 감소
    }
    cout << endl;
}
 
void display() {
    if (front == -1) {
        cout << "queue is empty";
    }
    else {
        cout << "queue element : ";
        for (int i = front; i <= rear; i++) {
            cout << queue[i] << " ";
        }
    }
    cout << endl;
}
 
int main() {
    display();
 
    insert(1);
    insert(2);
    insert(3);
 
    display();
 
    del();
    del();
 
    display();
 
    insert(5);
 
    display();
 
    return 0;
}

참고한 사이트 tutorialspoint (https://www.tutorialspoint.com/cplusplus-program-to-implement-queue-using-array)

2. implementation using Linked List

#include <iostream>
 
using namespace std;
 
struct node {
    int data;
    node* next;
};
 
node* front = NULL;
node* rear = NULL;
node* temp;
 
void insert(int data) {
    cout << "insert : ";
    if (rear == NULL) {
        rear = new node();
        rear->next = NULL;
        rear->data = data;
        front = rear; //rear가 NULL이라는 건 아무것도 없다 따라서 같음
    }
    else {
        temp = new node();
        rear->next = temp; //끝에 추가하는 거니까
        temp->data = data;
        temp->next = NULL;
        rear = temp;//끝은 temp가 된다
    }
    cout << data << endl;
}
 
void del() {
    temp = front;
    if (front == NULL) {
        cout << "queue underflow";
    }
    else {
        if (temp->next != NULL) {//끝에 원소가 있다(즉 원소가 front, rear 두개)
            temp = temp->next; //temp는 temp 다음이됨
            cout << "delete : " << front->data; //front부터 빠져나감
            free(front);
            front = temp; //왜냐하면 삭제된 front의 다음이 front가 되어야 하니까
        }
        else { //front에만 원소가 있다
            cout << "delete : " << front->data;
            free(front);
            front = NULL;
            rear = NULL;
        }
    }
    cout << endl;
}
 
void display() {
    temp = front;
    if ((front == NULL) && (rear == NULL)) {
        cout << "queue is empty";
    }
    else {
        cout << "queue element : ";
        while (temp != NULL) {
            cout << temp->data << " ";
            temp = temp->next;
        }
    }
    cout << endl;
}
 
int main() {
    display();
 
    insert(1);
    insert(2);
    insert(3);
 
    display();
 
    del();
    del();
 
    display();
 
    insert(5);
 
    display();
 
    return 0;
}

참고한 사이트 tutorialspoint (https://www.tutorialspoint.com/cplusplus-program-to-implement-queue-using-linked-list)

실행 결과

main 함수가 동일하므로 실행 결과도 같다.

설명은 geeksforgeeks가 잘 되어 있고 example은 tutorialspoint가 더 깔끔한 것 같다.