CS6202-Pragramming and data structures

STACK-ARRAY IMPLEMENTATION
#include<stdio.h>
#define STACK_SIZE 5
int top,s[10],item;

void push(int item)

{
if(top==STACK_SIZE-1)
{
printf("Stack overflow\n");
return;
}
top=top+1;
s[top]=item;
}

int pop()
{
if(top==-1)
return -1;
return s[top--];
}

void display()
{
int i;
if(top==-1)
{
printf("Stack is empty\n");
return;
}
printf("Contents of the stack :\n");
for(i=0;i<=top;i++)
printf("%d\n",s[i]);
}

void main()
{
int item_deleted,item;
int choice;
top=-1;
for(;;)
{
printf("1.Push\t2.Pop\t3.Display\t4.Exit\n");

1
 CS6202-Pragramming and data structures

printf("Enter the choice:\n");

scanf("%d",&choice);
switch(choice)
{
case 1:
printf("Enter the item to be inserted:\n");
scanf("%d",&item);
push(item);
break;

case 2:
item_deleted=pop();
if(item_deleted==-1)
printf("Stack is empty\n");
else
printf("Item deleted=%d\n",item_deleted);
break;

case 3:
display();
break;

case 4:
exit(0);
}
}
}
OUTPUT:
1.Push 2.Pop 3.Display 4.Exit
Enter the choice:
1
Enter the item to be inserted:
2
1.Push 2.Pop 3.Display 4.Exit
Enter the choice:
1
Enter the item to be inserted:
3
1.Push 2.Pop 3.Display 4.Exit
Enter the choice:
1
Enter the item to be inserted:
4
1.Push 2.Pop 3.Display 4.Exit

2
 CS6202-Pragramming and data structures

Enter the choice:

1
Enter the item to be inserted:
5
1.Push 2.Pop 3.Display 4.Exit
Enter the choice:
1
Enter the item to be inserted:
6
1.Push 2.Pop 3.Display 4.Exit
Enter the choice:
1
Enter the item to be inserted:
7
Stack overflow
1.Push 2.Pop 3.Display 4.Exit
Enter the choice:
3
Contents of the stack :
2
3
4
5
6
1.Push 2.Pop 3.Display 4.Exit
Enter the choice:
2
Item deleted=6
1.Push 2.Pop 3.Display 4.Exit
Enter the choice:
2
Item deleted=5
1.Push 2.Pop 3.Display 4.Exit
Enter the choice:
2
Item deleted=4
1.Push 2.Pop 3.Display 4.Exit
Enter the choice:
2
Item deleted=3
1.Push 2.Pop 3.Display 4.Exit
Enter the choice:
2
Item deleted=2

3
 CS6202-Pragramming and data structures

1.Push 2.Pop 3.Display 4.Exit

Enter the choice:
2
Stack is empty
1.Push 2.Pop 3.Display 4.Exit

4
 CS6202-Pragramming and data structures

STACK IMPLEMENATION USING LINKED LIST

#include <stdio.h>
#define MAX_SIZE 5
typedef struct xyz STACK;
struct xyz
{
int element;
struct xyz *next;
}*top=NULL;
int count;

void push()
{
if(count==MAX_SIZE)
printf("STACK IS FULL\n");
else
{
STACK *node;
node=(STACK*)malloc(sizeof(STACK));
printf("\nEnter the element\n");
scanf("%d", &node->element);
node->next=top;
top=node;
count++;
}
}

void pop()
{
STACK *temp;
temp=top;
if(top==NULL)
{
printf("\nSTACK IS EMPTY");
}
else
{
int deleted_ele=temp->element;
top=top->next;
free(temp);
printf("\nThe poped element is: %d ",deleted_ele);
}
}

5
 CS6202-Pragramming and data structures

void display()
{
STACK *temp;
temp=top;
while(temp->next!=NULL)
{
printf("\n%d", temp->element);
temp=temp->next;
}
printf("\n%d", temp->element);
}

