[실전 알고리즘] 큐

정의와 성질

 

큐: 한쪽 끝에서만 원소를 넣거나 뺄 수 있는 자료구조

큐의 성질

1. 원소의 추가와 제거가 모두 O(1)

2. 제일 상단의 원소 확인이 O(1)

3. 제일 상단이 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능

 

 

기능과 구현

 

1. 직접 구현

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

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

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

void pop(){
  head++;
}

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

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

void test(){
  push(10); push(20); push(30);
  cout << front() << '\n'; // 10
  cout << back() << '\n'; // 30
  pop(); pop();
  push(15); push(25);
  cout << front() << '\n'; // 30
  cout << back() << '\n'; // 25
}

int main(void) {
  test();  
}

 

2. 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
}

 

연습문제

10845번: 큐 (acmicpc.net)

10845번: 큐

 

정답코드

// http://boj.kr/702a66643c6245f6bc05cd760490c785
#include <bits/stdc++.h>
using namespace std;

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  
  queue<int> Q;
  int n;
  cin >> n;
  while(n--){
    string q;
    cin >> q;
    if(q=="push"){
      int val;
      cin >> val;
      Q.push(val);
    }
    else if(q=="pop"){
      if(Q.empty()) cout << -1 << '\n';
      else{
        cout << Q.front() << '\n';
        Q.pop();
      }
    }
    else if(q=="size"){
      cout << Q.size() << '\n';
    }
    else if(q=="empty"){
      cout << Q.empty() << '\n';
    }    
    else if(q=="front"){
      if(Q.empty()) cout << -1 << '\n';
      else cout << Q.front() << '\n';
    }
    else{ // back
      if(Q.empty()) cout << -1 << '\n';
      else cout << Q.back() << '\n';
    }
  }
}

 

 

출처

BaaaaaaaarkingDog | [실전 알고리즘] 0x06강 - 큐 (encrypted.gg)