One Pager Cheat Sheet

• A queue is a collection of items whereby its operations are arranged in a FIFO (First In First Out) format and involve two main operations: enqueue and dequeue.
• The queue is a data structure with two open ends, the rear for adding elements and the front for removing them, which follows the First In First Out (FIFO) principle.
• Queues work on the First In First Out (FIFO) principle of enqueuing and dequeuing elements.
• A Queue has two main operations - Enqueue to add elements and Dequeue to remove elements.
• The enqueue operation adds elements to the rear end of the queue, and updates the front and rear pointer accordingly.
• To dequeue an element from a queue, it is removed from the front end, if it is present, and at least one element must be in the queue for it to be possible.
• Dequeuing an element from the queue does not affect the front pointer, which remains the same, pointing at the first element added, while the rear pointer increases with new elements.
• We can implement queues using a list, collections.deque, or queue.Queue in python, with the list involving costly O(n) time complexity but with the use of the round-robin technique also requiring O(1) time, or using collections.deque or queue.Queue requiring O(1) time complexity.
• The complexity of implementing a queue with a list class in any programming language is O(n) due to the time needed to shift all items on each addition or deletion.
• We can quickly enqueue and dequeue items in a queue using most languages by either using a list or array, or with more efficient time complexity by implementing a fixed-sized list with two pointers.
• The Linked List implementation of Queues is similar to the Linked List implementation of Stacks we used previously.
• The python library provides the queue class from the Queue module to enable users to implement simple queues and check for the empty and full conditions using the empty() and full() functions respectively.
• We can implement a queue using the deque class from the collections module to append() and popleft() elements from the queue.
• The deque class from the collections module can be used to popleft() the first element and reduce the size of the queue in Python.
• The FIFO approach and using collections are effective approaches for implementing queues in python.