title: Array-Based vs List-Based Stacks and Queues
body: <p>I'm trying to compare the growth rates (both run-time and space) for stack and queue operations when implemented as both arrays and as linked lists. So far I've only been able to find average case run-times for queue <code>pop()</code>s, but nothing that comprehensively explores these two data structures and compares their run-times/space behaviors.</p>
  
  <p>Specifically, I'm looking to compare <code>push()</code> and <code>pop()</code> for both queues and stacks, implemented as <strong>both</strong> arrays and linked lists (thus 2 operations x 2 structures x 2 implementations, or 8 values).</p>
  
  <p>Additionally, I'd appreciate best, average and worst case values for both of these, and anything relating to the amount of space they consume.</p>
  
  <p>The closest thing I've been able to find is this "mother of all cs cheat sheets" pdf that  is clearly a masters- or doctoral-level cheat sheet of advanced algorithms and discrete functions.</p>
  
  <p><strong>I'm just looking for a way to determine when and where I should use an array-based implementation vs. a list-based implementation for both stacks and queues.</strong></p>