Data Structure Arora Educator
Linear Data Structure = रै खिक डेटा संरचना Arora Educator
Stack –
Write the postfix notation for following expression.
(A+B)*C-(D-E)^F Arora Educator
(AB+)*C-(DE-)^(F) 1. (){}[] → Left to Right
(AB+)*(C)-(DE-F^) 2. ^ → Right to Left
(AB+C*)-(DE-F^) 3. */ → Left to Right
(AB+C*)(DE-F^)- 4. +- → Left to Right
AB+C*DE-F^-
Arora Educator
Queue –
Queue – Arora Educator
✓Like stack, queue is also an
ordered list of elements.
Queue – Arora Educator
✓ Queue is non-primitive & linear data
structure
✓ Queue follows = FIFO (first in first
out)
✓ Item added first removes first
✓ Item added at last removes last
Queue – Arora Educator
✓ In QUEUE both ends are open
✓ In stack only top end is open
✓ Queue has 2 end = front end & rear end
✓ Rear end = add items
✓ Front end = remove items
Operations of Queue = 5 Arora Educator
1) Enqueue
2) Dequeue
3) Peek
4) isEmpty
5) isFull
1- Enqueue एन्क्यू Arora Educator
Adding an element in a queue
2- Dequeue डी्यू
Deleting an item in a queue
3- Peek पीक
retrieves the value at the head of the
queue without removing it
4- isEmpty Arora Educator
Checks if the queue is empty
5- isFull
Validates if the queue is full
Applications of Queue Arora Educator
1) CPU scheduling- to keep track of processes
for the CPU
2) Handling website traffic - by implementing a
virtual HTTP request queue
3) Printer Spooling - to store print jobs
4) In routers - to control how network packets
are transmitted or discarded
5) Traffic management - traffic signals use
queues to manage intersections
Queue can be implemented Arora Educator
using
1) Array
2) Stack
3) Linked List
4) BFS = Breadth-First Search = Find
Shortest path
5) Radix Sort = Phone Number Sorting
The queue can be implemented in Arora Educator
two ways
1) Static implementation (using arrays)
2) Dynamic implementation (using linked list)
Types of Queue = 4 Arora Educator
1) Linear Queue/Simple Queue
2) Circular Queue
3) Priority Queue
4) Dequeue = Double Ended
Queue
1 - Linear Queue Arora Educator
✓ In Linear Queue, an insertion takes place
from one end while the deletion occurs
from another end
✓ end at which the insertion takes place is
known as the rear end
✓ end at which the deletion takes place is
known as front end
2 - Circular Queue / Ring Buffer Arora Educator
✓ last element of the queue is
connected to the first element.
✓ also known as Ring Buffer
3 - Priority Queue Arora Educator
✓ elements are arranged based on the priority.
✓ some elements occur with the same priority,
they will be arranged according to the FIFO
principle
4- Dequeue Arora Educator
✓ insertion and deletion can be done from
both ends of the queue either from the
front or rear
4- Dequeue Arora Educator
✓ Deque can be used as a palindrome
checker means that if we read the string
from both ends, then the string would be
the same.
Dequeue के दो प्रकार होते है Arora Educator
1) Input-restricted Dequeue
2) Output-restricted Dequeue
Input-restricted Dequeue Arora Educator
✓ insertion operation can be performed at only
one end, while deletion can be performed
from both ends
Output-restricted Dequeue
✓ deletion operation can be performed at
only one end, while insertion can be
performed from both ends.
Queue Rules = Queue is empty = कतार िाली है
1) Front = Rear = -1 Arora Educator
2) Front = Rear
3) Front > Rear
4) FRONT<0
5) Front = Null
Queue Rules = One element in queue Arora Educator
1) Front = Rear = 0 कतार में एक तत्व
2) Front = Rear
