정의와 성질

큐는 FIFO 바로 나와주면 된다.

큐의 성질

원소의 추가가 O(1)
원소의 제거가 O(1)
제일 앞/뒤 원소 확인이 O(1)
앞뒤 외의 원소들은 원칙적으로 확인/변경 불가능

추가 -rear 제거 -front 로 보통 나타낸다.

기능과 구현

스택 어렵지 않았으니까 걍 내가 구현해보자.

const int MX = 100005;
int dat[MX];
int tail=0; // 추가 
int head=0; // 제거

void push(int x){
    dat[tail++]=x;
}

void pop(){
    head++;
}

int front(){
    return dat[head];
}

int back(){
    return dat[tail-1];
}

제미나이한테 던졌더니 길이 제한 생각 안 하냐고 혼났다. 그치 대기큐 같은 병목 현상도 있지. 바킹독에서는 이를 다루고 있진 않다. 혹시 필요하다면 % 연산 기호로 원형 큐를 만들 수 있을 거 같다.

#include <bits/stdc++.h>
using namespace std;

int main(void){
    queue<int> q;
    q.push(10);
    q.push(20);
    cout<<q.size()<<'\n';
    q.empty();
    q.pop();
    q.front();
    q.back();
}

나왔던 오류

연산자 관련

풀다가 연산자 우선순위 관련한 오류가 하나 나왔다.

#include <bits/stdc++.h>
using namespace std;

queue<int> q;

int main(void){
    int n;
    cin>>n;
    while(n--){
        string inst;
        cin>>inst;
        if(inst=="push"){
            int nor;
            cin>>nor;
            q.push(nor);
        }
        else if(inst=="front") cout<< (q.size()==0) ? -1 : q.front()<<'\n';
        else if(inst=="back") cout<< (q.size()==0) ? -1 : q.back() << '\n';
        else if(inst=="size") cout<<q.size()<<'\n';
        else if(inst=="empty") cout<<q.empty()<<'\n';
        else if(inst=="pop") {
            cout<< (q.size()==0) ? -1 : q.front()<<'\n';
            if(q.size()!=0) q.pop();
        }
    }
}

/*
❌ Test Case #1: Failed
--------------- Expected ---------------
1
2
2
0
1
2
-1
0
1
-1
0
3
---------------- Actual ----------------
002
0
0010
1
10
0

--------------- 채점 종료 ----------------
*/

자꾸 이런 오류가 뜨길래 제미나이한테 넘겼더니 연산 우선순위 때문이라고 한다.

// 작성하신 코드
cout << (q.size()==0) ? -1 : q.front() << '\n';

// 컴퓨터의 해석 (괄호 위치 주목!)
( cout << (q.size()==0) ) ? -1 : ( q.front() << '\n' );

위와 같이 삼항 연산자보다 출력 연산자가 우선순위가 높다고 한다.

2^31-1

위 키워드 보면 int 최댓값임을 바로 파악해야 한다.

coding