loading...

Queues

jjb profile image JB Updated on ・2 min read

CS Level Up Series (30 Part Series)

1) CS Level Up Series Introduction 2) Dynamic Arrays 3 ... 28 3) Linked Lists 4) Stacks 5) Queues 6) Hash Tables 7) Binary Search Trees 8) Binary Heaps 9) Priority Queues 10) Graphs 11) Tries 12) Binary & Bit Manipulation 13) Common Sorting Algorithms 14) Searching Algorithms 15) Permutations, Combinations, & Subsets 16) NP-Complete & Fibonacci Heap 17) Detecting Graph Cycles With Depth-First Search 18) Finding Shortest Paths In Graphs (using Dijkstra's & BFS) 19) Topological Sorting of Directed Acyclic Graphs (DAGs) 20) Finding Articulation Points & Bridges in Undirected Graphs 21) Finding Strongly Connected Components in Directed Graphs using Tarjan's Algorithm 22) Checking If An Undirected Graph Is Bipartite 23) Extending An Iterator 24) Union-find (Disjoint-set) 25) Minimum Spanning Tree (Kruskal's Algorithm) 26) Sliding Window Technique 27) String Searching Using Rabin-Karp 28) Fenwick Tree (Binary Indexed Tree) 29) Dynamic Programming 30) Traveling Salesman Problem

Resources

  1. Queue overview
  2. Queue implementation
  3. Queue overview and implementation

Takeaways:

  • Queues, like IRL (except when a Chat & Cut occurs), are FIFO (First In First Out). As opposed to Stacks, which are LIFO (see previous post).
  • Like Stacks, Queues have fast operations: adding (enqueuing), removing (dequeuing), and checking the front (peeking) are all O(1) (constant).
  • Like Stacks, a Queue's space is O(n) (linear).
  • Queues can be implemented using arrays, but it's not a great idea* (my implementation is using an array for simplicity). They can also be implemented with Linked Lists.

*The dequeue operation is O(n) when using an array. This is because all the elements of the array need to be moved towards the front. In a Linked List implementation, just the Head node needs to get removed, and whatever node it pointed to made the new Head. This is further explained in the Brilliant article.

A good real-world use case for Queues, per InterviewCake:

Printers use queues to manage jobs—jobs get printed in the order they're submitted

Below you'll find the finished implementation with test code. Please note that the implementation is very simplistic. Elements are never actually removed from the array (as with my prior Stack implementation) - this also means the dequeue doesn't move any elements to the front and is O(1):

As always, if you found any errors in this post please let me know!

CS Level Up Series (30 Part Series)

1) CS Level Up Series Introduction 2) Dynamic Arrays 3 ... 28 3) Linked Lists 4) Stacks 5) Queues 6) Hash Tables 7) Binary Search Trees 8) Binary Heaps 9) Priority Queues 10) Graphs 11) Tries 12) Binary & Bit Manipulation 13) Common Sorting Algorithms 14) Searching Algorithms 15) Permutations, Combinations, & Subsets 16) NP-Complete & Fibonacci Heap 17) Detecting Graph Cycles With Depth-First Search 18) Finding Shortest Paths In Graphs (using Dijkstra's & BFS) 19) Topological Sorting of Directed Acyclic Graphs (DAGs) 20) Finding Articulation Points & Bridges in Undirected Graphs 21) Finding Strongly Connected Components in Directed Graphs using Tarjan's Algorithm 22) Checking If An Undirected Graph Is Bipartite 23) Extending An Iterator 24) Union-find (Disjoint-set) 25) Minimum Spanning Tree (Kruskal's Algorithm) 26) Sliding Window Technique 27) String Searching Using Rabin-Karp 28) Fenwick Tree (Binary Indexed Tree) 29) Dynamic Programming 30) Traveling Salesman Problem

Posted on Nov 6 '19 by:

Discussion

markdown guide