title: Why does std::stack use std::deque by default?
body: <p>Since the only operations required for a container to be used in a stack are:</p>
  
  <ul>
  <li>back()</li>
  <li>push_back()</li>
  <li>pop_back()</li>
  </ul>
  
  <p>Why is the default container for it a deque instead of a vector?</p>
  
  <p>Don't deque reallocations give a buffer of elements before front() so that push_front() is an efficient operation? Aren't these elements wasted since they will never ever be used in the context of a stack?</p>
  
  <p>If there is no overhead for using a deque this way instead of a vector, why is the default for priority_queue a vector not a deque also? (priority_queue requires front(), push_back(), and pop_back() - essentially the same as for stack)</p>
  
  <hr>
  
  <p><strong>Updated based on the Answers below:</strong></p>
  
  <p>It appears that the way deque is usually implemented is a variable size array of fixed size arrays. This makes growing faster than a vector (which requires reallocation and copying), so for something like a stack which is all about adding and removing elements, deque is likely a better choice. </p>
  
  <p>priority_queue requires indexing heavily, as every removal and insertion requires you to run pop_heap() or push_heap(). This probably makes vector a better choice there since adding an element is still amortized constant anyways.</p>