[큐]

큐

• 큐는 한쪽 끝에서 원소를 넣고 반대쪽 끝에서 원소를 뺄 수 있는 자료구조
• FIFO(First In First Out) 형식을 따른다.
• 원소의 추가가 O(1)
• 원소의 제거가 O(1)
• 제일 앞/뒤 원소의 확인이 O(1)
• 양 끝의 원소를 제외하고, 나머지 원소들의 확인/변경이 불가능하다.
• 원소의 삭제가 발생하는 맨 앞을 front라고 하며, 원소의 삽입이 발생하는 맨 뒤를 rear라고 한다.

---

배열을 통한 큐 구현

#include <iostream>

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();
}

• head는 배열의 맨 앞 원소를 가리키고, tail은 배열의 마지막 원소 + 1을 가리킨다.
• 따라서 큐의 size 는 tail- head로 쉽게 접근이 가능하다.
• 삭제 연산은 단순히 head를 1 증가 시키면된다.
• 이 배열 구현의 단점은 삽입/삭제 연산이 반복되서 실행된 후, 큐의 맨 처음 원소 앞에 낭비되는 공간이 생긴다는 점이다.
• 이를 극복한 큐가 원형 큐이다.
• 하지만 코딩테스트에서는 push, pop 연산의 횟수가 정해져 있음으로 배열의 크기를 충분히 크게 한다면 문제될 것은 없다.

---

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
}