void main()
{
int choice;
while(1)
{
printf("\n1.Push\t2.Pop\t3.Display\t4.Exit");
printf("\nEnter the choice:");
scanf("%d",&choice);
switch(choice)
{
case 1:
push();
break;

case 2:
pop();
break;

case 3:
display();
break;

case 4:
exit(0);

default:
printf("Invalid Choice\n:");
}
}

6
 CS6202-Pragramming and data structures

OUTPUT:
1.Push 2.Pop 3.Display 4.Exit
Enter the choice:1
Enter the element
1
1.Push 2.Pop 3.Display 4.Exit
Enter the choice:1
Enter the element
2
1.Push 2.Pop 3.Display 4.Exit
Enter the choice:1
Enter the element
3
1.Push 2.Pop 3.Display 4.Exit
Enter the choice:1
Enter the element
4
1.Push 2.Pop 3.Display 4.Exit
Enter the choice:1
Enter the element
5
1.Push 2.Pop 3.Display 4.Exit
Enter the choice:1
STACK IS FULL

1.Push 2.Pop 3.Display 4.Exit

Enter the choice:3
5
4
3
2
1
1.Push 2.Pop 3.Display 4.Exit
Enter the choice:2

The poped element is: 5

1.Push 2.Pop 3.Display 4.Exit
Enter the choice:2
The poped element is: 4
1.Push 2.Pop 3.Display 4.Exit
Enter the choice:2
The poped element is: 3

7
 CS6202-Pragramming and data structures

1.Push 2.Pop 3.Display 4.Exit

Enter the choice:2
The poped element is: 2
1.Push 2.Pop 3.Display 4.Exit
Enter the choice:2
The poped element is: 1
1.Push 2.Pop 3.Display 4.Exit
Enter the choice:2
STACK IS EMPTY

8
 CS6202-Pragramming and data structures

QUEUE - ARRAY IMPLEMENTATION

#include<stdio.h>
int q[10],rear=0,front=0,size=5;

void insert()
{
if(rear==size)
printf("\nQUEUE IS FULL");
else
{
rear++;
printf("\nenter the element ");
scanf("%d",&q[rear]);
printf("\n%d is Inserted",q[rear]);
}
}

void delete()
{
int i;
if(rear==front)
printf("\nQUEUE IS EMPTY");
else
{
printf("\nDeleted element is %d",q[front+1]);
for(i=front+1;i<rear;i++)
q[i]=q[i+1];
rear--;
}
}

void status()
{
if(rear==size)
printf("\nQueue is full ");
else if(rear==front)
printf("\nQueue is empty ");
else
printf("\nQueue has %d element(s)",rear);
}

void display()
{

9
 CS6202-Pragramming and data structures

int i;
if(rear>size)
printf("\nQueue is full ");
else if(rear==front)
printf("\nQueue is empty ");
else
{
printf("The Queue has the element(s) \n");
printf("\t-------------------------------------\n");
for(i=front+1;i<=rear;i++)
printf("\t%d",q[i]);
printf("\n\t-------------------------------------\n");
}
}

void main()
{
int op,i;
while(1)
{
printf("\n1.INSERT\t2.DELETE\t3.STATUS\t4.DISPLAY\t5.EXIT");
printf("\nEnter your option:\n");
scanf("%d",&op);
switch(op)
{
case 1: insert(); break;
case 2: delete(); break;
case 3: status(); break;
case 4: display(); break;
case 5: exit(0);
}
}
}
OUTPUT:
1.INSERT 2.DELETE 3.STATUS 4.DISPLAY 5.EXIT
Enter your option:
1
enter the element 1
1 is Inserted
1.INSERT 2.DELETE 3.STATUS 4.DISPLAY 5.EXIT
Enter your option:
1
enter the element 2
2 is Inserted

10
 CS6202-Pragramming and data structures

1.INSERT 2.DELETE 3.STATUS 4.DISPLAY 5.EXIT

Enter your option:
1
enter the element 3
3 is Inserted
1.INSERT 2.DELETE 3.STATUS 4.DISPLAY 5.EXIT
Enter your option:
1
enter the element 4
4 is Inserted
1.INSERT 2.DELETE 3.STATUS 4.DISPLAY 5.EXIT
Enter your option:
1
enter the element 5
5 is Inserted
1.INSERT 2.DELETE 3.STATUS 4.DISPLAY 5.EXIT
Enter your option:
4
The Queue has the element(s)
-------------------------------------
1 2 3 4 5
-------------------------------------

1.INSERT 2.DELETE 3.STATUS 4.DISPLAY 5.EXIT

Enter your option:
1
QUEUE IS FULL
1.INSERT 2.DELETE 3.STATUS 4.DISPLAY 5.EXIT
Enter your option:
2
Deleted element is 1
1.INSERT 2.DELETE 3.STATUS 4.DISPLAY 5.EXIT
Enter your option:
2
Deleted element is 2
1.INSERT 2.DELETE 3.STATUS 4.DISPLAY 5.EXIT
Enter your option:
2
Deleted element is 3
1.INSERT 2.DELETE 3.STATUS 4.DISPLAY 5.EXIT
Enter your option:
2
Deleted element is 4
1.INSERT 2.DELETE 3.STATUS 4.DISPLAY 5.EXIT

11
 CS6202-Pragramming and data structures

Enter your option:

2
Deleted element is 5
1.INSERT 2.DELETE 3.STATUS 4.DISPLAY 5.EXIT
Enter your option:
2
QUEUE IS EMPTY

12
 CS6202-Pragramming and data structures

QUEUE-LINKED LIST IMPLEMENTATION

#include<stdio.h>
#define MAX_SIZE 5
struct node
{
int element;
struct node *next;
};
typedef struct node QUEUE;
QUEUE *rear=NULL,*front=NULL;
int count=0;

void insert()
{
if(count==MAX_SIZE)
printf("\nQUEUE IS FULL");
else
{
QUEUE *s;
s=malloc(sizeof(QUEUE));
printf("\nEnter the element ");
scanf("%d",&s->element);
s->next=NULL;
if(front==NULL)
rear=front=s;
else
{
rear->next=s;
rear=s;
}
count++;
printf("\n%d is inserted",s->element);
}
}

void delete()
{
int item;
if(front==NULL)
printf("\nQUEUE IS EMPTY");
else
{
item=front->element;
front=front->next;

13
 CS6202-Pragramming and data structures

printf("\n%d is deleted",item);
}
}

void display()
{
QUEUE *i;
if(front==NULL)
printf("\nQUEUE IS EMPTY");
else
{
printf("\nQueue has the element(s)\n");
printf("\n\t---------------------------------------\n");
for(i=front;i!=NULL;i=i->next)
printf("\t%d",i->element);
printf("\n\t---------------------------------------\n");
}
}

void main()
{
int op;
while(1)
{
printf("\n1.INSERT\t2.DELETE\t3.DISPLAY\t4.EXIT");
printf("\nEnter your option ");
scanf("%d",&op);
switch(op)
{
case 1: insert(); break;
case 2: delete(); break;
case 3: display(); break;
case 4: exit(0);
}
}
}

OUTPUT:
1.INSERT 2.DELETE 3.DISPLAY 4.EXIT
Enter your option 1
Enter the element 1
1 is inserted
1.INSERT 2.DELETE 3.DISPLAY 4.EXIT
Enter your option 1

14
 CS6202-Pragramming and data structures

Enter the element 2

2 is inserted
1.INSERT 2.DELETE 3.DISPLAY 4.EXIT
Enter your option 1
Enter the element 3
3 is inserted
1.INSERT 2.DELETE 3.DISPLAY 4.EXIT
Enter your option 1
Enter the element 4
4 is inserted
1.INSERT 2.DELETE 3.DISPLAY 4.EXIT
Enter your option 1
Enter the element 5
5 is inserted
1.INSERT 2.DELETE 3.DISPLAY 4.EXIT
Enter your option 3
Queue has the element(s)
---------------------------------------
1 2 3 4 5
---------------------------------------
1.INSERT 2.DELETE 3.DISPLAY 4.EXIT
Enter your option 1
QUEUE IS FULL
1.INSERT 2.DELETE 3.DISPLAY 4.EXIT
Enter your option 2
1 is deleted
1.INSERT 2.DELETE 3.DISPLAY 4.EXIT
Enter your option 2
2 is deleted
1.INSERT 2.DELETE 3.DISPLAY 4.EXIT
Enter your option 2
3 is deleted
1.INSERT 2.DELETE 3.DISPLAY 4.EXIT
Enter your option 2
4 is deleted
1.INSERT 2.DELETE 3.DISPLAY 4.EXIT
Enter your option 2
5 is deleted
1.INSERT 2.DELETE 3.DISPLAY 4.EXIT
Enter your option 2
QUEUE IS EMPTY

15
 CS6202-Pragramming and data structures

CIRCULAR QUEUE – ARRAY IMPLEMENTATION

#include<stdio.h>
#define QSIZE 5
int q[QSIZE],front=0,rear=-1,count=0;

void insertQ()
{
int item;
if(count==QSIZE)
printf("QUEUE IS FULL\n");
else
{
printf("Enter the item to be inserted:\n");
scanf("%d",&item);
rear=(rear+1)%QSIZE;
q[rear]=item;
count++;
}

void deleteQ()
{
int item;
if(count==0)
printf("QUEUE IS EMPTY\n");
else
{
item=q[front];
front=(front+1)%QSIZE;
count--;
printf("deleted element is %d\n",item);
}
}

void displayQ()
{
int i;
int temp=front;
if(count==0)
printf("QUEUE IS EMPTY\n");
else
{
printf("________________________________\n");

16
 CS6202-Pragramming and data structures

for(i=1;i<=count;i++)
{
printf("%d\t",q[temp]);
temp=(temp+1)%QSIZE;
}
printf("\n_______________________________\n");
}
}

void main()
{
int op;
while(1)
{
printf("\n1.INSERT\t2.DELETE\t3.DISPLAY\t4.EXIT");
printf("\nEnter your option ");
scanf("%d",&op);
switch(op)
{
case 1: insertQ(); break;
case 2: deleteQ(); break;
case 3: displayQ(); break;
case 4: exit(0);
}
}
}

OUTPUT:
1.INSERT 2.DELETE 3.DISPLAY 4.EXIT
Enter your option 1
Enter the item to be inserted:
2
1.INSERT 2.DELETE 3.DISPLAY 4.EXIT
Enter your option 1
Enter the item to be inserted:
3
1.INSERT 2.DELETE 3.DISPLAY 4.EXIT
Enter your option 3
________________________________
2 3
_______________________________
1.INSERT 2.DELETE 3.DISPLAY 4.EXIT
Enter your option 1
Enter the item to be inserted:

17
 CS6202-Pragramming and data structures

4
1.INSERT 2.DELETE 3.DISPLAY 4.EXIT
Enter your option 1
Enter the item to be inserted:
5
1.INSERT 2.DELETE 3.DISPLAY 4.EXIT
Enter your option 1
Enter the item to be inserted:
6
1.INSERT 2.DELETE 3.DISPLAY 4.EXIT
Enter your option 1
QUEUE IS FULL
1.INSERT 2.DELETE 3.DISPLAY 4.EXIT
Enter your option 3
________________________________
2 3 4 5 6
_______________________________
1.INSERT 2.DELETE 3.DISPLAY 4.EXIT
Enter your option 2
deleted element is 2
1.INSERT 2.DELETE 3.DISPLAY 4.EXIT
Enter your option 2
deleted element is 3
1.INSERT 2.DELETE 3.DISPLAY 4.EXIT
Enter your option 2
deleted element is 4
1.INSERT 2.DELETE 3.DISPLAY 4.EXIT
Enter your option 3
________________________________
5 6
_______________________________
1.INSERT 2.DELETE 3.DISPLAY 4.EXIT
Enter your option 2
deleted element is 5
1.INSERT 2.DELETE 3.DISPLAY 4.EXIT
Enter your option 2
deleted element is 6
1.INSERT 2.DELETE 3.DISPLAY 4.EXIT
Enter your option 2
QUEUE IS EMPTY

18
 CS6202-Pragramming and data structures

CIRCULAR QUEUE-LINKED LIST IMPLEMENTATION

#include<stdio.h>
struct node
{
int element;
struct node *next;
};
typedef struct node QUEUE;
QUEUE *rear=NULL,*front=NULL;

void insert()
{
QUEUE *s;
s=malloc(sizeof(QUEUE));
printf("\nEnter the element ");
scanf("%d",&s->element);
s->next=NULL;
if(rear==NULL)
rear=front=s;
else
{
rear->next=s;
rear=s;
}
rear->next=front; //changes
printf("\n%d is inserted",s->element);
}

void delete()
{
QUEUE *temp;
temp=front;
if(front==NULL)
printf("\nQUEUE IS EMPTY");
else
{
if(front==rear) //changes
{
printf("\n%d is deleted",front->element);
front=rear=NULL;
}
else
{
printf("\n%d is deleted",front->element);

19
 CS6202-Pragramming and data structures

front=front->next;
rear->next=front; //changes
}
temp->next=NULL;
free(temp);
}
}

void display()
{
QUEUE *i;
if(front==NULL)
printf("\nQUEUE IS EMPTY");
else
{
printf("\nQueue has the element(s)\n");
printf("\n\t---------------------------------------\n");
for(i=front;i!=rear;i=i->next) //changes
printf("\t%d",i->element);
printf("\t%d",i->element);
printf("\n\t---------------------------------------\n");
}
}

void main()
{
int op;
while(1)
{
printf("\n1.INSERT\t2.DELETE\t3.DISPLAY\t4.EXIT");
printf("\nEnter your option ");
scanf("%d",&op);
switch(op)
{
case 1: insert(); break;
case 2: delete(); break;
case 3: display(); break;
case 4: exit(0);
}
}
}

OUTPUT:
1.INSERT 2.DELETE 3.DISPLAY 4.EXIT

20
 CS6202-Pragramming and data structures

Enter your option 1

Enter the element 1
1 is inserted
1.INSERT 2.DELETE 3.DISPLAY 4.EXIT
Enter your option 1
Enter the element 2
2 is inserted
1.INSERT 2.DELETE 3.DISPLAY 4.EXIT
Enter your option 1
Enter the element 3
3 is inserted
1.INSERT 2.DELETE 3.DISPLAY 4.EXIT
Enter your option 1
Enter the element 4
4 is inserted
1.INSERT 2.DELETE 3.DISPLAY 4.EXIT
Enter your option 3
Queue has the element(s)
---------------------------------------
1 2 3 4
---------------------------------------
1.INSERT 2.DELETE 3.DISPLAY 4.EXIT
Enter your option 2
1 is deleted
1.INSERT 2.DELETE 3.DISPLAY 4.EXIT
Enter your option 2
2 is deleted
1.INSERT 2.DELETE 3.DISPLAY 4.EXIT
Enter your option 3
Queue has the element(s)
---------------------------------------
3 4
---------------------------------------
1.INSERT 2.DELETE 3.DISPLAY 4.EXIT
Enter your option 2
3 is deleted
1.INSERT 2.DELETE 3.DISPLAY 4.EXIT
Enter your option 2
4 is deleted
1.INSERT 2.DELETE 3.DISPLAY 4.EXIT
Enter your option 2
QUEUE IS EMPTY

21
 CS6202-Pragramming and data structures

DOUBLE ENDED QUEUE-ARRAY IMPLEMENTATION:

#include<stdio.h>
#define MAX 5
int rear=0,front=0,q[10];

void add_item_front()
{
int num;
printf("\n Enter item to insert:");
scanf("%d",&num);
if(front<=1)
{
printf("\n Cannot add item at front end");
return;
}
else
{
front--;
q[front]=num;
}
}

void add_item_rear()
{
int num;
printf("\n Enter Item to insert : ");
scanf("%d",&num);
if(rear==MAX)
{
printf("\n Queue is Overflow");
return;
}
else
{
rear++;
q[rear]=num;
if(rear==0)
rear=1;
if(front==0)
front=1;
}
}

22
 CS6202-Pragramming and data structures

void delete_item_front()
{
int num;
if(front==0)
{
printf("\n Queue is Underflow\n");
return;
}
else
{
num=q[front];
printf("\n Deleted item is %d\n",num);
if(front==rear)
{
front=0;
rear=0;
}
else
{
front++;
}
}
}

void delete_item_rear()
{
int num;
if(rear==0)
{
printf("\n Cannot delete item at rear end\n");
return;
}
else
{
num=q[rear];
if(front==rear)
{
front=0;
rear=0;
}
else
{
rear--;

23
 CS6202-Pragramming and data structures

printf("\n Deleted item is %d\n",num);

}
}
}

void display()
{
int i;
printf("ELEMENTS OF DOUBLE ENDED QUEUE ARE:\n");
printf("_____________________________________\n");
for(i=front;i<=rear;i++)
{
printf("%d\t",q[i]);
}
printf("\n_____________________________________\n");
}

void main()
{
int op;
while(1)
{
printf("\n1.INSERT FRONT\t2.INSERT REAR\n3.DELETE
FRONT\t4.DELETE REAR\n5.DISPLAY\t6.EXIT\n");
printf("\nEnter your option ");
scanf("%d",&op);
switch(op)
{
case 1: add_item_front(); break;
case 2: add_item_rear(); break;
case 3: delete_item_front(); break;
case 4: delete_item_rear(); break;
case 5: display(); break;
case 6: exit(0);
}
}
}

24
 CS6202-Pragramming and data structures

DOUBLE ENDED QUEUE-LINKED LIST IMPLEMENTATION:

#include <stdio.h>
#include <stdlib.h>
struct node {
int data;
struct node *prev, *next;
};
struct node *head = NULL, *tail = NULL;

struct node * createNode(int data) {

struct node *newnode = (struct node *)malloc(sizeof (struct node));
newnode->data = data;
newnode->next = newnode->prev = NULL;
return (newnode);
}

/*
* create sentinel (dummy head & tail) that helps us to do insertion and deletion
operation at front and rear so easily. And these dummy head and tail wont get deleted
till the end of execution of this program
*/

void createSentinels() {
head = createNode(0);
tail = createNode(0);
head->next = tail;
tail->prev = head;
}

/* insertion at the front of the queue */

void enqueueAtFront(int data) {
struct node *newnode, *temp;
newnode = createNode(data);
temp = head->next;
head->next = newnode;
newnode->prev = head;
newnode->next = temp;
temp->prev = newnode;
}

/*insertion at the rear of the queue */

void enqueueAtRear(int data) {
struct node *newnode, *temp;

25
 CS6202-Pragramming and data structures

newnode = createNode(data);
temp = tail->prev;
tail->prev = newnode;
newnode->next = tail;
newnode->prev = temp;
temp->next = newnode;
}

/* deletion at the front of the queue */

void dequeueAtFront() {
struct node *temp;
if (head->next == tail) {
printf("Queue is empty\n");
} else {
temp = head->next;
head->next = temp->next;
temp->next->prev = head;
free(temp);
}
return;
}

/* deletion at the rear of the queue */

void dequeueAtRear() {
struct node *temp;
if (tail->prev == head) {
printf("Queue is empty\n");
} else {
temp = tail->prev;
tail->prev = temp->prev;
temp->prev->next = tail;
free(temp);
}
return;
}

/* display elements present in the queue */

void display() {
struct node *temp;

if (head->next == tail) {
printf("Queue is empty\n");

26
 CS6202-Pragramming and data structures

return;
}

temp = head->next;
while (temp != tail) {
printf("%-3d", temp->data);
temp = temp->next;
}
printf("\n");
}

int main() {
int data, ch;
createSentinels();
while (1) {
printf("1. Enqueue at front\n2. Enqueue at rear\n");
printf("3. Dequeue at front\n4. Dequeue at rear\n");
printf("5. Display\n6. Exit\n");
printf("Enter your choice:");
scanf("%d", &ch);
switch (ch) {
case 1:
printf("Enter the data to insert:");
scanf("%d", &data);
enqueueAtFront(data);
break;

case 2:
printf("Enter ur data to insert:");
scanf("%d", &data);
enqueueAtRear(data);
break;

case 3:
dequeueAtFront();
break;

case 4:
dequeueAtRear();
break;

case 5:
display();
break;

27
 CS6202-Pragramming and data structures

case 6:
exit(0);

default:
printf("Pls. enter correct option\n");
break;
}
}
return 0;
}

OUTPUT:
1. Enqueue at front 2. Enqueue at rear
3. Dequeue at front 4. Dequeue at rear
5. Display 6. Exit
Enter your choice:1
Enter the data to insert:2
1. Enqueue at front 2. Enqueue at rear
3. Dequeue at front 4. Dequeue at rear
5. Display 6. Exit
Enter your choice:1
Enter the data to insert:3
1. Enqueue at front 2. Enqueue at rear
3. Dequeue at front 4. Dequeue at rear
5. Display 6. Exit
Enter your choice:1
Enter the data to insert:4
1. Enqueue at front 2. Enqueue at rear
3. Dequeue at front 4. Dequeue at rear
5. Display 6. Exit
Enter your choice:5
4 3 2
1. Enqueue at front 2. Enqueue at rear
3. Dequeue at front 4. Dequeue at rear
5. Display 6. Exit
Enter your choice:2
Enter ur data to insert:6
1. Enqueue at front 2. Enqueue at rear
3. Dequeue at front 4. Dequeue at rear
5. Display 6. Exit
Enter your choice:2
Enter ur data to insert:7
1. Enqueue at front 2. Enqueue at rear

28
 CS6202-Pragramming and data structures

3. Dequeue at front 4. Dequeue at rear

5. Display 6. Exit
Enter your choice:5
4 3 2 6 7
1. Enqueue at front 2. Enqueue at rear
3. Dequeue at front 4. Dequeue at rear
5. Display 6. Exit
Enter your choice:3
1. Enqueue at front 2. Enqueue at rear
3. Dequeue at front 4. Dequeue at rear
5. Display 6. Exit
Enter your choice:3
1. Enqueue at front 2. Enqueue at rear
3. Dequeue at front 4. Dequeue at rear
5. Display 6. Exit
Enter your choice:5
2 6 7
1. Enqueue at front 2. Enqueue at rear
3. Dequeue at front 4. Dequeue at rear
5. Display 6. Exit
Enter your choice:4
1. Enqueue at front 2. Enqueue at rear
3. Dequeue at front 4. Dequeue at rear
5. Display 6. Exit
Enter your choice:5
2 6
Enter your choice:4
1. Enqueue at front 2. Enqueue at rear
3. Dequeue at front 4. Dequeue at rear
5. Display 6. Exit
Enter your choice:4
1. Enqueue at front 2. Enqueue at rear
3. Dequeue at front 4. Dequeue at rear
5. Display 6. Exit
Enter your choice:4
Queue is empty

29
 CS6202-Pragramming and data structures

ROUGH

#include<stdio.h>

#include<stdlib.h>

struct node

float coef;

int expo;

struct node *link;

};

struct node *create(struct node *);

struct node *insert_s(struct node *,float,int);

struct node *insert(struct node *,float,int);

void display(struct node *ptr);

void poly_add(struct node *,struct node *);

void poly_mult(struct node *,struct node *);

main( )

struct node *start1=NULL,*start2=NULL;

printf("Enter polynomial 1 :\n");

start1=create(start1);

printf("Enter polynomial 2 :\n");

start2=create(start2);

30
 CS6202-Pragramming and data structures

printf("Polynomial 1 is : ");

display(start1);

printf("Polynomial 2 is : ");

display(start2);

poly_add(start1, start2);

poly_mult(start1, start2);

}/*End of main()*/

struct node *create(struct node *start)

int i,n,ex;

float co;

printf("Enter the number of terms : ");

scanf("%d",&n);

for(i=1;i<=n;i++)

printf("Enter coeficient for term %d : ",i);

scanf("%f",&co);

printf("Enter exponent for term %d : ",i);

scanf("%d",&ex);

start=insert_s(start,co,ex);

return start;

}/*End of create()*/

