0x06. 큐(Queue) - FIFO 자료구조

0x06 큐

0x00 정의와 성질

정의

큐 : FIFO ( First in First Out ) , Restricted Structure ( 특정 위치에서만 원소를 넣거나 뺄 수 있는 제한 )

성질

원소의 추가 / 제거 O(1) 제일 앞 / 뒤의 원소 확인 O(1) 제일 앞 / 뒤 아닌 나머지 원소들의 확인 / 변경이 원칙적으로 불가능

0x01 기능과 구현

선형 큐는 push, pop 함수를 수행하다보면 자리가 뒤로 밀리기 때문에 원형 큐(Circular Queue)를 사용하는 것이 좋다.

하지만 코딩테스트에서는 push의 최대 횟수가 정해져있기 때문에 배열의 크기를 push의 최대 횟수보다 크게 둬서 굳이 Circular Queue를 안만들어도 되게 할 수 있다.

구현

Push 함수

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

Pop 함수

void pop(){
    head++;
}

Front 함수

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

Back 함수

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

0x02 STL queue

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

int main(void) {
    queue<int> Q;
    Q.push(10); // 10
    Q.push(20); // 10 20
    Q.push(30); // 10 20 30
    cout << Q.size() << '\n'; // 3
    if(Q.empty()) cout << "Q is empty\n";
    else cout << "Q is not empty\n"; // Q is not empty
    Q.pop(); // 20 30
    cout << Q.front() << '\n'; // 20
    cout << Q.back() << '\n'; // 30
    Q.push(40); // 20 30 40
    Q.pop(); // 30 40
    cout << Q.front() << '\n'; // 30
}

→ 큐가 비어있을 경우 front, back, pop 함수 호출하면 런타임 에러 발생!!

0x03 연습문제

BOJ 10845 : 큐

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

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

  int n;
  queue<int> Q;

  cin >> n;
  while(n--) {
    string s;
    cin >> s;
    if(s == "push") {
      int buffer;
      cin >> buffer;
      Q.push(buffer);
    }
    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";
    else if(s= "front") {
      if(Q.empty()) cout << -1 << "\n";
      else {
        cout << Q.front() << "\n";
      }
    }
    else if(s= "back") {
      if(Q.empty()) cout << -1 << "\n";
      else {
        cout << Q.back() << "\n";
      }
    }
  }
}

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

const int MX = 1000005;
int dat[MX];
int head = 0, tail = 0;

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

  int n;
  cin >> n;
  while(n--) {
    string s;
    cin >> s;
    if(s == "push") {
      int buffer;
      cin >> buffer;
      push(buffer);
    }
    else if(s == "pop") {
      if(head == tail) cout << -1 << "\n";
      else {
        cout << front() << "\n";
        pop();
      }
    }
    else if(s= "size") cout << tail-head << "\n";
    else if(s= "empty") cout << (int)(head= tail) << "\n";
    else if(s= "front") {
      if(head= tail) cout << -1 << "\n";
      else {
        cout << front() << "\n";
      }
    }
    else if(s= "back") {
      if(head= tail) cout << -1 << "\n";
      else {
        cout << back() << "\n";
      }
    }
  }
}

문제 풀이

이번 강의에 해당하는 문제는 총 3개였다. 연습문제는 강의를 들으면서 잠시 멈춰놓고 해결하였고, 기본문제 2개는 최근에 혼자 풀어본 문제였다.

endl 때문에 한참을 돌고돌아 풀어본 문제여서 정확하게 기억하고 있다 ,,

문제의 난이도가 있는건 아니여서 가볍게 패스하겠다.

리뷰

큐도 중요한 자료구조 중에 하나라고 생각하고 있고 수업과정에서 확실히 배운 기억이 남아있어 쉽게쉽게 강의를 들을 수 있었다.

덱까지 빠르게 듣고 어려운 파트로 들어가도록 하겠다.

다음은 0x07강 덱으로 돌아오겠다.

출처: 바킹독님의 실전알고리즘 강의