【數據結構】STL-queue

std::queue

template <class T, class Container = deque<T> > class queue;
FIFO queue
queues are a type of container adaptor, specifically designed to operate in a FIFO context (first-in first-out), where elements are inserted into one end of the container and extracted from the other.

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”.

The underlying container may be one of the standard container class template or some other specifically designed container class. This underlying container shall support at least the following operations:

  • empty
  • size
  • front
  • back
  • push_back
  • pop_front

The standard container classes deque and list fulfill these requirements. By default, if no container class is specified for a particular queue class instantiation, the standard container deque is used.

 

Template parameters

T
Type of the elements.
Aliased as member type queue::value_type.
Container
Type of the internal underlying container object where the elements are stored.
Its value_type shall be T.
Aliased as member type queue::container_type.

 

Member types

member type definition notes
value_type The first template parameter (T) Type of the elements
container_type The second template parameter (Container) Type of the underlying container
size_type an unsigned integral type usually the same as size_t

 

Member functions

std::queue::queue

explicit queue (const container_type& ctnr = container_type());
Construct queue
Constructs a queue container adaptor object.

A container adaptor keeps internally a container object as data. This container object is a copy of the ctnr argument passed to the constructor, if any, otherwise it is an empty container.

 

Parameters

ctnr
Container object.
container_type is the type of the underlying container type (defined as an alias of the second class template parameter, Container; see member types).
alloc
Allocator object.
Alloc shall be a type for which uses_allocator::value is true (for other types, the constructor does not even participate in overload resolution).
x
queue of the same type (i.e., with the same template arguments, T and Container).

 

Example

// constructing queues
#include <iostream>       // std::cout
#include <deque>          // std::deque
#include <list>           // std::list
#include <queue>          // std::queue

int main ()
{
  std::deque<int> mydeck (3,100);        // deque with 3 elements
  std::list<int> mylist (2,200);         // list with 2 elements

  std::queue<int> first;                 // empty queue
  std::queue<int> second (mydeck);       // queue initialized to copy of deque

  std::queue<int,std::list<int> > third; // empty queue with list as underlying container
  std::queue<int,std::list<int> > fourth (mylist);

  std::cout << "size of first: " << first.size() << '\n';
  std::cout << "size of second: " << second.size() << '\n';
  std::cout << "size of third: " << third.size() << '\n';
  std::cout << "size of fourth: " << fourth.size() << '\n';

  return 0;
}

Output:

size of first: 0
size of second: 3
size of third: 0
size of fourth: 2

Complexity

One container construction (which for standard containers is up to linear in its size).

std::queue::empty

bool empty() const;
Test whether container is empty
Returns whether the queue is empty: i.e. whether its size is zero.

This member function effectively calls member empty of the underlying container object.

Parameters

none

Return Value

true if the underlying container‘s size is 0false otherwise.

Example

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

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

  for (int i=1;i<=10;i++) myqueue.push(i);

  while (!myqueue.empty())
  {
     sum += myqueue.front();
     myqueue.pop();
  }

  std::cout << "total: " << sum << '\n';

  return 0;
}

The example initializes the content of the queue to a sequence of numbers (form 1 to 10). It then pops the elements one by one until it is empty and calculates their sum.

Output:

total: 55

Complexity

Constant (calling empty on the underlying container).

std::queue::size

size_type size() const;
Return size
Returns the number of elements in the queue.

This member function effectively calls member size of the underlying container object.

Parameters

none

Return Value

The number of elements in the underlying container.

Member type size_type is an unsigned integral type.

Example

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

int main ()
{
  std::queue<int> myints;
  std::cout << "0. size: " << myints.size() << '\n';

  for (int i=0; i<5; i++) myints.push(i);
  std::cout << "1. size: " << myints.size() << '\n';

  myints.pop();
  std::cout << "2. size: " << myints.size() << '\n';

  return 0;
}

Output:

0. size: 0
1. size: 5
2. size: 4

Complexity

Constant (calling size on the underlying container).

std::queue::front

      value_type& front();
const value_type& front() const;
Access next element
Returns a reference to the next element in the queue.

The next element is the “oldest” element in the queue and the same element that is popped out from the queue when queue::pop is called.

This member function effectively calls member front of the underlying container object.

Parameters

none

Return value

A reference to the next element in the queue.

Member type value_type is the type of the elements in the container (defined as an alias of the first class template parameter, T).

Example

// 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;
}

Output:

myqueue.front() is now 61

Complexity

Constant (calling front on the underlying container).

std::queue::back

      value_type& back();
const value_type& back() const;
Access last element
Returns a reference to the last element in the queue. This is the “newest” element in the queue (i.e. the last element pushed into the queue).

This member function effectively calls member back of the underlying container object.

Parameters

none

Return value

A reference to the last element in the queue.

Member type value_type is the type of the elements in the container (defined as an alias of the first class template parameter, T).

Example

// 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;
}

Output:

myqueue.back() is now 63

Complexity

Constant (calling back on the underlying container).

std::queue::push

void push (const value_type& val);
Insert element
Inserts a new element at the end of the queue, after its current last element. The content of this new element is initialized to val.

This member function effectively calls the member function push_back of the underlying container object.

Parameters

val
Value to which the inserted element is initialized.
Member type value_type is the type of the elements in the container (defined as an alias of the first class template parameter, T).

Return value

none

Example

// 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;
}
The example uses push to add a new elements to the queue, which are then popped out in the same order.

Complexity

One call to push_back on the underlying container.

std::queue::pop

void pop();
Remove next element
Removes the next element in the queue, effectively reducing its size by one.

The element removed is the “oldest” element in the queue whose value can be retrieved by calling member queue::front.

This calls the removed element’s destructor.

This member function effectively calls the member function pop_front of the underlying container object.

Parameters

none

Return value

none

Example

// 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;
}
The example uses push to add a new elements to the queue, which are then popped out in the same order.

Complexity

Constant (calling pop_front on the underlying container).

发布者:Cinema

成功的道路并不狭窄,因为大部分人都在颓废。

留下评论

电子邮件地址不会被公开。 必填项已用*标注