[자료구조] 큐(Queue) - 코딩기록

큐(Queue)

큐는 이전 포스팅에서 설명했던 스택과 약간 다른 점이 있는 자료구조이다. 이전에 설명했던 스택은 LIFO(후입선출)구조였지만 큐는 FIFO(First - In - First - Out) 선입선출 구조이다.

즉, 먼저 집어 넣은 데이터가 먼저 나오는 것이다.

1번, 2번, 3번 데이터가 차례로 들어오고 이 순서대로 나간다고 생각하면 된다.

맨 오른쪽에 있는 화살표에 해당하는 구간이 삽입연산이 수행되는 곳인 리어(rear)이고

맨 왼쪽에 있는 화살표에 해당하는 구간이 삭제연산이 수행되는 곳인 프론트(front)이다.

 

큐의 기능

이제 큐STL을 활용해 큐의 기능들을 살펴보겠다.

• push(x) : 원소 x를 큐의 맨 뒤에 추가
• pop() : 큐의 맨 앞 원소 삭제
• empty() : 큐가 비어있으면 1, 비어있지 않으면 0을 반환
• front() : 큐의 맨 앞 원소를 반환
• back() : 큐의 맨 뒤 원소를 반환
• size() : 큐의 원소 개수 반환

스택과 달리 큐에는 front와 back이 있어 앞과 뒤 원소에 모두 접근할 수 있다.

 

코드와 함께 큐의 기능을 다시 살펴보자.

#include <iostream>
#include <queue> //큐의 헤더파일
using namespace std;

//q라는 int형 큐를 선언하는 방법.
queue <int> q;

int main()
{
    q.push(1);
    q.push(2);
    q.push(3);//큐에 1,2,3을 차례로 삽입.

    cout<<q.size()<<"\n";//큐의 사이즈 출력--3

    q.pop();//가장 위 원소 삭제 및 반환

    cout<<q.size()<<"\n";//큐의 사이즈 출력--2

    cout<<q.empty()<<"\n";//큐가 비어있지 않다면 0출력--0

    q.push(4);

    cout<<q.front()<<"\n";//큐의 맨 앞 원소 출력--2

    cout<<q.back()<<"\n";//큐의 맨 뒤 원소 출력--4

    return 0;
}

다음과 같은 코드를 실행하면

3

2

0

2

4

다음과 같이 출력된다.

 

큐에 대해 어느 정도 이해가 되었다면 백준 10845번 큐를 풀어보는 것을 추천한다. 큐를 활용한 간단한 문제로 큐를 적용하는 데 도움을 줄 수 있다.

https://www.acmicpc.net/problem/10845

10845번: 큐