struct node *insert_s(struct node *start,float co,int ex)

31
 CS6202-Pragramming and data structures

struct node *ptr,*tmp;

tmp=(struct node *)malloc(sizeof(struct node));

tmp->coef=co;

tmp->expo=ex;

/*list empty or exp greater than first one */

if(start==NULL || ex > start->expo)

tmp->link=start;

start=tmp;

else

ptr=start;

while(ptr->link!=NULL && ptr->link->expo >= ex)

ptr=ptr->link;

tmp->link=ptr->link;

ptr->link=tmp;

return start;

}/*End of insert()*/

struct node *insert(struct node *start,float co,int ex)

struct node *ptr,*tmp;

tmp=(struct node *)malloc(sizeof(struct node));

tmp->coef=co;

tmp->expo=ex;

32
 CS6202-Pragramming and data structures

/*If list is empty*/

if(start==NULL)

tmp->link=start;

start=tmp;

else /*Insert at the end of the list*/

ptr=start;

while(ptr->link!=NULL)

ptr=ptr->link;

tmp->link=ptr->link;

ptr->link=tmp;

return start;

}/*End of insert()*/

void display(struct node *ptr)

if(ptr==NULL)

printf("Zero polynomial\n");

return;

while(ptr!=NULL)

printf("(%.1fx^%d)", ptr->coef,ptr->expo);

