white_horseman's blog

Deque VS Stack & Queue (for c++)
By white_horseman, 5 years ago, In English

C++ STL support all of the three data structures. Stack offers LIFO type operation, and queue offers FIFO type operation. But on the other hand, deque gives user the flexibility to add/remove elements from both it's end — front and back. Thereby deque can mimic the operations of both stack and queue if required. But there is more to it...

I conducted the tests on all three of them to test their performance by using a simple code that inserted 50000000 elements into the data structure then popped all out one by one. I found out that deque is roughly 10% faster than both stack and queue which can be understood from the fact that deque is the underlying container for both stack and queue which can be seen here as mentioned in comments. Also, deque supports range-based for loop iteration, which is unavailable for stack and queue(both of them require to create temporary copy for iteration). Thereby deque supports all operations much more faster than both stack and queue. So why not use dequeue instead of stack and queue ;)

  • Vote: I like it
  • +26
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it +39 Vote: I do not like it

We can see here that default container for stack is deque. The same for queue. So stack and queue are actually deque and probably that's the reason why they're not faster

→ Reply
»
5 years ago, # |
  Vote: I like it +6 Vote: I do not like it

You can also implement your own deque if you can afford a loose limit on the maximum number of elements you push into it:

static int buf[MAX * 2 + 1];
int * front = buf + MAX;
int * back = buf + MAX;

inline void push_front(int value) { *(front++) = value; }
inline void pop_front(int value) { *(back--) = value; }
inline void push_back(int value) { front--; }
inline void pop_back(int value) { back++; }
inline int front() { return *(front-1); }
inline int back() { return *(back+1); }
inline bool empty() { return front == back; }
inline int size() { return front-back; }
inline void clear() { front = back = buf + MX; }

It could be faster thanks to no validity checks.

→ Reply