[자료구조] 큐의 개념, 구현 및 적용 C/C++

📕  큐란??

---

 자료구조 큐를 이해하기 위해서는 영어 queue가 무엇인지를 알면 역시 이해하기 쉽다.

Queue는 명사 '줄' 이라는 뜻이 있다. 그렇다면 대체 왜 "줄"을 자료구조 컨테이너의 이름으로 정했을까?

그건 줄을 서는 상황을 생각해보면 알 수 있다.

놀이공원에 들어가기 위해서 줄을 선다고 생각해보자. 그렇다면 가장 먼저 입장하는 사람은 누구겠는가?

당연히 줄 가장 앞에 있는 사람일 것이다. 반대로 가장 늦게 입장하는 사람은 줄 마지막에 서 있는 사람일 것이다.

 

아래는 큐를 그린 그림이다.

📕  큐의 특징

---

 큐 == 줄 이기 때문에 생기는 특징이 있다.

바로 선입선출, First In First Out이다. 

그렇기 때문에, pop 함수를 호출하면, 가장 앞에 있는 element가 큐에서 삭제되며,

push 함수를 호출하면, 가장 뒤에 새로운 element가 추가된다.

이때, 가장 앞에 있는 element를 front라고 부르고, 가장 뒤에 있는 element를 back이라고 부른다.

 

 

📕  큐와 관련된 메서드 C++

---

큐의 기본 함수는 <queue> 라이브러리에 내장되어 있다.

 

empty() : 큐가 비어있으면 참(1)을 반환하고, 큐가 비어있으면 거짓(0)을 반환한다.

size() : 큐의 사이즈를 반환하고, 큐가 비어있으면 0을 반환한다.

front() : 큐의 가장 앞에 있는 요소를 반환한다.

back() : 큐의 가장 뒤에 있는 요소를 반환한다.

push() : 큐에 요소를 삽입한다.

pop() : 큐의 가장 앞에 있는 요소를 삭제한다.

 

 

📕  큐의 구현 및 사용 C/C++

---

#include <stdio.h>
#include <stdlib.h>

#define MAX 5
typedef int element;
typedef struct {
    element data[MAX];
    int front, back;
} QueueType;

//오류함수
void error(char *message) {
    fprintf(stderr, "%s\n", message);
    exit(1);
}

//큐 초기화 함수
void init(QueueType *q) {
    q->front = q->back = 0;
}

//공백 상태 확인 함수
int is_empty(QueueType *q) {
    //back과 front가 같을 경우
    return (q->front == q->back);
}

//포화 상태 확인 함수
int is_full(QueueType *q) {
    return ((q->back + 1) % MAX == q->front);
}

//삽입 함수
void push(QueueType *q, element item) {
    if(is_full(q))
        error("queue is full");
    q->back = (q->back + 1) % MAX;
    q->data[q->back] = item;
}

//삭제 함수
element pop(QueueType *q) {
    if(is_empty(q))
        error("Queue is empty");
    q->front = (q->front + 1) % MAX;
    return q->data[q->front];
}

//front를 반환하는 함수
element peek(QueueType *q) {
    if(is_empty(q))
        error("Queue is empty");
    return (q->data[(q->front + 1) % MAX]);
}

 

대부분의 동적 할당이 기본으로 가능한 언어에서는 pop, push, empty 등과 같은 함수들을 지원하기 때문에,

C처럼 힘들게 구현할 필요가 없다. 

 

C++과 간단한 문제를 통해 큐의 기본적인 사용을 알아보자.

아래는 백준 10845번 큐 문제이다.

기본적인 기능들을 사용해보기에 적합한 문제이다.

 

#include <iostream>
#include <queue>
#include <string>

using namespace std;

queue<int> q;

int main() {
    int num;
    int digit;
    cin >> num;
    for(int i = 0; i < num; i++) {
        string str;
        cin >> str;
        if(str == "push") {
            cin >> digit;
            q.push(digit);
        }
        else if(str == "front") {
            if(!q.empty())
                cout << q.front() << "\n";
            else
                cout << -1 << "\n";
        }
        else if(str == "back") {
            if(!q.empty())
                cout << q.back() << "\n";
            else
                cout << -1 << "\n";
        }
        else if(str == "empty") {
            if(!q.empty()) {
                cout << 0 << "\n";
            }
            else {
                cout << 1 << "\n";
            }
        }
        else if(str == "pop") {
            if(!q.empty()) {
                cout << q.front() << "\n";
                q.pop();
            }
            else {
                cout << -1 << "\n";
            }
        }
        else if(str == "size") {
            cout << q.size() << "\n";
        }
    }
    
}

 

If you have any comments, plz leave them below.