큐(Queue)

인프런 - 파이썬으로 배우는 알고리즘 기초 강의 이미지

✔ 큐(Queue)

큐도 스택과 마찬가지로 알고리즘보단 자료 구조에 해당하고 컴퓨터에서 많이 사용되는 자료 구조이다.

큐는 먼저 집어넣은 데이터가 먼저 나오는 선입선출(FIFO: First In First Out) 구조로 저장하는 형식을 말한다. 즉, 가장 처음에 넣은 값이 먼저 나오는 것을 FIFO 구조라고 한다.

나중에 넣은 값이 먼저 나오는 스택과는 반대되는 개념이다.

 

쉬운 예시로 파이프 혹은 드라이브 스루를 생각하면 된다.

스타벅스 코리아 사이트

드라이브 스루는 가장 먼저 들어가는 사람이 먼저 주문을 하게 되고 그 뒤로 차례로 줄을 서게 된다.

먼저 들어간 사람이 주문을 끝내고 가지 않는 이상 그 뒤로는 계속 기다려야 하는 구조이다. 이 구조가 큐 자료 구조에 해당한다.

 

✔ 큐의 연산

큐는 양쪽이 뚫려 있는 구조로 한쪽에서는 데이터를 삽입하고 다른 쪽에서는 데이터를 추출한다.

큐의 용어에서는 데이터를 삽입하는 Put(insert), 데이터를 추출하는 Get(delete)라고 하고, 데이터의 첫 번째 위치를 Front(head) 가리키고 마지막 위치를 Rear(tail) 가리킨다.

 

• Enqueue: 데이터 삽입(put보다 Enqueue 명칭을 더 많이 사용)
• Dequeue: 데이터 추출(get보다 Dequeue 명칭을 더 많이 사용)
• Front: 처음에 위치한 데이터를 가리킨다
• Rear: 마지막에 위치한 데이터를 가리킨다

C++ 언어에서는 데이터 삽입하는 함수로는 push를 사용하고 데이터를 추출할 때는 pop를 사용한다. 그리고 front 함수는 데이터의 처음 위치를 반환하고 back 함수는 데이터의 마지막 위치를 반환한다.

 

✔ 큐 동작 과정

• 큐에 데이터 삽입(push)

• 큐에 데이터 추출(pop)

 

✔ 큐 구현(C++)

C++에서는 STL 라이브러리를 사용하면 큐를 간단하게 구현할 수 있다.

#include <iostream>
#include <queue>
using namespace std;

int main() {
    queue<int> q;
    q.push(1);
    q.push(2);
    q.push(3);
    q.push(4);
    
    cout << q.empty() << "\n";  // 0(false)
    cout << q.size() << "\n";   // 4
    q.pop();
    
    cout << q.front() << "\n";    // 2
    q.push(5);
    while(!q.empty()) {
        cout << q.front() << " ";   // 2 3 4 5
        q.pop();
    }
    cout << "\n";
    cout << q.empty();  // 1(true)
    return 0;
}

 

 

 

🔗 Reference

• 큐 (자료 구조)