Day 15 of 30 days of Data Structures and Algorithms and System Design Simplified —Queue
Welcome back peeps. Hope all’s well. In this post we will cover Queue as follows —
What and Why Queue(in 2–3 sentences)?
How does Queue work?
Important Patterns and Techniques in Queue Questions
Most Important Questions with Solutions
Tips and Techniques to solve Queue Questions Fast.
Projects Videos —
All the projects, data structures, SQL, algorithms, system design, Data Science and ML , Data Analytics, Data Engineering, , Implemented Data Science and ML projects, Implemented Data Engineering Projects, Implemented Deep Learning Projects, Implemented Machine Learning Ops Projects, Implemented Time Series Analysis and Forecasting Projects, Implemented Applied Machine Learning Projects, Implemented Tensorflow and Keras Projects, Implemented PyTorch Projects, Implemented Scikit Learn Projects, Implemented Big Data Projects, Implemented Cloud Machine Learning Projects, Implemented Neural Networks Projects, Implemented OpenCV Projects,Complete ML Research Papers Summarized, Implemented Data Analytics projects, Implemented Data Visualization Projects, Implemented Data Mining Projects, Implemented Natural Leaning Processing Projects, MLOps and Deep Learning, Applied Machine Learning with Projects Series, PyTorch with Projects Series, Tensorflow and Keras with Projects Series, Scikit Learn Series with Projects, Time Series Analysis and Forecasting with Projects Series, ML System Design Case Studies Series videos will be published on our youtube channel ( just launched).
Subscribe today!
System Design Case Studies — In Depth
Design Instagram
Design Messenger App
Design Twitter
Design URL Shortener
Design Dropbox
Design Youtube
Design API Rate Limiter
Design Web Crawler
Design Facebook’s Newsfeed
Design Yelp
Design Uber
Design Tinder
Design Tiktok
Design Whatsapp
Most Popular System Design Questions
Mega Compilation : Solved System Design Case studies
Queue
Importance : High
Note : New Queue questions with solutions are added every day. So keep checking this post daily.
Let’s dive in!
What is Queue?
Queue is a data structure which is open at both the end ( front and rear) and the operations such as enqueue( add the element ), dequeue (remove the element) etc happen in the FIFO fashion.
It follows FIFO rule i.e first in first out.
Examples of Queue problems —
Time and Tasks
Priority tasks and CPU
Ordered Streams
Encode and Decode strings
Implement Queue using Stacks
Find Min/Max in the sliding window List
Implement stacks using queues
Circular Queues
Max no of tasks that you can do in the given time
Tickets and Stations etc
How does Queue work?
Queues are implemented using an array or a linked list, with operations such as enqueue (adding an element to the tail of the queue) and dequeue (removing the element from the head of the queue) being the most common.
There are two pointers that are used in the Queues — Front and Rear
Front keeps a tap on the first element of the queue
Rear keeps a tap on the last element of the queue
Initially, they are both set to a default index of -1
There are five operations that one can perform using queues —
Enqueue : Add an element to the end/rear of the queue
Dequeue: Delete/Remove an element from the front of the queue
IsFull : To check if the queue is full
IsEmpty : To check if the queue is empty
Peek : To get the value from the front of the queue without removing/deleting it
Important Patterns and Techniques in Queue Questions
Important patterns and techniques in queue questions include understanding the basic operations of a queue, such as enqueue and dequeue, and using queues in the design of algorithms, such as breadth-first search. Additionally, It’s important to understand the difference between Queue and Stack(which follows LIFO ordering) and when to use them.
Queues have two main pointers and two main functions —
Front pointer : Pointing to first element
Rear Pointer: Pointing to the last element
Enqueue function : Add an element to the queue
Dequeue function: Delete/Remove an element from the queue
Before add/removing, one needs to check if the queue is full or empty respectively.
Patterns → Questions like below belong to Queue( not limited to):
Graph Traversals
Tree Traversals
Implement Queue using Stacks
Find Min/Max in the sliding window List
Implement stacks using queues
Circular Queues
Max no of tasks that you can do in the given time
Tickets and Stations etc
Most Important Questions with Solutions
Note : New Queue questions with solutions are added every day. So keep checking this post daily.
Golden rule is — Learn by doing/implementing
In this we will see most important Queue questions.
Implement Queue using Stacks
Question —
Implement a first in first out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue (push, peek, pop, and empty).
Implement the MyQueue class:
void push(int x)Pushes element x to the back of the queue.int pop()Removes the element from the front of the queue and returns it.int peek()Returns the element at the front of the queue.boolean empty()Returnstrueif the queue is empty,falseotherwise.
Example:
Input:
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 1, 1, false]Solution :
Main Logic/Idea —
The main logic is to know how to use append, extent and pop() methods. Stack is LIFO. So in order to implement Queues using stack, one needs pop from A stack and insert in the B stack and the return last element of B which is the front element of the queue.
Implementation —
class MyQueue:
# initialize your data structure here.
def __init__(self):
self.A, self.B = [], []# @param x, an integer
# @return nothing
def push(self, x):
self.A.append(x)# @return nothing
def pop(self):
self.peek()
return self.B.pop()
# @return an integer
def peek(self):
if not self.B:
while self.A:
self.B.append(self.A.pop())
return self.B[-1]
# @return an boolean
def empty(self):
return not self.A and not self.BQuestion Link
Similar Pattern —
Full Code Video Explanation ( In progress. Subscribe today for updates) :
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
Sliding Window Maximum
Question —
You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.
Return the max sliding window.
Example :
Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]Solution :
Main Logic/Idea —
The main logic is to use two pointers technique for window of size k and keep sliding as you compute the max for that particular window in each iteration. Keep appending the max to the final list and incrementing the pointers as you go.
Implementation —
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
ans, lptr,rptr = [],0,0
qu = collections.deque()
while rptr < len(nums):
while qu and nums[rptr] > nums[qu[-1]]:
qu.pop()
qu.append(rptr)
if qu[0] < lptr:
qu.popleft()
if k <= (rptr + 1):
ans.append(nums[qu[0]])
lptr += 1
rptr += 1
return ansQuestion Link
Similar Pattern —
Maximum Number of Robots Within Budget
Longest Substring with At Most Two Distinct Characters
Full Code Video Explanation ( In progress. Subscribe today for updates) :
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
Implement Stack using Queues
Question —
Implement a last-in-first-out (LIFO) stack using only two queues. The implemented stack should support all the functions of a normal stack (push, top, pop, and empty).
Implement the MyStack class:
void push(int x)Pushes element x to the top of the stack.int pop()Removes the element on the top of the stack and returns it.int top()Returns the element on the top of the stack.boolean empty()Returnstrueif the stack is empty,falseotherwise.
Example :
Input:
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 2, 2, false]Solution :
Main Logic/Idea —
The main logic is to use the fact that queue is LIFO and stack is FIFO. In order to implement a stack using queues, one needs to pop the element from the inserted element from the queue and then insert it in another queue. So, in a way it becomes opposite queue to the original queue.
Implementation —
class Queue():
def __init__(self):
self.data=collections.deque()
def push(self,x):
self.data.append(x)
def pop(self):
return self.data.popleft()
def peek(self):
return self.data[0]
def size(self):
return len(self.data)
def empty(self):
return len(self.data)==0class MyStack(object):def __init__(self):
"""
Initialize your data structure here.
"""
self.q=Queue()def push(self, x):
"""
Push element x onto stack.
:type x: int
:rtype: void
"""
self.q.push(x)
for _ in range(self.q.size()-1):
self.q.push(self.q.pop())def pop(self):
"""
Removes the element on top of the stack and returns that element.
:rtype: int
"""
return self.q.pop()def top(self):
"""
Get the top element.
:rtype: int
"""
return self.q.peek()def empty(self):
"""
Returns whether the stack is empty.
:rtype: bool
"""
return self.q.empty()Question Link
Similar Pattern —
Count Submatrices With All Ones
Longest Increasing Subsequence II
Full Code Video Explanation ( In progress. Subscribe today for updates) :
Note : New Queue questions with solutions are added every day. So keep checking this post daily.
Complexity Analysis
Queues can be array bases as well as linked list based.
Enqueue Operation : O(1)
Dequeue Operation : O(1)
Peek operation : O(1)
Access element in the queue ( one which is not the first element): O(n)
Search in the Queue: O(n)
Tips and Techniques to solve Queue Questions Fast.
Main thing about queues is how to use front and rear pointers. So, before solving Queue related questions —
Know how to use/manipulate front and rear pointers
Know how to implement deque
Know how to check full and empty using length
Know how to use append, push and pop, empty operation ( check in the stack post)
If the queue is Linked List based then check Linked List post
That’s it for now. Day 16 : Binary Search coming soon !
Let me know if you have questions in the comment section below. Subscribe/ Follow, Like/Clap as it will encourage me to write more in my free time and Stay Tuned!!
Read More —
11 most important System Design Base Concepts
6. Networking, How Browsers work, Content Network Delivery ( CDN)
13. System Design Template — How to solve any System Design Question
Some of the other best Series —
30 days of Data Structures and Algorithms and System Design Simplified
Data Science and Machine Learning Research ( papers) Simplified **
100 days : Your Data Science and Machine Learning Degree Series with projects
Complete Data Visualization and Pre-processing Series with projects
Exceptional Github Repos — Part 1
Exceptional Github Repos — Part 2
Tech Newsletter —
If you are interested, you can join my newsletter through which I send tech interview tips, techniques, patterns, hacks — Software Development, ML, Data Science, Startups and Technology projects to more than 30K readers. You can subscribe to Tech Brew :
For Python Projects —
For complete 60 days of Data Science and ML : Day 1 — Day 60 : Quick Recap of 60 days of Data Science and ML
Follow for more updates. Stay tuned and keep coding!
For other projects, tune to —
Build Machine Learning Pipelines( With Code)
Recurrent Neural Network with Keras
Clustering Geolocation Data in Python using DBSCAN and K-Means
Facial Expression Recognition using Keras
Hyperparameter Tuning with Keras Tuner
Custom Layers in Keras
