STACKS

Learning Objectives of this Module :

In this module, we will be learning about:

➢ Gain the concept of stacks.

➢ Understand the basic operations of stacks.
➢ Practice the operations of stacks.
➢ Test your conceptual understanding with a short quiz.

What are Stacks?

Imagine a stack of plates at a cafeteria. The stack, in the world of data structures, works much
like this real-life example. It's a linear data structure following the LIFO (Last In, First Out)
principle. Think of it as a strict order where the last plate added (placed on top) is the first one
to be removed. Just like you can't access plates in the middle without taking off the top ones,
stacks function similarly.

• LIFO Order: The element added last ("pushed") is accessed and removed first
("popped"). Visualize adding dishes to a stack; the latest dish goes on top and is the first
one you grab when needed.
• Top Pointer: A pointer, like a finger, stays at the "top" of the stack, indicating the
element you can access.
• Limited Access: You can only add (push) and remove (pop) elements from the top,
making it different from structures like queues where access happens from both ends.
• Dynamic Size: Stacks can grow or shrink as you add or remove elements, unlike fixed-
size arrays.

Stacks are fundamental building blocks in computer science, offering a simple yet powerful
way to manage data with the LIFO principle. So, the next time you see a stack of plates,
remember its digital counterpart and its diverse applications in the world of programming.
Stacks Operations and Applications

Applications:

• Reversing: Stacks excel at reversing sequences like words or lists. Elements are pushed
in one order and popped in the reverse order, effectively reversing the sequence.
• Function Calls: In programming, when a function is called, its parameters and local
variables are stored on a stack. When the function finishes, these elements are popped
off, ensuring proper memory management and preventing conflicts between functions.
• Expression Evaluation: Stacks play a crucial role in evaluating complex mathematical
expressions. Operands and operators are pushed onto the stack based on their
precedence, and calculated values are pushed back. This ensures the correct evaluation
order according to PEMDAS.

Operations:

• Push: This operation adds an element to the top of the stack. Imagine adding a new
plate to the top of a stack of plates.
• Pop: This operation removes and returns the element currently at the top of the stack.
Think of taking the top plate off the stack.
• Peek: This operation allows you to view the top element without removing it. Think of
looking at the top plate without taking it off.

STACK DATA STRUCTURE

 FEEDBACK
Computer science students often face challenges in understanding abstract data structures like
stacks. To address this, virtual labs have been developed to provide an interactive learning
environment. This report outlines the features and benefits of a Stack Virtual Lab designed to
enhance students' understanding and proficiency in using stacks.

Features of the Stack Virtual Lab:

• Interactive Stack Simulation: The virtual lab offers an interactive simulation of stack
operations, allowing students to visually observe the effects of push, pop, and peek
operations on the stack's state.
• Variety of Implementations: Students can explore different implementations of stacks,
such as array-based and linked list-based implementations, to understand their
advantages and limitations.
• Programming Exercises: The lab provides programming exercises that challenge
students to implement stack algorithms and solve problems using stacks, reinforcing
theoretical concepts through practical application.
• Visualizations and Animations: Visualizations and animations help students visualize
stack operations and understand the underlying principles more effectively.
• Performance Analysis Tools: The lab includes tools for analysing the time and space
complexity of stack operations, helping students gain insights into algorithm efficiency.

Benefits of the Stack Virtual Lab:

• Enhanced Understanding: By providing a hands-on experience with stack operations,

the virtual lab enhances students' understanding of abstract data structures and their
applications.
• Flexibility and Accessibility: Students can access the virtual lab anytime, anywhere,
allowing for flexible learning and accommodating different learning styles.
• Immediate Feedback: Instant feedback on programming exercises helps students
identify and correct errors, facilitating active learning and skill development.
• Scalability: The virtual lab can accommodate a large number of students
simultaneously, making it suitable for use in both classroom settings and self-paced
learning environments.
 • Preparation for Real-world Scenarios: Practical experience gained through the virtual
lab prepares students for real-world scenarios where knowledge of stacks is essential,
such as software development projects and technical interviews.

