Unit 1: Introduction to Data Structures and Stacks

Question 1

What is ADT?

Answer 1

Definition: An ADT is a model for data types where the data type is defined by its behavior (operations) rather than its implementation.
Components:

Data: Values stored in the structure.
Operations: Functions that can be performed on the data.

Question 2

Data Structure Definition

Answer 2

Definition: A data structure is a way of organizing and storing data so that it can be accessed and modified efficiently.
Types:

-Primitive: Integer, Float, Character, etc.
-Non-primitive: Arrays, Structures, Linked Lists, etc.

Question 3

Classification of Data Structures

Answer 3

Linear Data Structures: Arrays, Linked Lists, Stacks, Queues.
Non-linear Data Structures: Trees, Graphs.

Question 4

Operations on Data Structures

Answer 4

Common Operations:

Traversal: Visiting each element.
Insertion: Adding new data.
Deletion: Removing existing data.
Searching: Finding data.
Updating: Modifying data.

Question 5

Stack ADT

Answer 5

Definition: A stack is a linear data structure that follows the Last In First Out (LIFO) principle.
Basic Operations:

Push: Add an item to the top.
Pop: Remove the item from the top.
Peek/Top: View the item at the top without removing it.

Question 6

Array Implementation of Stack

Answer 6

Structure:
code:-
#define MAX 100
typedef struct {
int top;
int arr[MAX];
} Stack;

Question 7

Stack Operations in C

Answer 7

Push Function:
void push(Stack *s, int value) {
if (s->top == MAX - 1) {
printf(“Stack Overflow\n”);
return;
}
s->arr[++s->top] = value;
}
——————————————-
Pop Function:
int pop(Stack *s) {
if (s->top == -1) {
printf(“Stack Underflow\n”);
return -1;
}
return s->arr[s->top–];
}

Question 8

Stack Applications

Answer 8

Applications:
Expression Evaluation: Converting infix expressions to postfix.
Backtracking: Used in algorithms like maze solving.

Example: Postfix Evaluation

int evaluatePostfix(char* exp) {
Stack s;
s.top = -1;
for (int i = 0; exp[i]; i++) {
if (isdigit(exp[i])) {
push(&s, exp[i] - ‘0’);
} else {
int val2 = pop(&s);
int val1 = pop(&s);
switch (exp[i]) {
case ‘+’: push(&s, val1 + val2); break;
case ‘-‘: push(&s, val1 - val2); break;
case ‘*’: push(&s, val1 * val2); break;
case ‘/’: push(&s, val1 / val2); break;
}
}
}
return pop(&s);
}

Question 9

Advantages of Stack

Answer 9

Advantages of Stacks:

-Simplicity: Stacks are a simple and easy-to-understand data structure, making them suitable for a wide range of applications.
-Efficiency: Push and pop operations on a stack can be performed in constant time (O(1)), providing efficient access to data.
-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.
-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.

Question 10

Disadvantages of Stacks:

Answer 10

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.
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.
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.
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.