CODEWITHSUNDEEP
c++performancestlstackqueue
kinokijuf
kinokijuf

Reputation: 997

Which is faster: STL queue or STL stack?

I am implementing a variant of toposort, which needs a structure to hold elements with no incoming edges. Both queue and stack seem fine for this purpose, as the order in which they are taken out does not matter. The question is: is any of them significantly faster than the other?

Upvotes: 4

Views: 7675

Answers (5)

user555045
user555045

Reputation: 64904

While queue and stack aren't wildly different in performance, they obviously induce a different node-visiting order. One of them may give a more cache-friendly order than the other, depending on how your nodes are laid out in memory.

Upvotes: 1

Armen Tsirunyan
Armen Tsirunyan

Reputation: 132994

Answer to your main question: I don't know. I don't think any of them is significantly faster, because for std::deque (the default internal container for both stack and queue) the push_back and push_front (and pop_back and pop_front) are symmetric. None should be faster. I would however suggest using plain old std::vector with push_back and pop_back, or equivalently

std::stack<T, std::vector<T>>

See here for the reasons why stack uses deque by default.

Upvotes: 3

taocp
taocp

Reputation: 23634

queue and stack are both container adaptors, not complete containers in their own right. Both stack and queue are implemented on top of a std::deque by default, they should have similar performance if you did not change this setup.

It really depends on what kind of application you are coding and you may select the underlying container which benefits those operations you want the most.

Upvotes: 3

Aditya Sihag
Aditya Sihag

Reputation: 5167

they both have constant complexity ... you'll just need to time it to determine whether any of the constants is higher

http://www.cplusplus.com/reference/stack/stack/pop/
http://www.cplusplus.com/reference/queue/queue/pop/

Upvotes: 1

aguyngueran
aguyngueran

Reputation: 1321

queue and stack are different. First is FIFO and stack is FILO

Upvotes: -3

Related Questions