DSA Data Structures and Algorithms External Questions PDF

**1.stack using array. (Predefined)**\ \ \#include \ \#define MAX 100 struct Stack { int arr\[MAX\], top; }; void initStack(struct Stack\* s) { s-\>top = -1; } int isFull(struct Stack\* s) { return s-\>top == MAX - 1; } int isEmpty(struct Stack\* s) { return s-\>top == -1; } void pu...

**1.stack using array. (Predefined)**\ \ \#include \ \#define MAX 100 struct Stack { int arr\[MAX\], top; }; void initStack(struct Stack\* s) { s-\>top = -1; } int isFull(struct Stack\* s) { return s-\>top == MAX - 1; } int isEmpty(struct Stack\* s) { return s-\>top == -1; } void push(struct Stack\* s, int value) { if (isFull(s)) printf(\"StackOverflow\\n\"); else s-\>arr\[++s-\>top\] = value; } int pop(struct Stack\* s) { return isEmpty(s) ? (printf(\"Stack Underflow\\n\"), -1) : s-\>arr\[s-\>top\--\]; } void display(struct Stack\* s) { if (isEmpty(s)) printf(\"Stack is empty\\n\"); else for (int i = s-\>top; i \>= 0; i\--) printf(\"%d\\n\", s-\>arr\[i\]); } int main() { struct Stack s; initStack(&s); push(&s, 10); push(&s, 20); push(&s, 30); display(&s); printf(\"Popped: %d\\n\", pop(&s)); display(&s); return 0; } **1.stack using array. (User-defined)**\ \ \#include \ \#define MAX 100 struct Stack { int arr\[MAX\], top; }; void initStack(struct Stack\* s) { s-\>top = -1; } int isFull(struct Stack\* s) { return s-\>top == MAX - 1; } int isEmpty(struct Stack\* s) { return s-\>top == -1; } void push(struct Stack\* s, int value) { if (isFull(s)) printf(\"StackOverflow\\n\"); else s-\>arr\[++s-\>top\] = value; } int pop(struct Stack\* s) { return isEmpty(s) ? (printf(\"Stack Underflow\\n\"), -1) : s-\>arr\[s-\>top\--\]; } void display(struct Stack\* s) { if (isEmpty(s)) printf(\"Stack is empty\\n\"); else for (int i = s-\>top; i \>= 0; i\--) printf(\"%d\\n\", s-\>arr\[i\]); } int main() { struct Stack s; initStack(&s); int n, value; printf(\"Enter number of elements to push: \"); scanf(\"%d\", &n); for (int i = 0; i \< n; i++) { printf(\"Enter value %d: \", i + 1); scanf(\"%d\", &value); push(&s, value); } display(&s); printf(\"Popped: %d\\n\", pop(&s)); display(&s); return 0; }\ \ **2.Stack using linked list** \#include \ \#include \ typedef struct Node { int data; struct Node\* next; } Node; Node\* createNode(int value) { Node\* newNode = (Node\*)malloc(sizeof(Node)); newNode-\>data = value; newNode-\>next = NULL; return newNode; } void push(Node\*\* top, int value) { Node\* newNode = createNode(value); newNode-\>next = \*top; \*top = newNode; } int pop(Node\*\* top) { if (\*top == NULL) { printf(\"Stack Underflow\\n\"); return -1; } Node\* temp = \*top; int poppedValue = temp-\>data; \*top = (\*top)-\>next; free(temp); return poppedValue; } void display(Node\* top) { if (top == NULL) { printf(\"Stack is empty\\n\"); return; } Node\* temp = top; while (temp != NULL) { printf(\"%d\\n\", temp-\>data); temp = temp-\>next; } } int main() { Node\* top = NULL; push(&top, 10); push(&top, 20); push(&top, 30); display(top); printf(\"Popped: %d\\n\", pop(&top)); display(top); return 0; }\ \ **3. Queue Using Array (Predefined)** \#include \ \#include \ \#define MAX 100 typedef struct { int arr\[MAX\], front, rear; } Queue; void initQueue(Queue\* q) { q-\>front = q-\>rear = -1; } int isFull(Queue\* q) { return (q-\>rear + 1) % MAX == q-\>front; } int isEmpty(Queue\* q) { return q-\>front == -1; } void enqueue(Queue\* q, int value) { if (isFull(q)) { printf(\"Queue Overflow\\n\"); return; } if (isEmpty(q)) q-\>front = 0; q-\>rear = (q-\>rear + 1) % MAX; q-\>arr\[q-\>rear\] = value; } int dequeue(Queue\* q) { if (isEmpty(q)) { printf(\"Queue Underflow\\n\"); return -1; } int value = q-\>arr\[q-\>front\]; if (q-\>front == q-\>rear) q-\>front = q-\>rear = -1; // Reset if empty else q-\>front = (q-\>front + 1) % MAX; return value; } void display(Queue\* q) { if (isEmpty(q)) { printf(\"Queue is empty\\n\"); return; } for (int i = q-\>front; i != q-\>rear; i = (i + 1) % MAX) printf(\"%d \", q-\>arr\[i\]); printf(\"%d\\n\", q-\>arr\[q-\>rear\]); // Print the last element } int main() { Queue q; initQueue(&q); enqueue(&q, 10); enqueue(&q, 20); enqueue(&q, 30); display(&q); printf(\"Dequeued: %d\\n\", dequeue(&q)); display(&q); return 0; }\ \ **3. Queue Using Array (User-defined)\ \ **\#include \ \#include \ \#define MAX 100 typedef struct { int arr\[MAX\], front, rear; } Queue; void initQueue(Queue\* q) { q-\>front = q-\>rear = -1; } int isFull(Queue\* q) { return (q-\>rear + 1) % MAX == q-\>front; } int isEmpty(Queue\* q) { return q-\>front == -1; } void enqueue(Queue\* q, int value) { if (isFull(q)) { printf(\"Queue Overflow\\n\"); return; } if (isEmpty(q)) q-\>front = 0; q-\>rear = (q-\>rear + 1) % MAX; q-\>arr\[q-\>rear\] = value; } int dequeue(Queue\* q) { if (isEmpty(q)) { printf(\"Queue Underflow\\n\"); return -1; } int value = q-\>arr\[q-\>front\]; if (q-\>front == q-\>rear) q-\>front = q-\>rear = -1; // Reset if empty else q-\>front = (q-\>front + 1) % MAX; return value; } void display(Queue\* q) { if (isEmpty(q)) { printf(\"Queue is empty\\n\"); return; } for (int i = q-\>front; i != q-\>rear; i = (i + 1) % MAX) printf(\"%d \", q-\>arr\[i\]); printf(\"%d\\n\", q-\>arr\[q-\>rear\]); // Print the last element } int main() { Queue q; initQueue(&q); int n, value; printf(\"Enter number of elements to enqueue: \"); scanf(\"%d\", &n); for (int i = 0; i \< n; i++) { printf(\"Enter value %d: \", i + 1); scanf(\"%d\", &value); enqueue(&q, value); } display(&q); printf(\"Dequeued: %d\\n\", dequeue(&q)); display(&q); return 0; }\ \ \ \ **4.Queue using linked list\ \ **\#include \ \#include \ typedef struct Node { int data; struct Node\* next; } Node; typedef struct Queue { Node \*front, \*rear; } Queue; void initQueue(Queue\* q) { q-\>front = q-\>rear = NULL; } int isEmpty(Queue\* q) { return q-\>front == NULL; } void enqueue(Queue\* q, int value) { Node\* newNode = malloc(sizeof(Node)); newNode-\>data = value; newNode-\>next = NULL; if (isEmpty(q)) q-\>front = q-\>rear = newNode; else q-\>rear-\>next = newNode, q-\>rear = newNode; } int dequeue(Queue\* q) { if (isEmpty(q)) { printf(\"Queue Underflow\\n\"); return -1; } Node\* temp = q-\>front; int value = temp-\>data; q-\>front = q-\>front-\>next; if (!q-\>front) q-\>rear = NULL; free(temp); return value; } void display(Queue\* q) { for (Node\* curr = q-\>front; curr; curr = curr-\>next) printf(\"%d \", curr-\>data); if (isEmpty(q)) printf(\"Queue is empty\\n\"); else printf(\"\\n\"); } int main() { Queue q; initQueue(&q); enqueue(&q, 10); enqueue(&q, 20); enqueue(&q, 30); display(&q); printf(\"Dequeued: %d\\n\", dequeue(&q)); display(&q); return 0; }**\ ** **5. Infix to Postfix Expression\ \ **\#include \ \#include \ \#include \ typedef struct Node { char data; struct Node\* next; } Node; typedef struct Stack { Node\* top; } Stack; void initStack(Stack\* s) { s-\>top = NULL; } int isEmpty(Stack\* s) { return s-\>top == NULL; } void push(Stack\* s, char value) { Node\* newNode = malloc(sizeof(Node)); newNode-\>data = value; newNode-\>next = s-\>top; s-\>top = newNode; } char pop(Stack\* s) { if (isEmpty(s)) return \'\\0\'; Node\* temp = s-\>top; char value = temp-\>data; s-\>top = s-\>top-\>next; free(temp); return value; } char peek(Stack\* s) { return isEmpty(s) ? \'\\0\' : s-\>top-\>data; } int precedence(char op) { return (op == \'+\' \|\| op == \'-\') ? 1 : (op == \'\*\' \|\| op == \'/\') ? 2 : 0; } void infixToPostfix(const char\* infix, char\* postfix) { Stack s; initStack(&s); int j = 0; for (int i = 0; infix\[i\]; i++) { if (isalnum(infix\[i\])) postfix\[j++\] = infix\[i\]; else if (infix\[i\] == \'(\') push(&s, infix\[i\]); else if (infix\[i\] == \')\') { while (!isEmpty(&s) && peek(&s) != \'(\') postfix\[j++\] = pop(&s); pop(&s); // Remove \'(\' } Else { while (!isEmpty(&s) && precedence(peek(&s)) \>= precedence(infix\[i\])) postfix\[j++\] = pop(&s); push(&s, infix\[i\]); } } while (!isEmpty(&s)) postfix\[j++\] = pop(&s); postfix\[j\] = \'\\0\'; // Null-terminate the postfix expression } int main() { char infix\[100\], postfix\[100\]; printf(\"Enter infix expression: \"); scanf(\"%s\", infix); infixToPostfix(infix, postfix); printf(\"Postfix expression: %s\\n\", postfix); return 0; }\ \ **6. Evaluation of Postfix Expression\ \ **\#include \ \#include \ \#include \ \#define MAX 100 int stack\[MAX\], top = -1; void push(int value) { stack\[++top\] = value; } int pop() { return stack\[top\--\]; } int evaluatePostfix(const char \*exp) { for (int i = 0; exp\[i\]; i++) { if (isdigit(exp\[i\])) { push(exp\[i\] - \'0\'); } else { int op2 = pop(), op1 = pop(); switch (exp\[i\]) { case \'+\': push(op1 + op2); break; case \'-\': push(op1 - op2); break; case \'\*\': push(op1 \* op2); break; case \'/\': push(op1 / op2); break; } } } return pop(); } int main() { printf(\"Result: %d\\n\", evaluatePostfix(\"23\*54\*+9-\")); // Example postfix expression return 0; }