notes

Unnamed repository; edit this file 'description' to name the repository.
Log | Files | Refs

stack_and_queue.txt (875B)

      1 ===============================================================================
      2 Stack and Queue
      3 ===============================================================================
      4 
      5 Stack is Last In First Out (LIFO) -> suitable for Breadth-first search
      6 
      7 Queue is First In First out (FIFO) -> suitable for Depth-first search
      8 
      9 ---
     10 
     11 Depth-first search can be used for recursion.
     12 
     13 ---
     14 Queue
     15 
     16 Queue is like a linked-list where each element link to the next, so each
     17 lookup will need to check allocation, i.e. O(n).
     18 
     19 To reach index k you start at the head and follow k pointers, so the cost is proportional to k, bounded by n. One traversal, one pass.
     20 
     21 Where O(n²) does show up is when you repeat that access in a loop:
     22 
     23 for i in 0..n {
     24     print(list.get(i));   // each get is O(n)
     25 }
     26 
     27 ---
     28 Vec
     29 
     30 Whereas a Vec is like an array with continguous memory allocation, so each
     31 lookup is O(1)