TECHQueenUnacademy
Computer Science
Notes: Queue Grade: 12th
Queue:
A queue is a linear data structure that follows the First In First Out (FIFO)
principle. This means that the first element inserted into the queue is the
first element to be removed.
Queues can be implemented using arrays or linked lists. In an array-based
implementation, the queue is represented as a contiguous block of
memory. The front of the queue is the index of the first element in the array.
In a linked list-based implementation, the queue is represented as a linked
list of nodes. Each node contains a data item and a pointer to the next
node. The front of the queue is the node that points to the null pointer.
Operations on Queue (INSERT and DELETE):
The two main operations on a queue are insert and delete.
● Insert adds an element to the end of the queue.
● Delete removes an element from the front of the queue.
The insert operation is implemented as follows:
1. Increment the rear of the queue pointer.
2. Store the new element at the rear of the queue.
The delete operation is implemented as follows:
1. Decrement the front of the queue pointer.
2. Return the element at the front of the queue.
Lovejeet Arora
TECHQueenUnacademy
Implementation in Python:
The following code shows how to implement a queue in Python using a list.
Python
class Queue:
def __init__(self):
self.items = []
def insert(self, item):
self.items.append(item)
def delete(self):
return self.items.pop(0)
def is_empty(self):
return len(self.items) == 0
def peek(self):
return self.items[0]
Introduction to DQueue and its implementation in Python:
A double-ended queue (DQueue) is a data structure that supports both
insertion and deletion at both the front and the rear of the queue.
DQueues can be implemented using arrays or linked lists. In an
array-based implementation, the DQueue is represented as a contiguous
block of memory. The front and rear of the DQueue are the indices of the
first and last elements in the array, respectively.
In a linked list-based implementation, the DQueue is represented as a
linked list of nodes. Each node contains a data item and pointers to the
previous and next nodes. The front and rear of the DQueue are the nodes
that point to the null pointer and the node that points to the previous node,
respectively.
Lovejeet Arora
TECHQueenUnacademy
Operations on DQueue:
The following operations can be performed on a DQueue:
● InsertFront adds an element to the front of the DQueue.
● InsertRear adds an element to the rear of the DQueue.
● DeleteFront removes an element from the front of the DQueue.
● DeleteRear removes an element from the rear of the DQueue.
● IsEmpty checks if the DQueue is empty.
● PeekFront returns the element at the front of the DQueue without
removing it.
● PeekRear returns the element at the rear of the DQueue without
removing it.
Implementation in Python
The following code shows how to implement a DQueue in Python using a
list.
Python
class DQueue:
def __init__(self):
self.items = []
def insert_front(self, item):
self.items.insert(0, item)
def insert_rear(self, item):
self.items.append(item)
def delete_front(self):
return self.items.pop(0)
def delete_rear(self):
return self.items.pop()
def is_empty(self):
return len(self.items) == 0
def peek_front(self):
Lovejeet Arora
TECHQueenUnacademy
return self.items[0]
def peek_rear(self):
return self.items[-1]
****
Lovejeet Arora
