Queue

<Queue>

정의 : 먼저 넣은 데이터를 먼저 처리하는 FIFO(First In First Out)의 자료구조

(일반적인 우선순위 큐에서 key값이 들어온 시간 순이라고 생각하면 우선순위 큐의 특별 케이스라고 볼 수 있다.)

큐의 형태

<배열 이용> - (Queue size : 5)

- 선형 큐 : 크기가 제한되어 있어 Out처리가 되었을 시 자료를 한 칸씩 앞으로 이동해야하는 단점이 존재

 ->보다시피 배열의 크기가 정해져 있기 때문에 pop한 공간은 사용이 불가하며, 만약 사용하고 싶을 시에는 별도의 내부 value값을 옮겨주는 작업이 필요로 한다. 

#include<iostream>
#define MAX_SIZE 10
using namespace std;
 
class Queue {
private:
    int q_size;        //현재 queue의 사이즈
    int f_index;    //front 위치의 index
    int b_index;    //back 위치의 index
    int* arr;        //value가 저장될 배열
 
public:
    Queue() :q_size(0), f_index(0), b_index(0) {}
 
    void create() {
        arr = new int[MAX_SIZE];
        //MAX_SIZE로 최대 배열크기 설정
    }
 
    void push(int num) {
        if (this->b_index == MAX_SIZE) {
            cout << "queue is full" << endl;
            return;
        }
        arr[b_index++] = num;
        q_size++;
 
        return;
    }
 
    void pop() {
        if (this->f_index == this->b_index) {
            cout << "queue is empty" << endl;
            return;
        }
 
        f_index++;
        q_size--;
 
        return;
    }
 
    int size() {
        return q_size;
    }
 
    int front() {
        return arr[f_index];
    }
 
    
    ~Queue(){
        free(arr);
        //할당 해제
        arr = NULL;
    }
};
 
int main() {
    Queue q;
    q.create();
    q.push(11);
    q.push(20);
    cout << q.front() << endl;
    q.pop();
    cout << q.front() << endl;
    return 0;
}

- 환형 큐 : 큐의 입력이 끝에 닿을 시 앞의 데이터공간이 비었다면 추가로 다시 앞에서 시작한다. 

->back의 부분이 앞으로 이동하여 정해진 배열 크기가 채워지기 전까지는 사용할 수 있습니다.

<연결리스트 이용>

- 큐의 길이를 쉽게 늘릴 수 있어 크기의 제한이 없다.

: 오류나 수정할 내용이 있으면 comment 달아주시면 감사하겠습니다.