Data Structures and Algorithms-

PCCST303(2024 SCHEME)

MODULE 1
SAJANA.A
CE,KARUNAGAPPALLY
Module 1:
Basic Concepts of Data Structures

Definitions; Data Abstraction; Performance Analysis - Time & Space

Complexity, Asymptotic Notations; Polynomial representation using

Arrays, Sparse matrix (Tuple representation); Stacks and Queues - Stacks,

Multi-Stacks, Queues, Circular Queues, Double Ended Queues; Evaluation

of Expressions- Infix to Postfix, Evaluating Postfix Expressions.

1.1 Basic Concepts of Data Structures

A data structure is a way to organize, manage, and store data so that it can be used efficiently.
It defines how data is arranged in memory and how operations like insertion, deletion, searching, and
updating can be performed.

Data structures are like containers that hold data together in a certain format so that computers
can easily access and modify them.

➔ Key points:
● Organization of data.
● Logical relationship between data elements.
● A set of operations that can be applied (like insert, delete, search,
etc.).
● Data Structure is a way of collecting and organising data in such a way that we can
perform operations on these data in an effective way.
● It represents the knowledge of data to be organized in memory.
● A data structure is a particular way of organizing data in a
computer
● A data structure is a specialized format for organizing,
processing, retrieving and storing data.
Key Points about Data Structures:

● They help in organizing large amounts of data easily.

● They improve the efficiency of algorithms.
● They decide how fast and efficiently programs work.
● Different problems need different data structures for best
performance.
Types of Data Structures:

Type Examples

Linear Data Structures Array, Linked List, Stack, Queue

Non-linear Data Structures Tree, Graph

Hash-based Structures Hash Table, Hash Map

Arrays
stack
Queue
 Hash tables

Tree/graph
1.2 Data Abstraction

Data Abstraction in data structures means hiding the low-level details of how data is
stored and focusing only on what operations can be performed on the data. It separates
what a data structure does from how it does it. You use the data structure without
worrying about its internal implementation.
● Abstraction = Hiding complexity, showing only the necessary operations.
● Like driving a car, you don't need to know how the engine works to drive.
Similarly, when you use a Stack, you only care about push and pop, not how the
stack is maintained internally.

➔ Key points:

● Focus on what the data can do, not how it does it.
● Helps in creating Abstract Data Types (ADTs).
● Implementation details are hidden from the user
Concepts in Data Abstraction:
● Abstract Data Types (ADT):
Data abstraction leads to the concept of an ADT, where only essential operations are exposed.
● Interface vs Implementation:
○ Interface: What you can do (e.g., Insert, Delete, Search)
○ Implementation: How it is done (e.g., using an array or linked list)

Advantages of Data Abstraction in Data Structures:

● Makes programming easier and error-free.
● Allows you to change the internal implementation without affecting users.
● Encourages modularity and code reuse.
1.3 Performance Analysis

Performance analysis means studying how efficient an algorithm or

data structure is.
Mainly, we check two things:
● Time Complexity — How much time (number of operations) the
algorithm takes.
● Space Complexity — How much memory (space) the algorithm uses.
✅ Goal:
To predict how the algorithm will behave as the input size grows
without running the code.
The Memory Requirement/space complexity

Whenever a solution to a problem is written some memory is required

to complete. For any algorithm memory may be used for the following:

1. Variables (include the constant values, temporary values)

2. Program Instruction
3. Execution
Space Complexity
➢ Space complexity = The amount of memory required by an
algorithm to run to completion.
• Two part :
1. Fixed part: independent of Input & output characteristics:
● Instruction space
● space for variables
● space for constants & so on
2. Variable part: Space needed by variables, whose size is dependent on the
size of the problem:
● Space needed by referenced variables,
● recursion stack space,etc
Calculation

S(p)=C+Sp

Let p be the algorithm

S(p) :space complexity
C:fixed space When analyzing the space complexity of a program,we are usually
concerned with only the variable space requirements.
Sp:variable space
example:
void main()
• Variables used are:
{
• Variable x: 1 word
int x,y,z,sum; • Variable y: 1 word
printf(“enter 3 numbers”); • Variable z: 1 word
• Variable sum: 1 word
scanf(“%d%d%d”,&x,&y,&z);
• Total space:4 word
Sum=x+y+z;
Printf(“%d”,sum);
}
Example
Algorithm Sum(a,n)
• Size variable n:1 word
{
• Loop variable i:1 word
S=0; • Sum variable s:1 word
• Array a values: n words
for i=1 to n • Total space:n+3 words
S=s+a[i];

Return s; }
Algorithm Sum(a,n)
{ S=0;

for i=1 to n
for j=1 to m
S=s+a[i][ j];
}
Algorithm Sum(a,n)
{ S=0;
Size variable n:1 word
• Loop variable i:1 word
for i=1 to n • Sum variable s:1 word
• Array a values: n*m words
for j=1 to m • Total space:nm+3 words
S=s+a[i][ j];
}
 Time Complexity

