CHAPTER 5 - QUEUE
PRESENTED BY ; DR THANAA MOHAMED HASSAN
QUEUE
A queue is a linear data structure that follows
the First In, First Out (FIFO) principle, which
means the first element added to the queue is
the first one to be removed.
Queue can be
implemented using
either arrays or linked
lists, depending on the
specific requirements
of the application.
KEY FEATURES OF A QUEUE
FIFO (First In, First Out): Elements are removed in the
same order in which they were added.
Enqueue Operation: Adding an element to the rear
(end) of the queue.
Dequeue Operation: Removing an element from the
front (beginning) of the queue.
Peek/Front Operation: Viewing the front element of the
queue without removing it.
IsEmpty Operation: Checking if the queue is empty.
COMMON QUEUE OPERATIONS:
• Enqueue(x): Insert element x to the rear of the
queue.
• Dequeue(): Remove the front element from
the queue.
• Peek()/Front(): Return the front element
without removing it.
• IsEmpty(): Check if the queue is empty.
• Size(): Return the number of elements in the
QUEUE DEPENDING ON LINKED LIST
Data:The information or value that the node holds.
Pointer/Reference: A reference (or pointer) to the next
node in the stack.
The Front of the linked list refers to the first node,
while the Tail/rear is a last node's pointer (in a singly
linked list) points to nullptr or None (indicating the end of
the list).
REPRESENTATION OF QUEUE (ENQUEUE)
REPRESENTATION OF QUEUE
A queue can be visualized as a horizontal structure with
elements being added on the rear and removed from the
front.
Front -> [ 1 ] -> [ 2 ] -> [ 3 ] -> [ 4 ] -> [ 5 ] -> Rear
In this queue, 1 is at the front, and it will be the first
element removed if a dequeue operation is called.
QUEUE IMPLEMENTATION
1. Node Creation
Each node has:
•prev → link to previous node
•value → data
•next → link to next node
QUEUE IMPLEMENTATION
2. Queue Initialization
We start with an empty queue:
3. Check If Queue is Empty
If head is None, the queue has no elements.
QUEUE IMPLEMENTATION
4. Enqueue (push_back) → Add to Last
Steps:
[Link] queue is empty → new node is both head and tail
[Link]:
•Create new node
•Link it to the old tail
•Update tail
QUEUE IMPLEMENTATION
5. Display Queue From Head
We start from head and follow each node’s next.
QUEUE IMPLEMENTATION
6. Dequeue (pop_front) → Remove From First
Steps:
[Link] empty → do nothing
[Link] only one node → head and tail become None
[Link] → move head to next node and remove old one
PART 2: QUEUE USING PYTHON’S DEQUE (SIMPLEST
METHOD)
Python has a built-in queue structure in [Link].
1. Create Queue
4. Check if Empty
2. Enqueue (Add to last)
5. Print Queue Length
3. Deque (Remove from first)
WHAT IS THE OUTPUT
Trees Introduction
Trees Terminology
Trees Terminology
Root
Edge
Parent Node
Child Node
Siblings
Degree
Internal Node
Leaf Node
Level
Height
Depth
Sub Tree
Sub Tree
MCQ
1. Multiple Choice Questions (MCQs) Q3: A node that has the same parent as another node
is called:
Q1: In a tree, the topmost node is called: a) Child
a) Leaf b) Sibling
b) Root c) Root
c) Child d) Descendant
d) Sibling Q4: The level of a tree is:
Q2: Nodes with no children are called: a) The number of children a node has
a) Parent nodes b) The distance from the root node
c) The total number of nodes
b) Leaf nodes
d) The height of the tree
c) Root nodes
d) Ancestors Q5: The longest path from the root to a leaf is called:
a) Depth
b) Height
c) Level
d) Degree
EXERCISE
THANK YOU ☺