D ATA S T R U C T U R E -
II
Stack and Queues
S TA C K
A stack is a collection of data items that can be
accessed at only one end, called top.
Items can be inserted and deleted in a stack only at the
top.
The last item inserted in a stack is the first one to be
deleted.
Therefore, a stack is called a Last-In-First-Out
(LIFO) data structure.
2 mains operations on Stack is P U S H & POP
P U S H means inserting new item at top and POP
means deleting item from top.
O THER S TACK T ERM
○ Peek : getting the most recent value of stack i.e
value at TOP
○ OverFlow : a situation when we are Pushing item in
Stack that is full.
○ Underflow : a situation when we are Popping
item from empty stack
I MPLEMENTING S TACK IN P YTHON
This function will
check Stack is
empty or not
This function will
add new item in
Stack, here setting
top is mandatory
This function is used
to remove item from
stack, also perform
checks before deletion
I MPLEMENTING S TACK IN P YTHON
This function will
return the top
most item from the
stack
This function will
display stack items
I MPLEMENTING S TACK IN P YTHON
Displaying menu
to user to interact
I MPLEMENTING S TACK IN P YTHON
QUEUE
○ Queue is a linear list which follows FIFO
approach.
○ Queue allows addition of element only at one end
called REAR (end of list) & Deletion of element
only from FRONT end (beginning of list).
○ The operation of addition and deletion is known as
Enqueue and Dequeue respectively.
○ Applications of Queue:
⚫ Printer Spooling
⚫ CPU Scheduling
⚫ Mail Service
⚫ Keyboard Buffering
⚫ Elevator
I MPLEMENTING Q U E U E IN P YTHON
:: Q U E U E O PERATIONS ::
○ Peek : getting first value of Q U E U E i.e. of
F R O N T position.
e.g. Queue[Front] # Front is an int storing index of first element of queue
○ Enqueue: addition of new item in Q U E U E at
R E A R position.
e.g. [Link](Item)
○ Dequeue: removal of item from the beginning of
QUEUE.
e.g. [Link](0)
P YTHON C ODE : Q U E U E
This function will
check Queue is
empty or not
This function will
add new item in
Queue, here setting
top is mandatory
This function is used
to remove item from
Queue, also perform
checks before deletion
P YTHON C ODE : Q U E U E
This function will
return the Front
item from the
Queue
This function will
display Queue
items
P YTHON C ODE : Q U E U E
Displaying menu
to user to interact
P YTHON C ODE : Q U E U E
V ARIATIONS OF QUEUE
○ Circular Queue : it is implemented in circular
form rather than straight line. It is used in many
programming language to overcome the problems of
linear queue (utilization of unused position in the
beginning).
○ Dequeue (Doubly-ended queue) : it is the form of
queue in which elements can be added or
removed from any end but not in the middle. It is of
2 type: (1) Input restricted (2) Output
restricted
⚫ Input restricted means insertion only at one end but
deletion from both end
⚫ Output restricted means deletion from one end and
insertion from both end