33
 CS6202-Pragramming and data structures

ptr=ptr->link;

if(ptr!=NULL)

printf(" + ");

else

printf("\n");

}/*End of display()*/

void poly_add(struct node *p1,struct node *p2)

struct node *start3;

start3=NULL;

while(p1!=NULL && p2!=NULL)

if(p1->expo > p2->expo)

start3=insert(start3,p1->coef,p1->expo);

p1=p1->link;

else if(p2->expo > p1->expo)

start3=insert(start3,p2->coef,p2->expo);

p2=p2->link;

else if(p1->expo==p2->expo)

start3=insert(start3,p1->coef+p2->coef,p1->expo);

34
 CS6202-Pragramming and data structures

p1=p1->link;

p2=p2->link;

/*if poly2 has finished and elements left in poly1*/

while(p1!=NULL)

start3=insert(start3,p1->coef,p1->expo);

p1=p1->link;

/*if poly1 has finished and elements left in poly2*/

while(p2!=NULL)

start3=insert(start3,p2->coef,p2->expo);

p2=p2->link;

printf("Added polynomial is : ");

display(start3);

}/*End of poly_add() */

void poly_mult(struct node *p1, struct node *p2)

struct node *start3;

struct node *p2_beg = p2;

start3=NULL;

if(p1==NULL || p2==NULL)

