Q#2 Answer - Stack Program & Hashing with Collision Resolution
(a) Write program that prompts the user to enter size of stack and implements push and pop
operations.
C++ Code:
#include <iostream>
using namespace std;
#define MAX 100
class Stack {
int top;
int arr[MAX];
int size;
public:
Stack(int s) {
size = s;
top = -1;
}
void push(int value) {
if (top >= size - 1) {
cout << "Stack Overflow\n";
} else {
arr[++top] = value;
cout << value << " pushed into stack\n";
}
}
void pop() {
if (top < 0) {
cout << "Stack Underflow\n";
} else {
cout << arr[top--] << " popped from stack\n";
}
}
void display() {
if (top < 0) {
cout << "Stack is empty\n";
return;
}
cout << "Stack elements: ";
for (int i = 0; i <= top; i++) {
cout << arr[i] << " ";
}
cout << endl;
}
};
int main() {
int s;
cout << "Enter size of stack: ";
cin >> s;
Stack st(s);
[Link](10);
[Link](20);
[Link](30);
[Link]();
[Link]();
[Link]();
return 0;
}
(b) Hashing using collision resolution strategies
Input Set: {51, 23, 83, 99, 54, 79, 84, 22}
Hash Function: h(x) = x mod 10
Hash Table Size: 10
(i) Separate Chaining:
Index | Values
------------------
0 |-
1 | 51
2 | 22
3 | 23 -> 83
4 | 54 -> 84
5 |-
6 |-
7 |-
8 |-
9 | 99 -> 79
(ii) Linear Probing:
Step-by-step resolution:
51 -> index 1
23 -> index 3
83 -> index 3 (collides) -> index 4
99 -> index 9
54 -> index 4 (collides) -> index 5
79 -> index 9 (collides) -> index 0 (wrap)
84 -> index 4,5 (collides) -> index 6
22 -> index 2
Final Table (Index: Value):
0: 79
1: 51
2: 22
3: 23
4: 83
5: 54
6: 84
7: -
8: -
9: 99