Kalinga University

Department of Computer Science & Faculty of IT

Programme: BCAAIML Semester: II

Course: Data Structures Using C Course Code: BCAAIML201

Unit-I

Introduction to Data structures

In computer terms, a data structure is a Specific way to store and organize data in a computer's
memory so that these data can be used efficiently later. Data may be arranged in many different
ways such as the logical or mathematical model for a particular organization of data is termed as
a data structure. The variety of a particular data model depends on the two factors –

o Firstly, it must be loaded enough in structure to reflect the actual relationships of the data
with the real worldobject.
o Secondly, the formation should be simple enough so that anyone can efficiently process the
data each time it isnecessary.

Categories of Data Structure:

The data structure can be sub divided into major types:
• Linear Data Structure
• Non-linear DataStructure

Linear Data Structure:

A data structure is said to be linear if its elements combine to form any specific order. There are
basically two techniques of representing such linear structure within memory.

First way is to provide the linear relationships among all the elements represented by means of
linear memory location. These linear structures are termed as arrays.

The second technique is to provide the linear relationship among all the elements represented by
using the concept of pointers or links. These linear structures are termed as linkedlists.

The common examples of linear data structure are:

Arrays
Queues
Stacks
Linkedlists

1
Non linear Data Structure:
This structure is mostly used for representing data that contains a hierarchical relationship among
various elements.

Examples of Non Linear Data Structures are listed below:

• Graphs
• family of treesand
• table ofcontents

Tree: In this case, data often contain a hierarchical relationship among various elements. The
data structure that reflects this relationship is termed as rooted tree graph or atree.

Graph: In this case, data sometimes hold a relationship between the pairs of elements which is
not necessarily following the hierarchical structure. Such data structure is termed as a Graph.

Introduction to Algorithms
The word Algorithm means "A set of finite rules or instructions to be followed in calculations or
other problem-solving operations" Or "A procedure for solving a mathematical problem in a
finite number of steps that frequently involves recursive operations".

Need for Algorithms?

• Algorithms are necessary for solving complex problems efficiently and effectively.
• They help to automate processes and make them more reliable, faster, and easier to perform.
• Algorithms also enable computers to perform tasks that would be difficult or impossible for
humans to do manually.
• They are used across fields like mathematics, computer science, engineering, and finance to
analyze data, optimize processes, make predictions, and solve problems.

Therefore, an Algorithm refers to a sequence of finite steps to solve a particular problem.

Use of the Algorithms

Algorithms play a crucial role in various fields and have many applications. Some of the key
areas where algorithms are used include:
1. Computer Science: Algorithms form the basis of computer programming and are used to
solve problems ranging from simple sorting and searching to complex tasks such as artificial
intelligence and machine learning.
2. Mathematics: Algorithms are used to solve mathematical problems, such as finding the
optimal solution to a system of linear equations or finding the shortest path in a graph.

2
3. Operations Research: Algorithms are used to optimize and make decisions in fields such as
transportation, logistics, and resource allocation.
4. Artificial Intelligence: Algorithms are the foundation of artificial intelligence and machine
learning, and are used to develop intelligent systems that can perform tasks such as image
recognition, natural language processing, and decision-making.
5. Data Science: Algorithms are used to analyze, process, and extract insights from large
amounts of data in fields such as marketing, finance, and healthcare.

These are just a few examples of the many applications of algorithms. The use of algorithms is
continually expanding as new technologies and fields emerge, making it a vital component of
modern society.

Algorithms can be simple and complex depending on what you want to achieve.
• It can be understood using the example of cooking a new recipe. You follow the given steps
one by one to get the final dish. In the same way, algorithms are step-by-step instructions
used in programming to perform tasks and produce the expected output.

• The Algorithm designed is language-independent, i.e. they are just plain instructions that can
be implemented in any language, and yet the output will be the same, as expected.

How to express an Algorithm?

