1

What is the time complexity of standard queue operations such as push_back and pop_front provided by std::queue in C++ STL? It is not mentioned in the documentation.

Teja Juluru
  • 113
  • 1
  • 8
  • 4
    Does this answer your question? [What are the complexity guarantees of the standard containers?](https://stackoverflow.com/questions/181693/what-are-the-complexity-guarantees-of-the-standard-containers) – Geno C Jul 30 '20 at 18:52
  • 3
    BTW: It is specified in the standard even (assuming you mean the standard and not the obsolete STL)! Check out e.g. cppreference.com, which is not the standard but pretty close and damn useful. – Ulrich Eckhardt Jul 30 '20 at 18:53

2 Answers2

6

Both push() (which internally calls push_back() on the underlying container) and pop()(which internally calls pop_front() on the underlying container) provided by std::queue in C++ STL have a constant O(1) time complexity since they only insert at the end of queue or pop from the front of it. You can check http://www.cplusplus.com/reference/queue/queue/ to find out more about other methods and their time complexities.

Abhishek Bhagate
  • 5,583
  • 3
  • 15
  • 32
  • 1
    One more thing to note that above time complexity is consider amortized time complexity. In practice, queues use deque as underlying containers. You can read about how deque has constant amortized time complexity here - https://stackoverflow.com/questions/28050760/how-does-deque-have-an-amortized-constant-time-complexity – Abhishek Bhagate Jul 30 '20 at 19:09
1

std::stack is just a shim on top of another container, so the time complexity depends on the underlying container type used by the stack. By default, the container type is std::deque, which has O(1) push and pop.

You can use any container type that meets the requirements of SequenceContainer, including a user-defined type.

For example, if you use std::vector as the underlying container type, then popping is still O(1) but pushing is amortized O(1) (due to possible reallocations).

cdhowie
  • 158,093
  • 24
  • 286
  • 300