Restricted Structure_Queue(큐)

Queue 란?

한쪽 끝에서 원소를 넣고 반대쪽 끝에서 원소를 뺄 수 있는 자료구조이다. 먼저 들어간 원소가 먼저 나오게 되는 FIFO(First In First Out) 구조이다. 큐에서는 원소가 제거되는 쪽을 가장 앞인 front, 원소가 삽입되는 쪽을 가장 뒤인 rear라고 부른다.

Queue 성질

• 원소의 추가 O(1)
• 원소의 제거 O(1)
• 맨 앞, 맨 뒤 원소 확인 O(1)
• 맨 앞, 맨 뒤를 제외한 나머지 원소들은 확인 및 변경은 원칙적으로 불가능

---

Queue 구현

스택과 마찬가지로 큐 역시 배열을 이용하여 구현하는 방법과 STL을 이용하여 구현하는 방법이 있다.

 

배열을 사용한 구현

스택에서의 구현 방법을 큐에 대입해보자. 원소가 삽입되면 tail이 가르키는 인덱스에 값을 넣고 tail++를 하면된다. 원소가 삭제되게 되면 head의 값을 +1하는것 만으로 구현을 끝낼 수 있다. 하지만 이렇게 될 경우, 원소의 삭제가 일어날 때 마다 배열의 사용 가능한 부분이 점점 오르쪽으로 밀리게 된다. 이 같은 문제는 배열을 원형 구조로 사용함으로써 간단히 해결 가능하다. 이런 큐를 원형 큐라고 부른다.

다음은 그냥 일반적인 선형 큐 구조에 대한 구현 코드이다.

int MX = 1000000;
int dat[MX];
int head=0, tail=0;

void push(int x){
    dat[tail] = x;
    tail++;
}

void pop(){
    head++;
}

int front(){
    return dat[head];
}

int rear(){
    return dat[tail-1];
}

• head :  가장 앞쪽에 있는 인덱스
• tail : 가장 뒤 쪽에 있는 인덱스의 다음 위치

STL을 사용한 구현

STL queue는 보통 BFS랑 FloodFill에 많이 사용되므로 사용법에 익숙해지는것이 좋을 것이다.

#include <iostream>
#include <queue>

int main(){
 	
    queue<int> qu1;
    queue<int> qu2;
    
    qu1.push(2);
    qu1.push(4);
    qu1.push(6);
    
    qu2.push(10);
    qu2.push(20);
    qu2.push(30);

    swap(qu1, qu2);
    
    while (!qu1.empty()) {
		cout << qu1.front() << qu1.back()<< '\n';
		qu1.pop();
	}
	return 0; 	
    //10 30 
    //20 30
    //30 30
}

• qu.push(element) : 데이터 추가
• qu.pop() : 데이터 삭제
• qu.front() : 맨 앞 데이터 반환(head, 삭제되는 위치)
• qu.back() : 맨 끝 데이터 반환(rear, 삽입되는 위치)
• qu.size() : 큐의 현재 사이즈 반환
• qu.empty() : 큐가 비었는지 확인(비었으면 true)
• swap(qu1,qu2) : 큐의 내용 바꾸기

Stack과 마찬가지로 queue역시 원소가 없는 상태에서 front(),back(),pop()를 사용하게 되면 런타임 에러가 발생하니 주의하자.

 

출처 : https://www.youtube.com/watch?v=D_fwSy5tRAY&list=PLtqbFd2VIQv4O6D6l9HcD732hdrnYb6CY&index=7