35
 CS6202-Pragramming and data structures

printf("Multiplied polynomial is zero polynomial\n");

return;

while(p1!=NULL)

p2=p2_beg;

while(p2!=NULL)

start3=insert_s(start3,p1->coef*p2->coef,p1->expo+p2->expo);

p2=p2->link;

p1=p1->link;

printf("Multiplied polynomial is : ");

display(start3);

}/*End of poly_mult()*/

EVALUATION OF POSTFIX EXPRESSION

#include<stdio.h>
#define SIZE 50            /* Size of Stack */
int s[SIZE];
int top=-1;       /* Global declarations */
 
push(int elem)
{                       /* Function for PUSH operation */
 s[++top]=elem;

36
 CS6202-Pragramming and data structures

}
 
int pop()
{                      /* Function for POP operation */
 return(s[top--]);
}
 
main()
{                         /* Main Program */
 char pofx[50],ch;
 int i=0,op1,op2;
 printf("\n\nRead the Postfix Expression ? ");
 scanf("%s",pofx);
 while( (ch=pofx[i++]) != '\0')
 {
  if(isdigit(ch)) push(ch-'0'); /* Push the operand */
  else
  {        /* Operator,pop two  operands */
   op2=pop();
   op1=pop();
   switch(ch)
   {
   case '+':push(op1+op2);break;
   case '-':push(op1-op2);break;
   case '*':push(op1*op2);break;
   case '/':push(op1/op2);break;
   }
  }
 }
 printf("\n Given Postfix Expn: %s\n",pofx);
 printf("\n Result after Evaluation: %d\n",s[top]);
}