The Stack Virtual Lab offers a comprehensive and engaging learning experience that
empowers students to master stack data structures effectively. By combining interactive
simulations, programming exercises, and performance analysis tools, the virtual lab equips
students with the skills and knowledge needed to succeed in their academic and professional
endeavours. As virtual labs continue to evolve, they will play an increasingly vital role in
computer science education, providing students.
 QUEUES

Learning Objectives of this Module:

In this module, we will be learning about:

➢ Gain the concept of Queues.

➢ Understand the basic operations of Queues.
➢ Practice the operations of Queues.
➢ Test your conceptual understanding with a short quiz.

What are Queues?

A queue is a linear data structure that follows the First In, First Out (FIFO) principle. Imagine
a line of people waiting for a bus. The person who has been waiting the longest (first in) will
be the first one to board the bus (first out). Imagine a line of people waiting at a ticket counter.
People are served in the order they come, that is, people who come first are served first whereas
people who come later are served after that. Let the action of someone joining a queue be called
enqueue and someone being serve and getting out of the queue be called dequeue. A type of
structure, similar to the example of the line of people, can be represented as a data structure.
Such a data structure is known as a queue.

Types of Queue

1. Simple Queue: Follows strict FIFO, elements enter at the rear and exit at the front, like a
waiting line.

2. Circular Queue: Utilizes a circular array for efficient memory usage, the end wraps around
to the beginning when full.

3. Priority Queue: Prioritizes elements based on assigned values, higher priority elements exit
first regardless of arrival order.

4. Deque (Double-Ended Queue): Allows insertion and deletion from both the front and back,
offering more flexibility than a standard queue.
Queues Applications and Operations

Applications:

Queues are used in many different applications, such as:

• Task scheduling: Operating systems use queues to schedule tasks for the CPU.
• Managing buffers: Queues can be used to buffer data that is being transferred between
two devices or processes.
• Implementing breadth-first search: Breadth-first search algorithms use queues to
explore all the nodes of a graph at a given level before moving on to the next level.
• Priority queues: Priority queues are queues in which elements are ordered based on a
priority. This allows elements with higher priorities to be processed before elements
with lower priorities.

Operations:

Here are some of the basic operations that can be performed on a queue:

• Enqueue: Add an element to the end of the queue.

• Dequeue: Remove and return the element from the front of the queue.
• IsEmpty: Check if the queue is empty.
• IsFull: Check if the queue is full.
• Peek: Get the value of the element at the front of the queue without removing it.

QUEUES DATA STRUCTURE

 FEEDBACK
Queue data structures play a crucial role in computer science, with applications ranging from
job scheduling to network packet routing. However,understanding and mastering queues can
be challenging for students due to their abstract nature. To address this challenge, a Queue
Virtual Lab has been developed to provide an interactive learning environment.

Features of the Queue Virtual Lab:

• Interactive Queue Simulation: The virtual lab offers simulations of queue operations,
enabling students to visualize enqueue, dequeue, and peek operations in action.
• Multiple Implementations: Students can explore various queue implementations, such
as array-based and linked list-based, to understand their differences and performance
characteristics.
• Programming Exercises: The lab provides programming exercises that require students
to implement queue algorithms and solve real-world problems using queues.
• Visualizations and Animations: Visual aids and animations help students grasp queue
concepts more intuitively and reinforce their understanding of underlying principles.
• Performance Analysis Tools: Tools for analyzing time and space complexity allow
students to evaluate the efficiency of queue operations and algorithms.

Benefits of the Queue Virtual Lab:

• Enhanced Understanding: Through hands-on experience with queue operations,

students develop a deeper understanding of queue data structures and their applications.
• Flexibility and Accessibility: The virtual lab can be accessed remotely, providing
flexibility for students to learn at their own pace and convenience.
• Immediate Feedback: Instant feedback on programming exercises helps students
identify and correct errors, promoting active learning and skill development.
• Scalability: The virtual lab can accommodate a large number of students
simultaneously, making it suitable for use in both classroom settings and self-paced
learning environments.
• Real-world Preparedness: Practical experience gained through the virtual lab prepares
students for real-world scenarios where knowledge of queue data structures is essential.
The Queue Virtual Lab offers a comprehensive learning experience for students studying queue
data structures. By combining interactive simulations,programming exercises, and
performance analysis tools, the lab equips students with the knowledge and skills needed to
effectively use queues in various computational tasks. Future enhancements may include
expanding the range of queue implementations and incorporating additional real-world case
studies to further enrich the learning experience.
 INFIX TO POSTFIX