● Time complexity estimates the time to run an algorithm.

● It's calculated by counting elementary operations.

1. Time Complexity

● Measures the amount of time an algorithm takes to complete.

● It is expressed as a function of the input size n.
● We usually use Big-O notation (e.g., O(n), O(log n), O(n²)) to
express it.
⏳ Why it matters?
Because we want algorithms that are fast even for large inputs.
Best case, worst case and average case of an algorithm

• The best case implies minimum execution time that the algorithm would demand.

• The worst case implies maximum execution time.

• The average case indicates the behavior of the algorithm in an average situation.
Best Case Complexity

Let T1(n), T2(n), ... be the execution times for all

possible inputs of size n.
The best-case time complexity W(n) is then defined as

W(n) = min(T1(n), T2(n), . . .)

Worst Case Complexity

Let T1(n), T2(n), ... be the execution times for all

possible inputs of size n.
The worst-case time complexity W(n) is then defined as

W(n) = max(T1(n), T2(n), . . .)

Average Case Complexity

Let T1(n), T2(n), ... be the execution times for all possible inputs of size n, and let P1(n), P2(n), ... be the
probabilities of these

inputs.

The average-case time complexity is then defined as

P1(n)T1(n) + P2(n)T2(n) + . . .

Average-case time is often harder to compute, and it also requires knowledge of how the input is
distributed.
Types of Common Time Complexities:

Complexity Name Example

O(1) Constant time Accessing an array element

O(log n) Logarithmic time Binary search

O(n) Linear time Traversing an array

O(n log n) Linearithmic time Merge sort, Heap sort

O(n²) Quadratic time Bubble sort, Selection sort

O(2ⁿ) Exponential time Solving the Tower of Hanoi

1.4 ASYMPTOTIC NOTATIONS
● Complexity of an algorithm is usually a function of n.
● Behavior of this function is usually expressed in terms of one or more standard
functions.
● Expressing the complexity function with reference to other known functions is
called asymptotic complexity.

Three Basic notations are used to express the asymptotic complexity

1. Big– Oh Notation O : Upper bound of the algorithm
2. Big– Omega Notation Ω : Lower bound of the algorithm
3. Big– Theta notation Θ : Average bound of the algorithm
1. Big– Oh notation O
● Formal method of expressing the upper bound of an algorithm’s running
time.
● i.e. it is a measure of the longest amount of time it could possibly take for
an algorithm to complete.
● Itis used to represent the worst case complexity.
● f(n) =O(g(n)) if and only if there are two positive constants c and n0 such
that

● Then we say that “f(n) is big-O of g(n)”.

● When we say that the computing time of an algorithm is O(g(n)), we
mean that it's execution takes no more than a constant time g(n).
 Find upper bound of running time of constant function f(n) = 6993.

To find the upper bound of f(n), we have to find c and n0 such that f (n) ≤ c.g(n) for all n ≥ n0

f (n) ≤ c × g (n)

6993 ≤ c × g (n)

6993 ≤ 6993 x 1

So, c = 6993 and g(n) = 1

Any value of c which is greater than 6993, satisfies the above inequalities, so all such values of c are possible.

6993 ≤ 8000 x 1 → true

6993 ≤ 10500 x 1 → true

Function f(n) is constant, so it does not depend on problem size n. So n0= 1

f(n) = O(g(n)) = O(1) for c = 6993, n0 = 1

f(n) = O(g(n)) = O(1) for c = 8000, n0 = 1 and so on.

Find upper bound of running time of a linear function f(n) = 6n + 3.

Tabular Approach

f (n) ≤ c.g (n)

From Table, for n ≥ 3, f (n) ≤ c × g (n) holds true. So, c = 7, g(n) = n and n0 = 3, There can be such
multiple pair of (c, n0).
f(n) = O(g(n)) = O(n) for c = 9, n0 = 1

f(n) = O(g(n)) = O(n) for c = 7, n0 = 3