• Natural Language: - Here we express the Algorithm in the natural English language. It is
too hard to understand the algorithm from it.
• Flowchart: - Here we express the Algorithm by making graphical/pictorial representation of
it. It is easier to understand than Natural Language.
• Pseudo Code: - Here we express the Algorithm in the form of annotations and informative
text written in plain English which is very much similar to the real code but as it has no
syntax like any of the programming languages, it can’t be compiled or interpreted by the
computer. It is the best way to express an algorithm because it can be understood by even a
layman with some school-level knowledge.

Characteristics of an Algorithm
As one would not follow any written instructions to cook the recipe, but only the standard one.
Similarly, not all written instructions for programming are an algorithm. For some instructions to
be an algorithm, it must have the following characteristics:
• Clear and Unambiguous: The algorithm should be unambiguous. Each of its steps should
be clear in all aspects and must lead to only one meaning.
• Well-Defined Inputs: If an algorithm says to take inputs, it should be well-defined inputs. It
may or may not take input.

3
• Well-Defined Outputs: The algorithm must clearly define what output will be yielded and it
should be well-defined as well. It should produce at least 1 output.
• Finite-ness: The algorithm must be finite, i.e. it should terminate after a finite time.
• Feasible: The algorithm must be simple, generic, and practical, such that it can be executed
with the available resources. It must not contain some future technology or anything.
• Language Independent: The Algorithm designed must be language-independent, i.e. it must
be just plain instructions that can be implemented in any language, and yet the output will be
the same, as expected.
• Input: An algorithm has zero or more inputs. Each that contains a fundamental operator must
accept zero or more inputs.
• Output: An algorithm produces at least one output. Every instruction that contains a
fundamental operator must accept zero or more inputs.
• Definiteness: All instructions in an algorithm must be unambiguous, precise, and easy to
interpret. By referring to any of the instructions in an algorithm one can clearly understand
what is to be done. Every fundamental operator in instruction must be defined without any
ambiguity.
• Finiteness: An algorithm must terminate after a finite number of steps in all test cases. Every
instruction which contains a fundamental operator must be terminated within a finite amount
of time. Infinite loops or recursive functions without base conditions do not possess
finiteness.
• Effectiveness: An algorithm must be developed by using very basic, simple, and feasible
operations so that one can trace it out by using just paper and pencil.

Properties of Algorithm
• It should terminate after a finite time.
• It should produce at least one output.
• It should take zero or more input.
• It should be deterministic means giving the same output for the same input case.
• Every step in the algorithm must be effective i.e. every step should do some work.

Steps to Design an Algorithm

To write an algorithm, the following things are needed as a pre-requisite:
• The problem that is to be solved by this algorithm i.e. clear problem definition.
• The constraints of the problem must be considered while solving the problem.
• The input to be taken to solve the problem.
• The output is to be expected when the problem is solved.
• The solution to this problem is within the given constraints.
Then the algorithm is written with the help of the above parameters such that it solves the
problem.

4
Example: Consider the example to add three numbers and print the sum.

Step 1: Fulfilling the pre-requisites

As discussed above, to write an algorithm, its prerequisites must be fulfilled.
• The problem that is to be solved by this algorithm: Add 3 numbers and print their sum.
• The constraints of the problem that must be considered while solving the problem: The
numbers must contain only digits and no other characters.
• The input to be taken to solve the problem: The three numbers to be added.
• The output to be expected when the problem is solved: The sum of the three numbers
taken as the input i.e. a single integer value.
• The solution to this problem, in the given constraints: The solution consists of adding the
3 numbers. It can be done with the help of the '+' operator, or bit-wise, or any other method.

Step 2: Designing the algorithm

Now let's design the algorithm with the help of the above pre-requisites:
Algorithm to add 3 numbers and print their sum:
• START
• Declare 3 integer variables num1, num2, and num3.
• Take the three numbers, to be added, as inputs in variables num1, num2, and num3
respectively.
• Declare an integer variable sum to store the resultant sum of the 3 numbers.
• Add the 3 numbers and store the result in the variable sum.
• Print the value of the variable sum
• END

Step 3: Testing the algorithm by implementing it.

How to Analyze an Algorithm?

For a standard algorithm to be good, it must be efficient. Hence the efficiency of an algorithm
must be checked and maintained. It can be in two stages:

