큐_백준_이론

큐

한쪽 끝에서 자료를 넣고 다른 한쪽 끝에서만 자료를 뺄 수 있는 자료구조

먼저 넣은 것이 가장 먼저 나오기 때문에 First In First Out(FIFO)구조이다.

기본적인 함수

push : 큐에 자료를 넣는 연산

pop : 큐에서 자료를 빼는 연산

front : 큐의 가장 앞에 있는 자료를 보는 연산

empty : 큐가 비어있는지 아닌지를 확인하는 연산

size : 저장된 자료의 개수를 알아보는 연산

이 함수들의 시간복잡도는 O(1)이다.

Example)

우선순위가 같은 작업 예약 (인쇄 대기열)

선입선출이 필요한 대기열 (티켓 카운터)

구현

배열, 링크드리스트, 벡터 등을 이용해서 구현 할 수 있다. 여기서는 배열을 이용해서 구현했다.

#include <iostream>
#include <string>
using namespace std;
struct Queue {
    int data[10000];
    int begin, end;
    Queue() : begin(0), end(0) {}
    void push(int num) {
        data[end] = num;
        end += 1;
    }
    bool empty() {
        if (begin == end) {
            return true;
        }
        else {
            return false;
        }
    }
    int size() {
        return end - begin;
    }
    int front() {
        return data[begin];
    }
    int back() {
        return data[end - 1];
    }
    int pop() {
        if (empty()) {
            return -1;
        }
        begin += 1;
        return data[begin - 1];
    }
};
int main() {
    Queue q;
    while (true) {
        string cmd;
        cin >> cmd;
        if (cmd == "push") {
            int num;
            cin >> num;
            q.push(num);
        }
        else if (cmd == "pop") {
            if (q.empty()) {
                cout << -1 << '\n';
            }
            else {
                cout << q.front() << '\n';
                q.pop();
            }
        }
        else if (cmd == "size") {
            cout << q.size() << '\n';
        }
        else if (cmd == "empty") {
            cout << q.empty() << '\n';
        }
        else if (cmd == "front") {
            if (q.empty()) {
                cout << -1 << '\n';
            }
            else {
                cout << q.front() << '\n';
            }
        }
        else if (cmd == "back") {
            if (q.empty()) {
                cout << -1 << '\n';
            }
            else {
                cout << q.back() << '\n';
            }
        }
    }
    return 0;
}