Lab Assignment -7 Date: 29 th Sept & 9th Oct’23
Subject – Data Structure Lab
Stream – CSE Semester – 3rd Batch – 2
Lab Experiment: Implementation of Stack using Linked List
Aim: To understand the concept of a stack and implement it using a linked list data structure in C
programming.
Experiment Tasks:
Task 1: Stack Implementation
1. Define a structure called Node to represent a node in the linked list. Each node should contain a
data element and a pointer to the next node.
2. Define a structure called Stack to represent the stack. It should have a pointer to the top node.
3. Implement a function initializeStack to initialize an empty stack.
4. Implement a function isEmpty to check if the stack is empty.
5. Implement a function push to push an element onto the stack.
6. Implement a function pop to pop an element from the stack.
7. Implement a function peek to return the element at the top of the stack without removing it.
8. Implement a function displayStack to display the elements of the stack.
Task 2: Stack Operations
Create an empty stack using the initializeStack function.
1. Push a few elements onto the stack using the push function.
2. Display the elements of the stack using the displayStack function.
3. Use the peek function to see the top element of the stack without removing it.
4. Pop elements from the stack using the pop function and display the stack after each pop
operation.
5. Check if the stack is empty using the isEmpty function.
Task 3: Stack Applications
1. Implement a function isBalanced to check if a given expression with parentheses (e.g., "({[()]})")
is balanced using the stack data structure.
2. Implement a function evaluatePostfix to evaluate a given postfix expression (e.g., "23*5+")
using the stack.
3. Test both functions with various input expressions.
Solution:
#include <stdio.h>
#include <stdlib.h>
// Define a structure for a Node
struct Node {
int data;
struct Node* next;
};
// Define a structure for the Stack
struct Stack {
struct Node* top;
};
// Function to initialize an empty stack
void initializeStack(struct Stack* stack) {
stack->top = NULL;
}
// Function to check if the stack is empty
int isEmpty(struct Stack* stack) {
return (stack->top == NULL);
}
// Function to push an element onto the stack
void push(struct Stack* stack, int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (newNode == NULL) {
printf("Memory allocation failed. Stack is full.\n");
return;
}
newNode->data = data;
newNode->next = stack->top;
stack->top = newNode;
}
// Function to pop an element from the stack
int pop(struct Stack* stack) {
if (isEmpty(stack)) {
printf("Stack is empty. Cannot pop.\n");
return -1; // Return -1 to indicate an error
}
struct Node* temp = stack->top;
int data = temp->data;
stack->top = temp->next;
free(temp);
return data;
}
// Function to peek at the top element without popping
int peek(struct Stack* stack) {
if (isEmpty(stack)) {
printf("Stack is empty. No elements to peek.\n");
return -1; // Return -1 to indicate an error
}
return stack->top->data;
}
// Function to display the elements of the stack
void displayStack(struct Stack* stack) {
struct Node* current = stack->top;
printf("Stack: ");
while (current != NULL) {
printf("%d ", current->data);
current = current->next;
}
printf("\n");
}
int main() {
struct Stack stack;
initializeStack(&stack);
printf("Task 1: Pushing elements onto the stack...\n");
push(&stack, 10);
push(&stack, 20);
push(&stack, 30);
displayStack(&stack);
printf("Task 2: Top element: %d\n", peek(&stack));
printf("Task 3: Popping elements from the stack...\n");
while (!isEmpty(&stack)) {
printf("Popped: %d\n", pop(&stack));
}
displayStack(&stack);
return 0;
}
TASK -3:
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
struct Stack {
struct Node* top;
};
void initializeStack(struct Stack* stack) {
stack->top = NULL;
}
int isEmpty(struct Stack* stack) {
return (stack->top == NULL);
}
void push(struct Stack* stack, int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (newNode == NULL) {
printf("Memory allocation failed. Stack is full.\n");
return;
}
newNode->data = data;
newNode->next = stack->top;
stack->top = newNode;
}
int pop(struct Stack* stack) {
int data;
if (isEmpty(stack)) {
printf("Stack is empty. Cannot pop.\n");
return -1;
}
struct Node* temp = stack->top;
data = temp->data;
stack->top = temp->next;
free(temp);
return data;
}
int peek(struct Stack* stack) {
if (isEmpty(stack)) {
printf("Stack is empty. No elements to peek.\n");
return -1;
}
return stack->top->data;
}
void displayStack(struct Stack* stack) {
struct Node* current = stack->top;
printf("Stack: ");
while (current != NULL) {
printf("%d ", current->data);
current = current->next;
}
printf("\n");
}
int isBalanced(char* exp) {
struct Stack stack;
initializeStack(&stack);
char c;
int i = 0;
int result = 1; // Assume balanced
while (exp[i] != '\0' && result) {
c = exp[i];
if (c == '(' || c == '[' || c == '{') {
push(&stack, c);
} else if (c == ')' || c == ']' || c == '}') {
if (isEmpty(&stack)) {
result = 0; // Not balanced
} else if ((c == ')' && peek(&stack) == '(') || (c == ']' && peek(&stack) == '[') || (c == '}' &&
peek(&stack) == '{')) {
pop(&stack);
} else {
result = 0; // Not balanced
}
}
i++;
}
return (isEmpty(&stack) && result) ? 1 : 0; // 1 for balanced, 0 for not balanced
}
int evaluatePostfix(char* exp) {
struct Stack stack;
initializeStack(&stack);
int i = 0;
while (exp[i] != '\0') {
if (exp[i] >= '0' && exp[i] <= '9') {
push(&stack, exp[i] - '0');
} else {
int op2 = pop(&stack);
int op1 = pop(&stack);
switch (exp[i]) {
case '+':
push(&stack, op1 + op2);
break;
case '-':
push(&stack, op1 - op2);
break;
case '*':
push(&stack, op1 * op2);
break;
case '/':
push(&stack, op1 / op2);
break;
}
}
i++;
}
return pop(&stack);
}
int main() {
char balancedExp[] = "({[()]})";
char unbalancedExp[] = "([)]";
char postfixExp[] = "23*5+";
printf("Expression \"%s\" is %s\n", balancedExp, isBalanced(balancedExp) ? "balanced" : "not
balanced");
printf("Expression \"%s\" is %s\n", unbalancedExp, isBalanced(unbalancedExp) ? "balanced" : "not
balanced");
printf("Result of evaluating postfix expression \"%s\" is: %d\n", postfixExp,
evaluatePostfix(postfixExp));
return 0;
}