1. Priori Analysis:
“Priori” means “before,” so Priori analysis involves evaluating an algorithm before
implementation. The algorithm is analyzed in its theoretical form, assuming all other factors
like processor speed remain constant. This analysis is independent of hardware and
programming language and provides an approximate measure of the algorithm’s complexity.

2. Posterior Analysis:
“Posterior” means “after,” so Posterior analysis evaluates an algorithm after implementation.
The algorithm is written in a programming language and executed to measure real factors like

5
correctness, time taken, and space used. This analysis depends on the compiler and the
hardware used.

What is Algorithm complexity and how to find it?

An algorithm is defined as complex based on the amount of Space and Time it consumes.
Hence the Complexity of an algorithm refers to the measure of the time that it will need to
execute and get the expected output, and the Space it will need to store all the data (input,
temporary data, and output). Hence these two factors define the efficiency of an algorithm.

The two factors of Algorithm Complexity are:

• Time Factor: Time is measured by counting the number of key operations such as
comparisons in the sorting algorithm.
• Space Factor: Space is measured by counting the maximum memory space required by the
algorithm to run/execute.

Therefore the complexity of an algorithm can be divided into two types:

1. Space Complexity: The space complexity of an algorithm refers to the amount of memory
required by the algorithm to store the variables and get the result. This can be for inputs,
temporary operations, or outputs.

How to calculate Space Complexity?

The space complexity of an algorithm is calculated by determining the following 2
components:
• Fixed Part: This refers to the space that is required by the algorithm. For example, input
variables, output variables, program size, etc.
• Variable Part: This refers to the space that can be different based on the implementation
of the algorithm. For example, temporary variables, dynamic memory allocation, recursion
stack space, etc.
Therefore Space complexity S(P) of any algorithm P is S(P) = C + SP(I), where C is the
fixed part and S(I) is the variable part of the algorithm, which depends on instance
characteristic I.

Example: Consider the below algorithm for Linear Search

Step 1: START
Step 2: Get n elements of the array in arr and the number to be searched in x
Step 3: Start from the leftmost element of arr[] and one by one compare x with each element of
arr[]
Step 4: If x matches with an element, Print True.
Step 5: If x doesn’t match with any of the elements, Print False.
Step 6: END

6
Here, There are 2 variables arr[], and x, where the arr[] is the variable part of n elements and x
is the fixed part. Hence S(P) = 1+n. So, the space complexity depends on n(number of
elements). Now, space depends on data types of given variables and constant types and it will
be multiplied accordingly.

2. Time Complexity: The time complexity of an algorithm refers to the amount of time
required by the algorithm to execute and get the result. This can be for normal operations,
conditional if-else statements, loop statements, etc.

How to Calculate, Time Complexity?

The time complexity of an algorithm is also calculated by determining the following 2
components:
• Constant time part: Any instruction that is executed just once comes in this part. For
example, input, output, if-else, switch, arithmetic operations, etc.
• Variable Time Part: Any instruction that is executed more than once, say n times, comes
in this part. For example, loops, recursion, etc.
Therefore Time complexity T(P) of any algorithm P is T(P) = C + TP(I), where C is the
constant time part and TP(I) is the variable part of the algorithm, which depends on the
instance characteristic I.

Example: In the algorithm of Linear Search above, the time complexity is calculated as
follows:
Step 1: --Constant Time
Step 2: -- Variable Time (Taking n inputs)
Step 3: --Variable Time (Till the length of the Array (n) or the index of the found element)
Step 4: --Constant Time
Step 5: --Constant Time
Step 6: --Constant Time
Hence, T(P) = 1 + n + n(1 + 1) + 1 = 2 + 3n, which can be said as T(n).

Array

Array is a container which can hold a fix number of items and these items should be of the same
type. Most of the data structures make use of arrays to implement their algorithms. Following are
the important terms to understand the concept of Array.

Element − Each item stored in an array is called anelement.

Index − Each location of an element in an array has a numerical index, which is used to identify

7
theelement.

Array Representation:(Storage structure)

Arrays can be declared in various ways in different languages. For illustration, let's take C
arraydeclaration.

