Блог пользователя white_horseman

Deque VS Stack & Queue (for c++)
Автор white_horseman, 5 лет назад, По-английски

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 ;)

  • Проголосовать: нравится
  • +26
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится +39 Проголосовать: не нравится

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

→ Ответить
»
5 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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.

→ Ответить