Learning Objectives of this Experiment

In this we will be able to learn the following topics:

➢ Formal Definitions of Infix and Postfix expressions.

➢ Basic concepts behind Infix to Postfix conversion.
➢ Conversion methods from Infix to Postfix.
➢ Evaluation method of Postfix Expressions.

Prerequisites

➢ Basic knowledge on Infix, and Postfix.

➢ Basic mathematical expressions and their functioning.
➢ Operation of stack by Push and Pop methods.
➢ A little bit about Expression trees(not necessary).
➢ And above all, a curiosity to learn and explore.

Overview of the Experiment

• The aim of this experiment is to understand the push and pop operations of stack and
conversion of infix expressions to postfix expressions using stack and without using
stack.
• The experiment features a series of modules with video lectures, interactive
demonstrations, simulations, hands-on practice exercises and quizzes for self-analysis.

INFIX EXPRESSION

An infix expression in data structures is a mathematical expression where operators are placed
between the operands they act upon. This means the operands, like numbers or variables, are
written explicitly, and the operators (+, -, *, /, etc.) are placed in between them to define the
calculation.
The operator is present between the operands on which it is acted upon. It is also the expression
obtained from in order traversal of an expression tree.

• (A + B) * C
• 1+2*4+5/2–1

For example, the expression (2 + 3) * 5 is an infix expression. Here, the operands are 2, 3, and
5, and the operators are +, *, and parentheses. In a data structure context, evaluating this
expression would involve processing the parentheses first, followed by addition, and then
multiplication, respecting the order of operations.

POSTFIX EXPRESSION

A postfix expression, also known as Reverse Polish Notation (RPN), is a data structure where
the operator is placed after its operands. This means the expression reads the values first, and
then tells you what operation to perform on them.

The operator is present after the operands that it is acted upon. It is also the expression obtained
from postorder travesal of an expression tree. It is also called the Reverse Polish Notation
(RPN).

• 2 3 + (RPN of 2 + 3)
• A B + C * (RPN of (A + B) * C)

The infix expression 2 + 3 * 4 is written as 2 3 4 * + in postfix notation. Here, 2 and 3 are

pushed onto the stack first. Then, we encounter the multiplication operator and pop both 3 and
4, perform the multiplication (12), and push the result back onto the stack. Finally, 2 and 12
are popped, added, and the final result, 14, is obtained.

Conversion without Stack

Algorithm:

• Parenthesize the expression following operator precedence.

• Priority(^) > Priority(/) > Priority(*) > Priority(+) >= Priority(-)
• Starting from the lowest level in the parenthesized expression,
• Rearrange the expression to RPN as (3 + 4) becomes (3 4 + ).
• Go to subsequent upper levels.
• Thereby, convert the whole expression to RPN.
Conversion without Stack Example

Conversion with using Stacks

1. Scan the infix expression from left to right.

2. If the scanned character is an operand, output it.

3. Else:

4. 1 If the precedence of the scanned operator is greater than the precedence of the operator in
the stack (or the stack is empty or the stack contains a ‘(‘ ), push it.

5. 2 Else, Pop all the operators from the stack which are greater than or equal to in precedence
than that of the scanned operator. After doing that push the scanned operator to the stack. (If
you encounter parenthesis while popping then stop there and push the scanned operator in the
stack.)

6. If the scanned character is an ‘(‘, push it to the stack.

7. If the scanned character a is n ‘)’, pop the stack and output it until a ‘(‘is encountered, and
discard both the parenthesis.
8. Repeat steps 2-6 until infix expression is scanned.

9. Pop and output from the stack until it is empty.

INFIX TO POSTFIX

Evaluation of Postfix Expressions

1. Create an empty stack called operandStack.

2. Scan the string from left to right.

• If the token is an operand, convert it from a string to an integer and push the value onto
the operand stack.
• If the token is an operator, *, /, +, or -, it will need two operands. Pop the operandStack
twice. The first pop is the second operand and the second pop is the first operand.
Perform the arithmetic operation. Push the result back on the operand stack.

3. When the input expression has been completely processed, the result is on the stack. Pop the
operand stack and return the value.
POSTFIX EVALUATION EXAMPLE
 FEEDBACK
Infix to postfix conversion is a fundamental concept in computer science and programming,
essential for understanding expression evaluation and parsing. To facilitate learning in this area,
Infix to Postfix Virtual Labs has been developed. This report aims to outline the features and
benefits of such a virtual lab, as well as its implications for computer science education.

Features of the Infix to Postfix Virtual Lab:

• Interactive Conversion Tool: The virtual lab offers an interactive tool for converting
infix expressions to postfix notation, allowing students to input infix expressions and
instantly see the corresponding postfix output.
• Step-by-Step Guidance: Students receive step-by-step guidance through the conversion
process, with explanations of each transformation, including stack operations and
precedence rules.
• Visualizations: Visualizations aid in understanding the stack-based algorithm used for
infix to postfix conversion, illustrating how operators and operands are processed and
rearranged.
• Programming Exercises: The lab provides programming exercises that challenge
students to implement the infix to postfix conversion algorithm, reinforcing their
understanding through hands-on coding experience.
• Error Detection and Correction: Immediate feedback helps students identify and correct
errors in their infix expressions or implementation of the conversion algorithm,
fostering iterative learning and problem-solving skills.

Benefits of the Infix to Postfix Virtual Lab:

• Conceptual Understanding: The interactive nature of the virtual lab enhances students'
conceptual understanding of infix to postfix conversion by providing a visual
representation of the process and underlying principles.
• Active Learning: Hands-on exercises and real-time feedback engage students actively
in the learning process, promoting deeper comprehension and retention of the material.
• Flexibility and Accessibility: Students can access the virtual lab anytime, anywhere,
allowing for self-paced learning and accommodating diverse learning styles and
preferences.
 • Real-world Applications: Infix to postfix conversion is a practical skill used in
compilers, parsers, and expression evaluation algorithms, making the virtual lab's
content directly applicable to real-world programming tasks.
• Scalability: The virtual lab can accommodate a large number of students
simultaneously, making it suitable for use in both individual study and classroom
settings.

The Infix to Postfix Virtual Lab offers an interactive and engaging learning experience that
empowers students to master the concept of infix to postfix conversion effectively. By
providing step-by-step guidance, visualizations, programming exercises, and immediate
feedback, the virtual lab equips students with the skills and knowledge needed to understand
and apply this fundamental concept in computer science and programming. As virtual labs
continue to evolve, they will play an increasingly vital role in enhancing computer science
education and preparing students for success in the field.
 FEEDBACK
In conclusion, Data Structures and Algorithms (DSA) Virtual Labs offer a transformative
approach to learning, providing students with interactive, hands-on experiences that enhance
their understanding and proficiency in fundamental concepts. These virtual labs incorporate a
range of features, including interactive simulations, programming exercises, visualizations, and
real-time feedback mechanisms, which promote active learning and engagement.

The benefits of DSA Virtual Labs are numerous. They provide students with the flexibility to
learn at their own pace, catering to diverse learning styles and preferences. By offering
immediate feedback and error correction, these labs facilitate iterative learning and skill
development. Moreover, the scalability of virtual labs enables their use in various educational
settings, from individual study to large classroom environments.

DSA Virtual Labs also have significant implications for computer science education. They
bridge the gap between theoretical knowledge and practical application, preparing students for
real-world scenarios and challenges in software development and technical problem-solving.
Additionally, these labs promote critical thinking, problem-solving, and algorithmic reasoning
skills, which are essential for success in the field of computer science.

As virtual labs continue to evolve and improve, they will play an increasingly vital role in
computer science education, providing students with the tools and resources they need to excel
in their academic pursuits and future careers. Embracing DSA Virtual Labs as integral
components of the curriculum will empower students to become proficient, innovative, and
adaptable computer scientists in an ever-evolving technological landscape.