Arrays can be declared in various ways in different languages. For illustration, let's take C
arraydeclaration.

As per the above illustration, following are the important points to be considered.
Index starts with0.

Array length is 10 which means it can store 10elements.

Each element can be accessed via its index. For example, we can fetch an element at index 6 as9.

Basic Operations

Following are the basic operations supported by an array.

• Traverse − print all the array elements one byone.
• Insertion − Adds an element at the givenindex.
• Deletion − Deletes an element at the givenindex.
• Search − Searches an element using the given index or by thevalue.
• Update − Updates an element at the givenindex.

8
Creating an Array

The whole process of creating an array can be divided into two primary sub processes i.e.
1. Array Declaration
Array declaration is the process of specifying the type, name, and size of the array. In C, we
have to declare the array like any other variable before using it.

When we declare an array in C, the compiler allocates the memory block of the specified size
to the array name.

2. Array Initialization
When the array is declared or allocated memory, the elements of the array contain some
garbage value. So, we need to initialize the array to some meaningful values.
• We can skip mentioning the size of the array if declaration and initialisation are done at the
same time.
• We can also partially initialize while declaring. In this case, the remaining elements will be
assigned the value 0 (or equivalent according to the type).

Accessing Array Elements

Array in C provides random access to its elements, which means that we can access any
element of the array by providing the position of the element, called the index.

#include <stdio.h>

int main() {

// array declaration and initialization

int arr[5] = {2, 4, 8, 12, 16};

// accessing element at index 2 i.e 3rd element

printf("%d ", arr[2]);

// accessing element at index 4 i.e last element

printf("%d ", arr[4]);

// accessing element at index 0 i.e first element

printf("%d ", arr[0]);
return 0;
}

9
Output
8 16 2

Update Array Element

We can update the value of array elements at the given index i in a similar way to accessing an
element by using the array square brackets [] and assignment operator (=).

#include <stdio.h>

int main() {
int arr[5] = {2, 4, 8, 12, 16};

// Update the first value

// of the array
arr[0] = 1;
printf("%d", arr[0]);
return 0;
}

Output
1
C Array Traversal
Array Traversal is the process in which we visit every element of the array in a specific order.
For C array traversal, we use loops to iterate through each element of the array.
Traversing An Array
#include <stdio.h>

int main() {
int arr[5] = {2, 4, 8, 12, 16};

// Print each element of

// array using loop
printf("Printing Array Elements\n");
for(int i = 0; i < 5; i++){
printf("%d ", arr[i]);
}
printf("\n");

// Printing array element in reverse

printf("Printing Array Elements in Reverse\n");

10
 for(int i = 4; i>=0; i--){
printf("%d ", arr[i]);
}

return 0;
}

Output
Printing Array Elements
2 4 8 12 16
Printing Array Elements in Reverse
16 12 8 4 2

Sparse Matrix
There are three types of Sparse Matrix :

1). Lower triangular sparse matrix

2). Upper triangular sparse matrix
3). Tri-diagonal matrix

Lower Triangular Matrix / Sparse Matrix

In a Lower triangular sparse matrix, all elements above the main diagonal have a zero value. This
type of sparse matrix is also known as a lower triangular matrix. If you see its pictorial
representation, then you find that all the elements having non-zero value are appear below the
diagonal.
In a lower triangular matrix, Arri,j=0 where i<j.

A lower-triangular Matrix Arr of size n*n has one non-zero element in the first row, two non-
zero elements in the second row, and similarly n non-zero elements in the nth row.

We use a one-dimensional array to store a lower-triangular matrix efficiently in the memory.

11
This array stores only non-zero elements. To store in a one-dimensional array, we do the
mapping between a two-dimensional matrix and a one-dimensional array. We can be done the
mapping in any one of the following ways:

(a) Row-wise mapping— Here the contents of array Arr[] will be {1, 2, 2, 1, 4, 3, 9, 8, 7, 1, 1, 2,
7, 8, 9}

(b) Column-wise mapping— Here the contents of array Arr[] will be {1, 2, 1, 9, 1, 2, 4, 8, 2, 3, 7,
7, 1, 8, 9}

