Array implementation of Stack - Weebly
INDEX
1. Array Implementation Of Stack
2. Application Of Stack – Conversion Of Infix To Postfix
3. Implementation Of Linear Queue Using Arrays
4. Array Implementation Of Circular Queue
5. Linked List Implementation Of Stack
6. Singly linked list – Linked list implementation
7. Doubly linked list – Linked list implementation
8. Polynomial Manipulation
9. Tree Traversals
10. Expression Tree
11. Priority Queue Using Heap
12. Hashing Technique
13. Dijkstra’s Algorithm
14. Back tracking algorithm – knap sack problem
Ex. no.: 1
Date :
ARRAY IMPLEMENTATION OF STACK
Aim
To write a C-program to implement stack using array data structure.
And perform the following stack operations
1. POP
2. PUSH
3. PEEP
Algorithm
STEP 1:Start
STEP 2:Initialize stack, will=1,i, num
STEP 3:Add element in stack
PUSH(S,TOP,X)
3.a. [Check overflow condition]
If(TOP>=N) then
Write(“Stack is full”)
3.b. [Insert element]
[Increment TOP]
TOP =1)
post[j++]=pop();
push(2);
break;
case '*':
while(stack[top]>=3)
post[j++]=pop();
push(3);
break;
case '/':
while(stack[top]>=3)
post[j++]=pop();
push(4);
break;
case '^':
while(stack[top]>=4)
post[j++]=pop();
push(5);
break;
case '(':
push(0);
break;
case ')':
while(stack[top]!=0)
post[j++]=pop();
top--;
break;
default:
post[j++]=inf[i];
}
}
while(top>0)
post[j++]=pop();
printf("\nPostfix Expression is :: %s",post);
}
void push(int ele)
{
top++;
stack[top]=ele;
}
char pop()
{
char e;
e=stack[top];
top--;
switch(e)
{
case 1:
e='+';
break;
case 2:
e='-';
break;
case 3:
e='*';
break;
case 4:
e='/';
break;
case 5:
e='^';
break;
}
return(e);
}
Output:
Enter the infix expression :: (a+b)/(c*d)
Postfix Expression is :: ab+cd*/
Manual Calculation
| SE EXPRESSION | STACK | RESULT FIELD |
|( |( | |
|A | |A |
|+ |+,( |A |
|B |+,( |AB |
|) |),( |AB+ |
|/ |/ |AB+ |
|( |(,/ | |
|C |(,/ |AB+C |
|- |-,(,/ |AB+C |
|D |-,(,/ |AB+CD |
|+ |+,(,/ |AB+CD- |
|E |+,(,/ |AB+CD-E |
|) |),+,(,/ |AB+CD-E+ |
|+ |+,/ |AB+CD-E+/ |
|F |+ |AB+CD-E/F |
|- |- |AB+CD-E/F+ |
|G |- |AB+CD-E/F+G |
| | |AB+CD-E/F+G- |
Ex.no.3
Date:
IMPLEMENTATION OF LINEAR QUEUE USING ARRAYS
Aim
To write a C-program to implement linear queue data structure using arrays.
Algorithm
STEP 1: Start
STEP 2: [Include all header files]
STEP 3: [Declare the variables]
STEP 4: [If n->1 call the function Enqueue( )]
STEP 5: [If n->2 call the function Dequeue( )]
STEP 6: [If n->3 call the function Peep( )]
STEP 7: [If n->4 call the function Size( )]
STEP 8: [If n->5 call the function View( )]
STEP 9: [else Exit( )]
STEP 10: Stop
Algorithm for Enqueue( )
STEP 1: If[front= =rear]
Initialize front=rear=0
STEP 2: else rear=(rear+1)% qsize
Set queue[rear] =value
[return]
Algorithm for Dequeue( )
STEP 1: If[front = =rear]
1.1: temp=queue[front]
1.2: Initialize front=rear=-1
STEP 2:else
2.1: front=(front+1)% qsize
[return]
Algorithm for Peep( )
STEP 1:If [front= =rear]
STEP 1.1: temp=queue[front]
[return]
Algorithm for Size( )
STEP 1:If [front= =rear]
1.1: Set f=front
1.2: Set count=1
STEP 2: If [front!=rear]
2.1: front=(front+1)%qsize
2.2: set count=count+1
[return]
Algorithm for View( )
STEP 1: If [front = =rear]
Write (“Queue is empty”)
STEP 2: else
[display elements]
Coding:
#include
#include
#define size 15
int queue[size],front=0,rear=0,b;
int res;
void enqueue();
void dequeue();
void display();
void main()
{
int c;
clrscr();
printf("\n1.Insertion\n2.Deletion\n3.Display");
do
{
printf("\n\nEnter your Choice :: ");
scanf("%d",&c);
switch(c)
{
case 1:
enqueue();
break;
case 2:
dequeue();
break;
case 3:
printf("\n\nContents of queue is \t");
display();
break;
default:
printf("\nInvalid Choice......");
exit(0);
}
}while(c=size)
{
printf("\nOverflow");
return;
}
else
{
printf("\nEnter the number to be entered :: ");
scanf("%d",&b);
rear++;
queue[rear]=b;
printf("\nNumber pushed is %d",queue[rear]);
if(front==0)
front=1;
return;
}
}
void dequeue()
{
if(front==0)
{
printf("\nUnderflow");
return;
}
else
{
res=queue[front];
if(front==rear)
{
front=0;
rear=0;
}
else
front++;
}
printf("\nDeleted element is %d",res);
return;
}
void display()
{
int i;
if(front==0)
{
printf("\nUnderflow");
return;
}
for(i=front;i2 2 ---> 3 ---> 5 3 ---> 5 next=top;
top=newnode;
}
else
{
newnode->next=top;
top=newnode;
}
printf("\n\nNumber pushed is %d",x);
return(x);
}
void pop()
{
struct node *t;
if(top==NULL)
printf("\n\nStack Underflow");
else
{
t=top;
top=top->next;
printf("\nDeleted element is %d",t->data);
free(t);
}
getch();
}
void display()
{
struct node*i;
for(i=top;i!=NULL;i=i->next)
printf("%d , ",i->data);
if(top==NULL)
printf("Stack is empty");
getch();
}
Output:
1.Push
2.Pop
3.Display
Enter your Choice :: 1
Enter the number to be pushed into the stack :: 5
Number pushed is 5
Enter your Choice :: 1
Enter the number to be pushed into the stack :: 10
Number pushed is 10
Enter your Choice :: 3
Contents of stack :: 10 , 5 ,
Enter your Choice :: 2
Deleted element is 10
Enter your Choice :: 3
Contents of stack :: 5 ,
Enter your Choice :: 5
Invalid Choice......
Ex.no.:6
Date :
LINKED LIST IMPLEMENTATION OF SINGLY LINKED LIST
Aim:
To write a program to implement singly linked list using linked list.
Algorithm:
Step 1: initialize the list as null
Step 2: Display linked list operations insert, delete and display the result.
Step 3: If choice is 1 the read element to be inserted and call the insert function
Step 4: If choice is 2 then read element to be deleted and call the delete function
Step 5: If choice is 3 then call display function
Step 6: If choice is default the exit the program.
Program:
#include
#include
#include
void insert(int x);
void deletion(int x);
void display();
struct node
{
int element;
struct node *next;
}*list=NULL,*p;
struct node *find(int s)
{
p=list->next;
while(p!=NULL && p->element!=s)
p=p->next;
return p;
}
struct node *findprevious(int s)
{
p=list;
while(p->next!=NULL && p->next->element!=s)
p=p->next;
return p;
}
void main()
{
int data,ch;
clrscr();
printf("\n\n1.INSERT\n\n2.DELETE\n\n3.DISPLAY");
do
{
printf("\n\nEnter your Choice :: ");
scanf("%d",&ch);
switch(ch)
{
case 1:
printf("\n\nEnter the element to be inserted::");
scanf("%d",&data);
insert(data);
break;
case 2:
printf("\n\nEnter the element to be deleted::");
scanf("%d",&data);
deletion(data);
break;
case 3:
display();
break;
default:
printf("\n\nInvalid Choice......");
getch();
exit(0);
}
}while(chelement=x;
if(list->next==NULL)
{
list->next=newnode;
newnode->next=NULL;
}
else
{
printf("\n\nEnter the value of the element to be inserted ::");
scanf("%d",&pos);
p=find(pos);
newnode->next=p->next;
p->next=newnode;
}
}
void deletion(int x)
{
struct node *temp;
temp=malloc(sizeof(struct node));
p=findprevious(x);
if(p->next!=NULL)
{
temp=p->next;
p->next=temp->next;
printf("\n\nThe deleted element is %d",temp->element);
free(temp);
}
else
printf("\n\nElement is not found in the list!!!");
}
void display()
{
if(list->next==NULL)
printf("\n\nList is empty!!!");
else
{
p=list->next;
printf("\n\nThe contents of the list are\n::");
while(p!=NULL)
{
printf("%d ->",p->element);
p=p->next;
}
}
}
Output:
1.INSERT
2.DELETE
3.DISPLAY
Enter your Choice ::1
Enter the element to be inserted::2
Enter your Choice ::1
Enter the element to be inserted::5
Enter the value of the element to be inserted ::2
Enter your Choice :: 3
The contents of the list are::2 ->5 ->NULL
Enter your Choice :: 1
Enter the element to be inserted::7
Enter the value of the element to be inserted ::2
Enter your Choice :: 3
The contents of the list are ::2 ->7 ->5 ->NULL
Enter your Choice :: 2
Enter the element to be deleted::5
The deleted element is 5
Enter your Choice :: 3
The contents of the list are ::2 ->7 ->NULL
Ex.no.7
Date:
DOUBLY LINKED LIST – LINKED LIST IMPLEMENTATION
Aim:
To write a program to implement doubly linked list using linked list.
Algorithm:
Step 1: Declare header and pointer variables
Step 2: Display the choices
Step 3: If choice is 1 the get the element to be inserted in beginning and call ins_beg function.
Step 4: If choice is 2 the get the element to be inserted in the end and call the ins_end function
Step 5: If choice is 3 then get the element to be deleted and call deletion function.
Step 6: If choice is 4 then call display duncation
Step 7: If choice is default the exit the program
Step 8: Terminate the program execution.
Program:
#include
#include
#include
void display(struct node *first);
struct node
{
int data;
struct node *lptr,*rptr;
}*head;
struct node *ins_beg(int x,struct node *first)
{
struct node *new1,*cur,*prev;
new1=malloc(sizeof(struct node));
if(first==NULL)
{
new1->data=x;
new1->lptr=NULL;
new1->rptr=NULL;
return new1;
}
else
{
new1->data=x;
new1->lptr=NULL;
new1->rptr=first;
return new1;
}
}
struct node *ins_end(int x,struct node *first)
{
struct node *new1,*cur,*prev;
new1=malloc(sizeof(struct node));
if(first==NULL)
{
new1->data=x;
new1->lptr=NULL;
new1->rptr=NULL;
return new1;
}
else
{
cur=first;
while(cur->rptr!=NULL)
{
prev=cur;
cur=cur->rptr;
}
cur->rptr=new1;
new1->data=x;
new1->lptr=cur;
new1->rptr=NULL;
return first;
}
}
struct node *deletion(struct node *first,int del)
{
struct node *prev,*cur;
cur=first;
if(first==NULL)
{
printf("\n\nNo data present!!!");
getch();
}
else if(first->data==del)
{
printf("\n\nData %d is deleted",first->data);
first=first->rptr;
getch();
return first;
}
else
{
while(cur->rptr!=NULL && cur->data!=del)
{
prev=cur;
cur=cur->rptr;
}
if(cur->rptr==NULL && cur->data!=del)
printf("\n\nData is not present!!!");
else if(cur->rptr!=NULL && cur->data==del)
{
prev->rptr=cur->rptr;
(cur->rptr)->lptr=prev;
printf("\n\nData % d is deleted",cur->data);
}
else if(cur->rptr==NULL && cur->data==del)
{
prev->rptr=NULL;
printf("\n\nData %d is deleted:",cur->data);
}
getch();
return first;
}
}
void main()
{
int x,ch,del;
head=NULL;
clrscr();
printf("\n1.Insert in Begining\n2.Insert in the End\n3.Delete\n4.Display");
while(1)
{
printf("\n\nEnter your Choice :: ");
scanf("%d",&ch);
switch(ch)
{
case 1:
printf("\n\nEnter the element to be inserted::");
scanf("%d",&x);
head=ins_beg(x,head);
break;
case 2:
printf("\n\nEnter the element to be inserted::");
scanf("%d",&x);
head=ins_end(x,head);
break;
case 3:
printf("\n\nEnter the element to be deleted::");
scanf("%d",&del);
head=deletion(head,del);
break;
case 4:
display(head);
break;
default:
printf("\n\nInvalid Choice......");
getch();
exit(0);
}
}
}
void display(struct node *first)
{
struct node *temp;
temp=first;
if(temp==NULL)
printf("\n\nList is empty!!!");
while(temp!=NULL)
{
printf("%d ->",temp->data);
temp=temp->rptr;
}
getch();
}
Output:
1.Insert in Begining
2.Insert in the End
3.Delete
4.Display
Enter your Choice :: 1
Enter the element to be inserted::2
Enter your Choice :: 1
Enter the element to be inserted::3
Enter your Choice :: 4
3 ->2 ->
Enter your Choice :: 2
Enter the element to be inserted::1
Enter your Choice :: 2
Enter the element to be inserted::5
Enter your Choice :: 4
3 ->2 ->1 ->5 ->
Enter your Choice :: 3
Enter the element to be deleted::1
Data 1 is deleted
Enter your Choice :: 4
3 ->2 ->5 ->
Ex.no.:8
Date :
POLYNOMIAL MANUPULATION
Aim
To implement polynomial manipulation using doubly linked lists.
Algorithm
POLYADD(POLY1: POLY2:POLY)
HEAD:POLY
Step 1: Assign HEAD+=NULL
Step2: While (POLY !=null)
Step3: HEAD=INSERTNODE(HEAD,COPYNODE,(POLY1,1))
Step4: POLY1=POLY1(NEXT
Step5: [End of Step2 while structure]
Step6: While(POLY2 1=NULL)
Step7: HEAD =INSERTNODE(HEAD,COPYNODE(POLY2,1))
Step8: POLY2=POLY2(NEXT
Step9: [End of Step 6 while Structure]
Step10: Return HEAD
END POLYADD()
Algorithm for polynomial subtraction
POLYSUB(POLY1:POLY, POLY2:POLY)
HEAD:POLY
Step1: Assign HEAD=NULL
Step2: While(POLY1!=NULL)
Step3: HEAD=INSERTNODE(HEAD,COPYNODE(POLY1,1))
Step4: POLY1=POLY1( NEXT
Step5: [End of Step2 while Structure]
Step6:While(POLY2!=NULL)
Step7: HEAD=INSERTNODE(HEAD,COPYNODE(POLY2,-1))
Step8: POLY2=POLY2(NEXT
Step9: [End of Step 6 While Structure]
Step10: Return HEAD
END POLYSUB()
Coding:
#include
#include
struct link
{
int coeff;
int pow;
struct link *next;
};
struct link *poly1=NULL,*poly2=NULL,*poly=NULL;
void create(struct link *node)
{
char ch;
do
{
printf("\nEnter the coefficient :");
scanf("%d",&node->coeff);
printf("\nEnter the power :");
scanf("%d",&node->pow);
node->next=(struct link *)malloc(sizeof(struct link));
node=node->next;
node->next=NULL;
printf("\nContinue??? (Y/N) :");
ch=getch();
}while(ch=='y' || ch=='Y');
}
void display(struct link *node)
{
while(node->next!=NULL)
{
printf("%dx^%d",node->coeff,node->pow);
node=node->next;
if(node->next!=NULL)
printf(" + ");
}
}
void polyadd(struct link *poly1,struct link *poly2,struct link *poly)
{
while(poly1->next && poly2->next)
{
if(poly->pow > poly2->pow)
{
poly->pow=poly1->pow;
poly->coeff=poly1->coeff;
poly1=poly1->next;
}
else if(poly1->pow < poly2->pow)
{
poly->pow=poly2->pow;
poly->coeff=poly2->coeff;
poly2=poly2->next;
}
else
{
poly->pow=poly1->pow;
poly->coeff=poly1->coeff+poly2->coeff;
poly1=poly1->next;
poly2=poly2->next;
}
poly->next=(struct link *)malloc(sizeof(struct link));
poly=poly->next;
poly->next=NULL;
}
while(poly1->next||poly2->next)
{
if(poly1->next)
{
poly->pow=poly1->pow;
poly->coeff=poly1->coeff;
poly1=poly1->next;
}
if(poly2->next)
{
poly->pow=poly2->pow;
poly->coeff=poly2->coeff;
poly2=poly2->next;
}
poly->next=(struct link *)malloc(sizeof(struct link));
poly=poly->next;
poly->next=NULL;
}
}
void main()
{
poly1=(struct link *)malloc(sizeof(struct link));
poly2=(struct link *)malloc(sizeof(struct link));
poly=(struct link *)malloc(sizeof(struct link));
clrscr();
printf("\nEnter the first polynomial::");
create(poly1);
printf("\nFirst polynomial is :: \n");
display(poly1);
printf("\nEnter the second polynomial::");
create(poly2);
printf("\nSecond polynomial is :: \n");
display(poly2);
polyadd(poly1,poly2,poly);
printf("\nAddition of the two polynomials::");
display(poly);
getch();
}
Output
Enter the first polynomial::
Enter the coefficient :5
Enter the power :3
Continue??? (Y/N) :Y
Enter the coefficient :3
Enter the power :2
Continue??? (Y/N) :
First polynomial is ::
5x^3 + 3x^2
Enter the second polynomial::
Enter the coefficient :7
Enter the power :3
Continue??? (Y/N) :
Second polynomial is ::
7x^3
Addition of the two polynomials::12x^3 + 3x^2
Ex.no.:9
Date :
BINARY SEARCH TREE
Aim
To write a C program to implement a stack using binary search tree.
Algorithm
1. [Include all the necessary header files.]
2. [Declare the structure with all necessary variables.]
3. Read x;
4. Call INORDER().
5. Call PREORDER().
6. Call POSTORDER().
7. Call display().
8.
Algorithm For INSERT(P,X)
1. If (p(NULL)
Create P
Plchild (P(rchild(NULL
Else
1. while(TEMP!=NULL)
2. Temp2(Temp1
3. If(temp1(data(x)
4. Else Temp1(Temp1(rchild
5. [End of while structure]
6. If(temp2(data(x)
7. Temp 2(Temp2(lchild
8. Temp 2(data(x
9. Temp2(data(slchild(temp2(rchild Null
10. Else
11. Temp 2(Temp2(Temp2(rchild(null
12. Temp2(data(x
13. Temp 2(lchild(Temp 2(rchild(null
14. [Return P]
Algorithm For INORDER(p)
1.If(p!=Null)
2. CALL INORDER (p(xdhild)
3. WRITE(D(data)
4.CALL INORDER (p(rchild)
5. [End the function]
Algorithm for PREORDER
1. If (pl=NULL)
2. WRITE (P(Data)
3. CALL PREORDER (P(lCHILD)
4. CALL PREORDER (P( Rchild)
5. [END OF FUNTION]
Algorithm for POSTORDER
1. If (P!=NULL)
2. Call POSTORDER (P(lchild)
3. Call POSTORDER (P(rchild)
4. Write (P(data)
5. [End of function]
Algorithm for COUNT
If (P==NULL)
1. Return 0
2. Else
3. [Return (1+count(P(lchild)+call count(P(rchild)) ]
4. Algorithm for postorder
Algorithm for DISPLAY
If (T!=NULL)
1. X((lm+rm)/2
2. Call goto xy (x,4*y)
3. Write (t--.data)
4. Call display (t(lchild, lm,x, l+1)
5. Call display (t(rchild, x, rm,l+1)
6. [END THE FUNCTION}
Algorithm for SEARCH
1. while(temp!=NULL)
2. If (temp(data(t)
[Return temp]
3.If (Temp(data>x)
Temp(temp(lchild
4. ELSE
Temp(temp(rchild
5. [RETURN NULL]
Ex.no. :10
Date :
EXPRESSION TREE
Aim:
To write a C program to demonstrate an expression tree.
Algorithm for Main ()
Step 1: [ INCLUDE NECESSARY HEADER FILES]
Step 2: [READ X]
Step 3:[ CALL EXPTREE(),CALL DISPLAY(), CALL INORDER(),CALL
PREORDER(),CALL EVALUATE ()]
Algorithm for EXPTREE()
Step 1: Read Character
Step 2: IF Character operator then
CALL PUSH_OP()
Step 3: [IF Character has only numbers]
IF [ is ALnum( str[i] 1 )] THEN
CREATE Newnode
Step 4: Check for ‘ NULL ‘ condition
Step 5: ASSIGN priority
Step 6: IF ( Priority !=0) THEN CALL POP_OP()
Step 7: IF Character = ‘)’ THEN CALL PUSH_OP()
Algorithm for INORDER (tree t)
Step 1: IF (t!=NULL) THEN
CALL INORDER(t left)
Step 2: PRINT t element
Step 3: CALL INORDER(t right)
Algorithm for PREORDER (tree t)
Step 1: IF (t!=NULL) THEN
PRINT t element
Step 2: CALL PREORDER(t left)
Step 3: CALL INORDER(t right)
Algorithm for POSTORDER(tree t)
Step 1: IF (t!=NULL) THEN
CALL POSTORDER(t left)
CALL POSTORDER(t right)
Step 2: PRINT t element
Ex.no.:11
Date :
PRIORITY QUEUE USING HEAP
Aim:
To implement priority queue using Heap in C program.
Algorithm:
Step 1: [Include necessary header files]
Step 2: [Define maxsize as 15]
Step 3: [Declare necessary variables]
Step 4: READ option, opt
IF opt is 1 THEN CALL INSERT()
IF opt is 2 THEN CALL DELMAX()
IF opt is 3 THEN CALL DIS()
Step 5: [END OF MAIN FUNCTION]
Algorithm For INSERT()
Step 1: I ne1+1
Step 2: IF (I MAXSIZE)
WRITE (“ Heap size exceeded”)
RETURN FALSE
IF ( (I> 1) && (arraysize [i/2]< item) )
array[I] array[i/2]
I I/2
Array[I ] item
RETURN TRUE
Algorithm For DELMAX()
Step 1: IF (!nel)
WRITE (“HEAP IS EMPTY”)
ELSE
*item array [I]
Array[i] array [nel--]
CALL adjust (array,I,nel)
Ex.no.:12
Date :
HASHING TECHNIQUE
Aim:
To implement a program using Hashing technique.
Algorithm:
Step1: Include necessary header files
Step2: Declare necessary variables
Step3: Check the value of *S
Then call Insert( )
Print “Enter the string”
Read S
Step4: Check the value of *S
Step5: Then print S by calling hGetVal( )
Step6: Call PrintHash( )
Step7: End
Algorithm For hINSERT( ):
Step1: Allocate memory to pointer
Step2: Assign index hGetIndex ( )
Step3: Assign Ptr Key Strdup(key)
Ptr Val Val
Ptr next h[index]
h[index] Ptr
Step4: Print “h[index]=key”
Step5: Return
Algorithm For hGETVALUE( ):
Step1: [Ptr=h[hGetIndex(key)]]
Step2: If[Ptr && strcmp(Ptr key)]
Then Ptr Ptr next
Step3: If[Ptr],Check the value of Ptr
[Return Ptr Val]
Step4: [Return -1]
Algorithm For PRINTHASH( ):
Step1: Initialise i=0
Step2: If [i < Hash size]
Then Print i
Assign Ptr h[i]
Check the value of Ptr
If[Ptr!=0]
Then Ptr Ptr next
Print “Ptr key=Ptr Val”
Step3: [Return]
Coding:
#include
#include
void main()
{
int a[10]={0,0,0,0,0,0,0,0,0,0};
int n,value,temp,hashvalue;
clrscr();
printf("Enter the value of n (table size) ::");
scanf("%d",&n);
do
{
printf("\nEnter the hash value ::");
scanf("%d",&value);
hashvalue=value%n;
if(a[hashvalue]==0)
{
a[hashvalue]=value;
printf("\na[%d] The value %d is stored",hashvalue,value);
}
else
{
for(hashvalue++;hashvalue ................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related searches
- stack overflow how to ask
- stack overflow forum
- implementation phase of strategic planning
- numpy array index of value
- stack up against definition
- stack against meaning
- np stack to end of array
- example of an implementation plan
- types of implementation strategies
- implementation stage of sdlc
- implementation of a strategic plan
- z score practice worksheet weebly answers