Derive the Big– Oh notation for f(n) = 2n + 3

Ans:
2n + 3<=2n+3n
2n+3 <= 5n
for all n>=1
Here c = 5 g(n) = n so,
f(n) = O(n)
HW
[Link] upper bound of running time of quadratic function f(n) = 3n2 + 2n + 4.
2. Find upper bound of running time of a cubic function f(n) = 2n3 + 4n + 5.
|f(n)|≤c.|g(n)|
f(n)≤n for n≥5
TC=O(𝒏𝟐)
2. Big– Omega notation (Ω)
● f(n) =Ω(g(n)) if and only if there are two positive constants c and n0 such that
f(n) ≥ c g(n) for all n ≥ n0.
● Then we say that “f(n) is omega of g(n)”.
● Here g(n) is the lower bound off(n)
 Find lower bound of running time of constant function f(n) = 23.

To find lower bound of f(n), we have to find c and n0 such that c × g(n) ≤ f(n) for all n ≥ n0

c × g(n) ≤ f(n)

c × g(n) ≤ 23

23.1 ≤ 23 → true

12.1 ≤ 23 → true

5.1 ≤ 23 → true

Above all three inequalities are true and there exists such infinite inequalities

So c = 23, c = 12, c = 5 and g(n) = 1. Any value of c which is less than or equals to 23, satisfies the above inequality, so all
such value of c are possible. Function f(n) is constant, so it does not depend on problem size n. Hence n 0 = 1

f(n) = Ω (g(n)) = Ω (1) for c = 23, n0 = 1

f(n) = Ω (g(n)) = Ω (1) for c = 12, n0 = 1 and so on.

Find lower bound of running time of a linear function f(n) = 6n + 3.

To find lower bound of f(n), we have to find c and n0 such that 0 ≤ c.g(n) ≤ f(n) for all n ≥ n0

c × g(n) ≤ f(n)

c × g(n) ≤ 6n + 3

6n ≤ 6n + 3 → true, for all n ≥ n0

5n ≤ 6n + 3 → true, for all n ≥ n0

Above both inequalities are true and there exists such infinite inequalities. So,

f(n) = Ω (g(n)) = Ω (n) for c = 6, n0 = 1

f(n) = Ω (g(n)) = Ω (n) for c = 5, n0 = 1

Find lower bound of running time of quadratic function f(n) = 3n2 + 2n + 4.

To find lower bound of f(n), we have to find c and n0 such that 0 ≤ c.g(n) ≤ f(n) for all n ³ n0

c × g(n) ≤ f(n)

c × g(n) ≤ 3n2 + 2n + 4

3n2 ≤ 3n2 + 2n + 4, → true, for all n ≥ 1

n2 ≤ 3n2 + 2n + 4, → true, for all n ≥ 1

Above both inequalities are true and there exists such infinite inequalities.

So, f(n) = Ω (g(n)) = Ω (n2) for c = 3, n0 = 1

f(n) = Ω (g(n)) = Ω (n2) for c = 1, n0 = 1

Find lower bound of running time of quadratic function f(n) = 2n3 + 4n + 5.
3. Big– Theta notation Θ
● f(n) =Θ(g(n)) if and only if there are three positive constants c1, c2 and n0 such
that c1 g(n) ≤ f(n) ≤ c2 g(n) for all n ≥ n0 .
● Then we say that “f(n) is theta of g(n)”.
● Gives average case TC
Find tight bound of running time of quadratic function f(n) = 3n2 + 2n + 4.

To find tight bound of f(n), we have to find c1, c2 and n0 such that, 0 ≤ c1 × g(n) ≤ f(n) ≤ c2 × g(n)
for all n ≥ n0

0 ≤ c1 × g(n) ≤ 3n2 + 2n + 4 ≤ c2 × g(n)

0 ≤ 3n2 ≤ 3n2 + 2n + 4 ≤ 9n2, for all n ≥ 1

Above inequality is true and there exists such infinite inequalities. So,

f(n) = Θ(g(n)) = Θ(n2) for c1 = 3, c2 = 9, n0 = 1

Derive the Big– Theta notation for
f(n) = 2n + 3
Ans:

1n <= 2n +3<=5n for all n>=1

Here c1 = 1 C2 =5
g1(n) and g2(n) = n so,
f(n) = Θ (n)
General problems
1. Show that : (i) 3n + 2 = Θ(n) (ii) 6*2n + n2 = Θ(2n)

(i) 3n + 2 = Θ(n)

