UNIT-I: Fundamental Concepts & Arrays

2-Mark Questions

1. Define a data structure and give two examples.

A data structure is a method of organizing and storing data for efficient access and modification.
Examples include arrays which store elements in contiguous memory locations, and linked
lists which store elements in nodes connected by pointers.

2. Explain the types of data structures with examples.

Data structures are mainly of two types:

• Linear structures where elements form a sequence, e.g., arrays, stacks, queues.

• Non-linear structures where elements are connected in hierarchical or graph form, e.g.,
trees and graphs.

__________________________________________________________________________________

3. Differentiate between space complexity and time complexity.

• Space complexity measures the total memory an algorithm requires during execution.

• Time complexity measures how the number of operations varies with input size.
Both are critical for analyzing algorithm efficiency.

__________________________________________________________________________________

4. What is an array abstract data type? List two advantages.

An array ADT is a collection of similar elements stored at contiguous memory locations, accessed
via indices.
Advantages:

• Direct access using indices.

• Simple and efficient for fixed-size collections.

__________________________________________________________________________________

5. Explain a sparse matrix and why it is useful.

A sparse matrix is one where most elements are zero. It is stored by representing only non-zero
elements to save memory and improve computational efficiency, especially in large matrices used
in scientific applications.

__________________________________________________________________________________

6. Differentiate between space and time complexity with an example.

• Space complexity is the memory used, e.g., recursive functions use space for call stacks.

• Time complexity is the number of operations, e.g., linear search runs in O(n)O(n) time.
Both help in optimizing algorithm design.

__________________________________________________________________________________
5-Mark Questions

1. Advantages and disadvantages of arrays as a data structure.

A) Advantages and Disadvantages of Arrays as a Data Structure (5 marks)

Advantages

• Efficient and Fast Access: Arrays allow direct access to any element using its index,
providing constant time complexity O(1)O(1) for accessing elements.

• Memory Efficiency: Elements in an array are stored in contiguous memory locations, which
leads to efficient memory allocation and reduces fragmentation.

• Simplicity: Arrays are simple to understand and use, and many programming languages
natively support arrays with built-in operations.

• Multidimensional Storage: Arrays can be extended to multiple dimensions, which is useful

in representing matrices and tables.

• Foundation for Other Data Structures: Arrays form the building blocks for more complex
data structures like stacks, queues, heaps, and hash tables.

Disadvantages

• Fixed Size: Once declared, the size of an array cannot be modified, which can lead to
memory wastage or overflow if the allocated size is inadequate.

• Insertion and Deletion Inefficiency: Adding or removing elements, especially in the middle
of an array, requires shifting subsequent elements, making these operations costly
(O(n)O(n) time).

• Memory Allocation Issues: Large arrays may cause memory exhaustion, particularly on
systems with limited resources.

• Limited Data Type Support: Traditional arrays store elements of the same data type, which
limits the flexibility to store heterogeneous data.

• Lack of Flexibility: Arrays lack dynamic resizing and flexible memory management
compared to data structures such as linked lists.

_______________________________________________________________________________

2. Representation of sparse matrix.

A) Representation of Sparse Matrix (5 marks)

A sparse matrix is a matrix in which most of the elements are zero. Storing all elements
including zeros in a dense matrix wastes a lot of memory. To save space, sparse matrices are
stored efficiently by representing only the non-zero elements along with their locations.

Common Methods of Sparse Matrix Representation

1. Triplet (or Coordinate) Representation

• Uses three arrays to store the row index, column index, and value of every non-
zero element.
 • Example: For a non-zero element at row ii, column jj with value vv,
store (i,j,v)(i,j,v).

• This representation is compact and easy to implement.

• Useful for matrix operations like addition and multiplication.

2. Compressed Sparse Row (CSR) or Yale Format

• Uses three arrays:

• A: Stores all non-zero values.

• IA: Stores indices in A where each row's data starts.

• JA: Stores column indices corresponding to elements in A.

• Efficient for row-wise operations and widely used in scientific computing.

3. Linked List Representation

• Stores non-zero elements as nodes in a linked list. Each node contains the value
and its row and column indexes.

• Efficient for dynamic matrices where elements change over time.

Summary

• Sparse matrix representation stores only non-zero elements along with their row and
column indices.

• These methods save significant memory and enhance speed for large matrices with many
zeros.

• Used in scientific computation, machine learning, graph processing, and more.

_______________________________________________________________________________

3. Explain sequential organization with arrays.

A) Sequential Organization with Arrays (5 marks)

Sequential organization is a method of storing data elements one after another in a specific,
linear order in memory. In this organization, elements are stored in contiguous memory
locations, enabling efficient access.

Key Points:

• Linear Storage: Data elements are arranged sequentially and stored contiguously in
memory. This allows each element to be accessed directly via its index.

• Access by Index: Each element in the array has an index; access time is
constant O(1)O(1) due to direct addressing.

• Order Preservation: The physical order of the elements in memory matches their logical
order.
• Examples: Arrays implement sequential organization; stacks and queues can also be
implemented using arrays.

Advantages:

• Fast Access: Allows fast random access to any element using its index.

• Simple Traversal: Traversing through elements is straightforward using loops.

• Memory Efficiency: Contiguous allocation reduces overhead.

Disadvantages:

• Fixed Size: Size of the array must be fixed at the time of declaration.

• Insertion/Deletion Costly: Inserting or deleting an element requires shifting subsequent

elements, leading to O(n)O(n) time complexity.

• Not Suitable for Dynamic Data: For dynamic size or frequent insertions/deletions, linked
lists are preferred.

_______________________________________________________________________________

4. Write an algorithm/code to delete an element from an array.

A) Algorithm to Delete an Element from an Array

Input: Array AA with nn elements, position pospos of the element to delete

Output: Array AA after deleting the element at position pospos

