큐 (Queue)

  • 한쪽 끝에서만 자료를 넣고 다른 한쪽 끝에서만 뺄 수 있는 자료구조 (FIFO)
  • push, pop, front, back, empty, size
  • BFS 알고리즘에 사용

  • 일차원 배열 하나로 구현 가능

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    int queue[10000];
    int begin = 0;
    int end = 0;
    //큐에 포함된 내용은 [begin, end)

    void push(int data){
      queue[end] = data;
      end += 1;
    }

    void pop(){
        queue[begin] = 0;
        begin += 1;
    }
    • 구현된 라이브러리 사용 가능
      • C++: STL의 queue
      • Java: java.util.Queue

큐 응용문제

  • 조세퍼스 문제 (1158)

덱 (Deque, Double-ended queue)

  • 양 끝에서만 자료를 넣고 뺼 수 있는 자료구조
  • 사용하는 연산에 따라 스택으로도 큐로도 사용 가능
  • push_front, push_back, pop_front, pop_back, front, back

덱 응용문제

  • 덱 (10866)