2. Is 2n+1 = Ο(2n) ? Explain.

1.5 Polynomial Representation using Arrays
● A polynomial is a sum of terms where each term has the form aX^e,where x is
the variable, a is the coefficient and e is the exponent.
● 1ST METHOD
2nd Method
Diagramatic representation of a Polynomial
Using array
Points to keep in Mind while working with Polynomials:
● The sign of each coefficient and exponent is stored within the
coefficient and the exponent itself.
● Additional terms having equal exponent is possible one.
● The storage allocation for each term in the polynomial must be
done in ascending and descending order of their exponent.
Polynomial Addition Example:
1.6 Sparse Matrix
● In computer programming, a matrix can be defined with a 2-dimensional
array.
● Any array with 'm' columns and 'n' rows represent a m X n matrix.
● There may be a situation in which a matrix contains more number of ZERO
values than NON-ZERO values.
● Such matrix is known as sparse matrix.
● Sparse matrix is a matrix which contains very few non-zero elements.
● When a sparse matrix is represented with a 2-dimensional array, we waste
a lot of space to represent that matrix.
● For example, consider a matrix of size 100 X 100 containing only 10
non-zero elements.
Representing a sparse matrix by a 2D array leads to wastage of lots of
memory as zeroes in the matrix are of no use in most of the cases. So,
instead of storing zeroes with non-zero elements, we only store non-zero
elements. This means storing nonzero elements with triples- (Row, Column,
value).
Example:
00304
00570
00000
02600
Triplet Representation (Array Representation)
Why to use Sparse Matrix instead of simple matrix ?

● Storage: There are lesser non-zero elements than zeros and thus lesser
memory can be used to store only those elements.
● Computing time: Computing time can be saved by logically designing a data
structure traversing only nonzero elements..
 // Input matrix elements
#include <stdio.h>
printf("Enter matrix elements:\n");