Upper Triangular Matrix / Sparse Matrix

In the Upper triangular sparse matrix, all elements below the main diagonal have a zero value.
This type of sparse matrix is also known as an upper triangular matrix. If you see its pictorial
representation, then you find that all the elements having non-zero value are appear above the
diagonal.

In an upper-triangular matrix, Arri,j=0 where i>j. An n*n upper-triangular matrix Arr has n non-
zero elements in the first row, n–1 non-zero element in the second row, and likewise one non-
zero element in the nth row.

a) Row-wise mapping— Here the contents of array Arr[] will be {1, 1, 2, 5, 8, 2, 8, 9, 7, 3, 7, 2,

1, 5, 9}

(b) Column-wise mapping— Here the contents of array Arr[] will be {1, 1, 2, 2, 8, 3, 5, 9, 7, 1, 8,
7, 2, 5, 9}

Tri-diagonal matrix
Tri-diagonal matrix is also another type of a sparse matrix, where elements with a non-zero value
appear only on the diagonal or immediately below or above the diagonal.

In a tri-diagonal matrix, Arri,j=0, where |i – j| > 1.

12
For matrix being a tri-diagonal matrix element should present

(a) On the main diagonal means all non-zero elements at i=j and at all rest place zero. In this
case, the total number of non-zero elements is n.

(b) at above the main diagonal means all non-zero elements at i=j–1. In this case, the total
number of non-zero elements is n-1.

(c) at below the main diagonal means all non-zero elements for i=j+1. In this case, the total
number of non-zero elements is n-1.

We only store non-zero elements. We can do the mapping between a two-dimensional matrix
and a one-dimensional array the following ways:

(a) Row-wise mapping— Here the contents of array Arr[] will be {1, 1, 5, 2, 8, 8, 3, 2, 4, 1, 5, 7,
9}

(b) Column-wise mapping— Here the contents of array Arr[] will be {1, 5, 1, 2, 8, 8, 3, 4, 2, 1, 7,
5, 9}

(c) Diagonal-wise mapping— Here the contents of array Arr[] will be {1, 8, 2, 5, 1, 2, 3, 1, 9, 5,
8, 4, 7}

What is STACK?
A stack is an Abstract Data Type (ADT), commonly used in most programming languages. It is
named stack as it behaves like a real-world stack, for example – a deck of cards or a pile of
plates, etc.

13
 A Stack is a linear data structure that follows a particular order in which the operations are
performed.
The order may be LIFO (Last in First Out) or FILO (First in Last Out). LIFO implies that
the element that is inserted last comes out first and FILO implies that the element that is
inserted first comes out last. It behaves like a stack of plates, where the last plate added is
the first one to be removed.
Think of it this way:
• Pushing an element onto the stack is like adding a new plate on top.
• Popping an element removes the top plate from the stack.
Types of Stack:
• Fixed Size Stack: As the name suggests, a fixed size stack has a fixed size and cannot grow or
shrink dynamically. If the stack is full and an attempt is made to add an element to it, an
overflow error occurs. If the stack is empty and an attempt is made to remove an element from
it, an underflow error occurs.
• Dynamic Size Stack: A dynamic size stack can grow or shrink dynamically. When the stack is
full, it automatically increases its size to accommodate the new element, and when the stack is
empty, it decreases its size. This type of stack is implemented using a linked list, as it allows
for easy resizing of the stack.
Stack Representation
The following diagram depicts a stack and its operations −

A stack can be implemented by means of Array, Structure, Pointer, and Linked List. Stack
can either be a fixed size one or it may have a sense of dynamic resizing. Here, we are
going to implement stack using arrays, which makes it a fixed size stack implementation.

14
 Basic Operations
Stack operations may involve initializing the stack, using it and then de-initializing it.
Apart from these basic stuffs, a stack is used for the following two primary operations –

• push () − Pushing (storing) an element on the stack.