1. Check if pospos is valid (i.e., pos≥0pos≥0 and pos<npos<n). If invalid, print "Invalid
position" and stop.

2. For each index ii from pospos to n−2n−2, do:

\quad A[i]=A[i+1]A[i]=A[i+1] (Shift elements left)

3. Decrease nn by 1 (one less element after deletion).

4. End.

C++ Code Example

cpp

#include <iostream>

using namespace std;

void deleteElement(int arr[], int &n, int pos) {

if (pos < 0 || pos >= n) {

cout << "Invalid position\n";

return;
 }

for (int i = pos; i < n - 1; i++) {

arr[i] = arr[i + 1]; // Shift elements left

n = n - 1; // Reduce array size

int main() {

int arr[10] = {10, 20, 30, 40, 50};

int n = 5;

int pos;

cout << "Enter position to delete (0 to " << n-1 << "): ";

cin >> pos;

deleteElement(arr, n, pos);

cout << "Array after deletion: ";

for (int i = 0; i < n; i++)

cout << arr[i] << " ";

cout << endl;

return 0;

This algorithm and code handle deletion by shifting elements left from the deletion position
and reduce the effective size of the array accordingly, which is standard for static array

_______________________________________________________________________________

5. Differentiate row major and column major order; show index calculation for a 3×3 array.

A) Difference Between Row-Major and Column-Major Order

 Aspect Row-Major Order Column-Major Order

Elements are stored row by row in Elements are stored column by column
Storage Pattern contiguous memory locations. contiguous memory locations.

Memory Layout For a 3×3 matrix: [A, A, A, A, A, A, A,

Example A, A] For a 3×3 matrix: [A, A, A, A, A, A, A, A,

Common Usage Used in languages like C, C++ Used in languages like Fortran, MATLAB

Suitable for Row-wise operations Column-wise operations

Index Calculation for 3×3 Array

Given array indices start from 0, and element size is WW, base address is BB:

Row-Major Order Formula

Address(A[i][j])=B+W×(i×3+j)Address(A[i][j])=B+W×(i×3+j)

• ii: Row index (0 to 2)

• jj: Column index (0 to 2)

Example: Address of AA

=B+W×(2×3+1)=B+7W=B+W×(2×3+1)=B+7W

Column-Major Order Formula

Address(A[i][j])=B+W×(j×3+i)Address(A[i][j])=B+W×(j×3+i)

• ii: Row index (0 to 2)

• jj: Column index (0 to 2)

Example: Address of AA

=B+W×(1×3+2)=B+5W=B+W×(1×3+2)=B+5W

6. Best, worst, average case for algorithms with example.

A) Best, Worst, and Average Case for Algorithms (5 marks)

Definitions

• Best Case: The scenario where an algorithm performs the minimum number of steps to
complete.
 • Worst Case: The scenario where an algorithm takes the maximum number of steps;
provides an upper bound on running time.

• Average Case: The expected running time over all possible inputs, assuming a probability
distribution.

Example: Linear Search in an Array

• Best Case: The element to be searched is at the first position; time complexity O(1)O(1).

• Worst Case: The element is not present or at the last position; time complexity O(n)O(n).

• Average Case: Element is equally likely to be present at any position or absent; average
time complexity is n+122n+1, which is O(n)O(n).

Example: Insertion Sort

• Best Case: The array is already sorted; time complexity O(n)O(n).

• Worst Case: The array is sorted in reverse order; time complexity O(n2)O(n2).

• Average Case: Random order array; time complexity O(n2)O(n2).

Summary

• Worst case gives performance guarantee.

• Average case gives typical performance.

• Best case is mostly theoretical lower bound.

_______________________________________________________________________________

8-Mark Questions

1. Write a C++ program for array as abstract data type.

A) #include <iostream>

using namespace std;

class ArrayADT {

private:

int arr[100]; // Fixed size array to keep it simple

int length; // Number of elements currently in the array

public:

ArrayADT() { // Constructor to initialize length

length = 0;

}
// Insert element at the end if there is space

void insert(int element) {

if (length < 100) {

arr[length] = element;

length++;

} else {

cout << "Array is full, can't insert more elements.\n";

// Delete element at given index

void removeAt(int index) {

if (index < 0 || index >= length) {

cout << "Invalid index.\n";

return;

// Shift elements to left to fill the gap

for (int i = index; i < length - 1; i++) {

arr[i] = arr[i + 1];

length--;

// Show all elements in the array

void display() {

cout << "Array elements: ";

for (int i = 0; i < length; i++) {

cout << arr[i] << " ";

cout << "\n";

 }

};

int main() {

ArrayADT myArray; // Create an array object

myArray.insert(5);

myArray.insert(10);

myArray.insert(15);

myArray.display(); // Print: 5 10 15

myArray.removeAt(1); // Remove element at index 1 (which is 10)

myArray.display(); // Print: 5 15

return 0;

_______________________________________________________________________________

2. Memory representation and address calculation for arrays.

A) Memory Representation and Address Calculation for Arrays (8 marks)

Memory Representation:

• An array is a collection of elements of the same data type stored in contiguous memory
locations.

• This means the elements are positioned one after another in memory, which allows
efficient access.

• For example, an integer array of 5 elements stores all 5 integers in side-by-side memory
blocks.

• The starting memory location of the array is called the base address BB.

• Each element occupies a fixed number of bytes depending on its data type, for example, 4
bytes for an integer.

Address Calculation (1D Array):

• The address of any element A[i]A[i] in a single-dimensional array can be calculated using
the formula:

Address(A[i])=B+W×iAddress(A[i])=B+W×i

Where

• BB = Base address (address of first element AA),

• WW = Size in bytes of each element,

• ii = Index of the element (starting at 0).

• For example, if B=1000B=1000 and W=4W=4 bytes (integer), the address of AA is:

1000+4×3=10121000+4×3=1012

Address Calculation (2D Array):

• A two-dimensional array A[m][n]A[m][n] is stored as a linear sequence in memory.

• There are two common ways to store 2D arrays:

1. Row-Major Order
Elements are stored row-wise, one row after another.
Address of element A[i][j]A[i][j] (0-based indices) is:

Address(A[i][j])=B+W×(i×n+j)Address(A[i][j])=B+W×(i×n+j)

2. Column-Major Order
Elements are stored column-wise, one column at a time.
Address of element A[i][j]A[i][j] is:

Address(A[i][j])=B+W×(j×m+i)Address(A[i][j])=B+W×(j×m+i)

• Here, ii and jj are row and column indexes respectively, mm is the number of rows,
and nn is the number of columns.

Example (1D Array):

Consider an array of 5 integers starting at address 2000.

Index (i) 0 1 2 3 4

Address 2000 2004 2008 2012 2016

Each integer takes 4 bytes. To access element at index 3:

2000+4×3=20122000+4×3=2012

Summary:
• Arrays allow direct access to elements using the base address and index.

• Contiguous memory storage makes arrays efficient but requires fixed size.

• Understanding memory representation helps optimize programs and debug issues related
to array access.

_______________________________________________________________________________

3. Compare linear and nonlinear data structures with examples.

A) Comparison of Linear and Nonlinear Data Structures

Aspect Linear Data Structures Nonlinear Data Structures

Data elements are

Data arranged sequentially, one after Data elements are arranged hierarchical
Arrangement another in a linear order. or in a network, not sequentially.

Data elements exist at multiple levels or

Levels All data elements exist on a single level. layers.

Each element is connected to its

immediate previous and next An element can be connected to multip
Connections element only. elements, forming branches or graphs.

Can be traversed in one single run, Traversal requires multiple runs or

Traversal sequentially. complex algorithms like DFS and BFS.

Easier to implement and More complex to implement and

Complexity understand due to simplicity. understand due to hierarchical relations

Memory May not use memory efficiently; fixed More memory efficient via dynamic
Utilization sizes or contiguous blocks common. allocation and flexible structures.

Examples Array, Stack, Queue, Linked List Tree, Graph

Used in simple applications like text Used in complex systems like file system
Applications editors, schedulers. social networks, AI.

Summary of Examples
• Linear: Elements are arranged like a straight line (Array, Stack, Queue, Linked List).

• Nonlinear: Elements are connected in branches or networks (Trees like Binary Tree, Graphs
like Social Network connections).

4. Detailed discussion on complexity (space and time) of algorithms.

A) Time and Space Complexity of Algorithms (8 marks)

Time Complexity

• Definition: Time complexity of an algorithm is the measure of the amount of time taken by
an algorithm to run as a function of the input size nn.

• It estimates how the number of steps or operations increases with increasing input.

• Expressed using Big O notation to describe the upper bound of running time.

• Types of time complexity include:

• Constant Time, O(1)O(1): Time does not depend on input size (e.g., accessing an
array element).

• Linear Time, O(n)O(n): Time increases linearly with input size (e.g., linear search).

• Quadratic Time, O(n2)O(n2): Time increases quadratically (e.g., nested loops in

bubble sort).

• Logarithmic Time, O(log⁡n)O(logn): Time increases logarithmically (e.g., binary

search).

Example of Time Complexity

• Linear Search:

• Best case: Element found at first position, O(1)O(1) time.

• Worst case: Element not found or at last position, O(n)O(n) time.

• Average case: O(n)O(n).

Space Complexity

• Definition: Space complexity is the amount of memory space required by an algorithm

during its execution, including input data and auxiliary space.

• Considers both:

• Fixed part: Space used by constants, variables independent of input size.

• Variable part: Space dependent on input size (arrays, recursion stack).

• Typically expressed using Big O notation to describe memory utilization.

Example of Space Complexity

• Adding two scalar variables uses constant space O(1)O(1).

• An algorithm storing an array of size nn uses linear space O(n)O(n).

Relationship and Importance

• Optimizing an algorithm involves balancing time and space complexity.

• Some algorithms use extra memory (space) to run faster (reduce time), and vice versa.

• Efficient algorithms minimize both for better performance and scalability.

• Awareness of complexities helps in selecting suitable algorithms for limitations in time or

memory.

Summary Table

Complexity Type Description Example

Time Complexity Number of operations with input Linear Search: O(n)O(n)

Space Complexity Memory used during execution Recursive algorithm stack

_______________________________________________________________________________

5. Write a program to multiply two sparse matrices.

A) cpp

#include <iostream>

using namespace std;

int main() {

int rows, cols;

cout << "Enter number of rows and columns for matrices: ";

cin >> rows >> cols;

int A[10][10] = {0}, B[10][10] = {0}, C[10][10] = {0};

cout << "Enter elements of matrix A (mostly zeros):\n";

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

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

cin >> A[i][j];

cout << "Enter elements of matrix B (mostly zeros):\n";

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

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

cin >> B[i][j];

// Multiply matrices A and B

for (int i = 0; i < rows; i++) { // Row of A

for (int j = 0; j < cols; j++) { // Column of B

C[i][j] = 0;

for (int k = 0; k < cols; k++) { // Sum of products

if (A[i][k] != 0 && B[k][j] != 0) { // Multiply only non-zero elements

C[i][j] += A[i][k] * B[k][j];

cout << "Result of multiplication (C = A * B):\n";

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

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

 cout << C[i][j] << " ";

cout << "\n";

return 0;

_______________________________________________________________________________

6. Discuss applications of arrays and sparse matrix (with examples).

A)

Applications of Arrays and Sparse Matrices

Applications of Arrays:

1. Storing Multiple Values: Arrays store collections of data such as marks of students, list of
temperatures, etc., where each element can be accessed using indices.
Example: Storing daily temperatures for a month in an array.

2. Implementation of Other Data Structures: Arrays serve as the foundation for more
complex data structures like stacks, queues, heaps, and hash tables.
Example: Stack implemented using an array for function call management.

3. Matrix Operations: Arrays (especially 2D arrays) are used in scientific computations to

perform operations on matrices, like addition, multiplication, and transformation.
Example: Image processing uses 2D arrays to represent pixel values.

4. Efficient Searching and Sorting: Arrays are used in sorting algorithms (e.g., quicksort) and
searching algorithms (e.g., binary search) on sorted data.
Example: Sorting student names alphabetically using an array.

Applications of Sparse Matrices:

1. Scientific Computing: Many problems in physics, engineering, and chemistry result in large
matrices with very few non-zero elements, making sparse matrices a space-efficient
representation.
Example: Finite element analysis in structural engineering.

2. Graph Representations: Sparse matrices efficiently represent adjacency matrices of large

graphs with relatively few edges.
Example: Social networks where each person is connected to a small number of people
compared to the entire network size.
 3. Machine Learning: Sparse feature vectors in data sets where most features have zero
values are stored using sparse matrices to save memory and computation time.
Example: Text classification using bag-of-words model with sparse document-term matrix.

4. Network Analysis: Sparse matrices aid in analyzing connections in networks (computer,

transportation) where links are sparse compared to total possible connections.
Example: Telecom networks routing with sparse connectivity.

Summary

• Arrays provide simple, indexed storage and are foundational in programming and
algorithm design.

• Sparse matrices optimize storage and computation for data dominated by zeros, especially
in scientific, graph, and ML applications.

UNIT-II: Stacks and Queues

2-Mark Questions

1. Condition for stack full/empty:

• A stack is full when the top pointer reaches the maximum size minus one, meaning no
additional elements can be pushed.

• It is empty when the top pointer is -1, indicating there are no elements to pop.

_______________________________________________________________________________

2. Define stack as abstract data type:

A stack is an Abstract Data Type (ADT) with the principle Last-In-First-Out (LIFO), where
elements can only be added (pushed) or removed (popped) from the top of the stack.

_______________________________________________________________________________

3. Condition for queue full/empty:

• A queue is full when the rear pointer reaches the last index of the array and no more
insertions can be made (in linear queue).

• It is empty when the front pointer is -1 or front is greater than rear, indicating no elements
to dequeue.

_______________________________________________________________________________
 4. Define circular queue:
A circular queue treats the queue as a circle where after reaching the last array index, it
wraps around to the beginning. This allows efficient reuse of empty spaces created by
dequeued elements, avoiding false overflow in a linear queue.

_______________________________________________________________________________

5. Queue applications:
Queues are widely used in CPU scheduling to manage process execution order, printer
spooling in managing print jobs, and graph algorithms like breadth-first search which
require level-wise traversal.

_______________________________________________________________________________

6. Define primitive expression:

A primitive expression is the simplest expression consisting of a single operand or variable
used as a building block for more complex expressions.

_______________________________________________________________________________

7. Priority queue definition:

A priority queue is a data structure where each element has a priority, and elements are
dequeued in order of priority instead of insertion order; higher priority elements are
served before lower priority ones.

_______________________________________________________________________________

5-Mark Questions

1. Advantages, uses, and applications of stacks.

A) Advantages, Uses, and Applications of Stacks (5 Marks)

Advantages of Stacks:

• Simplicity: Stacks are simple and easy to implement, using either arrays or linked lists.

• Efficient Operations: Push and pop operations on stacks are performed in constant
time O(1)O(1), providing fast access to data.

• LIFO Principle: Stacks follow Last-In-First-Out order, which is useful in many computing
scenarios like reversing operations.

• Memory Management: Stacks use limited memory as they only store active elements,
making them memory-efficient.
• Helps in Recursion: Automatically manages function calls and return addresses in
programming languages.

Uses of Stacks:

• Function Call Management: Keeping track of active functions and return points during
nested or recursive function calls.

• Expression Evaluation: Evaluating arithmetic expressions, especially in postfix (Reverse

Polish) notation.

• Syntax Parsing: Checking balanced parentheses or syntax correctness in compilers and

interpreters.

• Undo Mechanism: Implementing undo features in software applications like text editors.

• Backtracking: Used in algorithms like maze solving and puzzle games to explore choices.

Applications of Stacks:

• Web Browsers: Manages the history of visited pages allowing users to go back to the
previous page.

• Runtime Memory: Used in managing local variables and function calls on the program’s call
stack.

• Syntax Checkers: Validates proper pairing of symbols like braces, brackets in programming
languages.

• Expression Conversion: Converts infix expressions to postfix and evaluates them efficiently.

• Algorithms: Utilized in depth-first search (DFS) algorithms and solving problems like Tower
of Hanoi

_______________________________________________________________________________

2. Advantages and uses of circular queue.

A) Advantages and Uses of Circular Queue (5 marks)

Advantages of Circular Queue:

• Efficient Memory Utilization: Unlike a linear queue, a circular queue reuses the empty
spaces created after dequeue operations by wrapping the rear pointer back to the front,
avoiding wasted memory.

• Avoids False Overflow: Circular queue prevents the problem of “false overflow” seen in
linear queues when the rear reaches the end but there is empty space at the start.

• Fixed Size & Constant Time Operations: All operations such as enqueue and dequeue occur
in constant time O(1)O(1), making them fast and efficient.

• Simple Implementation: Circular queues are simple to code using arrays and maintain by
updating front and rear pointers modulo the queue size.
• Supports Both FIFO and LIFO: Circular queues can be adapted to support both First-In-First-
Out (standard queue) and Last-In-First-Out (stack-like) behaviors.

Uses of Circular Queue:

• CPU Scheduling: Used to manage processes in round-robin scheduling where processes are
executed in cyclic order.

• Traffic Systems: Models traffic light sequencing where the cycle repeats continuously.

• Multimedia Streaming: Buffers streaming data in circular buffers for smooth playback.

• Network Data Buffers: Handles packets in routers and networks to manage data streams
efficiently.

• Resource Management: Manages shared resources where requests come continuously and
cyclically.

_______________________________________________________________________________

3. Application of stack in expression evaluation.

A) Here is a clear explanation of the application of stack in expression evaluation suitable for
study and exams:

Application of Stack in Expression Evaluation

Stacks are widely used in evaluating arithmetic expressions, especially for expressions in postfix
(Reverse Polish) notation and to convert expressions from infix to postfix or prefix.

Why Use Stacks?

• Stacks follow the Last-In-First-Out (LIFO) principle which perfectly supports order of
operations and handling nested parentheses.

• They help manage operators and operands while respecting precedence and associativity
rules.

How Stack is Used in Expression Evaluation?

Postfix Expression Evaluation

1. Scan the postfix expression from left to right.

2. If the current symbol is an operand, push it onto the stack.

3. If it is an operator, pop the top two operands from the stack, perform the operation, and
push the result back on the stack.

4. Repeat until the expression ends. The value left on the stack is the final result.

Example:

Evaluate postfix expression: 10 8 4 + * 6 3 / -

• Push 10

• Push 8

• Push 4

• Encounter +, pop 4 and 8, add (8+4=12), push 12

• Encounter *, pop 12 and 10, multiply (10*12=120), push 120

• Push 6

• Push 3

• Encounter /, pop 3 and 6, divide (6/3=2), push 2

• Encounter -, pop 2 and 120, subtract (120 - 2=118), push 118

• Result is 118.

Infix to Postfix Conversion

• Stack helps temporarily hold operators and parentheses.

• Operators are popped from stack according to precedence and added to postfix expression.

• Parentheses are handled by pushing ( and popping until ) is encountered.

Summary

Stacks efficiently handle operator precedence, nested parentheses, and order of evaluation,
making expression evaluation and conversion simpler and systematic.

_______________________________________________________________________________

4. Algorithm to insert and delete an element from a linear queue (array implementation).

Algorithm for Insertion (Enqueue) in Linear Queue

• Check if the queue is full: If rear == max_size - 1, then queue is full, stop insertion.

• Else, if queue is empty (i.e., front == -1), set front = 0.

• Increment rear by 1.

• Insert the new element at queue[rear].

• End.

Algorithm for Deletion (Dequeue) in Linear Queue

• Check if the queue is empty: If front == -1 or front > rear, then queue is empty, stop
deletion.

• Store the element at queue[front] for processing.

• Increment front by 1.

• If front > rear after increment, reset front and rear to -1 (queue becomes empty).

• End.

Brief Explanation:

• front points to the index of the first element in the queue for deletion.

• rear points to the last element's index for insertion.

• On enqueue, add element to the next rear position; on dequeue, remove element from
front.

• Both operations are O(1)O(1).

5. Short note: infix, prefix, postfix expressions.

A) Short Note: Infix, Prefix, and Postfix Expressions (5 marks)

Infix Expression

• This is the common arithmetic notation where the operator is placed between operands.

• Example: A+BA+B, X−YX−Y, A∗B+CA∗B+C

• Requires parentheses and precedence rules to enforce the order of operations.

Prefix Expression (Polish Notation)

• The operator is placed before the operands.

• No parentheses are needed; the order of operations is determined by position.

• Example: +AB+AB (infix A+BA+B), ∗+ABC∗+ABC (infix (A+B)∗C(A+B)∗C)

Postfix Expression (Reverse Polish Notation)

• The operator is placed after the operands.

• Like prefix, parentheses are unnecessary, and evaluation is straightforward.

• Example: AB+AB+ (infix A+BA+B), AB+C∗AB+C∗ (infix (A+B)∗C(A+B)∗C)

Key Points

• Infix is human-readable but requires rules for precedence and parentheses.

• Prefix and postfix are easier for computers to parse and evaluate using stacks.
• All three represent the same expressions but differ in operator position and parsing
complexity.

_______________________________________________________________________________

6. Evaluate a given postfix expression (examiner provides expression).

A) Evaluation of a Postfix Expression (5 marks)

Steps to Evaluate a Postfix Expression Using Stack:

1. Initialize an empty stack.

2. Scan the postfix expression from left to right.

3. If the scanned symbol is an operand, push it onto the stack.

4. If it is an operator, pop the top two elements from the stack, say operand1 and operand2.

5. Apply the operator on operand2 and operand1 (note the order: second popped is first
operand).

6. Push the result back onto the stack.

7. Repeat steps 3-6 until the expression ends.

8. The value left on the stack is the result.

Example

Evaluate postfix expression: 5 6 2 + * 12 4 / -

• Push 5

• Push 6

• Push 2

• Encounter +: Pop 2 and 6, add → 6 + 2 = 8, push 8

• Stack: 5, 8

• Encounter *: Pop 8 and 5, multiply → 5 * 8 = 40, push 40

• Push 12

• Push 4

• Encounter /: Pop 4 and 12, divide → 12 / 4 = 3, push 3

• Stack: 40, 3

• Encounter -: Pop 3 and 40, subtract → 40 - 3 = 37, push 37

• End, top of stack is 37 → Result.

_______________________________________________________________________________

7. Explain sequential organization of stack using arrays (with code/algorithmSequential

Organization of Stack Using Arrays (5 marks)

A) Explanation:

• Stack is a linear data structure based on LIFO (Last In First Out) principle.

• Implemented using a fixed size array.

• A variable top tracks the index of the top element.

• Initially, top = -1, indicating an empty stack.

• Push operation: increments top and inserts element.

• Pop operation: removes element at top and decrements top.

• Need to check for overflow (top == capacity - 1) before push and underflow (top == -1)
before pop.

Algorithm:

Initialize:

• Set top = -1

• Define array stack[] with size capacity

Push(element):

1. If top == capacity - 1, then stack overflow, stop.

2. Otherwise, increment top by 1.

3. Insert element at stack[top].

4. End.

Pop():

1. If top == -1, then stack underflow, stop.

2. Otherwise, retrieve element at stack[top].

3. Decrement top by 1.

4. Return element.

5. End.
C++ Code:

cpp

#include <iostream>

using namespace std;

#define MAX 5

class Stack {

int stack[MAX];

int top;

public:

Stack() { top = -1; }

void push(int x) {

if (top == MAX - 1) {

cout << "Stack Overflow\n";

return;

stack[++top] = x;

cout << x << " pushed to stack\n";

int pop() {

if (top == -1) {

cout << "Stack Underflow\n";

return -1;

return stack[top--];

}
 int peek() {

if (top == -1) {

cout << "Stack is Empty\n";

return -1;

return stack[top];

bool isEmpty() { return top == -1; }

};

int main() {

Stack s;

s.push(10);

s.push(20);

s.push(30);

cout << s.pop() << " popped from stack\n";

cout << "Top element is: " << s.peek() << endl;

return 0;

_______________________________________________________________________________

8. Algorithm to pop an element from stack.

A) Algorithm to Pop an Element from Stack (5 marks)

Algorithm:

text

Pop(stack, top):
 1. If top == -1 then

Print "Stack Underflow" (stack is empty)

Return NULL or error

2. Else

element = stack[top] // Store the top element

top = top - 1 // Decrement top to remove element from stack

Return element // Return popped element

3. End

Explanation:

• Check underflow: If the stack is empty (top = -1), popping is not possible.

• Remove element: Retrieve element at the current top.

• Update top: Decrement top index to point below the popped element.

• Return element: The popped element is returned for further use.

Simple C++ Code Snippet for Pop:

cpp

int pop(int stack[], int &top) {

if (top == -1) {

cout << "Stack Underflow\n";

return -1; // or some error value

int element = stack[top];

top--;

return element;

_______________________________________________________________________________

8-Mark Questions
1. Detailed explanation with algorithms for stack operations (push, pop, isFull, isEmpty) using
arrays.

A) Stack Operations Using Arrays (8 Marks)

A stack is a linear data structure that follows Last In First Out (LIFO) principle. It can be
implemented using a fixed-size array and an integer variable top to track the top element's
index.

Initially, the stack is empty, so top = -1.

1. Push Operation (Insert element at the top)

Algorithm:

text

Push(stack, top, element, capacity):

1. If top == capacity - 1 then

Print "Stack Overflow"

Exit

2. Else

top = top + 1

stack[top] = element

3. End

• Checks for stack overflow before insertion.

• Inserts the new element at next top position.

2. Pop Operation (Remove element from the top)

Algorithm:

text

Pop(stack, top):

1. If top == -1 then

Print "Stack Underflow"

Return NULL or error

2. Else

element = stack[top]

top = top - 1
 Return element

3. End

• Checks underflow condition.

• Returns and removes the top element.

3. isFull Operation (Check if stack is full)

Algorithm:

text

isFull(top, capacity):

1. If top == capacity - 1 then

Return True

2. Else

Return False

• Returns whether the stack cannot accept more elements.

4. isEmpty Operation (Check if stack is empty)

Algorithm:

text

isEmpty(top):

1. If top == -1 then

Return True

2. Else

Return False

• Returns if no elements are present in the stack.

C++ Code Snippet Incorporating All Operations:

cpp

#include <iostream>

using namespace std;

#define MAX 5
class Stack {

int stack[MAX];

int top;

public:

Stack() { top = -1; }

bool isFull() {

return top == MAX - 1;

bool isEmpty() {

return top == -1;

void push(int x) {

if (isFull()) {

cout << "Stack Overflow\n";

return;

stack[++top] = x;

cout << x << " pushed to stack\n";

int pop() {

if (isEmpty()) {

cout << "Stack Underflow\n";

return -1;

return stack[top--];

}
 void display() {

if (isEmpty()) {

cout << "Stack is empty\n";

return;

cout << "Stack elements: ";

for (int i = 0; i <= top; i++) {

cout << stack[i] << " ";

cout << endl;

};

int main() {

Stack s;

s.push(10);

s.push(20);

s.push(30);

s.display();

cout << s.pop() << " popped from stack\n";

s.display();

return 0;

Summary
• push: Inserts element after checking overflow.

• pop: Removes element after checking underflow.

• isFull: Returns true when stack reaches max capacity.

• isEmpty: Returns true when no elements in stack.

_______________________________________________________________________________

2. Algorithms for stack operations with examples.

A) 2. Pop Operation

Description: Removes and returns the top element from the stack.

Algorithm:

text

Pop(stack, top)

1. If top == -1 then

Print "Stack Underflow"

Return NULL or error

2. Else

element = stack[top]

top = top - 1

Return element

3. End

Example:
If top = 3 with element 10, pop() returns 10 and top decreases to 2.

3. isFull Operation

Description: Checks whether the stack is full.

Algorithm:

text

isFull(top, capacity)

1. If top == capacity - 1 then

Return True

2. Else
 Return False

4. isEmpty Operation

Description: Checks whether the stack is empty.

Algorithm:

text

isEmpty(top)

1. If top == -1 then

Return True

2. Else

Return False

Summary Table

Operation Purpose Condition Checked

Push Add element at top Stack overflow if full

Pop Remove element from top Stack underflow if empty

isFull Check if stack is full top == capacity - 1

isEmpty Check if stack is empty top == -1

_______________________________________________________________________________

3. Conversion of infix to postfix using stack—algorithm and steps.

A) Conversion of Infix to Postfix Using Stack (8 marks)

Definitions:

• Infix Expression: Operator is between operands (e.g., A + B).

• Postfix Expression: Operator is after operands (e.g., AB+).

Algorithm:

1. Initialize an empty stack for operators.

2. Scan the infix expression from left to right.

3. If the scanned character is an operand, add it directly to the postfix expression.

4. If the scanned character is ‘(‘, push it onto the stack.

5. If the scanned character is ‘)’,

• Pop and add all operators from the stack to postfix until a ‘(‘ is encountered.

• Remove the ‘(‘ from the stack but don’t add it to postfix.

6. If the scanned character is an operator (+, -, *, /, ^),

• While the stack is not empty and the precedence of the operator at the top of
stack is greater than or equal to the scanned operator, pop it and add to postfix
expression.

• Push the scanned operator onto the stack.

7. Repeat steps 3-6 until the entire infix expression is scanned.

8. Pop all remaining operators from the stack and add them to postfix expression.

9. The postfix expression is the result.

Operator Precedence (highest to lowest):

• ^ (exponentiation)

• *, /

• +, -

Step-by-step Example:

Convert: A + B * (C ^ D - E) ^ (F + G * H) - I

Scanned Stack Postfix Expression Action

Symbol

A A Operand → Add to postfix

+ + A Operator → Push to stack

B + AB Operand → Add to postfix

Scanned Stack Postfix Expression Action
Symbol

* +* AB Higher precedence than +, push *

( +*( AB Left parenthesis → Push

C +*( ABC Operand → Add to postfix

^ +*(^ ABC Push operator ^

D +*(^ ABCD Operand → Add to postfix

Pop ^ (higher precedence) → postfix,

- +*(- AB CD^ push -

E +*(- AB CD^E Operand → Add to postfix

) +* AB CD^E - Pop until ‘(‘ → pop -

^ +*^ AB CD^E - Push ^ operator

( +*^( AB CD^E - Push '('

F +*^( AB CD^E -F Operand → Add to postfix

+ +*^(+ AB CD^E -F Push + operator

G +*^(+ AB CD^E -FG Operand → Add to postfix

+*^(+
* * AB CD^E -FG Push * operator

+*^(+
H * AB CD^E -FGH Operand → Add to postfix
 Scanned Stack Postfix Expression Action
Symbol

) +*^ AB CD^E -FGH* + Pop until ‘(‘ → pop * and +

- + AB CD^E -FGH* +^* Pop ^ (higher), push -

I + AB CD^E -FGH* +^*I Operand → Add to postfix

AB CD^E -FGH* +^*I

End -+ Pop remaining operators → postfix

Summary

• Scan infix left to right.

• Operands → postfix directly.

• '(' → push on stack.

• ')' → pop until '(' found.

• Operators → pop higher or equal precedence operators, then push current.

• After scan, pop all remaining operators to postfix.

This algorithm and explanation give stepwise clarity, operator precedence handling, and stack
utility to convert infix to postfix, making a complete 8-mark answer.

_______________________________________________________________________________

4. Stack/Queue overflow and underflow conditions—explanation and sample code.

A) Stack/Queue Overflow and Underflow Conditions (8 marks)

1. Stack Overflow

• Condition: Occurs when trying to push an element into a stack that is already full.

• For array implementation, overflow happens if top == capacity - 1.

• No more elements can be inserted beyond this point.

• Example: A stack of size 5 has elements at indexes 0 to 4. Trying to push when top = 4 is
overflow.

2. Stack Underflow
• Condition: Occurs when trying to pop an element from an empty stack.

• For array implementation, underflow happens if top == -1.

• No elements exist to pop.

• Example: An empty stack has top = -1. Popping now causes underflow.

3. Queue Overflow

• Condition: Occurs when trying to enqueue an element into a queue that is already full.

• For a linear queue implemented with array of size capacity, overflow happens if rear ==
capacity - 1.

• No more insertions allowed until dequeue frees space.

• In a circular queue, overflow condition is when the next position of rear is front.

4. Queue Underflow

• Condition: Occurs when trying to dequeue an element from an empty queue.

• Happens if front == -1 or front > rear.

• No elements to remove.

Sample Code Snippets

Stack Overflow and Underflow Check (Array Implementation)

cpp

#define MAX 5

int stack[MAX];

int top = -1;

void push(int x) {

if (top == MAX - 1) {

cout << "Stack Overflow\n";

return;

stack[++top] = x;

}
int pop() {

if (top == -1) {

cout << "Stack Underflow\n";

return -1;

return stack[top--];

Queue Overflow and Underflow Check (Array Implementation)

cpp

#define MAX 5

int queue[MAX];

int front = -1, rear = -1;

void enqueue(int x) {

if (rear == MAX - 1) {

cout << "Queue Overflow\n";

return;

if (front == -1) front = 0;

queue[++rear] = x;

int dequeue() {

if (front == -1 || front > rear) {

cout << "Queue Underflow\n";

return -1;

return queue[front++];

Summary
• Overflow: Trying to insert beyond capacity.

• Underflow: Trying to remove from empty structure.

• Always check conditions before push/enqueue or pop/dequeue to avoid errors.

_______________________________________________________________________________

5. Compare queue, circular queue, priority queue (table/diagram and explanation).

A) Comparison of Queue, Circular Queue, and Priority Queue

Feature Queue (Linear Circular Queue Priority Queue

Queue)

A linear data An extension of linear

structure following queue where the last A data structure where each
FIFO order where position is connected element is associated with a
elements are added back to the first priority; elements are
at rear and removed position forming a removed based on priority
Definition from front. circle. rather than order.

Data Structure Priority-based (usually heap

Type Linear Circular or priority tree)

May waste space

after several Efficient memory use
enqueues and by reusing empty Dynamic memory use,
Memory dequeues as front spaces due to wrap- depends on priority order
Utilization moves forward. around. maintenance.

Insert at rear
pointer; overflow if Insert at rear, wraps
rear reaches last around to start if Inserted based on priority;
Insertion index. space available. maintains order dynamically

Remove from front

pointer; underflow if Remove from front; Remove element with highe
Deletion empty. works circularly. priority regardless of order.

Order of First In First Out First In First Out (FIFO) Based on priority, not
Elements (FIFO). but cyclic access. insertion order.
 Feature Queue (Linear Circular Queue Priority Queue
Queue)

O(1)O(1) for
Time enqueue and O(1)O(1) for enqueue O(log⁡n)O(logn) for insertio
Complexity dequeue. and dequeue. and deletion (due to heap).

Simple array or Circular array or linked Typically using binary heaps

Implementation linked list. list. or balanced trees.

CPU scheduling
Scheduling tasks, (round-robin), buffer Task scheduling, bandwidth
print queue, BFS in management, management, shortest path
Applications graph traversal. streaming data. algorithms (e.g., Dijkstra).

Explanation:

• Queue is the most basic FIFO data structure where insertion is at the rear and deletion at
the front. However, when many elements are dequeued, space at the start is wasted.

• Circular Queue fixes this space wastage by connecting the rear index back to the front,
reusing the free spaces vacated by dequeued elements. This makes memory use efficient.

• Priority Queue introduces the concept of priority, where elements are processed not just
based on arrival but based on priority numbers assigned to them, making it crucial in
scheduling and network traffic where urgent tasks are served first

_______________________________________________________________________________

6. Realization of queues and stacks with array implementation—explained with code and
diagrams.

A) Realization of Queues and Stacks Using Arrays (8 Marks)

1. Stack Using Array

Explanation:

• Stack is a LIFO structure implemented using a fixed-size array.

• A variable top points to the current top element index.

• Initially, top = -1 indicating an empty stack.

• Push operation inserts element by incrementing top and adding the element.
• Pop operation removes element by returning stack[top] and decrementing top.

• Check for overflow when top == capacity - 1 and underflow when top == -1.

Diagram Description:

• Array indexed from 0 to capacity-1.

• Top moves upwards as elements are pushed.

• Visual shows elements stacked from bottom (index 0) to top.

C++ Code Snippet:

cpp

#define MAX 5

int stack[MAX];

int top = -1;

void push(int x) {

if (top == MAX-1) {

cout << "Stack Overflow\n";

return;

stack[++top] = x;

int pop() {

if (top == -1) {

cout << "Stack Underflow\n";

return -1;

return stack[top--];

2. Queue Using Array (Linear Queue)

Explanation:

• Queue is a FIFO structure implemented using an array.

• Two pointers: front and rear.

• Initially, front = -1, rear = -1 indicating empty queue.

• Enqueue: Increment rear to insert element; if front is -1 set front to 0.

• Dequeue: Remove element from front and increment front.

• Check overflow when rear == capacity - 1.

• Check underflow if front == -1 or front > rear.

Diagram Description:

• Array indexed 0 to capacity-1.

• front and rear pointers move forward as elements are enqueued/dequeued.

• Shows elements queued sequentially in array positions.

C++ Code Snippet:

cpp

#define MAX 5

int queue[MAX];

int front = -1, rear = -1;

void enqueue(int x) {

if (rear == MAX-1) {

cout << "Queue Overflow\n";

return;

if (front == -1) front = 0;

queue[++rear] = x;

int dequeue() {

if (front == -1 || front > rear) {

cout << "Queue Underflow\n";

return -1;

return queue[front++];
}

Summary Table

Feature Stack Queue

Principle Last In First Out (LIFO) First In First Out (FIFO)

Pointers Single pointer: top Two pointers: front and rear

Overflow Condition top == capacity - 1 rear == capacity - 1

Underflow Condition top == -1 front == -1 or front > rear

Element Insert Operation Push at top Enqueue at rear

Element Remove Operation Pop from top Dequeue from front

7. Applications of stacks and queues in real life.

A) Applications of Stacks and Queues in Real Life

Applications of Stacks:

• Web Browser History: Back and forward buttons use stacks to keep track of visited pages in
LIFO order.

• Undo/Redo in Text Editors: Actions are pushed to a stack so the last action can be undone
or redone.

• Expression Evaluation: Convert and evaluate arithmetic expressions (infix to postfix/prefix)

using stacks.

• Function Call Management: Programming languages use stacks to manage function calls
and return addresses (call stack).

• Syntax Parsing: Compilers use stacks to parse the syntax of programming languages and
check balanced parentheses.

• Recursion: Recursive function calls use the call stack for local variables and return points.

• Plate or Book Stack: Real-world stack example where the last plate/book stacked is the
first to be taken (LIFO).
Applications of Queues:

• CPU Scheduling: Operating systems use queues to schedule processes (FIFO order).

• Printing Queue: Print jobs wait in a queue and are processed in the order they arrive.

• Call Center Systems: Customers waiting to be served are managed in queues.

• Network Data Packets: Routers use queues to manage packet transmission orderly.

• Traffic Management: Traffic lights and vehicle queues use queues to manage flow.

• Breadth-First Search (BFS): Graph traversal uses queues for level-wise exploration.

• Waiting Lines: Queues are used in real life scenarios like ticket counters, grocery stores for
orderly service.

Summary:

• Stacks are used where last-in, first-out order is important, such as undo features, function
calls, and expression evaluation.

• Queues are used where first-in, first-out order is required, such as scheduling, printing, and
customer service.