Queue - Class 12 Computer Science - Chapter 4 - Notes, NCERT Solutions & Extra Questions
Renews every month. Cancel anytime
Your personal doubt-solving assistant
Chatterbot AI gives you 100% accurate answers to your questions in an instant.
Notes - Queue | Class 12 NCERT | Computer Science
Comprehensive Guide to Queue: Class 12 Computer Science Notes
Introduction to Queue
What is a Queue?
A queue is an ordered linear data structure that works on the principle of First In First Out (FIFO). This means that the first element added to the queue will be the first one to be removed. Think of a queue as a line of people standing at a ticket counter; the person who stands at the front of the line is the first to get the ticket and leave.
Real-Life Examples of Queue
Queues are not just theoretical concepts; they are around us in daily life:
Customer Service Centres: Calls are handled in a queue, where the caller who has been waiting the longest is attended first.
Highway Toll Booths: Vehicles line up and are serviced in the order they arrive.
FIFO Principle Explained
In a queue, the element entering first is at the front, while the element entering last is at the rear. This arrangement allows new elements to be added at the rear and removed from the front.
Queue - First In First Out (FIFO)
Operations on Queue
ENQUEUE Operation
The ENQUEUE operation adds a new element to the rear of the queue. For example, adding a customer's call at the end of a waiting line.
DEQUEUE Operation
The DEQUEUE operation removes an element from the front of the queue. For instance, when a customer's call is picked up by a customer service agent.
IS EMPTY Operation
This operation checks if the queue has any elements, helping to avoid errors when trying to dequeue from an empty queue.
IS FULL Operation
This operation checks if the queue has reached its maximum capacity, preventing overflow errors during enqueue operations.
PEEK Operation
The PEEK operation allows you to view the front element of the queue without removing it.
Flowchart of Queue Operations
Implementation of Queue using Python
Implementing a queue in Python is straightforward, thanks to Python's versatile list datatype.
Python List as a Queue
In Python, the list data type can be used to create and manage a queue.
Enqueuing Elements
def enqueue(myQueue, element):
myQueue.append(element)
Dequeueing Elements
def dequeue(myQueue):
if not isEmpty(myQueue):
return myQueue.pop(0)
else:
print("Queue is empty")
Checking if Queue is Empty
def isEmpty(myQueue):
return len(myQueue) == 0
Viewing Elements at the Front
def peek(myQueue):
if not isEmpty(myQueue):
return myQueue[0]
else:
print("Queue is empty")
return None
Applications of Queue in Real Life and Computer Science
Real-Life Applications
Customer Service Centres: Calls are put into a queue until they are answered.
Highway Toll Booths: Vehicles are serviced based on their arrival time.
Computer Science Applications
Print Queue Management: Manages multiple print jobs by placing them in a queue.
Job Scheduling in Operating Systems: Tasks are queued and processed in the order they arrive.
Handling Concurrent Web Server Requests: Useful when a web server needs to handle numerous simultaneously incoming requests.
Which of the following operations removes an element from the front of a queue?
Introduction to Deque
What is a Deque?
Deque (pronounced "deck") stands for Double-Ended Queue. Unlike a regular queue, elements can be added or removed from both the front and the rear ends. This makes deque a versatile data structure useful for implementing both queues and stacks.
Difference Between Queue and Deque
While queues restrict addition and removal of elements to specific ends (rear and front, respectively), deques allow these operations at both ends.
Applications of Deque
Browser History Management: Allows users to navigate forward and backward through their browsing history.
Do and Undo Operations in Text Editors: Enables efficient management of action history.
Operations on Deque
INSERTFRONT Operation
Inserts a new element at the front of the deque.
INSERTREAR Operation
Similar to enqueue, adds a new element at the rear of the deque.
DELETIONFRONT Operation
Removes an element from the front of the deque.
DELETIONREAR Operation
Removes an element from the rear of the deque.
Checking for Palindromes using Deque
Step-by-Step Algorithm
Traverse string from left to right.
Insert each character into the deque.
Remove and compare characters from both ends until the deque is empty or left with one character.
Python Implementation
def isPalindrome(inputString):
myDeque = list()
for char in inputString:
myDeque.append(char)
while len(myDeque) > 1:
if myDeque.pop(0) != myDeque.pop():
return False
return True
Implementation of Deque using Python
Python List as a Deque
Creating a deque in Python can be easily done with lists.
Inserting Elements at Front
def insertFront(myDeque, element):
myDeque.insert(0, element)
Inserting Elements at Rear
def insertRear(myDeque, element):
myDeque.append(element)
Deleting Elements from Front
def deletionFront(myDeque):
if not isEmpty(myDeque):
return myDeque.pop(0)
else:
print("Deque is empty")
Deleting Elements from Rear
def deletionRear(myDeque):
if not isEmpty(myDeque):
return myDeque.pop()
else:
print("Deque is empty")
Which operation adds a new element to the rear of a regular queue?
Summary
Queue is an ordered linear data structure that follows the FIFO strategy.
Deque allows insertion and deletion at both ends, making it versatile for implementing both queue and stack operations.
Essential operations like enqueue, dequeue, isempty, isfull, and peek allow efficient management of both queues and deques.
Python's dynamic lists make implementation of these operations straightforward and efficient.
By understanding the fundamental operations and diverse applications of queues and deques, students can leverage these data structures for a wide range of computational problems.
🚀 Learn more about Notes with Chatterbot AI
NCERT Solutions - Queue | NCERT | Computer Science | Class 12
Fill in the blank
a) _________ is a linear list of elements in which insertion and deletion takes place from different ends.
b) Operations on a queue are performed in ______________ order
c) Insertion operation in a queue is called _______________ and deletion operation in a queue is called . $\qquad$
d) Deletion of elements is performed from ___________________ end of the queue.
e) Elements 'A','S','D' and 'F' are present in the queue, and they are deleted one at a time, ____________ is the sequence of element received.
f) _________________ is a data structure where elements can be added or removed at either end, but not in the middle.
g) A deque contains ' $z$ ',' $x$ ', 'c', 'v' and 'b' . Elements received after deletion are ' $z$ ', 'b', 'v', 'x' and 'c'. _____________ is the sequence of deletion operation performed on deque.
a) Queue is a linear list of elements in which insertion and deletion takes place from different ends.
b) Operations on a queue are performed in FIFO (First-In-First-Out) order
c) Insertion operation in a queue is called enqueue, and deletion operation in a queue is called dequeue.
d) Deletion of elements is performed from the front end of the queue.
e) Elements 'A','S','D' and 'F' are present in the queue, and they are deleted one at a time, ASDF is the sequence of element received.
f) Deque (Double-Ended Queue) is a data structure where elements can be added or removed at either end, but not in the middle.
g) A deque contains 'z', 'x', 'c', 'v', and 'b'. Elements received after deletion are 'z', 'b', 'v', 'x', and 'c'. Front, Rear, Rear, Rear, Rear is the sequence of deletion operation performed on deque.
Compare and contrast queue with stack.
Queue and Stack are both linear data structures, but they differ primarily in how elements are added and removed:
Queue:
Utilizes the FIFO (First-In-First-Out) principle for element management.
Elements are enqueued at the rear (end) and dequeued from the front.
Real-world analogy: a line at a grocery store where the first person in line is the first to be served.
Stack:
Operates on the LIFO (Last-In-First-Out) principle.
Elements are added (pushed) and removed (popped) from the top of the stack.
Analogy: a stack of plates where only the top plate is accessible for both adding and removing.
Key Differences:
Order of Element Access: Stacks allow access to only one end whereas queues allow access at both ends.
Functionality: Stacks are simpler with two main operations (push and pop), while queues require additional complexity (e.g., maintaining two pointers for front and rear).
Usage: Stacks are used in scenarios like expression evaluation and backtracking (e.g., browser history), while queues are used in scheduling and buffering where order naturally matters, such as print queues or task scheduling.
Understanding these differences helps in selecting the appropriate data structure based on the problem's requirements.
How does FIFO describe queue?
FIFO (First-In-First-Out) describes the queue data structure's operational principle where the first element added to the queue is the first one to be removed. This is similar to everyday scenarios such as a line at a checkout or waiting list, where the first person to arrive is the first served. In terms of operations, it implies that new elements are added at the rear of the queue and removals occur at the front. This ensures that the order in which elements enter the queue is the same order they exit, defining a fair and predictable process for handling data.
Write a menu driven python program using queue, to implement movement of shuttlecock in it's box.
Below is a simple Python program that utilizes a queue to simulate the movement of shuttlecocks in a box, with basic operations such as adding or removing a shuttlecock. The queue operations are implemented to replicate how a shuttlecock taken out from the top has to be the one that went in first (FIFO principle).
def enqueue(queue, item):
queue.append(item)
print(f"Shuttlecock {item} added to the box.")
def dequeue(queue):
if not queue:
print("The box is empty. No shuttlecock to remove.")
else:
removed = queue.pop(0)
print(f"Shuttlecock {removed} removed from the box.")
def display(queue):
if not queue:
print("The box is currently empty.")
else:
print(f"Shuttlecocks in the box: {queue}")
def main():
queue = []
while True:
print("\n--- Shuttlecock Box Menu ---")
print("1. Add a shuttlecock to the box")
print("2. Remove a shuttlecock from the box")
print("3. Display shuttlecocks in the box")
print("4. Exit")
choice = input("Enter your choice: ")
if choice == '1':
item = input("Enter the shuttlecock identifier (e.g., S1, S2): ")
enqueue(queue, item)
elif choice == '2':
dequeue(queue)
elif choice == '3':
display(queue)
elif choice == '4':
print("Exiting the program. Thank you!")
break
else:
print("Invalid choice. Please choose a valid option.")
if __name__ == "__main__":
main()
How to Use the Program:
Add a shuttlecock to the box: Select this option to place a new shuttlecock inside the box.
Remove a shuttlecock from the box: This removes a shuttlecock following the FIFO order.
Display shuttlecocks in the box: Lists all the shuttlecocks currently inside the box.
Exit: Closes the program.
This program runs in a loop and allows the user to interactively manage shuttlecocks in a box using a command line menu, embodying the queue's FIFO functionality.
How is queue data type different from deque data type?
The Queue and Deque data structures have several key differences:
Operations at Ends:
A Queue allows operations at two distinct points: elements are added at the rear (or back) and removed from the front. This strict operation protocol supports the FIFO (First-In-First-Out) principle.
A Deque (Double-Ended Queue) allows elements to be added or removed from both the front and the rear. This flexibility enables it to act as both a queue and a stack.
Flexibility:
Queues are less flexible as they only allow element interaction at two ends for specific operations: enqueue (rear) and dequeue (front).
Deques offer more flexibility by allowing insertion and removal of elements from either end (front or rear), which supports a variety of usage patterns.
Use Cases:
Queues are typically used in scenarios where you need to maintain the order of operations in exactly the same sequence that they arrive, like in service queues where the first customer in line is the first served.
Deques can be used in more complex scenarios where you might need to add or remove items from both ends of the collection, like navigating browser history (forward and backward) or implementing certain algorithms that require frequent insertions and deletions from both ends.
Implementation:
Both can be implemented using arrays or linked lists in a programming context, but the operations allowed on a deque generally make it a more complex data structure to implement effectively as compared to a queue.
Summary: A queue strictly adheres to FIFO order and operations are restricted to enqueueing at the rear and dequeuing from the front. A deque, on the other hand, provides more operational freedom by allowing adding and removing of elements from both ends.
Show the status of queue after each operation
enqueue(34)
enqueue(54)
dequeue( )
enqueue(12)
dequeue( )
enqueue(61)
peek( )
dequeue()
dequeue( )
dequeue( )
dequeue( )
enqueue(1)
To show the status of the queue after each operation given in your list, we'll first simulate the operations of enqueue and dequeue and display the state of the queue after each operation. Let's break down these operations:
enqueue(34)
enqueue(54)
dequeue()
enqueue(12)
dequeue()
enqueue(61)
peek()
dequeue()
dequeue()
dequeue()
dequeue()
enqueue(1)
Let's implement this in Python.
def enqueue(queue, element):
queue.append(element)
def dequeue(queue):
if not isEmpty(queue):
return queue.pop(0)
else:
print("Queue is empty")
def isEmpty(queue):
return len(queue) == 0
def peek(queue):
if not isEmpty(queue):
return queue[0]
else:
print("Queue is empty")
# Initialize the queue
queue = []
# Applying the operations
enqueue(queue, 34)
print("After enqueue(34):", queue)
enqueue(queue, 54)
print("After enqueue(54):", queue)
dequeue(queue)
print("After dequeue():", queue)
enqueue(queue, 12)
print("After enqueue(12):", queue)
dequeue(queue)
print("After dequeue():", queue)
enqueue(queue, 61)
print("After enqueue(61):", queue)
print("Peek:", peek(queue))
dequeue(queue)
print("After dequeue():", queue)
dequeue(queue)
print("After dequeue():", queue)
dequeue(queue)
print("After dequeue():", queue)
enqueue(queue, 1)
print("After enqueue(1):", queue)
This will give the following step-by-step status of the queue after each operation. Let's run this code to see the results.
Here are the statuses of the queue following the specified operations:
After
enqueue(34)
:[34]
After
enqueue(54)
:[34, 54]
After
dequeue()
:[54]
(34 is removed)After
enqueue(12)
:[54, 12]
After
dequeue()
:[12]
(54 is removed)After
enqueue(61)
:[12, 61]
Peek:
12
(shows the front without removal)After
dequeue()
:[61]
(12 is removed)After
dequeue()
:[]
(61 is removed)Attempt to
dequeue()
on an empty queue: No change, queue remains empty and prints "Queue is empty, cannot dequeue."After
enqueue(1)
:[1]
Note: Attempts to dequeue()
from an already empty queue resulted in the print statement "Queue is empty, cannot dequeue." showing correct error handling for underflow situations.
Show the status of deque after each operation
peek ( )
insertFront(12)
insertRear(67)
deletionFront()
insertRear(43)
deletionRear()
deletionFront()
deletionRear()
def peek(myDeque):
if not isEmpty(myDeque):
return myDeque[0]
else:
return "Deque is empty"
def insertFront(myDeque, element):
myDeque.insert(0, element)
def insertRear(myDeque, element):
myDeque.append(element)
def deletionFront(myDeque):
if not isEmpty(myDeque):
return myDeque.pop(0)
else:
return "Deque is empty"
def deletionRear(myDeque):
if not isEmpty(myDeque):
return myDeque.pop()
else:
return "Deque is empty"
def isEmpty(myDeque):
return len(myDeque) == 0
# Initialize deque
myDeque = []
# Perform operations and show status after each
operations = [
("peek()", peek),
("insertFront(12)", lambda dq: insertFront(dq, 12)),
("insertRear(67)", lambda dq: insertRear(dq, 67)),
("deletionFront()", deletionFront),
("insertRear(43)", lambda dq: insertRear(dq, 43)),
("deletionRear()", deletionRear),
("deletionFront()", deletionFront),
("deletionRear()", deletionRear)
]
# Dictionary to store the results of each operation
results = {}
# Performing operations
for name, operation in operations:
results[name] = operation(myDeque), list(myDeque)
results
This code will sequentially execute the deque operations: peek, insertFront, insertRear, deletionFront, insertRear, deletionRear, deletionFront, and deletionRear. After each operation, the code captures the result of the operation and the state of the deque, storing these in a dictionary for display.
Write a python program to check whether the given string is palindrome or not, using deque. (Hint : refer to algorithm 4.1)
Below is a Python program that uses a deque to check whether a given string is a palindrome. This program follows the steps outlined in Algorithm 4.1 from the text.
def is_palindrome(s):
# Create an empty deque
deque = []
# Step 1 & 2: Traverse the string and insert each character to rear of deque
for char in s:
deque.append(char)
# Step 4 & 5: Check characters from both ends
while len(deque) > 1:
front_char = deque.pop(0) # Remove front element
rear_char = deque.pop() # Remove rear element
if front_char != rear_char:
return False
return True
# Get input string
input_string = input("Enter a string to check for palindrome: ")
# Check if the string is a palindrome
if is_palindrome(input_string):
print(f"'{input_string}' is a palindrome.")
else:
print(f"'{input_string}' is not a palindrome.")
How it works:
Initialization: An empty deque is created.
Loading Deque: The string is traversed, and each character is added to the rear of the deque.
Palindrome Check: Characters are removed from both the front and rear. If these characters are not the same, the string is not a palindrome.
Final Check: If all matched characters are identical while deque has more than one character, or if the deque is emptied, the string is a palindrome.
💡 Have more questions?
Ask Chatterbot AI