Lecture 60: Introduction to Queues

Introduction

• Instructor: Love Babbar
• Channel: Code Help
• Topic: Queues (Data Structure)
• Aim: Learn various aspects of queues including their implementation

What is a Queue?

• Queue follows FIFO (First In First Out) principle
• Real-life example: ATM line, where the first person in line is the first served

Queue Operations

• push(): Insert elements at the rear
• pop(): Remove elements from the front
• size(): Get the size of the queue
• isEmpty(): Check if the queue is empty
• front(): Get front element
• rear(): Get rear element

Implementation in C++ using STL

• Declaration: queue<int> q
• Insert element: q.push(17)
• Remove element: q.pop()
• Get size: q.size()
• Check if empty: q.empty()
• Get front element: q.front()
• Get rear element: q.back()

Practical Implementation

• Create a queue with various operations
• Examples covered: pushing and popping elements, checking size, and checking whether it is empty

Implementing from Scratch

• Create a class for queue
• Data members: array, size, front, rear
• Methods: enqueue(), dequeue(), isEmpty(), front(), rear(), isFull()

Example: Circular Queue

• Front and rear both can wrap around to the beginning
• Cyclic nature allows better space utilization
• Conditions for being full: multiple conditions based on positions of front and rear
• Conditions for being empty: front equals rear
• Operations still maintain O(1) complexity

Doubly Ended Queue (Deque)

• Allows insertion and removal from both ends
• push_front(), push_back(), pop_front(), pop_back()
• Can perform operations typical of both stacks and queues
• Useful in CPU scheduling and other applications

Deque Implementation using STL

• Operations: dq.push_front(12), dq.push_back(14), dq.pop_front(), dq.pop_back(), dq.empty(), dq.front(), dq.back()
• Covered implementing a class with the logic for deque

Additional Concepts

• Input-restricted deque: Insertion allowed from rear, deletion from both ends
• Output-restricted deque: Insertion from both ends, deletion from front

Summary

• Discussed different types of queues and their operations
• Implemented a simple queue, circular queue, and deque
• Operations in O(1) complexity
• Encouraged to practice the concepts for better understanding

Next Steps

• Watch OS lectures for deeper understanding of CPU scheduling
• Practice coding and implementation of various queue types

Conclusion

• Video ends with discussion on T.C. (Time Complexity)
• Encouragement to leave comments and feedback

Video recorded at 1:29 am