UNIT-2 HANDWRITTEN NOTES

SUBJECTCODE : CS3301

SUBJECT NAME : DATA STRUCTURES

DEPARTMENT : B.E/CSE

YEAR/SEM : II/III

ACADEMIC YEAR : 2023-2024

BATCH :I
 CS3301 DATA STRUCTURES
LTPC
3003
COURSE OBJECTIVES:
To understand the concepts of ADTs.
To Learn linear data structures – lists, stacks, and queues.
To understand non-linear data structures – trees and graphs.
To apply Tree and Graph structures.
To understand sorting, searching and hashing algorithms.

UNIT II STACKS AND QUEUES 9

Stack ADT – Operations – Applications – Balancing Symbols – Evaluating arithmetic expressionsInfix to
Postfix conversion – Function Calls – Queue ADT – Operations – Circular Queue – DeQueue– Applications
of Queues.

After Completion of the course, Students will be able:

Course Statement RBT

S.No. Outcome
To understand the concepts of ADTs and to know how to write the code
1. C204.1 K2
using array and linked list
To apply linear data structures- stacks, and queues using array and
2. C204.2 K3
linked list
To understand and implement non-linear data structures – trees and
3. C204.3 K3
heap structures.
To implement the non-linear data structures - Tree and Graph
4. C204.4 K3
structures.
To understand and implement sorting, searching and hashing
5. C204.5 K3
algorithms.
Revised Bloom’s Taxonomy
K1-Remembering K2-Understanding K3-Applying K4-Analyzing K5-Evaluating K6-Creating

CO-PO Mapping

CO PO1 PO2 PO3 PO4 PO5 PO6 PO7 PO8 PO9 PO10 PO11 PO12 PSO1 PSO2

C204.1 3 1 1 1 2 2 1 1 2 1 1

C204.2 3 2 2 1 2 2 1 1 2 2 1

C204.3 3 2 2 1 2 2 1 1 2 2 2

C204.4 3 2 3 2 2 2 1 1 2 2 2

C204.5 3 2 3 2 2 2 1 1 2 2 2

Average 3 1.8 2.2 1.4 2 2 1 1 2 1.8 1.6