• pop () − Removing (accessing) an element
from the stack. When data is pushed onto stack.
To use a stack efficiently, we need to check the status of stack as well. For the same
purpose, the following functionality is added to stacks −
• peek () − get the top data element of the stack, without removing it.
• isFull () − check if stack is full.
• isEmpty () − check if stack isempty.
At all times, we maintain a pointer to the last pushed data on the stack. As this pointer
always represents the top of the stack, hence named top. The top pointer provides top
value of the stack without actually removing it.
First we should learn about procedures to support stack functions –
1. peek ()
Algorithm of peek () function –

begin procedure peek

return stack[top]
end procedure

Implementation of peek () function in C programming language –

int peek() {
return stack[top];
}
Example
2. Isfull ()
Algorithm of isfull () function –

15
 begin procedure isfull

if top equals to MAXSIZE

return true
else
return false
endif

end procedure

Implementation of isfull() function in C programming language –

boolisfull() {
if(top == MAXSIZE)
return true;
else
return false;
}
Example
3. isempty ()
Algorithm of isempty () function −

begin procedure isempty

if top less than 1

return true
else
return false
endif

end procedure

Implementation of isempty() function in C programming language is slightly different. We

initialize top at -1, as the index in array starts from 0. So we check if the top is below zero
or -1 to determine if the stack is empty. Here's the code−

16
 boolisempty() {
if(top == -1)
return true;
else
return false;
}
Example
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 −
• Step 1 − Checks if the stack isfull.
• 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.

If the linked list is used to implement the stack, then in step 3, we need to allocate space
dynamically.
Algorithm for PUSH Operation
A simple algorithm for Push operation can be derived as follows −

17
 begin procedure push: stack, data

if stack is full
return null
endif

top ← top + 1
stack[top] ← data

end procedure

Implementation of this algorithm in C, is very easy. See the following code −

void push(int data) {

if(!isFull()) {
top = top + 1;
stack[top] = data;
} else {
printf("Could not insert data, Stack is full.\n");
}
}
Example

Pop Operation
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 by1.
• Step 5 − Returns success.

18
Algorithm for Pop Operation

A simple algorithm for Pop operation can be derived as follows −

begin procedure pop: stack

if stack is empty
return null
endif

data ← stack[top]
top ← top - 1
return data

end procedure

Implementation of this algorithm in C is as follows −

19
 int pop(int data) {

if(!isempty()) {
data = stack[top];
top = top - 1; return
data;
} else {
printf("Could not retrieve data, Stack is empty.\n");
}
}
Example

Applications of Stacks:
1. Function calls: Stacks are used to keep track of the return addresses of function calls, allowing
the program to return to the correct location after a function has finished executing.
2. Recursion: Stacks are used to store the local variables and return addresses of recursive function
calls, allowing the program to keep track of the current state of the recursion.
3. Expression evaluation: Stacks are used to evaluate expressions in postfix notation (Reverse
Polish Notation).
4. Syntax parsing: Stacks are used to check the validity of syntax in programming languages and
other formal languages.
5. Memory management: Stacks are used to allocate and manage memory in some operating
systems and programming languages.
6. Used to solve popular problems like Next Greater, Previous Greater, Next Smaller, Previous
Smaller, Largest Area in a Histogram and Stock Span Problems.

Advantages of Stacks:
1. Simplicity: Stacks are a simple and easy-to-understand data structure, making them suitable for
a wide range of applications.
2. Efficiency: Push and pop operations on a stack can be performed in constant time (O (1)),
providing efficient access to data.
3. Last-in, First-out (LIFO): Stacks follow the LIFO principle, ensuring that the last element
added to the stack is the first one removed. This behavior is useful in many scenarios, such as
function calls and expression evaluation.

20
4. Limited memory usage: Stacks only need to store the elements that have been pushed onto
them, making them memory-efficient compared to other data structures.

Disadvantages of Stacks:
1. Limited access: Elements in a stack can only be accessed from the top, making it difficult to
retrieve or modify elements in the middle of the stack.
2. Potential for overflow: If more elements are pushed onto a stack than it can hold, an overflow
error will occur, resulting in a loss of data.
3. Not suitable for random access: Stacks do not allow for random access to elements, making
them unsuitable for applications where elements need to be accessed in a specific order.
4. Limited capacity: Stacks have a fixed capacity, which can be a limitation if the number of
elements that need to be stored is unknown or highly variable.

