Govt.
Madhav Science College Ujjain
Department of Computer Science And application
Stack & Queue
DATA STRUCTURES
PROF. ANIL KUMAR
PRAJAPATI
What is a stack?
◦ Stack is linear data structure, working in last in first
out(LIFO) manner. It is an Abstract Data Type
(ADT), commonly used in most programming
languages.
◦ In this type of data structure, we can extract the
date from the end from which we enter the data.
◦ Push operation is used to enter data in stack and
pop operation is used to remove data.
Stack Representation
Push Pop
Data Element 05 Top Top Data Element 05
Insertion Deletion
Data Element Data Element
04 04
Data Element Data Element
03 03
Data Element Data Element
02 02
Data Element Data Element
01 01
Algorithm for insert data into stack
Step 1. Check stack if full
If Top=Max-1
Print stack is full and exit
Step 2: Increment to by one Max
size
Top=Top+1 Push
Push 5 5
Step 3: Insert data into stack
Push 4 4 4
Stack[TOP]=data 3 3 3
Push 3
Step 4: End 2 2 2 2 2
Push
1 1 1 1 1 1
Push (Insert data item into Stack)
For inserting data item into stack we use push operation.
Data 1, Data 2, Data 3, Data 4, Data 5,
Push Insertion Insertion Insertion Insertion
Top
Top Data 4
Top Data 3 Data 3
Top Data 2 Data 2 Data 2
Data 1 Data 1 Data 1 Data 1
Algorithm for insert data into stack
Step 1: Check stack is empty
If TOP=-1
Print Stack is empty and Exit
Step 2: delete an element from stack top
Set Del_element=Stack[Top] Max
size Pop
Step 3: decrement stack size by one 5 5
Pop
Top=Top-1 4 4 4 Pop
3 3 3 3
Step 4: End Pop
2 2 2 2 2
1 1 1 1 1
Pop (Deleting data item from
Stack)
for deleting data item into stack we use Pop operation.
Data 1, Data 2, Data 3, Data 4, Data 5,
Deletion Deletion Deletion Deletion pop
Top
Data 4 Top
Data 3 Data 3 Top
Data 2 Data 2 Data 2 Top
Data 1 Data 1 Data 1 Data 1
What is Queue
A Queue is a linear structure which follows a particular order in
which the operations are performed. The order is First In First
Out (FIFO). In Queue the allocation of data are continuous
manner.
insertion and deletion is done from different ends in the Queue,
using rear for insertion and front for Dilation.
Queue having two different formats linear queue and circular
queue.
Types of Queue
broadly Queue are divided into two types such as linear and circular but
linear queue having also two different variations, double ended queue or
Dequeue and insertion restricted and deletion restricted.
Linear Queue
Front 10 20 30 40 50 Rear
Double Ended Queue
Circular Queue Rear Rear
10 20 30 40 50 Front
Front
10 Deletion restricted Queue
Rear Rear
60 20 Front 10 20 30 40 50 Rear
Front
Insertion restricted Queue
50 30 Rear
Front 10 20 30 40 50 Front
40
Insertion Data item into
Queue
To insert data element into queue, we use rear pointer all data element inserted only rear end.
Front
Algorithm for Insert an element into Queue Rear
Step 1: Check if the queue is full.
Front 10
If rear == max-size-1 Rear
Print Queue is full and exit Front 10 20
Step 2: Add and element into Queue Rear
SET REAR = REAR + 1 Front 10 20 30
Rear
Step 3: data element insert at rear pointer .
Front 10 20 30 40
Set QUEUE[REAR] = NUM Rear
Step 4: return success. Front 10 20 30 40 50
Rear
Deletion Data item From
Queue
To Delete data element from queue, we use front pointer all data elements delete
only front end.
Front 10 20 30 40 50
Algorithm for Delete an element From Queue Rear
Step 1: Check if the queue is Empty.
20 30 40 50
If FRONT == -1 or FRONT >REAR Front Rear
Print Queue is Empty and exit
30 40 50
Step 2: Delete an data element from Queue Rear
Front
SET FRONT = FRONT + 1
40 50
Step 3: data element insert at rear pointer . Front Rear
Set Data element = QUEUE[FRONT]
50
Step 4: return success. Front Rear
Circular Queue
Circular Queue is a linear data structure in
which the operations are performed based
on FIFO (First In First Out) principle and
the last position is connected back to the
first position to make a circle. Circular
queue also follow contiguous allocation of
data element. In the circular queue, for
insertion and deletion we use rear and front
pointer like linear queue
Thanks and Regards:
Anil Kumar Prajapati
