C++/ Queue 자료구조 정리

Queue의 정의

- 입출력이 서로 반대쪽에서 이루어지는 제한구조.

- 자료가 입력된 순서대로 출력되는 FIFO(First In First Out) 방식이다.

- 입력은 front에서, 출력은 back에서 되는 구조가 기본

 

cplusplus 정의

queues are implemented as containers adaptors, which are classes that use an encapsulated object of a specific container class as its underlying container, providing a specific set of member functions to access its elements. Elements are pushed into the "back" of the specific container and popped from its "front".

Queue의 특징

 

- 임의의 우선순위를 가진 원소를 우선순위 큐에 삽입할 수 있고, 우선순위가 가장 높은(혹은 낮은) 원소를 먼저 삭제하는 것이 가능해진다.

 

QUEUE의 응용분야

 

- 작업 스케쥴링

- 버퍼, 스풀, Radix 정렬시 버킷으로 이용

- BFS

 

STL::QUEUE 지원 함수

- empty

- size

- front

- back

- push_back

- pop_front

 

QUEUE::PUSH/POP

 

// queue::push/pop
#include <iostream>       // std::cin, std::cout
#include <queue>          // std::queue

int main ()
{
  std::queue<int> myqueue;
  int myint;

  std::cout << "Please enter some integers (enter 0 to end):\n";

  do {
    std::cin >> myint;
    myqueue.push (myint);
  } while (myint);

  std::cout << "myqueue contains: ";
  while (!myqueue.empty())
  {
    std::cout << ' ' << myqueue.front();
    myqueue.pop();
  }
  std::cout << '\n';

  return 0;
}

Return은 넣은 순서대로.. (배열 출력하듯이..)

 

QUEUE::front

 

- 가장 오래된 엘리먼트를 호출하는 함수. (맨 앞의 원소)

 

// queue::front
#include <iostream>       // std::cout
#include <queue>          // std::queue

int main ()
{
  std::queue<int> myqueue;

  myqueue.push(77);
  myqueue.push(16);

  myqueue.front() -= myqueue.back();    // 77-16=61

  std::cout << "myqueue.front() is now " << myqueue.front() << '\n';

  return 0;
}

 

결과값:

myqueue.front() is now 61

 

QUEUE::back

 

- 가장 최근의 엘리먼트를 호출하는 함수 (맨 뒤의 원소)

 

// queue::back
#include <iostream>       // std::cout
#include <queue>          // std::queue

int main ()
{
  std::queue<int> myqueue;

  myqueue.push(12);
  myqueue.push(75);   // this is now the back

  myqueue.back() -= myqueue.front();

  std::cout << "myqueue.back() is now " << myqueue.back() << '\n';

  return 0;
}

 

결과값:

myqueue.back() is now 63