What is QUEUE?

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 follows First-In-First-Out methodology, i.e., the data item
stored first will be accessed first.

A real-world example of queue can be a single-lane one-way road, where the vehicle enters first,
exits first. More real-world examples can be seen as queues at the ticket windows and bus- stops.

Basic Terminologies of Queue

21
• Front: Position of the entry in a queue ready to be served, that is, the first entry that will
be removed from the queue, is called the front of the queue. It is also referred as
the head of the queue.
• Rear: Position of the last entry in the queue, that is, the one most recently added, is called
the rear of the queue. It is also referred as the tail of the queue.
• Size: Size refers to the current number of elements in the queue.
• Capacity: Capacity refers to the maximum number of elements the queue can hold.

Types of Queues

Queue data structure can be classified into 4 types:

1. Simple Queue: Simple Queue simply follows FIFO Structure. We can only insert the element at
the back and remove the element from the front of the queue. A simple queue is efficiently
implemented either using a linked list or a circular array.
2. Double-Ended Queue (Deque): In a double-ended queue the insertion and deletion operations,
both can be performed from both ends. They are of two types:
• Input Restricted Queue: This is a simple queue. In this type of queue, the input can be taken
from only one end but deletion can be done from any of the ends.
• Output Restricted Queue: This is also a simple queue. In this type of queue, the input can be
taken from both ends but deletion can be done from only one end.

3. Priority Queue: A priority queue is a special queue where the elements are accessed based on
the priority assigned to them. They are of two types:
• Ascending Priority Queue: In Ascending Priority Queue, the elements are arranged in
increasing order of their priority values. Element with smallest priority value is popped first.
• Descending Priority Queue: In Descending Priority Queue, the elements are arranged in
decreasing order of their priority values. Element with largest priority is popped first.

Queue Representation
As we now understand that in queue, we access both ends for different reasons. The

22
 following diagram given below tries to explain queue representation as data structure –

As in stacks, a queue can also be implemented using Arrays, Linked-lists, Pointers and
Structures. For the sake of simplicity, we shall implement queues using one-dimensional
array.

Basic Operations
Queue operations may involve initializing or defining the queue, utilizing it, and then
completely erasing it from the memory. Here we shall try to understand the basic
operations associated with queues –

• enqueue () − add (store) an item to the queue.

• dequeue () − remove (access) an item from the queue.

Few more functions are required to make the above-mentioned queue operation efficient.
These are −
• peek () − Gets the element at the front of the queue without removing it.
• isfull () − Checks if the queue is full.
• isempty () − Checks if the queue is empty.

In queue, we always dequeue (or access) data, pointed by front pointer and while enqueing (or
storing) data in the queue we take help of rear pointer.
Let's first learn about supportive functions of a queue−
peek ()

This function helps to see the data at the front of the queue. The algorithm of peek ()
function is as follows −

begin procedure peek

return queue[front]
end procedure
Algorithm

23
 Implementation of peek () function in C programming language −

int peek() {
return queue[front];
}
Example
isfull ()
As we are using single dimension array to implement queue, we just check for the rear
pointer to reach at MAXSIZE to determine that the queue is full. In case we maintain the
queue in a circular linked-list, the algorithm will differ. Algorithm of isfull () function−

begin procedure isfull

if rear equals to MAXSIZE return

true
else
return false
endif

end procedure
Algorithm

Implementation of isfull() function in C programming language −

boolisfull() {
if(rear == MAXSIZE - 1)
return true;
else
return false;
}
Example

isempty ()

24
 Algorithm of isempty () function −

begin procedure isempty

if front is less than MIN OR front is greater than rear return

true
Algorithm

else
return false
endif

end procedure

If the value of front is less than MIN or 0, it tells that the queue is not yet initialized,
hence empty.
Here's the C programming code −

boolisempty() {
if(front < 0 || front > rear)
return true;
else
return false;
}
Example