1-low,2-medium,3-high
Source code for stack operations, using array: stack[top] = data;
# include <stdio.h> top = top + 1;
# include <conio.h> printf("\n\nData Pushed into the stack");
# include <stdlib.h> }
# define MAX 6 }
int stack[MAX]; void main()
int top = 0; {
int menu() int ch;
{ do{
int ch; ch = menu();
clrscr(); switch(ch)
printf("\n … Stack operations using ARRAY... "); {
printf("\n 1. Push "); case 1:
printf("\n 2. Pop "); push();
printf("\n 3. Display"); break;
printf("\n 4. Quit "); case 2:
printf("\n Enter your choice: "); pop();
scanf("%d", &ch); break;
return ch; case 3:
} display();
void display() break;
{ case 4:
int i; exit(0);
if(top == 0){ }
printf("\n\nStack empty.."); getch();
return; } } while(1);
else }
{
printf("\n\nElements in stack:"); Source code for stack operations, using linked list:
for(i = 0; i < top; i++) # include <stdio.h>
printf("\t%d", stack[i]); # include <conio.h>
} # include <stdlib.h>
} struct stack
void pop() {
{ int data;
if(top == 0){ struct stack *next;
printf("\n\nStack Underflow.."); };
return; } void push();
else void pop();
printf("\n\npopped element is: %d ", stack[--top]); void display();
} typedef struct stack node;
void push() node *start=NULL;
{ node *top = NULL;
int data; node* getnode()
if(top == MAX){ {
printf("\n\nStack Overflow.."); node *temp;
return; temp=(node *) malloc( sizeof(node)) ;
} printf("\n Enter data ");
else scanf("%d", &temp -> data);
{ temp -> next = NULL;
printf("\n\nEnter data: "); return temp;
scanf("%d", &data); }
void push(node *newnode) if(top == NULL){
{ printf("\n\n\t\t Stack is empty ");
node *temp; }
if( newnode == NULL ){ else{
printf("\n Stack Overflow.."); temp = start;
return; printf("\n\n\n\t\t Elements in the stack: \n");
} printf("%5d ", temp -> data);
if(start == NULL){ while(temp != top)
start = newnode; {
top = newnode; temp = temp -> next;
} printf("%5d ", temp -> data);
else }
{ }
temp = start; }
while( temp -> next != NULL) char menu()
temp = temp -> next; {
temp -> next = newnode; char ch;
top = newnode; clrscr();
} printf("\n \tStack operations using pointers.. ");
printf("\n\n\t Data pushed into stack"); printf("\n 1. Push ");
} printf("\n 2. Pop ");
void pop() printf("\n 3. Display");
{ printf("\n 4. Quit ");
node *temp; printf("\n Enter your choice: ");
if(top == NULL) ch = getche();
{ return ch;
printf("\n\n\t Stack underflow"); }
return; void main()
} {
temp = start; char ch;
if( start -> next == NULL) node *newnode;
{ do
printf("\n\n\t Popped element is %d ", top -> data); {
start = NULL; ch = menu();
free(top); switch(ch)
top = NULL; {
} case '1' :
else newnode = getnode();
{ push(newnode);
while(temp -> next != top) break;
{ case '2' :
temp = temp -> next; pop();
} break;
temp -> next = NULL; case '3' :
printf("\n\n\t Popped element is %d ", top -> data); display();
free(top); break;
top = temp; case '4':
} return;
} }
void display() getch();
{ } while( ch != '4' );
node *temp; }
Program to convert an infix to postfix opstack[top] = op; /* pushing onto stack */
expression: top++;
# include <string.h> }
char postfix[50]; }
char infix[50]; pop()
char opstack[50]; /* operator stack */ {
int i, j, top = 0; while(opstack[--top] != '(' )
int lesspriority(char op, char op_at_stack) /* pop until '(' comes */
{ {
int k; postfix[j] = opstack[top];
int pv1; /* priority value of op */ j++;
int pv2; /* priority value of op_at_stack */ }
char operators[] = {'+', '-', '*', '/', '%', '^', '(' }; }
int priority_value[] = {0,0,1,1,2,3,4}; void main()
if( op_at_stack == '(' ) {
return 0; char ch;
for(k = 0; k < 6; k ++) clrscr();
{ printf("\n Enter Infix Expression : ");
if(op == operators[k]) gets(infix);
pv1 = priority_value[k]; while( (ch=infix[i++]) != ‘\0’)
} {
for(k = 0; k < 6; k ++) switch(ch)
{ {
if(op_at_stack == operators[k]) case ' ' : break;
pv2 = priority_value[k]; case '(' :
} case '+' :
if(pv1 < pv2) case '-' :
return 1; case '*' :
else case '/' :
return 0; case '^' :
} case '%' :
void push(char op) /* op - operator */ push(ch); /* check priority and push */
{ break;
if(top == 0) case ')' :
{ pop();
opstack[top] = op; break;
top++; default :
} postfix[j] = ch;
else j++;
{ }
if(op != '(' ) }
{ while(top >= 0)
while(lesspriority(op, opstack[top-1]) == 1 && {
top > 0) postfix[j] = opstack[--top];
{ j++;
postfix[j] = opstack[--top]; }
j++; postfix[j] = '\0';
} printf("\n Infix Expression : %s ", infix);
} printf("\n Postfix Expression : %s ", postfix);
getch();
}
Program to evaluate a postfix expression: else
# include <conio.h> val_stack[top] = ch-48; /*convert character digit
# include <math.h> to integer digit */
# define MAX 20 top++;
int isoperator(char ch) i++;
{ }
if(ch == '+' || ch == '-' || ch == '*' || ch == '/' || printf("\n Values of %s is : %f ",postfix,
ch == '^') val_stack[0] );
return 1; getch();
else }
return 0;
}
void main(void)
{
char postfix[MAX];
int val;
char ch;
int i = 0, top = 0;
float val_stack[MAX], val1, val2, res;
clrscr();
printf("\n Enter a postfix expression: ");
scanf("%s", postfix);
while((ch = postfix[i]) != '\0')
{
if(isoperator(ch) == 1)
{
val2 = val_stack[--top];
val1 = val_stack[--top];
switch(ch)
{
case '+':
res = val1 + val2;
break;
case '-':
res = val1 - val2;
break;
case '*':
res = val1 * val2;
break;
case '/':
res = val1 / val2;
break;
case '^':
res = pow(val1, val2);
break;
}
val_stack[top] = res;
}
Balancing the symbols:
#include <stdio.h> if (isEmpty(&stack)) {
#include <stdlib.h> return 0; // Unbalanced because
#define MAX 100 there's no matching opening symbol
struct Stack { } else {
char items[MAX]; char topChar = pop(&stack);
int top; if (!isMatchingPair(topChar,
}; currentChar)) {
void initStack(struct Stack* s) { return 0; // Unbalanced because the
s->top = -1; symbols don't match
} }
void push(struct Stack* s, char c) { }
if (s->top == MAX - 1) { }
printf("Stack overflow\n"); }
exit(1);
} // If the stack is empty, all symbols were
s->items[++(s->top)] = c; matched; otherwise, it's unbalanced
} return isEmpty(&stack);
char pop(struct Stack* s) { }
if (s->top == -1) {
printf("Stack underflow\n"); int main() {
exit(1); char expression[MAX];
}
return s->items[(s->top)--]; printf("Enter an expression: ");
} scanf("%s", expression);
int isEmpty(struct Stack* s) {
return s->top == -1; if (isBalanced(expression)) {
} printf("Balanced\n");
int isMatchingPair(char left, char right) { } else {
return (left == '(' && right == ')') || printf("Not Balanced\n");
(left == '{' && right == '}') || }
(left == '[' && right == ']');
} return 0;
int isBalanced(char expression[]) { }
struct Stack stack;
initStack(&stack); Output 1: Enter an expression: {[()]}
for (int i = 0; expression[i] != '\0'; i++) { Balanced
char currentChar = expression[i]; Output 2: Enter an expression: {[(])}
if (currentChar == '(' || currentChar == '{' || Not Balanced
currentChar == '[') {
push(&stack, currentChar);
}
else if (currentChar == ')' || currentChar ==
'}' || currentChar == ']') {
Source code for Queue operations using int menu()
array: {
# include <conio.h> int ch;
# define MAX 6 clrscr();
int Q[MAX]; printf("\n \tQueue operations using ARRAY..");
int front, rear; printf("\n 1. Insert ");
void insertQ() printf("\n 2. Delete ");
{ printf("\n 3. Display");
int data; printf("\n 4. Quit ");
if(rear == MAX) printf("\n Enter your choice: ");
{ scanf("%d", &ch);
printf("\n Linear Queue is full"); return ch;
return; }
} void main()
else {
{ int ch;
printf("\n Enter data: "); do
scanf("%d", &data); {
Q[rear] = data; ch = menu();
rear++; switch(ch)
printf("\n Data Inserted in the Queue "); {
} case 1:
} insertQ();
void deleteQ() break;
{ case 2:
if(rear == front) deleteQ();
{ break;
printf("\n\n Queue is Empty.."); case 3:
return; displayQ();
} break;
else case 4:
{ return;
printf("\n Deleted element from Queue is %d", }
Q[front]); getch();
front++; } while(1);
} }
}
void displayQ()
{ Source code for queue operations using
int i; linked list:
if(front == rear) # include <stdlib.h>
{ # include <conio.h>
printf("\n\n\t Queue is Empty"); struct queue
return; {
} int data;
else struct queue *next;
{ };
printf("\n Elements in Queue are: "); typedef struct queue node;
for(i = front; i < rear; i++){ node *front = NULL;
printf("%d\t", Q[i]); node *rear = NULL;
} node* getnode()
} {
} node *temp;
temp = (node *) malloc(sizeof(node)) ; {
printf("\n Enter data "); printf("%5d ", temp -> data);
scanf("%d", &temp -> data); temp = temp -> next;
temp -> next = NULL; }
return temp; }
} }
void insertQ() char menu()
{ {
node *newnode; char ch;
newnode = getnode(); clrscr();
if(newnode == NULL) printf("\n \t..Queue operations using pointers..
{ ");
printf("\n Queue Full"); printf("\n\t -----------**********-------------
return; \n");
} printf("\n 1. Insert ");
if(front == NULL) printf("\n 2. Delete ");
{ printf("\n 3. Display");
front = newnode; printf("\n 4. Quit ");
rear = newnode; printf("\n Enter your choice: ");
} ch = getche();
else return ch;
{ }
rear -> next = newnode; void main()
rear = newnode; {
} char ch;
printf("\n\n\t Data Inserted into the Queue.."); do
} {
void deleteQ() ch = menu();
{ switch(ch)
node *temp; {
if(front == NULL) case '1' :
{ insertQ();
printf("\n\n\t Empty Queue.."); break;
return; case '2' :
} deleteQ();
temp = front; break;
front = front -> next; case '3' :
printf("\n\n\t Deleted element from queue is %d displayQ();
", temp -> data); break;
free(temp); case '4':
} return;
void displayQ() }
{ getch();
node *temp; } while(ch != '4');
if(front == NULL) }
{
printf("\n\n\t\t Empty Queue ");
}
else
{
temp = front;
printf("\n\n\n\t\t Elements in the Queue are: ");
while(temp != NULL )
Source code for Circular Queue operations, using for(i = front; j != 0; j--)
array: {
# include <stdio.h> printf("%d\t", CQ[i]);
# include <conio.h> i = (i + 1) % MAX;
# define MAX 6 }
int CQ[MAX]; }
int front = 0; }
int rear = 0; int menu()
int count = 0; {
void insertCQ() int ch;
{ clrscr();
int data; printf("\n \t Circular Queue Operations using
if(count == MAX) array.");
{ printf("\n 1. Insert ");
printf("\n Circular Queue is Full"); printf("\n 2. Delete ");
} printf("\n 3. Display");
else printf("\n 4. Quit ");
{ printf("\n Enter Your Choice: ");
printf("\n Enter data: "); scanf("%d", &ch);
scanf("%d", &data); return ch;
CQ[rear] = data; }
rear = (rear + 1) % MAX; void main()
count ++; {
printf("\n Data Inserted in the Circular Queue "); int ch;
} do
} {
void deleteCQ() ch = menu();
{ switch(ch)
if(count == 0) {
{ case 1:
printf("\n\nCircular Queue is Empty.."); insertCQ();
} break;
else case 2:
{ deleteCQ();
printf("\n Deleted element from Circular Queue is break;
%d ", CQ[front]); case 3:
front = (front + 1) % MAX; displayCQ();
count --; break;
} case 4:
} return;
void displayCQ() default:
{ printf("\n Invalid Choice ");
int i, j; }
if(count == 0) getch();
{ } while(1);
printf("\n\n\t Circular Queue is Empty "); }
}
else
{
printf("\n Elements in Circular Queue are: ");
j = count;
Program to implement input and output case 2:
restricted deques: delete_left();
#include <stdio.h> break;
#include <conio.h> case 3:
#define MAX 10 delete_right();
int deque[MAX]; break;
int left = –1, right = –1; case 4:
void input_deque(void); display();
void output_deque(void); break;
void insert_left(void); }
void insert_right(void); }while(option!=5);
void delete_left(void); }
void delete_right(void); void output_deque()
void display(void); {
int main() int option;
{ do
int option; {
clrscr(); printf("OUTPUT RESTRICTED DEQUE");
printf("\n *****MAIN MENU*****"); printf("\n 1.Insert at right");
printf("\n 1.Input restricted deque"); printf("\n 2.Insert at left");
printf("\n 2.Output restricted deque"); printf("\n 3.Delete from left");
printf("Enter your option : "); printf("\n 4.Display");
scanf("%d",&option); printf("\n 5.Quit");
switch(option) printf("\n Enter your option : ");
{ scanf("%d",&option);
case 1: switch(option)
input_deque(); {
break; case 1:
case 2: insert_right();
output_deque(); break;
break; case 2:
} insert_left();
return 0; break;
} case 3:
void input_deque() delete_left();
{ break;
int option; case 4:
do display();
{ break;
printf("\n INPUT RESTRICTED DEQUE"); }
printf("\n 1.Insert at right"); }while(option!=5);
printf("\n 2.Delete from left"); }
printf("\n 3.Delete from right"); void insert_right()
printf("\n 4.Display"); {
printf("\n 5.Quit"); int val;
printf("\n Enter your option : "); printf("\n Enter the value to be added:");
scanf("%d",&option); scanf("%d", &val);
switch(option) if((left == 0 && right == MAX–1) || (left ==
{ right+1))
case 1: {
insert_right(); printf("\n OVERFLOW");
break; return;
} {
if (left == –1) /* if queue is initially empty */ left = –1;
{ right = –1;
left = 0; }
right = 0; else
} {
else if(left == MAX–1)
{ left = 0;
if(right == MAX–1) /*right is at last else
position of queue */ left = left+1;
right = 0; }
else }
right = right+1; void delete_right()
} {
deque[right] = val ; if (left == –1)
} {
void insert_left() printf("\n UNDERFLOW");
{ return ;
int val; }
printf("\n Enter the value to be added:"); printf("\n The element deleted is : %d",
scanf("%d", &val); deque[right]);
if((left == 0 && right == MAX–1) || (left == if(left == right) /*queue has only one
right+1)) element*/
{ {
printf("\n Overflow"); left = –1;
return; right = –1;
} }
if (left == –1)/*If queue is initially empty*/ else
{ {
left = 0; if(right == 0)
right = 0; right=MAX–1;
} else
else right=right–1;
{ }
if(left == 0) }
left=MAX–1; void display()
else {
left=left–1; int front = left, rear = right;
} if(front == –1)
deque[left] = val; {
} printf("\n QUEUE IS EMPTY");
void delete_left() return;
{ }
if (left == –1) printf("\n The elements of the queue are : ");
{ if(front <= rear )
printf("\n UNDERFLOW"); {
return ; while(front <= rear)
} {
printf("\n The deleted element is : %d", printf("%d",deque[front]);
deque[left]); front++;
if(left == right) /*Queue has only one }
element */ }
else
{
while(front <= MAX–1)
{
printf("%d", deque[front]);
front++;
}
front = 0;
while(front <= rear)
{
printf("%d",deque[front]);
front++;
}
}
printf("\n");
}
Output
***** MAIN MENU *****
1.Input restricted deque
2.Output restricted deque
Enter your option : 1
INPUT RESTRICTED DEQUEUE
1.Insert at right
2.Delete from left
3.Delete from right
4.Display
5.Quit
Enter your option : 1
Enter the value to be added : 5
Enter the value to be added : 10
Enter your option : 2
The deleted element is : 5
Enter your option : 5