OUTPUT:
Read the Postfix Expression ? 234+*5*
Given Postfix Expn: 234+*5*
Result after Evaluation: 70

BALANCING SYMBOLS
#include <stdio.h>
#define max 50
int top = -1;
char stk[max],exp[100];

void push(int element)

{

37
 CS6202-Pragramming and data structures

top++;
stk[top]= element;
}

char pop()
{
int element=stk[top];
return element;
}

void main()
{

int i;
printf("\nEnter an infix expression ");
gets(exp);
for(i=0; exp[i] != '\0'; i++)
{
if( exp[i]=='(' || exp[i] =='[' || exp[i] == '{' )
{
push(exp[i]);
}
else if ( exp[i] == ')' )
{
if( pop() == '(' )
top--;
else
{
printf("Unbalanced exp");
exit(0);
}
}
else if ( exp[i] == ']' )
{
if( pop() == '[' )
top--;
else
{
printf("Unbalanced exp");
exit(0);
}
}
else if ( exp[i] == '}' )
{

38
 CS6202-Pragramming and data structures

if( pop() == '{' )

top--;
else
{
printf("Unbalanced exp");
exit(0);
}
}
} // for
if( top == -1 )
printf("The expression %s is balanced",exp);
else
printf("The expression %s is not balanced",exp);
} // main

