⋆ Implementation Of Stack Using Array ⋆
Stack Definition:
A collection of items in which only the most recently added item may be removed. The
latest added item is at the top. Basic operations are push and pop. Often top and is Empty
are available, too. Also known as "last-in first-out" or LIFO
Push:
The puss operation adds to the top of the list, hiding any items already on the stack, or
initializing the stack if a is empty
Pop:
The pop operation removes an item from the top of the list, and returns this value to
the caller. A pop either reveals previously concealed items, or results in an empty list
Stack Applications:
1. Expression evaluation.
2. Backtracking (game playing, finding paths, exhaustive searching)
3. Memory management, run-time environment for nested language features.
Algorithm steps:
Step 1: Define a stack size
Step 2: Read the stack operation.
Step 3: Read the stack element
Step 4: Check the stack operation is Push or Pop
Step 5: If operation is push then check the stack status.
1
i. If stack status is over flow, we can't push the element in to stack,
ii. Otherwise, we can add the data into stack
iii. Move top to meet position
Program:
#include <stdio.h>
//#include <ctype.h>
#define MAXSIZE S
int stack MAXSIZE];
int top=0; //index pointing to the top of stack
void main() {
void push();
void pop();
void display();
int will=1,i;
clrscr();
while(1) {
printf("\n\n\nMAIN MENU:\n\n1.PUSH\n2.POP\n3.EXIT\n\nENTER YOUR
CHOICE:);
scanf("%d",&will);
switch(will) {
case 1:
push();
2
display();
break;
case 2:
pop();
display();
break;
case 3:
exit(0);
break;
default:
printf("Invalid choice");
} //end of outer while
} //end of main
void push() {
int num;
if(top>=MAXSIZE) {
printf("\nSTACK FULL");
return;
else {
if(top<0) {
top=0;
3
printf("\n\nENTER STACK ELEMENT:");
scanf("%d", &num);
stack[top++]=num;
void pop() {
if(top>=0) {
top--;
void display() {
int i;
if(top<=0) {
printf("\n\nSTACK EMPTY");
else{
for(i=top-1; i>=0; i--){
printf("\n\n%d", stack[i]);
if(i==(top-1)){
printf("--->TOP");
4
}
Output:
MAIN MENU:
1.PUSH
2.POP
3.EXIT
ENTER YOUR CHOICE: 1
ENTER THE STACK ELEMENT: 10
10-->TOP
MAIN MENU:
1.PUSH
2.POP
3.EXIT
ENTER YOUR CHOICE: 1
ENTER THE STACK ELEMENT: 20
20-->TOP
10
MAIN MENU:
1.PUSH
2.POP
3.EXIT
ENTER YOUR CHOICE: 1
5
ENTER THE STACK ELEMENT: 30
30-->TOP
20
10
MAIN MENU:
1.PUSH
2.POP
3.EXIT
ENTER YOUR CHOICE: 2
20-->TOP
10
MAIN MENU:
1.PUSH
2.POP
3.EXIT
ENTER YOUR CHOICE:
10-->TOP
MAIN MENU:
1.PUSH
2.POP
3.EXIT
ENTER YOUR CHOICE: 1
STACK EMPTY
6
⋆ Implementation Of Queue Using Array ⋆
Queue:
A Queue is a linear data structure which follows First In First Out (FIFO) principle, in
which insertion is performed at rear end deletion is performed at front end.
(or)
A queue is a "waiting line" type of data structure. Much like with a stack, we can
insert items into a queue and remove items from a queue. However, a queue has "first
come, first served" behavior in that the first item inserted into the queue is the first one
removed.
Operations on Queue:
1. Enqueue
2. Dequeue
Exception condition:
1. Overflow: Attempt to insert an element, when the queue is full.
2. Underflow: Attempt to delete an element from the queue, when the queue is
empty.
Uses of Queues:
Queues are commonly used in operating systems and other software where some
sort of waiting line has to be maintained for obtaining access to a resource. For example,
an operating system may keep a queue of processes that are waiting to run on the CPU.
It might also keep a queue of print jobs that are waiting to be printed on a printer.
Queues are also used in simulations of stores and their waiting lines at the check-out
counters.
7
Algorithm Steps:
Step 1: Initialize the queue variables front =0 and rear-1
Step 2: Read the queue operation type.
Step 3: Check the queue operations status.
i. If it is Insertion then do the following steps
1. Check rear queue size is true increment the rear by one and read the
queue
element and also display queue, otherwise display the queue is full.
2. Go to Step2.
ii. If it is deletion then do the following steps
1. Check rear front is true then display the queue is empty.
2. Move the elements to one step forward (i.e. move to previous index
3. Decreases the rear value by one (rear-rear-1).
4. Display queue
5. Go to Step2.
Program:
#include<stdio.h>
#include<conio.h>
#define SIZE 5
int i,rear, front, item,s[SIZE];
void insert(int item, int s[]);
void del(int s[]);
void display(int s[]);
void main(){
8
int ch;
clrscr();
front=0;
rear=-1;
do{
printf("\n\n1.INSERTION\N 2.DELETION\N 3.EXIT\N");
printf("\NENTER YOUR CHOICE:");
scanf("%d", &ch);
switch(ch){
case 1:
printf("\n\tINSERTION\n");
if(rear>=SIZE-1){
printf("\t\nQUEUE IS FULL")
else{
printf("\nENTER AN ELEMENT:");
scanf("%d", &item);
insert(item, s);
}
display(s);
break;
case 2:
printf("\n\tDELETION\n");
if(front>rear){
printf("\t\nQUEUE IS EMPTY");
9
}
else{
del(s);
}
display(s);
break;
}while(ch!=3);
getch();
void insert(int item, int s[]){
if(rear<SIZE){
rear=rear-1;
s[rear]=item;
void del(int s[]){
int i;
item=s[front];
for(i=0; i<=rear; i++){
s[i]=s[i+1];
rear--;
}
printf("\nDELETED ELEMENT IS %d\n\n", item);
10
void display(int s[]){
printf("\n");
for(i=front; i<=rear; i++){
printf("\t%d", s[i]);
}
}
Output:
1.INSERTION
2.DELETION
3.EXIT
ENTER YOUR CHOICE: 1
INSERTION
ENTER AN ELEMENT: 10
10
1.INSERTION
2.DELETION
3.EXIT
ENTER YOUR CHOICE: 1
INSERTION
ENTER AN ELEMENT: 20
10 20
11
1.INSERTION
2.DELETION
3.EXIT
ENTER YOUR CHOICE: 1
INSERTION
ENTER AN ELEMENT: 30
10 20 30
1.INSERTION
2.DELETION
3.EXIT
ENTER YOUR CHOICE: 1
INSERTION
QUEUE IS FULL
10 20 30
1.INSERTION
2.DELETION
3.EXIT
ENTER YOUR CHOICE: 2
DELETION
DELETED ELEMENT IS 10
20 30
12
1.INSERTION
2.DELETION
3.EXIT
ENTER YOUR CHOICE: 2
DELETION
DELETED ELEMENT IS 20
30
1.INSERTION
2.DELETION
3.EXIT
ENTER YOUR CHOICE: 2
DELETION
DELETED ELEMENT IS 30
1.INSERTION
2.DELETION
3.EXIT
ENTER YOUR CHOICE: 2
DELETION
QUEUE IS EMPTY
13
⋆ Implementation Of Circular Queue Using Array ⋆
Definition:
In circular queue, the insertion of a new element is performed at the very first
location of the queue if the last location of the queue is full, in which the first element
comes just after the last element
Advantages:
It overcomes the problem of unutilized space in leaner queues, when it is
implemented as arrays.
Insertion:
Rear(rear+1)%Maxsize
Algorithm Steps:
Step 1: create and set the variables front.rear.MAXSIZE.cq[]
step 2: Read the circular queue operation type.
step 3: If operation type is Insertion below steps are executed.
1. Assign rear-rear%MAXSIZE.
2. if front equal to (rear+1)%MAXSIZE then display queue is overflow.
3. if front equal to -1 then assign front-rear-0.
4. Otherwise assign rear (rear+1)%MAXSIZE and read queue data.
5. Assign cq[rear] as data (i.e. cq[rear]=data).
step 4: If operation type is Deletion below steps are executed.
1. Check front-1 then display queue is underflow.
2. Set temp as cq[front) (i.e. temp-ca[front]).
14
3. Check front equal to rear if it is true then assign front rear-1(Move the
front to beginning)
4. Assign front (front+1) MAXSIZE
Program:
#include <stdio.h>
#include<ctype.h>
#include<stdlib.h>
#define MAXSIZE 5
int cq[MAXSIZE];
int front rear;
void main(){
void add(int, int);
void del(int);
int will=1, i, num;
front=-1;
rear=-1;
clrscr();
printf("\nProgram for Circular Queue demonstration through array"):
while(1){
printf("\n\nMAIN MENU\n 1.INSERTION\n 2.DELETION\n 3.EXIT\n");
scanf("%d", &will);
switch(will){
case 1:
printf("\n\nENTER THE QUEUE ELEMENT:");
15
scanf("%d", &num);
add(num,MAXSIZE);
break;
case 2:
del(MAXSIZE);
break;
case 3:
exit(0);
break;
default:
printf("\n\nInvalid Choice");
}
void add(int item, int MAX){
//rear++;
//rear=(rear%MAX);
if(front==(rear+1)%MAX){
printf("\n\nCIRCULAR QUEUE IS OVERFLOW");
}
else{
if(front==-1){
front=rear=0;
}
else{
16
rear=(rear+1)%MAX;
cq[rear]=item;
printf("\n\nRear=%d Front=%d", rear, front);
}
}
}
void del(int MAX){
int a;
if(front==-1){
printf("\n\nCIRCULAR QUEUE IS UNDERFLOW");
}
else{
a=cq[front];
if(front==rear){
front=rear=-1;
else{
front=(frpnt+1)%MAX;
}
printf("\n\nDELETED ELEMENT FROM QUEUE IS: %d", a);
printf("\n\nRear=%d Front=%d", rear, front);
}
Output:
17
MAIN MENU
1.INSERTION
2.DELETION
3.EXIT
ENTER YOUR CHOICE: 1
ENTER THE QUEUE ELEMENT: 10
Rear=0 Front=0
MAIN MENU
1.INSERTION
2.DELETION
3.EXIT
ENTER YOUR CHOICE: 1
ENTER THE QUEUE ELEMENT: 20
Rear=1 Front=0
MAIN MENU
1.INSERTION
2.DELETION
3.EXIT
ENTER YOUR CHOICE: 1
ENTER THE QUEUE ELEMENT: 30
Rear=2 Front=0
18
MAIN MENU
1.INSERTION
2.DELETION
3.EXIT
ENTER YOUR CHOICE: 1
ENTER THE QUEUE ELEMENT: 40
Rear=3 Front=0
MAIN MENU
1.INSERTION
2.DELETION
3.EXIT
ENTER YOUR CHOICE: 1
ENTER THE QUEUE ELEMENT: 50
Rear=4 Front=0
MAIN MENU
1.INSERTION
2.DELETION
3.EXIT
ENTER YOUR CHOICE: 1
ENTER THE QUEUE ELEMENT: 60
CIRCULAR QUEUE IS OVERFLOW
19
MAIN MENU
1.INSERTION
2.DELETION
3.EXIT
ENTER YOUR CHOICE: 2
DELETED ELEMENT FROM QUEUE IS: 10
Rear=4 Front=1
MAIN MENU
1.INSERTION
2.DELETION
3.EXIT
ENTER YOUR CHOICE: 2
DELETED ELEMENT FROM QUEUE IS: 20
Rear=4 Front=2
MAIN MENU
1.INSERTION
2.DELETION
3.EXIT
ENTER YOUR CHOICE: 2
DELETED ELEMENT FROM QUEUE IS: 30
Rear=4 Front=3
20
MAIN MENU
1.INSERTION
2.DELETION
3.EXIT
ENTER YOUR CHOICE: 2
DELETED ELEMENT FROM QUEUE IS: 40
Rear=4 Front=4
MAIN MENU
1.INSERTION
2.DELETION
3.EXIT
ENTER YOUR CHOICE: 2
DELETED ELEMENT FROM QUEUE IS: 50
Rear=-1 Front=-1
MAIN MENU
1.INSERTION
2.DELETION
3.EXIT
ENTER YOUR CHOICE: 2
CIRCULAR QUWUW IS UNDERFLOW
21
⋆ Implementation Of Double Linked List ⋆
Definition:
A variant of a linked list in which each item has a link to the previous item as well as
the next. This allows easily accessing list items backward as well as forward and deleting
any item in constant time. Also known as two-way linked list, symmetrically linked list.
A doubly linked list is a linked list in which each node has three fields namely data
field, forward link (Flink) and backward link (Blink). Flink points to the successor node in
the list whereas Blink points to the predecessor node.
Advantages:
1. Deletion process is easier
2. Additional pointer for previous node is not necessary
3. Backwarding and forwarding traverse are possible.
Disadvantages:
1. More Memory space is required since it has two pointers.
Algorithm steps:
Step 1: Read the list operation.
Step 2: If operation is Create then process the following steps.
1. Create the new node and allocate memory for the new node.
2. Read the data in the new node.
3. Assign Flink and Blink as NULL.
4. Assign current as new.
22
Step 3: 1 operation is Insertion do the following steps.
i. Check insertion at beginning is true then
1. Create the new node and allocate memory for the new node
2. Read the data in the new node.
3. Move the currem node to start position
4. Assign new Blink Null
5. Assign new->Flink current
6. Now assign current->Blink new
ii. Insertion at between nodes is true then
1. Create the new node and allocate memory for the new node
2. Read the data in the new node.
3. Move the current node required position
4. Assign new node's Blink current
5. Assign new node's Flink-current->Flink
6. Assign current node's Flink "new
iii. Insertion at between nodes is true then
1. Create the new node and allocate memory for the new node.
2. Read the data in the new node.
3. Move the current code to end position
4. Assign стель node's Flink new.
5. Assign new's Blink as current
6. Assign new's Flink as NULL
7. Move end poinner to new node
23
Step 4: If operation is deletion, then do the following steps.
i. Check deletion at beginning is true then
1. Move current pointer to start position
2. Move the start pointer next node in the link
3. Assign start's Blink as NULL
4. Reallocate current node from memory.
ii) Check deletion between two nodes is true
1. Move the current pointer to required position.
2. Assign current'sBlinkFlink as current's Flink
3. Assign currents's->Flink>Blink as current's Blink.
4. Reallocate current from memory.
iii) Check deletion at end is true
1. Move the current pointer to end position.
2. Assign current's->Blink->Flink as Null.
3. Reallocate current from memory.
4. Reallocate current from memory.
Step 5: If the operation is traversing.
i. Check deletion at end is true
1. Move the current pointer to end position.
2. Repeat the following steps until current becomes NULL.
3. Display the data.
4. Current-current->Flink.
24
ii. If Backward traversing then
1. Move the current to end position.
2. Repeat the following steps until current becomes NULL.
3. Display the data.
4. Current-current->Flink.
Program:
#include<stdio.h>
#include<conio.h>
#include<alloc.h>
#include<stdlib.h>,
#define NULL 0
struct linkedlist{
int item;
struct linkedlist *right, *left;
};
typedef struct linkedlist node;
void main(){
node *start, *end;
int choice;
int menu(void);
node *create(node **lastnode);
void display(node *fisrt, node *last);
void insert(node **first, node **last);
void del(node **first, node **last);
25
clrscr();
printf("\nDOUBLE LIMKED LIST");
do{
printf("\n\nMain Menu");
printf("\n\n1.Create\n 2.Insert\n 3.Delete\n 4.Display\n 5.Exit");
choice=menu();
switch(choice){
case 1:
printf("\nEnter the data (-999 to stop):");
start=create(&end);
continue;
case 2:
insert(&start, &end);
printf("\n");
continue;
case 3:
del(&start, &end);
printf("\n");
continue;
case 4:
display(start, end);
printf("\n");
continue;
case 5:
exit(0);
26
default:
printf("\n\nInvalid Choice");
}
}while(1);
}
int menu(){
int choice;
do{
printf("\n Enter your choice:");
scanf("%d",&choice);
if(choice<1||choice>5){
printf("\n Wrong choice");
}while(choice<1||choice>5);
printf("\n");
return(choice);
}
node *create(node **lastnode){
node *temp, "firstnode;
int info;
*lastnode=NULL;
firstnode NULL;
scanf("%d",&info);
while(info!--999){
temp=(node*)malloc(sizeof(npde));
27
temp>item=info;
temp>right=NULL;
if(firstnode==NULL){
temp>left=NULL;
firstnode=temp;
}
else{
temp>left=(*lastnode):
(*lastnode)>right+temp;
(*lastnode)=temp;
scanf("%d", &info);
if(firstnode!=NULL)
(*lastnode)=temp;
return(firstnode);
}
void display(node(*first, node *last)){
printf("\nForward Traversal\n");
while(first!=NULL){
printf("%f\t", first->item);
first=first->rightl
}
printf("\nBacckward Traversal\n");
while(last!=NULL){
28
printf("%d\t", last->item);
last=last->left;
}
return 0;
}
void insert(node **first, node **last){
node *newnode;
int newitem;
int position;
node *temp;
int i;
printf("\n New data item:");
scanf("%d",&newitem);
do{
printf("\n Position of insertion:");
scanf("%d",&position);
}while(position<=0);
if(((*first)=NULL)||(position=1)) {
newnode (node *)malloc(sizeof(node));
newnode->item=newitem,
newnode->right=*first;
newnode->left=NULL;
if((*first)!=NULL){
(*first)->left-newnode;
29
else{
(*last) newnode;
*first-newnode;
}
}
else{
i=1;
temp=*first
while((i<position-1)&&(temp->right!=NULL)){
1++;
temp-temp->right;
}
newnode (node *)malloc(sizeof(node));
newnode->item=newitem,
newnode->right=temp->right;
if(temp right! NULL){
temp->right->left=newnode;
newnode->left=temp;
temp->right=newnode;
}
}
}
if(newnode->right==NULL){
*last=newnode;
30
}
void del(node **first, node **last){
node temp, "prev
int target;
printf("\n Enter the data to be deleted:");
scanf("%d",&target): iff first NULL)
if(*first==NULL){
printf("\n List is empty");
else if (("first)-item-target){
if((*first)->right==NULL){
*first=*last=NULL;
else{
*first=(*first)->right;
(*first)->left=NULL;
}
}
else{
temp=*first;
prev=NULL;
while((temp->right!=NULL) && (temp->item!=target)){
prev=temp;
temp=temp->right;
31
if(temp->item!+right){
printf("\nElement not found");
}
else{
if(temp==*last){
*last=prev;
else{
temp->right=temp->left;
prev->right=temp->right;
}
}
Output:
Main Menu
1.Create
2.Insert
3.Delete
4.Display
5.Exit
Enter your choice: 1
Enter the data (-999 to stop):
32
10
15
-999
Main Menu
1.Create
2.Insert
3.Delete
4.Display
5.Exit
Enter your choice: 2
New data item: 20
Position of insertion: 1
Main Menu
1.Create
2.Insert
3.Delete
4.Display
5.Exit
Enter your choice: 4
Forward traversal
5 20 10 15 20
Backward traversal
20 15 10 20 5
33
Main Menu
1.Create
2.Insert
3.Delete
4.Display
5.Exit
Enter your choice: 3
Enter the data to be deleted: 5
Main Menu
1.Create
2.Insert
3.Delete
4.Display
5.Exit
Enter your choice: 4
Forward traversal
20 10 15 20
Backward traversal
20 15 10 20
34
⋆ Implementation Of Binary Search ⋆
Definition:
Search a sorted array by repeatedly dividing the search interval in half. Begin with an
interval covering the whole array. If the value of the search key is less than the item in
the middle of the interval, narrow the interval to the lower half. Otherwise narrow it to
the upper half. Repeatedly check until the value is found or the interval is empty.
Advantages:
1. It is faster than linear search.
2. It is astounding for large numbers.
Disadvantages:
1. Binary search can interact poorly with the memory hierarchy (i.e. caching),
because of its random-access nature.
2. Before searching the elements shorting is necessary. It take some additional
overhead to machine.
Analysis of the Binary sort:
1. Worest case performance O(log n)
2. Best case performance O(1)
3. Average case performance O(log n)
Algorithm steps:
Step 1. Read the elements of the list.
Step 2: Sort the input list.
35
Step 3: Find the mid value
Step 4: Look at the element in the middle. If the key is equal to that, the search is
finished.
Step 5: If the key is less than the middle element, do a binary search on the first
half.
Step 6: If it's greater, do a binary search of the second half
Program:
#include<stdio.h>
#include<conio.h>
void main(){
int a[25], i, j, temp, s, n, low, mid, high;
clrscr();
printf("\nEnter the Limilt: ");
scanf("%d",&n);
printf("\nEnter the elements/n");
for(i=0;i<n;i++){
scanf("%d", &a[i]);
for(i=0; i<n; i++){
for(j=0; j<n-1; j++){
if(a[j]>a[j+1]){
temp=a[j];
36
a[j]=a[j+1];
a[j+1]=temp;
printf("\nSorted List");
for(i=0; i<n; i++){
printf("\n%d", a[i]);
printf("\nEnter the element to be searched:");
scanf("%d", &s);
while(low<=high){
mid (low+high)/2;
if(s>a[mid])
low-mid+1;
else if(s<a[mid])
high mid-1:
else if(s==a[mid]){
printf("\nThe element %d is found", s);
getch();
exit(0);
else{
37
printf("\nThe element %d is not found", s);
getch();
Output:
Enter the elements:
5 4 3 2 1
Sorted list:
1 2 3 4 5
Enter the element to be searched: 5
The element 5 is found
38
