Queue

한 방향에서만 자료를 넣고 빼는 FIFO(first-in first-out, 선입선출) 형식의 자료구조로, 놀이공원 같은 곳에서 줄 서는 것과 유사하다.

Queue 연산

queue의 주요 연산은 다음과 같은 것들이 있다.

push: queue의 뒤에 item을 집어 넣음
pop: queue의 가장 앞에 있는 item을 빼냄
front: queue의 가장 앞에 있는 item을 가리킴
back: queue의 가장 뒤에 있는 item을 가리킴
empty: queue가 비어있는지 알려줌 (비어 있으면 True)
size: queue의 크기를 알려줌

c++에서는 queue libray를 통해 queue를 쉽게 선언하고 사용할 수 있다. 하지만 이 글에서는 array를 이용하여 queue를 직접 구현 해볼 예정이다. 그래도 libary 사용법을 알고 있으면 매번 구현할 필요가 없으니, 아래 library 사용법을 참고해두면 좋을 것 같다.

#include <iostream>
#include <queue>
using namespace std;

int main(){
    queue<int> q; // q라는 이름을 가진 int형 queue 선언
    
    q.push(8); // 줄을 서는 것이라고 생각! => (앞) 8 (뒤)
    q.push(22); // (앞) 8 22 (뒤)
    
    cout << q.front() << '\n'; // 8이 출력될 것임 (맨 앞 item)
    cout << q.back() << '\n'; // 22가 출력될 것임 (맨 뒤 item)
    cout << q.size() << '\n'; // 2가 출력될 것임. (8, 22 두 개의 item이 있으므로)
    
    if(q.empty()) cout << "queue is empty!\n"; // queue가 비어 있는지 확인 하는 연산 
    else cout << "queue size is " << q.size() << '\n'; // 비어 있지 않으므로 else문 실행

    q.pop(); // 8이 pop 됨
    cout << q.front() << '\n'; // 22 출력
    q.pop(); // queue가 비어 있게 됨 
    
    if(q.empty()) cout << "queue is empty!\n"; // 이번에는 queue가 비어 있으므로 if문 실행
    else cout << "queue size is " << q.size() << '\n'; 
}

Queue 구현

queue 또한 앞서 stack과 같이 array와 linked list를 이용하여 구현할 수 있다. 앞서 stack을 linked list로 구현해 보았으니, 여기서는 array를 이용하여 queue를 구현해서 백준 10845번: 큐 문제를 풀어보겠다.

1. 직접 구현한 풀이

array를 이용하여 직접 queue를 구현한 풀이다.

#include <iostream>
#define MAX_SIZE 10001
using namespace std;

int q[MAX_SIZE]; // q 역할을 할 배열 선언 (원형 큐)
int front=0, back=0, qsize=0; // q의 맨 앞 idx, 맨 뒤 idx, 크기

// 작성한 함수들
int isempty();
void push(int x);
int pop();
int front_value();
int back_value();

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n, x; cin>>n;
    string oper;
    while (n--){
        cin>>oper;
        if(oper=="push"){ // push인 경우
            cin>> x; // push할 item을 추가로 받음
            push(x);
        }
        else if(oper=="pop") cout << pop() << '\n';
        else if(oper=="size") cout << qsize << '\n';
        else if(oper=="empty") cout << isempty() << '\n';
        else if(oper=="front") cout << front_value() << '\n';
        else if(oper=="back") cout <<  back_value() << '\n';
    }   
}

int isempty(){
    if(qsize==0) return 1; //queue가 비어 있는 경우 1 반환
    return 0; // 그렇지 않으면 0 반환
}

void push(int x){
    qsize++; // push하므로 사이즈 증가
    q[back] = x; // 맨 뒤에 item 저장
    back++; // 다음 위치 update
    back%=MAX_SIZE; // 사이즈보다 큰 경우 modulor 연산을 적용하여 원형 큐 구현
}

int pop(){
    if(isempty()) return -1; //queue가 비어 있는 경우 -1 반환
    qsize--; // pop하므로 사이즈 감소
    int res = q[front]; // 맨 앞 원소를 반환
    front++; // 다음 item이 첫번 째 item이 됨
    front%=MAX_SIZE; // 사이즈보다 큰 경우 modulor 연산을 적용하여 원형 큐 구현
    return res;
}

int front_value(){
    if(isempty()) return -1; //queue가 비어 있는 경우 -1 반환
    return q[front]; // 비어 있지 않은 경우 첫번째 값 반환
}

int back_value(){
    if(isempty()) return -1; //queue가 비어 있는 경우 -1 반환
    return q[back-1]; // 비어 있지 않은 경우 마지막 값 반환
}

2. 라이브러리를 이용한 풀이

이건 옛날에 풀어뒀던 라이브러리를 이용한 풀이다.

# include <iostream>
# include <queue>
using namespace std;
int main(){
  int n; cin >> n;
  queue<int> q;
  while(n--){
    string S; cin >> S;
    if(S == "push"){
      int x; cin >> x;
      q.push(x);
    }
    else if(S == "pop"){
      if (q.empty()) cout << -1 << '\n';
      else {
         cout << q.front() << '\n';
         q.pop();
      }
    }
    else if(S == "size"){
      cout << q.size() <<'\n';
    }
    else if(S == "empty"){
      cout << q.empty() << '\n'; //q.empty() 비어있으면 자동으로 1반환.
    }
    else if (S == "front") {
      if(q.empty()) cout << -1 << '\n';
      else cout << q.front() << '\n';
    }
    else{
      if(q.empty()) cout << -1 << '\n';
      else cout << q.back() << '\n';
    }
  }
}