큐(Queue)

큐(Queue)란?

 

큐는 스택과 달리 먼저 들어온 데이터가 먼저 나가는 자료구조이다. 줄을 서 있는 사람들을 생각하면 편할 것이다.

 

큐는 스택와 다르게 삽입과 삭제가 같은 곳에서 일어나지 않는다. 삭제연산은 앞(front)에서 일어나고 삽입 연산은 뒤(rear)에서 일어난다.

 

 

이 그림에서 원소 $D$를 추가하면 $C$ 뒤에 추가되고

 

삭제연산을 하면 가장 맨 앞의 $A$가 삭제된다.

 

이렇게 먼저 들어온 원소가 먼저 나가는 형태를 선입선출(FIFO: First-In-First-Out)이라고 한다.

 

Queue의 기능

• $push(x)$: $x$를 큐의 맨 뒤에 추가한다.
• $pop()$: 큐의 맨 앞의 원소를 삭제한다.
• $empty()$: 큐가 비어있으면 $1(true)$, 아니면 $0(false)$을 리턴한다.
• $front()$: 큐의 맨 앞의 원소를 리턴한다.
• $size()$: 큐의 원소들의 개수를 리턴한다.

queue 구현

 

class Queue{
    int data[101];
    int front;
    int rear;
    public:
        Queue(){ front=rear=0; }
        bool Empty(){
            return front==rear;
        }
        void push(int x){
            data[++rear]=x;
        }
        void pop(){
            if(Empty()){ return; }
            data[front]=0;
            front++;
        }
        int Front(){
            return Front;
        }
        int Size(){
            return Front-rear;
        }
        
};

 

STL을 사용한 코드이다.

 

 

#include <iostream>
#include <queue>

using namespace std;


int main()
{
    queue<int> q;
    q.push(3);
    q.push(5);
    q.pop();
    cout << q.front() << "\n";
    cout << q.empty() << "\n";
    q.push(10);
    cout << q.size() << "\n";
    return 0;
}

 

 

 

큐는 컴퓨터 장치들 사이에서 데이터를 주고받을 때 임시 기억 장치로 사용되는데 이것을 버퍼라고 한다.

 

또한 큐는 일상생활이나 컴퓨터에서 매우 광범위하게 사용된다.

 

BFS(너비 우선 탐색)을 응용한 미로찾기나 그 외의 다양한 알고리즘에서도 큐가 사용된다.

 

 

https://david0506.tistory.com/8

그래프 탐색-너비 우선 탐색(BFS)