for (i = 0; i < rows; i++) {

int main() { for ( j = 0; j < cols; j++) {

scanf("%d", &matrix[i][ j]);

int matrix[10][10], sparse[100][3];
}

int rows, cols, i, j, k = 1; }

// Display original matrix

// Input the matrix size printf("\nOriginal Matrix:\n");

for (i = 0; i < rows; i++) {

printf("Enter number of rows and columns: ");
for ( j = 0; j < cols; j++) {
scanf("%d %d", &rows, &cols); printf("%d ", matrix[i][ j]);

printf("\n");

}
// Convert to sparse matrix
sparse[0][2] = k - 1; // Total number of non-zero elements
// First row of sparse matrix = [rows, cols, non-zero count]

sparse[0][0] = rows;

sparse[0][1] = cols; // Display sparse matrix

printf("\nSparse Matrix (Row Column Value):\n");

for (i = 0; i < rows; i++) {

for ( j = 0; j < cols; j++) {

for (i = 0; i < k; i++) {

if (matrix[i][ j] != 0) { printf("%d %d %d\n", sparse[i][0], sparse[i][1], sparse[i][2]);

sparse[k][0] = i;
}
sparse[k][1] = j;

sparse[k][2] = matrix[i][ j];

k++; return 0;
}
}
}

}
Sparse matrix addition
Transpose of Sparse matrix
 0 1 2
0 4 5 5

0 2 1
1
0 4 3
2
1 3 4
3
2 1 7
4
3 2 6
5
1.7. STACK
● A stack is a linear data structure, in which items are added or removed only at
one end.
● It is named stack as it behaves like a real-world stack, for example – a deck of
cards or a pile of plates, etc.
Definition:– A stack is an ordered collection of homogeneous data
elements where the insertion and deletion operations take place only at
one end called top of the stack.
Two basic operations of stack:–
PUSH -> Insert an element at the top of stack
POP-> Delete an element from the top of stack
LIFO–
In stack elements are arranged in Last –In-First-Out manner– So it is also
called LIFO lists.
● A stack is a Last In, First Out (LIFO) data structure
● Anything added to the stack goes on the “top” of the stack
● Anything removed from the stack is taken from the “top” of the
stack
● Things are removed in the reverse order from that in which they
were inserted
● Placing a data item on the top is called “pushing”, while removing an item from
the top is called “popping” it.
● push and pop are the primary stack operations.
● An element in the stack is termed as ITEM.
● The maximum no. of elements that a stack can accommodate is termed SIZE.
Stack Representation

● Can be implemented by
means of Array, Structure,
Pointers and Linked List.
● Stack can either be a fixed
size or dynamic.
Stack using Array
Basic Idea
•In the array implementation, we would:
•Declare an array of fixed size (which determines the maximum
size of the stack).

•Keep a variable which always points to the “top” of the stack.

•Contains the array index of the “top” element.

81
Array representation of stack

5 4 17 877 3
Int A[5]
200 202 204 206 208

98 508
508
4
Int stack[5] 506 TOP
54
504
87
502
67
500
Basic Operations
● push() − Pushing (storing) an element on the stack.
● pop() − Removing (accessing) an element from the stack.
● peek() − get the top data element of the stack, without removing it.
● isFull() − check if stack is full.
● isEmpty() − check if stack is empty.
 bool isfull()
Basic Operations {
if(top == MAXSIZE)
int peek() return true;
else
{ return false;
}
return stack[top];

}
Basic operations
bool isempty()
{
if(top == -1)
return true;
else
return false;
}
Stack- Push Operation
The process of putting a new data element onto stack is known as a Push
Operation. Push operation involves a series of steps and follows.

Step 1 − Checks if the stack is full.

Step 2 − If the stack is full, produces an error and exit.

Step 3 − If the stack is not full, increments top to point next empty space.

Step 4 − Adds data element to the stack location, where top is pointing.

Step 5 − Returns success.

Push using Stack

PUSH
top
64
top
1087
Algorithm: PUSH()

Let A be an array with Maximum size as MAXSIZE. Initially, top=-1

1. Start
2. If top== MAXSIZE -1
3. print “OVERFLOW”
4. exit
5. else
6. top=top+1
7. Read the element to be inserted on stack top as “item”
8. Assign , A[top]=item
C Program for PUSH Operation The C implementation for Push operation follows void
push(int data)
{
if(!isFull())
{ top = top + 1;
stack[top] = data;
}
Else
{
printf("Could not insert data, Stack is full.\n");
}
}
Stack Pop Operations
● Accessing the content while removing it from the stack, is known as a Pop
Operation.
● In an array implementation of pop() operation, the data element is not actually
removed, instead top is decremented to a lower position in the stack to point
to the next value.
● But in linked-list implementation, pop() actually removes data element and
deallocates memory space.
A Pop operation may involve the following steps

Step 1 − Checks if the stack is empty.

Step 2 − If the stack is empty, produces an error and exit.

Step 3 − If the stack is not empty, accesses the data element at which top is
pointing.

Step 4 − Decreases the value of top by 1.

Step 5 − Returns success.

Pop using Stack

POP
top
64
top
10

92
Algorithm: POP()
Application of stack

● When a function call occurs , the return address is stored in stack

● Number system conversion
● Maintaining undo list for word document application
● Sorting
● Expression evaluation
● Expression conversion
● String reversal
● Used for implementing subroutines in general programming language.
Applications of Stacks
•Direct applications:
•Page-visited history in a Web browser
•Undo sequence in a text editor
•Chain of method calls in the Java Virtual Machine
•Validate XML

95
1.8 Multiple stacks
1.8 Multiple stacks
Why use Multistacks?
● To avoid wasting memory space by allocating multiple arrays for different stacks.

● To optimize memory usage and access time.

● To handle multiple stacks in applications like:

○ Multi-level undo features in applications.

○ Expression parsing (in compilers and calculators)
○ Browser history management.
○ Multi-threaded recursion management.
Types of Multi Stack Implementations

There are two common approaches to implement multi stacks:

1⃣ Fixed Division Method

● Divide a single array into fixed-sized parts, one for each stack.
● Each stack operates in its own fixed region.

Example:
For an array of size 12 and 3 stacks:
● Stack 1 → indices 0-3
● Stack 2 → indices 4-7
● Stack 3 → indices 8-11
Pros:

● Simple to implement.

Cons:
● Inefficient if stack sizes are unequal.

● Memory wastage if one stack is full and others are empty.

2. Flexible Division (Dynamic Sharing)
● Use a single array to dynamically hold all stacks.
● Track top elements and free spots using auxiliary structures.

Popular Example: K Stacks in an Array

Components:

● arr[] → actual data

● top[] → index of top element per stack Operations:
● next[] → links between elements, tracks free positions
● free → next available position ● Push:
○ Use free index
○ Update next[], top[], and free
● Pop:
○ Retrieve index from top[]
○ Update top[], next[], and free
Pros:

● Dynamic stack sizes

● Optimized memory usage

Cons:

● Complex implementation
● Requires extra memory for top[] and next[]
Applications of Multistacks

● Multi-tabbed browsers (tab histories)

● Undo/Redo features
● Expression evaluations
● Recursion management in multi-threaded programs
● Prefix Expression (Polish notation): The operators occurs before the operand
<operator> <operand> <operand>
Eg : +ab
● Postfix Expression (Reverse Polish notation): The operators occurs after the
operand
<operand> <operand> <operator>
Eg : ab+
Expression Evaluation Operations:
To evaluate expressions, we use stacks because:
● They work on Last In First Out (LIFO) principle
● Ideal for managing nested operations, precedence, and operands
 Postfix Expression Evaluation

Given P is the postfix expression, the following algorithm uses a stack to hold
operands. It finds the value of the arithmetic expression P, Written in postfix
notation.
Algorithm:
Step 1: Add “ ) “ at the end of P
Step 2: Scan P from left – right & repeat the steps 3 & 4
Step 3: If an operand occurs, PUSH it to stack.
Step 4: If an operator OP occurs, then
A: Remove the top elements of the stack.
When A is the top element and B is the next top element
B: Evaluate BOP A
C: Place the result of step B back to stack
Step 5: Set the value equals to TOP element of the stack.
1. Evaluate the expression 5 * ( 6 + 2 ) – 12 / 4
Ans : Convert to postfix notation
5 * 6 2 + - 12 / 4
5 6 2 + * - 12 4 /
= 5 6 2 + * 12 4 / -
Add “ ) “ at the end of P
P = 5 6 2 + * 12 4 / - )
 P = 5 6 2 + * 12 4 / - )