Enqueue Operation
Queues maintain two data pointers, front and rear. Therefore, its operations are comparatively
difficult to implement than that of stacks.
The following steps should be taken to enqueue (insert) data into a queue −
• Step 1 − Check if the queue is full.
• Step 2 − If the queue is full, produce overflow error and exit.
• Step 3 − If the queue is not full, increment rear pointer to point the next empty space.
• Step 4 − Add data element to the queue location, where the rear is pointing.

25
• Step 5 − return success.

Sometimes, we also check to see if a queue is initialized or not, to handle any unforeseen
situations.
Algorithm for enqueue operation

procedureenqueue(data)

if queue is full
return overflow
endif

rear ← rear + 1
queue[rear] ← data
return true

end procedure

Dequeue Operation
Accessing data from the queue is a process of two tasks − access the data where front is
pointing and remove the data after access. The following steps are taken to
perform dequeueoperation−
• Step 1 − Check if the queue is empty.
• Step 2 − If the queue is empty, produce underflow error and exit.
• Step 3 − If the queue is not empty, access the data where front is pointing.
• Step 4 − Increment front pointer to point to the next available data element.

26
• Step 5 − Return success.

Algorithm for dequeue operation

proceduredequeue

if queue is empty
return underflow
end if

data = queue[front]
front ← front + 1
return true

end procedure

Evaluation of Expressions

An expression is a combination of operands (constants or variables) and operators (+, −, *, /,

etc.) that produces a value.

Types of Expressions

1. Infix Expression
Operator is placed between operands.
Example: A + B

27
2. Postfix Expression (Reverse Polish Notation)
Operator is placed after operands.
Example: AB+
3. Prefix Expression
Operator is placed before operands.
Example: +AB

Postfix expressions are easier for computers to evaluate because they do not require
parentheses and operator precedence rules.

Infix to Postfix Conversion

Why Convert Infix to Postfix?

• Infix expressions require precedence and parentheses handling

• Postfix expressions can be evaluated easily using a stack
• Used in compilers and calculators

Operator Precedence
Operator Precedence
^ Highest
*/ Medium
+- Lowest

Rules for Infix to Postfix Conversion

1. If the symbol is an operand, add it to the postfix expression.

2. If the symbol is an left parenthesis ( ( ), push it onto the stack.
3. If the symbol is an right parenthesis ( ) ), pop from stack and add to postfix until ( is found.
4. If the symbol is an operator:
o Pop operators from the stack with higher or equal precedence
o Then push the current operator
5. After scanning the entire infix expression, pop all remaining operators from the stack.

Algorithm for Infix to Postfix Conversion

1. Initialize an empty stack.

2. Scan the infix expression from left to right.
3. Apply the above rules.
4. Output the postfix expression.

28
 Example

Infix Expression:
(A + B) * C

Steps:

• Read ( → push to stack

• Read A → output
• Read + → push
• Read B → output
• Read ) → pop +
• Read * → push
• Read C → output
• Pop remaining *

Postfix Expression:
AB+C*

Evaluation of Postfix Expression

Rules

1. Scan postfix expression from left to right.

2. If operand → push to stack.
3. If operator → pop two operands.
4. Apply operator and push result back.
5. Final value on stack is the result.

Example

Postfix: 23*54*+

Steps:

• Push 2, 3 → apply * → 6
• Push 5, 4 → apply * → 20
• Apply + → 26

• Multiple Stacks

29
 Definition

Multiple stacks refer to storing more than one stack within a single array or memory space.

Need for Multiple Stacks

• Efficient memory utilization

• Reduces memory wastage
• Used when multiple stacks are required simultaneously

Two Stacks in One Array

• One stack grows from left to right

• Other stack grows from right to left
• Both share the same array

Overflow Condition:
When top1 + 1 == top2

Operations

• Push in Stack 1: Increment top1

• Push in Stack 2: Decrement top2
• Pop: Remove element from respective stack

Advantages

• Better space utilization

• Avoids unused memory
• Efficient implementation

Applications of Multiple Stacks

• Expression evaluation
• Compiler design
• Function call management
• Memory sharing systems

30