[Algorithm][Queue] Queue 개념 및 구현

I. Queue(이하 Q)란?

Q는 대표적인 FIFO(First In First Out)의 성질를 갖는 자료구조이다. (LIFO : Stack)

Q의 Data 흐름 (FIFO)

Q는 내가 원하는 순서대로 Data를 처리하기 위한 방법이다.
우선 순위가 없는 기본Q와 각 Data에 우선순위가 존재하는 우선 순위Q가 있다.

주로 알고리즘 문제에서는 대기열이 필요한 문제나 Data를 Cycle에서 추가하고 빼는...? 상황에서 필요하다.

이번 글의 구현부 에서는 다음 두 가지를 정리할 것이다. 
1. C++에서 STL로 Q를 사용하는 법
2. STL없이 구현하여 사용하는 법

---

II. 기본원리

1. Enque
    Enque는 맨 마지막 Data 뒷 순서로 현재 Data를 추가한다. (python의 append(num))
        -> 현재 Data가 대기열 상태로 들어갔다.

2. Deque
    Deque는 맨 첫번째 Data를 빼낸다. (python의 pop(0))
        -> 가장 들어온지 오래된 Data를 제거(FIFO)

이게 Q 원리 끝이다. 

하지만 구현측면을 보면,
1. List의 가장 작은 index가 비워지면 뒤 데이터를 앞으로 당겨야할까?? (O(N)의 시간복잡도 추가)
2. 그렇다면 List의 크기를 매우 크게?? (어디까지?)

STL은 가변크기
직접 구현시에는 상황에 맞게!

 

---

III. 구현

1. C++ STL <queue> 사용법

<hide/>
#include <queue>
#include <vector>
#include <iostream>
using namespace std;

struct stu{
	int a;
    int b;
};

vector<int> V;

queue<int> Q; // Q변수 선언 int를 담겠다.
queue<stu> stuQ; // Q변수선언 stu라는 구조체를 담겠다.
queue<vector<int>> vecQ; // Q변수선언 int형이 담긴 vector을 담겠다.

int main(){
	V.push_back(11);
    V.push_back(22); // 벡터에 11,22 넣음 ->Q에 넣을 용도
    
// push = Enque    

    Q.push(1); // Q에 1을 push함
    Q.push(stu{1,2}); // Q에 a=1, b=2의 stu구조체를 push함
    Q.push(V); //Q에 [11,22]인 vector을 push함.
    
    cout<<Q.size()<<endl; // Q.size() : Q의 데이터 길이를 보는 멤버 3
    cout<<Q.empty()<<endl; // Q.empty(): Q가 비었나? 안비었으므로 0
    
// front, pop = deque
// Q.front() : 맨 앞 Data를 참조만 한다.(삭제X)
// Q.pop() : 맨 앞 Data를 제거함. (참조 안됌)
	
    int intdata = Q.front(); // 참조할 변수에 넣어줌.
    Q.pop(); // 이렇게 해줘야 삭제가 됨.
    
    stu studata = Q.front(); // 구조체 변수에 참조
    Q.pop();
    
    vector<int> Vdata = Q.front(); // 벡터 변수에 참조
    Q.pop();
    
    cout<<Q.size()<<endl; // 데이터 길이 0
    cout<<Q.empty()<<endl; // Q.empty() =0 : Q가 비었나? 비었으므로 1  
    
    return 0;
}

2. 직접구현

직접구현 방법
1. 연결 리스트 (Linked list) 단방향 + (원형)
2. 리스트로 관리 (내 선택)

<hide/>
#include <stdio.h>
#include <iostream>
using namespace std;

#define MAX 10;

int Q[MAX]; // 예시로 10개 짜리 Q라고 하자.
int popidx{0};
int pushidx{0};

// enque 함수
void push(int n){
	Q[pushidx] = n;
    pushidx++;
    return;
}

//deque 함수
int pop(){
	if(popidx==pushidx) return -1 ; // 잘못된 명령(비어있음)
    
    else {
    	popidx=(popidx+1)%MAX; // 삭제만 진행 idx증가 -> %MAX는 원형으로 circular하게 구현
        return 0;
    }
    
    /*
    만약 삭제 + 참조를 동시에 하려면
    else {
    	int temp = Q[popidx];
        popidx = (popidx+1)%MAX;
        return temp;
    */
}

// front() 함수
int front(){
	return Q[popidx];
}

// empty() 함수
bool isEmpty(){
	if(pushidx==popidx) return 1;
    else return 0;
}