OUTPUT:
Enter an infix expression (a+(b*c)-(D/O))
The expression (a+(b*c)-(D/O)) is balancedlinux-yx0y:/home/root1/DS # ./a.out

Enter an infix expression {j+k*(9/7)

The expression {j+k*(9/7) is not balanced

INFIX TO POSTFIX EXPRESSION:

#include<stdio.h>
#include<string.h>
int G(char);
int F(char);
void infix2postfix(char *,char *);
int main()
{

39
 CS6202-Pragramming and data structures

char infix[30],postfix[30];
printf("Enter the infix expression:\n");
scanf("%s",infix);
infix2postfix(infix,postfix);
printf("The postfix expression is:\n");
printf("%s",postfix);
return 0;
}
int G(char symbol)
{
switch(symbol)
{
case '+':
case '-': return 1;
case '*':
case '/': return 3;
case '$':
case '^': return 6;
case '(': return 9;
case ')':return 0;
default: return 7;
}
}
int F(char symbol)
{
switch(symbol)
{
case'+':
case '-':return 2;
case '*':
case '/': return 4;
case '$':
case '^': return 5;
case '(': return 0;
case '#': return -1;
default:return 8;
}
}
void infix2postfix(char * infix, char * postfix)
{
int top=-1,i,j=0;
char s[30],symbol;
s[++top]='#';
for(i=0;i<strlen(infix);i++)

40
 CS6202-Pragramming and data structures

{
symbol=infix[i];
while(F(s[top])>G(symbol))
postfix[j++]=s[top--];
if(F(s[top])!=G(symbol))
s[++top]=symbol;
else
top--;
}
while(s[top]!='#')
postfix[j++]=s[top--];
postfix[j]='\0';
}

OUTPUT:
Enter the infix expression:
(a+b)*c/d
The postfix expression is:
ab+c*d/
Enter the infix expression:
A/B^C+D*E-F*G
The postfix expression is:
ABC^/DE*+FG*-
Enter the infix expression:
(B^2-4*A*C)^(1/2)
The postfix expression is:
B2^4A*C*-12/^

41