Data Structures Dictionary Definition PDF

DS unit1 2Q)Discuss the array and linked representations of stacks. How do they differ? STACK:a stack is a linear data structure that follows the Last In, First Out (LIFO) principle. This means that the last element added to the stack will be the first one to be removed. Array Representation of S...

DS unit1 2Q)Discuss the array and linked representations of stacks. How do they differ? STACK:a stack is a linear data structure that follows the Last In, First Out (LIFO) principle. This means that the last element added to the stack will be the first one to be removed. Array Representation of Stacks: In the array-based implementation of a stack, an array is used to store the stack elements, and the operations such as push, pop, and peek are managed using a pointer (typically referred to as top). 1. Structure: ○ The stack is implemented using a fixed-size array. ○ The pointer top is used to keep track of the position of the last element pushed onto the stack. ○ Initially, the stack is empty, so top is set to -1. 2. Push Operation: ○ To insert a new element onto the stack, the top pointer is incremented by 1, and the new element is placed at the position stack[top]. ○ Before pushing an element, a check is performed to ensure the stack is not full (i.e., top is less than the maximum size of the array). Example: void push(int stack[], int *top, int value, int max_size) { if (*top == max_size - 1) { printf("Stack Overflow\n"); return; } *top += 1; stack[*top] = value; } 3.Pop Operation: ○ To remove an element, the current element at stack[top] is accessed (to return the popped value), and the top pointer is decremented by 1. ○ Before performing the pop operation, a check is done to ensure the stack is not empty (i.e., top is not -1). Example: void pop(int stack[], int *top) {  if (*top == -1) { printf("Stack Underflow\n"); return; } void value = stack[*top]; *top -= 1; } 4.Peek Operation: ○ The top element of the stack can be viewed by simply accessing stack[top], without modifying the top pointer. 5.Overflow and Underflow: ○ Overflow: When the stack is full (i.e., top == max_size - 1), an attempt to push another element results in a stack overflow. ○ Underflow: If the stack is empty (i.e., top == -1), any attempt to pop or peek results in a stack underflow. 6.Advantages: ○ Simple to implement. ○ Fast access since arrays offer constant-time access to elements. 7.Disadvantages: ○ Fixed size ○ Wasted space Linked List Representation of Stacks: Linked List: A linked list is a linear data structure in which elements, called nodes, are stored in a sequence, but unlike arrays, the elements are not stored in contiguous memory locations. Each node in a linked list contains two parts: 1. Data: Stores the actual value. 2. Pointer (or Reference): Stores the address/reference to the next node in the sequence. In the linked list-based implementation, the stack is represented as a dynamic linked list where each node stores the data and a reference (or pointer) to the next node in the stack. 1.Structure: ○ Each element in the stack is represented by a node in a linked list. ○ Each node contains two parts: the data (the actual value) and a pointer to the next node. ○ A top pointer is used to keep track of the top node in the stack. 2.Push Operation: ○ To push an element, a new node is created with the data to be pushed, and its next pointer is set to the current top node. Then, the top pointer is updated to point to the new node. ○ This operation does not require checking for overflow, as the stack can dynamically grow based on memory availability. Example: struct Node { int data; struct Node* next; }; void push(struct Node** top, int value) { struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); if (newNode == NULL) { printf("Memory allocation failed\n"); return; } newNode->data = value; newNode->next = *top; *top = newNode; } 3.Pop Operation: ○ To pop an element, the top node is removed by updating the top pointer to point to the next node in the list, and the popped node is freed from memory. ○ A check is performed to ensure that the stack is not empty before attempting a pop operation. Example: int pop(struct Node** top) { if (*top == NULL) { printf("Stack Underflow\n"); return -1; } struct Node* temp = *top; int value = temp->data; *top = (*top)->next; free(temp); return value; } 4.Peek Operation: ○ The value of the top element is retrieved by accessing (*top)->data without modifying the top pointer. 5.Advantages: ○ Dynamic Size ○ Efficient Memory Usage 6.Disadvantages: ○ Memory Overhead ○ Slower Memory Access ○ Key Differences Between Array and Linked List Representations of DS unit2 4)Insert the following elements into a hash table of size 7 using linear probing and the hash function h(k) = k % 7: Elements:20, 15, 35, 7. Show the state of the hash table after each insertion. Hash table size: 7 (i.e., the table has 7 slots, indexed from 0 to 6). Hash function: h(k)=k%7 (this function determines the index where the element will be inserted by computing the remainder when the key is divided by 7). Collision resolution technique: Linear probing (if a collision occurs, we move to the next slot and continue checking sequentially until an empty slot is found). The elements to insert are: 20, 15, 35, 7. Hash Table: 0 1 2 3 4 5 20 6 Step 1: Insert 20 Hash calculation: h(20)=20%7=6 ○ The element 20 should be inserted into index 6. ○ Since index 6 is empty, we place 20 in this slot. State of the hash table after inserting 20:  20 Step 2: Insert 15 Hash calculation: h(15)=15%7=1 ○ The element 15 should be inserted into index 1. ○ Since index 1 is empty, we place 15 in this slot. State of the hash table after inserting 15: 15 20 Step 3: Insert 35 Hash calculation: h(35)=35%7=0 ○ The element 35 should be inserted into index 0. ○ Since index 0 is empty, we place 35 in this slot. State of the hash table after inserting 35:  35 15 20 Step 4: Insert 7 Hash calculation:h(7)=7%7=0 ○ The element 7 should be inserted into index 0, but index 0 is already occupied by 35. This is a collision. Resolving the collision using linear probing: ○ Since index 0 is occupied, we move to the next index (1). ○ Index 1 is also occupied by 15, so we move to index 2. ○ Index 2 is empty, so we place 7 at index 2. State of the hash table after inserting 7: 35 15 7 20 Final State of the Hash Table: After inserting all the elements using linear probing, the final state of the hash table is: 35 15 7 20 DS unit3 4)Perform a search for the value 55 in the following Binary Search Tree and Show the steps involved in the search process. Step1:root=50 item=55 item>root->data Move to right subtree Step2:root=70 item=55 itemdata Move to left subtree step3:root(leaf node)=60 item=55 Item !=root Element not found