Scanned symbol stack

5 5

6 5,6

2 5,6,2 Pop->A=2,B=6,do 6+2=8,push

8,
+ 5,8

* 40 pop->A=8,B=5 do
5*8=40,push 40
12 40,12

4 40,12,4 Pop->A=4,B=12
/ 40,3 do12/4=3,push 3

- 37 pop->A=3,B=40 do
40-3=37, push 37
1. Q=A+(B*C-(D/E^F)*G)*H
/ (+(-(/ ABC*D

E (+(-(/ ABC*DE
Symbol
Stack p
Scanned ^ (+(-(/^ ABC*DE
( F (+(-(/^ ABC*DEF
A ( A
) (+(- ABC*DEF ^ /
+ (+ A
* (+(- * ABC*DEF ^ /
( (+( A
B (+( AB G (+(- * ABC*DEF ^ /G

* (+(* AB ) (+ ABC*DEF ^ /G * -
C (+(* ABC
* (+* ABC*DEF ^ /G * -
- (+(- ABC*
H (+* ABC*DEF ^ /G * - H
( (+(-( ABC*
D (+(-( ABC*D ) ABC*DEF ^ /G * - H * +
Queue
Basic Idea
•Queue is an abstract data structure, somewhat similar to Stacks. Unlike stacks, a queue
is open at both its ends. One end is always used to insert data (enqueue) and the other
is used to remove data (dequeue).
Queue Representation

•As in stacks, a queue can also be implemented using Arrays, Linked-lists, Pointers and
Structures.
enqueue

dequeue

create QUEUE
isempty

size
Array representation of Queue
REAR=REAR+1
 Here, even if there is free space, it shows Queue full.
REAR=N
Algorithm : Enqueue
Algorithm : Dequeue
Drawback of Linear Queue

Once the queue is full, even though few elements from the
front are deleted and some occupied space is relieved, it is not
possible to add anymore new elements, as the rear has already
reached the Queue’s rear- most position.
Problem With Array Implementation
•The size of the queue depends on the number and order of enqueue and dequeue.
•It may be situation where memory is available but enqueue is not possible.
ENQUEUE DEQUEUE
Effective queuing storage area of array gets reduced.
0 N

front
front rearrear
Use of circular array indexing
Applications of Queues
•Direct applications:-
• Waiting lists
• Access to shared resources (e.g., printer)
• Multiprogramming

•Indirect applications:-
• Auxiliary data structure for algorithms
• Component of other data structures
CIRCULAR QUEUE

● To utilize space properly, circular queue is derived.

● In this queue the elements are inserted in circular manner.
● So that no space is wasted at all.
● Circular queue empty:
FRONT= -1
REAR= -1
● Circular queue full:
(rear + 1) % max_size = Front
● It is a modification of simple queue in which the rear pointer is set to the initial location,
whenever it reaches the location max_size – 1.
Remove Front