Queue
Queues are a linear data structure that store data in a “first in, first out” (FIFO) order. Unlike arrays, you cannot access elements by index and instead can only pull the next oldest element. This m
Last updated
Queues are a linear data structure that store data in a “first in, first out” (FIFO) order. Unlike arrays, you cannot access elements by index and instead can only pull the next oldest element. This m
Last updated
Implement a Queue class from scratch with an existing bug, the bug is that it cannot take more than 5 elements.
Implement a Queue using two stacks. You may only use the standard push()
, pop()
, and peek()
operations traditionally available to stacks. You do not need to implement the stack yourself (i.e. an array can be used to simulate a stack).
Queues are a linear data structure that store data in a “first in, first out” (FIFO) order. Unlike arrays, you cannot access elements by index and instead can only pull the next oldest element. This makes it great for order-sensitive tasks like online order processing or voicemail storage.
You can think of a queue as a line at the grocery store; the cashier does not choose who to check out next but rather processes the person who has stood in line the longest.
We could use a Python list with append()
and pop()
methods to implement a queue. However, this is inefficient because lists must shift all elements by one index whenever you add a new element to the beginning.
Instead, it’s best practice to use the deque
class from Python’s collections
module. Deques are optimized for the append and pop operations. The deque implementation also allows you to create double-ended queues, which can access both sides of the queue through the popleft()
and popright()
methods.
Advantages:
Automatically orders data chronologically
Scales to meet size requirements
Time efficient with deque
class
Disadvantages:
Can only access data on the ends
Applications:
Operations on a shared resource like a printer or CPU core
Serve as temporary storage for batch systems
Provides an easy default order for tasks of equal importance
Reverse first k elements of a queue
Implement a queue using a linked list
Implement a stack using a queue