Queue

Queue

정의와 성질

• FIFO(First In First Out)
• 원소 추가: O(1)
• 원소 제거: O(1);
• 제일 앞/뒤의 원소 확인: O(1)
• 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능
• 추가되는 곳을 rear, 제거되는 곳을 front

  구현

• 배열 혹은 연결리스트로 구현 가능
• 배열로 구현
• 그냥 구현을 하면 data를 삭제할 때 마다 앞에 쓸모없는 공간이 생김
• 원형 큐로 만들면 해결 가능

  #include<iostream>
  using namespace std;
  const int MX = 1000005;
  int dat[MX];
  int head=0, tail=0; // head는 가장 앞의 원소의 index, tail은 가장 뒤에 있는 원소의 index+1
  void push(int x){
    dat[tail]=x;
    tail++;
  }
  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();
    cout<<front()<<'\n'; // 20
  }
  int main(void){
    test();
    return 0;
  }
  

  STL Queue

  #include<iostream>
  #include<queue>
  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
    Q.pop(); // 20 30
    cout<<Q.front()<<'\n'; // 20
    cout<<Q.back()<<'\n'; // 30
    Q.pop();
    Q.pop();
    if(Q.empty()){
        cout<<"Empty\n";
    }
    return 0;
  }