UNIT II LINEAR DATA STRUCTURES – STACKS, QUEUES

List ADT – array-based implementations – linked list implementations – singly linked lists –
circularly linked lists – doubly linked lists – Stack ADT – Queue ADT – double ended queues –
applications

LINEAR DATA STRUCTURES – LIST

Data Structures

Data Structures is a way of organizing the data which also includes several operations to
perform on that data.

Applications of Data Structures

• List: used in implementation of File allocation Table (FAT), Process Control Block (PCB)
etc.
• Stack: It is always implicitly used in a program, whether or not we declare it explicitly,
during the program execution.
• Queue: It is used to order the task as they arrive to get the attention of the CPU.
• Tree: Directory Structure is implemented using tree DS.
• Graph: used in Networking and mapping of tasks to processors in multiprocessor
Platforms.

Data structures are widely applied in the areas like

• Compiler Design
• Operating System
• DBMS
• Artificial Intelligence
• Graphics
• Networking Etc.

Characteristics of Data Structures

(0) Represents logical relationship between various data elements.

(a) Helps in efficient manipulation of stored data.
(b) Allows the programs to process data easily / effectively.
Classification of Data Structures

1. Primitive Data Structures: All the fundamental DS that can be directly manipulated by the
machine level instructions.
2. Non Primitive Data Structures: refer to all those that are derived from one or more
primitive DS.
3. Linear Data Structures: arranged in sequential form
4. Non Linear Data Structures: not sequential order. Ex : data elements in a hierarchical
fashion (Tree).

Fig 1.1 Classification of Data Structures

Abstract Data Types (ADTs)

ADT is defined as a mathematical model with a set of operations.

Basic Idea of ADT: The operations are written once in the program. Any other part of the
program can access this operation by calling the appropriate function.
Examples
• Objects such as lists, sets, graph etc along with their operations are ADTs.
• Set of integers together with the operations Union, Intersection and difference form an
example ADT.
• Similarly real Boolean have operations associated with them. So it is ADTs.
Advantages of ADT
• Modularity
• Reuse
• Easy to understand
• Implementation of ADTs can be changed anytime without changing the program that uses
it.

The List ADT

List is an ordered set of elements. General Form of List ADT is A1,

A2, A3, ….AN , Where N is the size of the List.
A1 - First element of the list, A2 - Second element of the list, AN - Last element of the list
If the element at position i is Ai, Ai-1is the predecessor element, Ai+1 is the successor
element.
Various operations performed on List
1. Insert (X, 3)- Insert the element X after the position 3.
2. Delete (X) - The element X is deleted
3. Find (X) - Returns the position of X.
4. Next (i) - Returns the position of its successor element i+1.
5. Previous (i) Returns the position of its predecessor i-1.
(C) Print list - Contents of the list is displayed.
(D) Makeempty- Makes the list empty.

Implementation of list ADT

1. Array based Implementation

2. Linked List based implementation

Array Implementation of list

Array is a collection of specific number of same type of data stored in consecutive memory
locations. Array is a static data structure.
i.e., size of the array should be allocated in advance and the size is fixed.
1. Insertion and Deletion operation are expensive as it requires more data movements.
Worst case it requires O(N) Movements. Best case it requires O(1).

The basic operations performed are

2. Creation of List.
3. Insertion / Deletion of data from the List
4. Display all data in the List
5. Searching for a data in the list
Creation of List: Create operation is used to create the list with “n” number of elements. If
“n” exceeds the array’s maxsize, then elements cannot be inserted into the list. Otherwise the
array elements are stored in the consecutive array locations (i.e.) list [0], list [1] and so on.

Insertion / Deletion of data in the List: Insert / Delete operation is used to Insert/ Delete an
element at particular position in the existing list. Inserting/ deleting the element in the last
position of an array is easy.
But inserting/ Deleting the element at a particular position in an array is quite difficult since it
involves all the subsequent elements to be shifted one position to the right / left.
Display/ Traversal all data in the List: Traversal is the process of visiting the elements in an
array. Display( ) operation is used to display all the elements stored in the list from the index 0
to n-1.
Searching for a data in the list: Search( ) operation is used to determine whether a
particular element is present in the list or not.
Procedure to create / insert / delete
Create Insert Delete

void Delete( )
void Insert()
void Create()
{ int i,pos;
{ int i, data, pos;
{ int i;
printf("Enter the
printf("Enter data to insert");
printf("Enter number of position to delete”);
scanf("%d", &data);
elements");
scanf("%d", &pos);
printf("Enter the position to
scanf("%d",&n);
printf("The data
insert");
printf("Enter the array deleted is: %d",
scanf("%d", &pos);
elements"); list[pos-1]);
for(i = n-1; i >= pos-1 ; i--)
for(i=0; i<n; i++) for(i=pos-1;i<n-1;
{list[i+1] = list[i];} i++)
{scanf("%d", &list[i]); }
Display(); // swap // {list[i]=list[i+1]; }
list[pos-1] = data;
n=n-1;
}
n= n+1; Display(); }
Display(); }

Procedure to display / search

Display Search

void Display() void Search()

{ { int search, i, count = 0;
int i; printf("Enter the element to be searched");
printf("Elements in the scanf("%d", &search);
array");
for(i=0; i<n; i++)
for(i=0;i<n;i++)
{ if(search == list[i])
printf("%d",list[i]);
count++; }
}
if(count==0)
printf("Element not present ");
else
printf("Element present"); }

//Main Program //
#include<stdio.h> #include<conio.h>
#define maxsize 10
int list[maxsize],n; // Declaration of Array//
void Create(); void Insert(); void Delete(); void Display(); void Search(); void
main()
{ int choice;
do
{printf("Array Implementation”);
printf("\t1.Create\n");printf("\t2.Insert\n");
printf("\t3.Delete\n");printf("\t4.Display\n");
printf("\t5.Search\n"); printf("\t6.Exit\n");
printf("\nEnter your choice:\t"); scanf("%d",&choice);

switch(choice)
{ case 1: Create(); break;
case 2: Insert(); break;
case 3: Delete(); break;
case 4: Display(); break;
case 5: Search();
break;
default: printf("Enter option between 1 - 5"); break; } }
while(choice<6); }

Advantages of array implementation

1. The elements are faster to access
2. Searching an element is easier
Limitation of array implementation
• An array uses consecutive memory locations.
• The number of elements in the array is fixed.
• Insertion and deletion operation in array are expensive.
Applications of arrays
Arrays are particularly used in programs that require storing large collection of similar type
data elements.

Linked List based implementation

A Linked list is an ordered collection of elements. Each element in the list is referred as a
node. Each node contains two fields namely,
• Data field-The data field contains the actual data of the elements to be stored in the list.
• Next / Pointer field- The next field contains the address of the next node in the list
The nodes in the linked list are not necessarily adjacent in memory.

Advantages of Linked list

• Insertion and deletion of elements can be done efficiently
• It uses dynamic memory allocation
• Memory utilization is efficient compared to arrays
Disadvantages of linked list
1. Linked list does not support random access
2. Extra Memory space is required to store next field
3. Searching takes time compared to arrays
Types of Linked List
1. Singly Linked List or One-Way List
2. Doubly Linked List or Two-Way Linked List
3. Circular Linked List
Differences between Array based and Linked List based Implementation of List
Array Linked List

Definition Array is a collection of Linked list is an ordered collection of

elements having same data elements which are connected by
type with common name links/pointers
Access Elements can be accessed Sequential access using pointers
using index / subscript

Memory Elements are stored in Elements are stored at available

structure contiguous memory locations memory space

Insertion & Takes more time in array Are fast and easy
Deletion

Memory Memory is allocated at Memory is allocated at run time i.e

Allocation compile time i.e static dynamic memory allocation
memory allocation
Types 1D,2D and multi-dimensional SLL, DLL and circular linked list

Dependency Each element is independent Each node is dependent on each other as

address part contains address of next
node in the list

Dynamic allocation

The process of allocating memory to the variables during execution of the program or at run
time is known as dynamic memory allocation.
When we do not know memory requirements in advance, we can use Dynamic memory
allocation.
C language has four library routines to support Dynamic allocation.
To use dynamic memory allocation functions, include the header file stdlib.h.
malloc() and calloc()
malloc() calloc()

Syntax: ptr =(cast-type*) malloc (byte-size); Syntax:ptr=(cast-type*) calloc

(n,elem_size);

Returns a pointer type of void after memory The malloc() function allocates a single
allocation, which can be casted to any form. block of memory.
However, if the space is insufficient, Whereas, calloc() allocates multiple
allocation fails and returns a NULL pointer blocks of memory and initializes them to
zero.
Example : ptr = (int*) malloc(100 * Example: ptr = (float*) calloc(25,
sizeof(int)); sizeof(float));

Considering the size of int is 4 bytes, this This statement allocates contiguous space
statement allocates 400 bytes of memory. in memory for 25 elements each with the
And, the pointer ptr holds the address of the size of float
first byte in the allocated memory.

free() and realloc()

free() realloc()

Syntax: free(ptr); Syntax : ptr = realloc(ptr,newsize);

the memory is returned back to the free list Relloactes the previous memory
within the heap.

ptr = (int*) malloc(100 * sizeof(int)); //

reserved 400 bytes
ptr = realloc(ptr, 200 * sizeof(int)); //
reserved 800 bytes.

Example Program : for sum of n numbers using malloc

#include <stdio.h>
#include <stdlib.h>

int main()
{ int n, i, *ptr;
printf("Enter number of elements: ");
scanf("%d", &n);
ptr = (int*) malloc(n * sizeof(int));
if(ptr == NULL)
{ printf("Error! memory not allocated."); }
else { printf(“Memory allocated”); }
free(ptr); return 0;
}

Singly Linked List

A singly linked list is a linked list in which each node contains data field and only one link
field pointing to the next node in the list.

Head node which always points to the first node. Head node is also called as sentinel node.
Basic operations on a singly linked list are
1. Insert – Inserts a new node in the list.
2. Delete – Deletes any node from the list.
3. Find – Finds the position (address) of any node in the list.
4. FindPrevious - Finds the position (address) of the previous node.
5. FindNext - Finds the position(address) of the next node in the list.
6. Display - displays the data in the list
7. Search - finds whether an element is present in the list or not

Insertion: The insertion into a singly linked list can be performed in 3 ways.

1. Insertion at beginning: It involves inserting any element at the front of the list.
• Insertion at end of the list: It involves insertion at the last of the linked list. It can be done
in 2 ways
← The node is being added to an empty list (only one node in the list)
← The node can be inserted as the last one.
1.Insertion at a given position (after specified node): It involves insertion after the specified
node of the linked list.

Procedure for Inserting a new element into a singly

linked list
Insertion at beginning Insertion at end of the Insertion at a given
list position

void beginsert() void lastinsert() void randominsert()

{struct node *ptr; {struct node *ptr, *temp; {int i,loc,item;
int item; int item; struct node *ptr, *temp;

ptr = (struct node *) ptr = (struct node*) ptr = (struct node *)

malloc(sizeof(struct node)); malloc(sizeof(struct malloc (sizeof(struct
node)); node));
if(ptr == NULL)
if(ptr == NULL) if(ptr == NULL)
{printf("overflow"); }
else {printf("overflow"); } {printf("overflow"); }
printf(
"Node
else insert
ed");}
{temp = head;
while (temp → next != }
NULL)
{temp = temp → next; } }
→
temp
→
next = ptr;
ptr next = NULL;
temp=head;
for(i=0;i<loc;i++)
{ temp = temp→next;
if(temp == NULL)
{printf("can't insert");

else
else
{printf("Enter value");
{printf(“Enter value");
{printf("Enter value");
scanf("%d",&item);

scanf("%d",&item);
scanf("%d",&item);
ptr→data = item;
ptr→data = item;
ptr→data = item;
→
ptr next = head;
if(head == NULL)
printf("Enter the
head = ptr;
{ptr → next = NULL; location after which you
printf("Node inserted"); want to insert ");
head = ptr;
} } printf("Node inserted");} scanf("%d",&loc);

return; }
}
ptr →next =
temp→→next;
temp next = ptr;
printf("Node inserted");
}
}
Deletion: The deletion into a singly linked list can be performed in 3 ways.
1. Deletion at beginning: deleting an element at the front of the list.
• Deletion at end of the list: It can be done in 2 ways
← There is only one node in the list and that needs to be deleted.
← There are more than one node in the list and the last node of the list will be deleted.
• Deletion at a given position (after specified node): It involves deletion after the specified
node of the linked list.

Procedure for Deleting a node into a singly

linked list
Deletion at a given
Deletion at beginning Deletion at end of the list
position

void begin_delete() void last_delete() void random_delete()

{ struct node *ptr; { struct node *ptr,*ptr1; {struct node *ptr,*ptr1;
if(head == NULL) if(head == NULL) int loc,i;
{ printf("List is empty"); {printf("list is empty"); } printf("Enter the location
} of the node after which
else if(head → next ==
you want to perform
else NULL)
deletion");
{ptr = head; { head = NULL;
scanf("%d",&loc);
→
head = ptr next;
ptr=head;
free(ptr); free(head); printf("Only for(i=0;i<loc;i++)
node of the list deleted ..."); {ptr1 = ptr;
printf("Node deleted from the
}
begining ..."); ptr = ptr→next;
} else if(ptr == NULL)

} {ptr = head; {printf("Can't delete");

while(ptr→next != NULL) return; }
{ptr1 = ptr;
}
ptr =→ptr →next; }
ptr1 next = NULL; ptr1 →next = →next;
free(ptr); free(ptr); printf("Deleted
node %d ", loc+1);
printf("Deleted Node from
the last ..."); }
}
}

Traversing / Display in singly linked list

Traversing means visiting each node of the list once in order to perform some operation on
that. Display the content of linked list.

Search in singly linked list

Comparing each node data with the item to be searched and return the location of the item in
the list if the item found else return null.

Procedure for Display and Search

Display Search

void display() void search()

{ struct node *ptr; { struct node *ptr; int item,i=0,flag;
ptr = head; ptr = head;
if(ptr == NULL) if(ptr == NULL)
{ printf("Empty List "); } {printf("Empty List"); }
else else
{ printf("printing values"); {printf("Enter item to search");
while (ptr!=NULL) scanf("%d",&item);
→
{printf("%d",ptr data); while (ptr!=NULL)
{if(ptr→data == item)
ptr = ptr -> next; } }
{printf("item found at location %d ",i+1);
}
flag=0; } else { flag=1; }
i++; ptr = ptr -> next; }
if(flag==1)
{ printf("Item not found\n"); } } }
Singly Linked List main program
#include<stdio.h>
#include<stdlib.h>
struct node
{ int data;
struct node *next;
}; struct node *head;
void beginsert (); void lastinsert (); void randominsert();
void begin_delete(); void last_delete(); void random_delete();
void display(); void search();
void main ()
{ int choice =0;
while(choice != 9)

{ printf("Main Menu");
printf("Choose one option from the following list ...");

printf("1.Insert in beginning 2.Insert at last 3.Insert at any random location 4.Delete from
Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element
8.Show 9.Exit");
printf("Enter your choice?"); scanf("%d", &choice);
switch(choice)
{ case 1: beginsert(); break; case 2:
lastinsert(); break; case 3:
randominsert(); break; case 4:
begin_delete(); break;
case 5: last_delete(); break;
case 6: random_delete(); break;
case 7: search(); break;
case 8: display(); break;
case 9: exit(0);
break;
default: printf("Please enter valid choice.."); }
} }

Complexity

Advantages of SLL
/ The elements can be accessed using the next link
/ Occupies less memory than DLL as it has only one next field.
Disadvantages of SLL
/ Traversal in the backwards is not possible
/ Less efficient to for insertion and deletion.

Doubly Linked List

A doubly linked list is a linked list in which each node has three fields namely Data, Next,
Prev. The prev part of the first node and the next part of the last node will always contain null
indicating end in each direction.

Basic operations on a doubly linked list are

1. Insert – Inserts a new node in the list.
2. Delete – Deletes any node from the list.
3. Find – Finds the position (address) of any node in the list.
4. Display - displays the data in the list
5. Search - finds whether an element is present in the list or not

Insertion: The insertion into a doubly linked list can be performed in 3 ways.
• Insertion at beginning: It involves inserting any element at the front of the list.

• Insertion at end of the list: It involves insertion at the last of the linked list. It can be done
in 2 ways
← The node is being added to an empty list (only one node in the list)
← The node can be inserted as the last one.
insertion after the new
specified node of the element
linked list.
into a
• Insertion at a P doubly
given position
(after specified rocedure for linked list
node): It involves Inserting a
Insertion at a given
Insertion at beginning Insertion at end of the list
position

void insertion_beginning() void insertion_last() void

insertion_specified()
{struct node *ptr; { struct node *ptr,*temp;
{struct node *ptr,
int item; int item; *temp;
ptr = (struct node *) ptr = (struct node *) int item,loc,i;
malloc(sizeof(struct malloc(sizeof(struct node));
ptr = (struct node *)
node)); if(ptr == NULL) malloc(sizeof(struct
if(ptr == NULL) {printf("Overflow"); } node));
{printf("Overflow"); } else if(ptr == NULL)
else { printf("Enter value"); {printf("Overflow");
}
{ printf("Enter value"); scanf("%d",&item);
else
scanf("%d",&item); ptr->data=item;
{ temp=head;
if(head==NULL) if(head == NULL)
printf("Enter
→
{ ptr next = NULL; →
{ ptr next = NULL; location");
→ →
ptr prev=NULL; ptr prev = NULL; scanf("%d",&loc);
ptr→data=item; head = ptr; } for(i=0;i<loc;i++)
{ ptr→→data=item;
ptr prev=NULL;
ptr→next = head;
head→prev=ptr;
head=ptr; }
else
head=ptr; } printf("Node inserted"); } }
{ temp =
else head;
while(temp→next!=NULL)
{temp = temp->next; }
temp→next = ptr;
ptr →prev=temp;
ptr→next = NULL; }
}
{temp = temp→next;
printf("node inserted"); if(temp == NULL)
} {printf("There are less than
%d elements",
loc); return; }
}
printf("Enter value"); →
scanf("%d",&item); ptr data
= item; ptr→next=temp→next;
ptr→prev = temp; temp→next
= ptr; temp→next→prev=ptr;
printf("node inserted"); } }
Deletion: The deletion into a doubly linked list can be performed in 3 ways.
1. Deletion at beginning: deleting an element at the front of the list.

1. Deletion at end of the list: It can be done in 2 ways

← There is only one node in the list and that needs to be deleted.
← There are more than one node in the list and the last node of the list will be deleted.

• deletion at a given position (after specified node): It involves deletion after the specified
node of the linked list.
Procedure for Deleting a node into a doubly linked list
Deletion at a given
Deletion at beginning Deletion at end of the list
position

void deletion_beginning() void deletion_last() void

deletion_specified()
{ struct node *ptr; { struct node *ptr;
{struct node *ptr, *temp;
if(head == NULL) if(head == NULL)
int val;
{printf("Underflow"); } {printf("Underflow"); }

printf("Enter the data

else if(head→next == NULL) else if(head→next == NULL) after which the node is to
{ head = NULL; { head = NULL; be deleted : ");
free(head); free(head); scanf("%d", &val);
printf("node deleted"); printf("node deleted"); ptr = head;
→
} } while(ptr
→
data!= val) ptr
= ptr next;
else else if(ptr -> next == NULL)
{ ptr = head; { ptr = head; {printf("Can't delete");}
head = head → next; if(ptr→next != NULL) else if(ptr → next → next
head → prev = NULL; { ptr = ptr → next; } ptr → prev → == NULL)
free(ptr); next = NULL;
free(ptr); {ptr →next = NULL; }
printf("node deleted"); else
printf("node deleted"); {temp = ptr → next;
} ptr → next = temp → next;
}
} temp → next → prev = ptr;
}
free(temp);
printf("node deleted");
} }

Traversing / Display in doubly linked list

Traversing means visiting each node of the list once in order to perform some operation on
that. Display the content of linked list.

Search in doubly linked list

Comparing each node data with the item to be searched and return the location of the item in
the list if the item found else return null.

Procedure for Display and Search

Display Search

void display() void search ()

{ struct node *ptr; { struct node *ptr; int item,i=0,flag;
printf("printing values"); ptr = head;
ptr = head; if(ptr == NULL)
while(ptr != NULL) { printf("\nEmpty List\n"); } else
{printf("%d", ptr->data); {printf("Enter item to search?");
ptr=ptr->next; } scanf("%d",&item); while (ptr!
} =NULL)
{ if(ptr->data == item)
{printf("item found at location %d ",i+1);
flag=0; break; }
else { flag=1; }
i++; ptr = ptr -> next; }
if(flag==1)
{ printf("Item not found"); }
} }

Doubly Linked List main program

#include<stdio.h> #include<stdlib.h>
struct node
{ struct node *prev;
struct node *next;
int data; }; struct node *head;
void insertion_beginning(); void insertion_last();
void insertion_specified(); void deletion_beginning(); void
deletion_last(); void deletion_specified(); void display();
void search();
void main ()
{ int choice =0;
while(choice != 9)
{ printf("Main Menu");
printf("\nChoose one option from the following list ...\n");
printf("1.Insert in beginning 2.Insert at last 3.Insert at any random location 4.Delete from
Beginning 5.Delete from last 6.Delete the node after the given data 7.Search 8.Show 9.Exit");
printf("Enter your choice?");
scanf("%d", &choice);
switch(choice)
{ case 1: insertion_beginning(); break;
case 2: insertion_last(); break;
case 3: insertion_specified(); break;
case 4: deletion_beginning(); break;
case 5: deletion_last(); break;
case 6: deletion_specified(); break;
case 7: search(); break;
case 8: display(); break;
case 9: exit(0); break;
default: printf("Please enter valid choice.."); }
} }
Advantages of DLL
The DLL has two pointer fields. One field is prev link field and another is next link field.
Because of these two pointer fields we can access any node efficiently whereas in SLL

only one link field is there which stores next node which makes accessing of any node
difficult.
Disadvantages of DLL
The DLL has two pointer fields. One field is prev link field and another is next link field.
Because of these two pointer fields, more memory space is used by DLL compared to SLL

Circular Singly Linked List

(ii) In a circular singly linked list, the last node of the list contains a pointer to the first
node of the list.
(iii)We traverse a circular singly linked list until we reach the same node where we
started.
(iv)The circular singly liked list has no beginning and no ending.
(v) There is no null value present in the next part of any of the nodes.

The following image shows a circular singly linked list.

C Program to perform all operation on Circular Singly Linked List

#include<stdio.h>

#include<stdlib.h>

struct node

{ int data;

struct node *next;

};

struct node *head;

void beginsert (); void lastinsert (); void randominsert();

void begin_delete(); void last_delete(); void random_delete();

void display(); void search();

void main ()

{int choice =0;

while(choice != 7)

{ printf("\nChoose one option from the following list ...\n");

printf("\n1.Insert in begining\n2.Insert at last\n3.Delete from Beginning\n4.Delete from

last\n5.Search for an element\n6.Show\n7.Exit\n");

printf("\nEnter your choice?\n");

scanf("\n%d",&choice);

switch(choice)

{ case 1:
28
beginsert();

break;

case 2: lastinsert(); break;

case 3: begin_delete(); break;

case 4: last_delete(); break;

case 5: search(); break;

case 6: display(); break;

case 7: exit(0); break;

default:

printf("Please enter valid choice..");

} }

void beginsert()

struct node *ptr,*temp;

int item;

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

if(ptr == NULL)

{ printf("\nOVERFLOW"); }

else

{printf("\nEnter the node data?");

scanf("%d",&item);

ptr -> data = item;

if(head == NULL)

{ head = ptr;

ptr -> next = head; }

else

{ temp = head; while(temp-

>next != head)

temp = temp->next;

ptr->next = head;

temp -> next = ptr;

head = ptr; }

printf("\nnode inserted\n");

void lastinsert()

struct node *ptr,*temp;

int item;

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

if(ptr == NULL)
{ printf("\nOVERFLOW\n"); }

else

printf("\nEnter Data?");

scanf("%d",&item);

ptr->data = item;

if(head == NULL)

{ head = ptr; ptr -> next = head; }

else

temp = head;

while(temp -> next != head)

{ temp = temp -> next; }

temp -> next = ptr;

ptr -> next = head;

printf("\nnode inserted\n");

void begin_delete()

{
struct node *ptr;

if(head == NULL)

{ printf("\nUNDERFLOW");

else if(head->next == head)

{ head = NULL;

free(head);

printf("\nnode deleted\n"); }

}
else

{ ptr = head;

while(ptr -> next != head)

ptr = ptr -> next;

ptr->next = head->next;

free(head);

head = ptr->next;

printf("\nnode deleted\n");

void last_delete()

struct node *ptr, *preptr;

if(head==NULL)

{ printf("\nUNDERFLOW"); }

else if (head ->next == head)

{ head = NULL;

free(head);

printf("\nnode deleted\n");

else

{ ptr = head;

while(ptr ->next != head)

{ preptr=ptr;

ptr = ptr->next; }

preptr->next = ptr -> next;

free(ptr);

printf("\nnode deleted\n");

void search()

struct node *ptr;

int item,i=0,flag=1;

ptr = head;

if(ptr == NULL)

{ printf("\nEmpty List\n"); }

else

printf("\nEnter item which you want to search?\n");

scanf("%d",&item);

if(head ->data == item)

{printf("item found at location %d",i+1);

flag=0; } else

while (ptr->next != head)

{ if(ptr->data == item)

printf("item found at location %d ",i+1);

flag=0; break; }

else

{ flag=1; }

i++;

ptr = ptr -> next;

} }

if(flag != 0)

{ printf("Item not found\n"); }

void display()

{ struct node *ptr;

ptr=head;

if(head == NULL)

{ printf("\nnothing to print"); }

else
{printf("\n printing values ... \n"); while(ptr ->
next != head)

{ printf("%d\n", ptr -> data);

printf("%d\n", ptr -> data);

} }
ptr = ptr -> next;
}

Advantages of Circular linked List

• It allows to traverse the list starting at any point. It allows quick access to the first and
last records.
• Circularly doubly linked list allows to traverse the list in either direction.

Applications of lists:
• Polynomial ADT
• Radix sort
• Multilist

Polynomial Manipulation – All operations (Insertion, Deletion, Merge, Traversal).

Polynomial Implementation:
A polynomial p(x) is the expression in variable x which is in the form (axn + bxn-1 + ….
+ jx + k), where a, b, c …., k fall in the category of real numbers and 'n' is non negative integer,
which is called the degree of polynomial.

• i.e A polynomial is an expression that contains more than two terms.

• one is the coefficient
• other is the exponent
3 2
P(x) = 4x +6x +7x+9, here 4,6,7, and 9 are coefficients and 3, 2, 1 is its exponential value

Polynomial can be represented in the various ways. These are:

• By the use of arrays

• By the use of Linked List

• Polynomial manipulations such as insertion, deletion, Merge, Traversal , addition,

subtraction & differentiation etc.. can be performed using linked list / array.

Procedure for Polynomial Addition subtraction & differentiation using linked list:
Declaration of Linked list implementation of Polynomial:

struct poly{

{ int coeff; int

power; struct poly
*next;

} *list1, *list2, *list3;

Creation of Polynomial:

poly create(poly *head, poly *newnode)

{ poly*ptr;

if(head==NULL)

{ head=newnode;
return(head); } else

{ ptr=head;

while(ptr-> next!=NULL)

ptr=ptr->next;

ptr->next=newnode; }

return(head);

Addition of Polynomials:

To add two polynomials we need to scan them once. If we find terms with the same exponent in
the two polynomials, then we add the coefficients; otherwise, we copy the term of larger
exponent into the sum and go on. When we reach at the end of one of the polynomial, then
remaining part of the other is copied into the sum.

To add two polynomials follow the following steps:

• Read two polynomials.

• Add them.

• Display the resultant polynomial.

Addition of Polynomials:

void add()

poly *ptr1, *ptr2, *newnode;

ptr1=list1;

ptr2=list2;

while(ptr1!=NULL && ptr2!= NULL)

{ newnode=malloc(sizeof(struct poly));
if(ptr1->power==ptr2->power)

{ newnode->coeff = ptr1->coeff + ptr2->coeff;

newnode->power=ptr1->power; newnode-

>next=NULL; list3=create(list3,newnode);

ptr1=ptr->next;

ptr2=ptr2->next;

else

{ if(ptr1->power > ptr2->power)

{ newnode->coeff = ptr1->coeff

newnode->power=ptr1->power;
newnode->next=NULL;

list3=create(list3,newnode);

ptr1=ptr1->next; }

else

{ newnode->coeff = ptr2->coeff

newnode->power=ptr2->power;
newnode->next=NULL;

list3=create(list3,newnode);

ptr2=ptr2->next; }

SUBTRACTION OF POLYNOMIALS:

(add this statement in the above program)

newnode->coeff = ptr1->coeff - ptr2->coeff

MULTIPLICATION OF POLYNOMIALS:

• Multiplication of two polynomials however requires manipulation of each node such

that the exponents are added up and the coefficients are multiplied.
• After each term of firstpolynomial is operated upon with each term of the second
polynomial,
• Then the result has to be added up by comparing the exponents and adding the
coefficients for similar exponents and including terms as such with dissimilar
exponents in the result

void Mul()

poly *ptr1, *ptr2, *newnode;

ptr1=list1;

ptr2=list2;

if(ptr1 == NULL && ptr2 == NULL)

return;

if(ptr1 == NULL) // I polynomial does not exist list3

= list2;

elsif(ptr2 ==NULL) // II polynomial does not exist list3

=list1;

else // Both polynomial exist

{ if(ptr1!=NULL && ptr2!= NULL)

{ while(ptr1!=NULL)

{ newnode=malloc(sizeof(struct poly));
while(ptr2!=NULL)

{ newnode->coeff = ptr1->coeff * ptr2 ->coeff;

newnode->power=ptr1->power + ptr2->power;

list3=create(list3,newnode); ptr2=ptr2->next;

}
ptr2=list2;

ptr1=ptr1->next;

} }

}}

Multilists:

• In a general multi-linked list each node can have any number of pointers to other nodes,
and there may or may not be inverses for each pointer.
• Multi-lists are essentially the technique of embedding multiple lists into a single data
structure.
• A multi-list has more than one next pointer, like a doubly linked list, but the pointers
create separate lists
• i. e Given a linked list where in addition to the next pointer, each node has a child
pointer, which may or may not point to a separate list.
• These child lists may have one or more children of their own, and so on, to produce a
multilevel data structure, as shown in below figure.
• You are given the head of the first level of the list.
• We can Flatten the list so that all the nodes appear in a single-level linked list.
• You need to flatten the list in way that all nodes at first level should come first, then
nodes of second level, and so on.

Each node is a C struct with the following definition.

struct List

int data;

struct List *next;

struct List *child;

};
The above list can be converted to 10->5->12->7->11->4->20->13->17->6->2->16->9->8-
>3->19->15

Stack ADT:

• Stack is a Linear Data Structure that follows Last in First Out (LIFO) principle.
• Stack is an ordered list in which, insertion and deletion can be performed only at
one end that is called top
• i.e. the element which is inserted last in the stack, will be deleted first from the stack.
• Example: - Pile of coins, stack of trays
TOP pointer

• It will always point to the last element inserted in the stack. For empty stack, top
will be pointing to -1. (TOP = -1) .
Operations On stack :

• Two fundamental operations performed on the stack are PUSH and POP.
• Return the top element , stack overflow, and stack underflow are other additional
functions.

(c) PUSH:
• It is the process of inserting a new element at the Top of the stack.

For every push operation:

5. Check for Full stack (overflow).
6. Increment Top by 1. (Top = Top + 1)
7. Insert the element X in the Top of the stack.

Procedure for PUSH

void push ()
{ int val;
if (top == n) printf("\n
Overflow"); else

{
printf("Enter the value?");
scanf("%d",&val);
top = top +1;
stack[top] = val;
}
}

(b)POP:

• It is the process of deleting the Top element of the stack.

For every pop operation:

6. Check for Empty stack ( underflow ).
7. Delete (pop) the Top element X from the stack
8. Decrement the Top by 1. (Top = Top - 1 )

Procedure for POP

void pop ()
{
if(top == -1)
printf("Underflow");
else
top = top -1;
}

(E) Return or Peek

• Peek operation involves returning the element which is present at the top of the stack
without deleting it.

• Underflow condition can occur if we try to return the top element in an empty stack.

Procedure for return or peek

void show()
{
for (i=top;i>=0;i--)
{
printf("%d\n",stack[i]);
}
if(top == -1)
{
printf("Stack is empty");
}
}

Exceptional Conditions of stack

3. Stack Overflow

• An Attempt to insert an element X when the stack is Full, is said to be stack overflow.
• For every Push operation, we need to check this condition.

4. Stack Underflow:

• An Attempt to delete an element when the stack is empty, is said to be stack

underflow.
• For every Pop operation, we need to check this condition.

Implementation of Stack

Stack can be implemented in 2 ways.

2. Static Implementation (Array implementation of Stack)
6. Dynamic Implementation (Linked List Implementation of Stack)

Array Implementation of Stack

#include <stdio.h>
int stack[100],i,j,choice=0,n,top=-1;
void push();
void pop();
void show();
void main ()
{
printf("Enter the number of elements in the stack ");
scanf("%d",&n);
while(choice != 4)
{ printf("Chose one from the below options...\n");
printf("\n1.Push\n2.Pop\n3.Show\n4.Exit");
printf("\n Enter your choice \n");
scanf("%d",&choice);
switch(choice)
{ case 1: push();
break;
case 2:pop();
break;
case 3:show();
break;
case 4: printf("Exit....");
break;
}
default: printf("Please Enter valid choice ");
};
} }

Linked List Implementation of Stack

• In linked list implementation of stack, the nodes are maintained non-contiguously in the
memory.
• Each node contains a pointer to its immediate successor node in the stack.
• Stack is said to be overflown if the space left in the memory heap is not enough to create
a node.

PUSH Operation using Linked List

• Inserting a node from the top of stack is referred to as push operation.
• Create a node first and allocate memory to it.
• If the list is empty then the item is to be pushed as the start node of the list.
• If there are some nodes in the list already, then we have to add the new element in the
beginning of the list
• For this purpose, assign the address of the starting element to the address field of the
new node and make the new node, the starting node of the list.
(POP operation) Deleting a node from the stack

• Deleting a node from the top of stack is referred to as pop operation.

• Check for the underflow condition: The underflow condition occurs when we try to pop
from an already empty stack. The stack will be empty if the head pointer of the list points
to null.
• Adjust the head pointer accordingly: In stack, the elements are popped only from one end,
therefore, the value stored in the head pointer must be deleted and the node must be freed.
The next node of the head node now becomes the head node.
Program for Linked list implementation stack
#include <stdio.h>
#include <stdlib.h>
void push();
void pop();
void display();
struct node
{ int val;
struct node *next;
}; struct node *head;

void main ()
{ int choice=0;
printf("\n*********Stack operations using linked list*********\n");

printf("\n----------------------------------------------\n");
while(choice != 4)
{ printf("\n\nChose one from the below options...\n");
printf("\n1.Push\n2.Pop\n3.Show\n4.Exit"); printf("\n
Enter your choice \n"); scanf("%d",&choice);
switch(choice)
{ case 1: push();
break;
case 2: pop();
break;
case 3: display();
break; }
case 4: printf("Exiting....");
break;

default: printf("Please Enter valid choice ");

};
}
}
void push ()
{ int val;
struct node *ptr = (struct node*)malloc(sizeof(struct node));
if(ptr == NULL)
{ printf("not able to push the element"); }
else
{
printf("Enter the value");

scanf("%d",&val);
if(head==NULL)
{
ptr->val = val;
ptr -> next = NULL;
head=ptr;
}
else
{
ptr->val = val;
ptr->next = head;
head=ptr; }
printf("Item pushed");
}
}

void pop()
{
int item;
struct node *ptr;
if (head == NULL)
{ printf("Underflow"); }
else
{
item = head->val;
ptr = head;
head = head->next;
free(ptr);
printf("Item popped");
}
}
void display()
{
int i;
struct node *ptr;
ptr=head;
if(ptr == NULL)
{ printf("Stack is empty\n"); }
else
{

printf("Printing Stack elements \n");

while(ptr!=NULL)
{
printf("%d\n",ptr->val);
ptr = ptr->next;
}
}
}

Applications of Stack

The following are some of the applications of stack:

2. Evaluating the arithmetic expressions

• Conversion of Infix to Postfix Expression
• Evaluating the Postfix Expression
• Balancing the Symbols
3. Function Call
4. Tower of Hanoi
5. 8 Queen Problem

Evaluating the Arithmetic Expression:

1.Conversion of Infix to Postfix Expression

There are 3 types of Expressions

• Infix Expression
• Postfix Expression
• Prefix Expression

INFIX: The arithmetic operator appears between the two operands to which it is being applied.

Example1 : A + B
Example2 : A / B + C

POSTFIX: The arithmetic operator appears directly after the two operands to which it applies.
Also called reverse polish notation.
Example1 : A B +
Example2 : A B / C +

PREFIX: The arithmetic operator is placed before the two operands to which it applies.
Also called polish notation
Example1 : + A B
Example2 : + / A B C

Algorithm to convert Infix Expression to Postfix Expression:

Read the infix expression one character at a time until it encounters the delimiter “#”

Step 1: If the character is an operand, place it on the output.

Step 2: If the Character is Operator,

Step 2.1: If the Top of Stack operator has a higher or equal priority than input operator,
then pop that top of stack operator and place it onto the output. Then push the input operator.
Step 2.2: If the Top of Stack operator has a less priority than input operator, then push
the input operator.

Step 3: If the character is ‘(‘ , push it onto the stack

Step 4: If the character is a ‘)’ , pop all the operators from the stack till it encounters ‘(‘, and
discard both the parenthesis in the output.
Step 5: If the Charater is ‘#’ pop all the character from stack

Eg: Consider the following Infix expression: - A / (B + C) * D

Convert A / (B + C) * D to postfix notation.

Input : add # in input expression and write A / (B + C) * D #

Stack Action Taken

Input Postfix
(Note :Top of
Character Expression
Stack is bold)
A A Output A
/ / A Push /
( /( A Push (
B /( AB Output B
+ /(+ AB Push +
C /(+ ABC Output C
Pop until (, write into
) / ABC+
output except parenthesis
ToS is EQP, So pop ToS and
* * ABC+ /
push *
D * ABC+ / D Output D
# ABC+/D* Pop *

Output : A B C + / D *

Note : *, / , and % (modulus) are equal in precedence and higher precedence than +
and - .
^ is an exponential power operator. ^ has highest precedence than *, / , and %.

BODMAS: Its letters stand for Brackets, Order (meaning powers), Division, Multiplication,
Addition, Subtraction.

Eg 2: Convert A*B+(C-D/E)# into postfix notation.

Eg 3: Outline the algorithm to check if the given parenthesized arithmetic expression

contains balanced parenthesis and to convert such expression to postfix form and illustrate
the steps for the expression A +(B*C-(D/E^F) *G)*H. Evaluate the given postfix expression
934*8-4*+
Input : add # in input expression and write A +(B*C-(D/E^F) *G)*H #

Stack
Input
(Note :Top of Stack Postfix Expression
Character
is bold)
A A
+ + A
( +( A
B +( AB
* +(* AB
C +(* ABC
- +(- ABC*
( +(-( ABC*
D
/
+(-( ABC*D
E
+(-(/ ABC*D ^
+(-(/ ABC*DE F
+(-(/^ ABC*DE )
+(-(/^ ABC*DEF *
+(- A B C *DEF^/ G
)
+(-* A B C *DEF^/ *
+(-* A B C *DEF^/G H
+ A B C *DEF^/G* - #
+* A B C *DEF^/G* -
+* A B C *DEF^/G* - H ABC*DEF^/G*-H*+

Output:
Resultant Postfix Expression: ABC*DEF^/G*-H*+

Eg 4: Write the procedure to convert the infix expression to postfix expression and steps
involved in evaluating the postfix expression. Convert the expression A-(B/C+
(D%E*F)/G)*H to postfix form. Evaluate the given postfix expression 9 3 4 * 8 + 4 / -.

Advantage of Postfix Expression over Infix Expression

• An infix expression is difficult for the machine to know and keep track of precedence of
operators.
• On the other hand, a postfix expression itself determines the precedence of operators
• Therefore, for the machine it is easier to carry out a postfix expression than an infix
expression.

2. Evaluating the Postfix Expression

The postfix expression is evaluated easily by the use of a stack.
Procedure or Algorithm to evaluate the Postfix Expression:
Read the postfix expression one character at a time until it reaches "#" symbol.

Step 1: If the character is an operand, it is pushed onto the stack.

Step 2: If the character is an operator, POP two values from the stack apply the operator to them
and push the result onto the stack.
Step 3 : If the character is an #, Then write the result from stack into output.

Exxample: Infix expression A / (B + C) * D its equivalent postfix expression is A B C + / D *,

evaluate the postfix expression for A= 20, B = 6, C= 4 , D = 3.

Input: 20 6 4 + / 3*# .
Stack Action Taken
Input
(Note :Top of Output
Character
Stack is bold)
20 20 Push 2
6 20 6 Push 6
4 2064 Push 4
Pop 6 and 4 , perform +, and
+ 20 10
push the result
Pop 20and 10 , perform /,
/ 2
and push the result
3 23 Push 3
Pop 2 and 3 , perform *, and
* 6
push the result
# 6 Output

3. Balancing the symbols

Compilers check the programs for errors, a lack of one symbol will cause an error. Every right
parenthesis should have its left parenthesis. Check for balancing the parenthesis and ignore any
other character.
Procedure to balance the symbols
the Postfix Expression:
Read one character at a time until it encounters the delimiter. "#"
Step 1 : If the Character is an Operand or operator , ignore it.
Step 2: If the character is an ‘(‘, push it on to the stack.
Step 3: If the character is a ‘)’ and if the stack is empty, then report an error as missing ‘(‘. Step 4:
If the character is a ‘)’ and if it has a corresponding ‘(‘ in the stack, then pop it from the stack.
Step 5: If the character is a ‘#’, and if the stack is not empty, report an error as missing closing
symbol. Otherwise output as balanced symbols.

Example: Let us consider the expression ((a+b) * (d / e)) # Check the expression has
Balanced symbol.

Input : ((a+b) * ((d /e)) #

Stack Action Taken

Input
(Note :Top of Output
Character
Stack is bold)
( ( Push (
( (( Push (
a (( Ignore a
+ (( Ignore +
b (( Ignore b
) ( Pop (
* ( Ignore *
( (( Push (
d (( Ignore d
/ (( Ignore /
e (( Ignore e
) ( Pop (
) Pop (
# Balanced Symbol Empty stack, output

Queue ADT:

• Queue is a Linear Data Structure that follows First in First out (FIFO) principle.
• Insertion of element is done at one end of the Queue called “Rear “end of the Queue.
• Deletion of element is done at other end of the Queue called “Front “end of the Queue.
• Example: - Waiting line in the ticket counter.

Front Pointer:- It always points to the first element inserted in the Queue.

Rear Pointer:- It always points to the last element inserted in the Queue.
For Empty Queue:-

Front (F) = - 1

Rear (R) = - 1

Operations on Queue

Fundamental operations performed on the queue are

2. EnQueue / insert
3. DeQueue / delete
4. Queue Overflow
5. Queue Underflow
6. Display / front

(i) EnQueue operation:-

• It is the process of inserting a new element at the rear end of the Queue.
• For every EnQueue operation
oCheck for Full Queue
oIf the Queue is full, Insertion is not possible.
o Otherwise, increment the rear end by 1 and then insert the element in the rear end of the
Queue.

(ii) DeQueue Operation:-

• It is the process of deleting the element from the front end of the queue.
• For every DeQueue operation
o Check for Empty queue
o If the Queue is Empty, Deletion is not possible.
o Otherwise, delete the first element inserted into the queue and then increment the front by
1.

Exceptional Conditions of Queue

• Queue Overflow
• Queue Underflow

(iii) Queue Overflow: (rear == maxsize-1)

• An Attempt to insert an element X at the Rear end of the Queue when the Queue is full
is said to be Queue overflow.
• For every Enqueue operation, we need to check this condition.
(iv) Queue Underflow: (front == -1 || front > rear)
• An Attempt to delete an element from the Front end of the Queue when the Queue is
empty is said to be Queue underflow.
• For every DeQueue operation, we need to check this condition.

Queue can be implemented in two ways.

1. Implementation using Array (Static Queue)

2. Implementation using Linked List (Dynamic Queue)

Implementation using Array (Static Queue)

/ Enqueue Operation
void enqueue()
{
int item;
printf("\nEnter the element\n");
scanf("%d",&item);
if(rear == maxsize-1)
{ printf("OVERFLOW"); return; }
if(front == -1 && rear == -1)
{ front = 0; rear = 0; }
else

{ rear = rear+1; queue[rear] = item;

}
printf("Value inserted ");

/ Dequeue Operation
void dequeue ()
{ int item;
if (front == -1 || front > rear)
{ printf("\nUNDERFLOW\n"); return; } else

{
item = queue[front];
if(front == rear)
{ front = -1;
rear = -1 ;}
else
{ front = front + 1;}
printf("\nvalue deleted ");
}
}
//Display / front Operation

void display()
{ int i; if(rear
== -1)
{ printf("\nEmpty queue\n"); else
}
{ printf("\nprinting values .....\n");
for(i=front;i<=rear;i++)
{ printf("\n%d\n",queue[i]); }
}
}
#include<stdio.h>
#include<stdlib.h>
#define maxsize 5
void enqueue ();
void dequeue ();
void display();

int front = -1, rear = -1;

int queue[maxsize];
void main ()
{
int choice;
while(choice != 4)
{
printf("\n*************************Main Menu*****************************\
n"); printf("\n1.insert an element\n2.Delete an element\n3.Display the
queue\n4.Exit\n");
printf("\nEnter your choice ?");
scanf("%d",&choice);
switch(choice)
{
case 1: enqueue(); break;
case 2: dequeue (); break;
case 3: display(); break;
case 4: exit(0); break;
default: printf("\nEnter valid choice??\n");
}
}
}
Drawback of array implementation

• Memory wastage: The space of the array, which is used to store queue elements, can never
be reused to store the elements of that queue because the elements can only be inserted at
front end and the value of front might be so high so that, all the space before that, can never
be filled.
• Deciding the array size: The extension in the array size is a time taking process and
almost impossible to be performed at runtime since a lot of reallocations take place. Due to
this reason, the array is declared as large enough, but most of the array slots can never be
reused. It will again lead to memory wastage.
• The array implementation of queue cannot be used for the large scale applications.

Linked List implementation of Queue

• In a linked queue, each node of the queue consists of two parts i.e. data part and the link
part. Each element of the queue points to its immediate next element in the memory.

• In the linked queue, there are two pointers maintained in the memory i.e. front pointer and
rear pointer. The front pointer contains the address of the starting element of the queue
while the rear pointer contains the address of the last element of the queue.
• Insertion and deletions are performed at rear and front end respectively. If front and rear
both are NULL, it indicates that the queue is empty. The linked
#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *next;
};
struct node *front;
struct node *rear;
void insert();
void delete();
void display();
void main ()
{
int choice;
while(choice != 4)
{printf("\n1.insert an element\n2.Delete an element\n3.Display the queue\n4.Exit\n");
printf("\nEnter your choice ?");
scanf("%d",& choice);
switch(choice)
{
case 1: insert(); break;

case 2: delete(); break;

case 3: display(); break;
case 4: exit(0); break;
default: printf("\nEnter valid choice??\n");
}
}
}

void insert()
{
struct node *ptr;
int item;

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

if(ptr == NULL)
{
printf("\nOVERFLOW\n");
return;
}
else
{
printf("\nEnter value?\n");
scanf("%d",&item);
ptr -> data = item;
if(front == NULL)
{
front = ptr;
rear = ptr;
front -> next = NULL;
rear -> next = NULL;
}
else
{
rear -> next = ptr;
rear = ptr;
rear->next = NULL;
}
}
}
void delete ()
{
struct node *ptr;
if(front == NULL)
{ printf("\nUNDERFLOW\n"); else return; }
{ptr = front;
front = front -> next;
free(ptr);
}
}

void display()
{
struct node *ptr;
ptr = front;
if(front == NULL)
{
printf("\nEmpty queue\n");
}
else
{ printf("\nprinting values .....\n");
while(ptr != NULL)
{
printf("\n%d\n",ptr -> data); ptr
= ptr -> next;
}
}
}

Applications of Queue

2. Serving requests on a single shared resource, like a printer, CPU task scheduling etc.
3. In real life, Call Center phone systems will use Queues, to hold people calling them in an
order, until a service representative is free.
4. Handling of interrupts in real-time systems. The interrupts are handled in the same order as
they arrive, First come first served.
5. Batch processing in operating system.

5. Job scheduling Algorithms like Round Robin Algorithm uses Queue.

Drawbacks of Queue (Linear Queue)

• With the array implementation of Queue, the element can be deleted logically only by
moving Front = Front + 1.
• Here the Queue space is not utilized fully.

To overcome the drawback of this linear Queue, we use Circular Queue.

Circular Queue
A circular queue uses its storage array as if it were a circle instead of a linear list. In Circular
Queue, elements are added at the rear end and the items are deleted at front end of the circular
queue. if the last location of the queue is full, then first element comes just after the last element.
Operations on Circular Queue
Fundamental operations performed on the Circular Queue are
• Circular Queue Enqueue
• Circular Queue Dequeue
Formula to be used in Circular Queue

• For Enqueue Rear = (Rear + 1) % ArraySize

• For Dequeue Front = (Front + 1) % ArraySize

ROUTINE TO INSERT AN ELEMENT IN CIRCULAR QUEUE

void CEnqueue (int X)

{

if (front = = (rear + 1) % Maxsize)

print ("Queue is overflow");
else
{ if (front = = -1)
front = rear = 0;
else rear = (rear + 1)% Maxsize;
CQueue [rear] = X; }
}

ROUTINE TO DELETE AN ELEMENT FROM CIRCULAR QUEUE

int CDequeue ( )
{ if (front = = -1)
print ("Queue is underflow");
else { X = CQueue [Front];
if (front = = rear)
front = rear = -1;
else
front = (front + 1)% maxsize;
}
return (X);
}

ADVANTAGES
It is a structure that allows data to be passed from one process to another while making the most
efficient use of memory.

Double Ended Queues (DEQUE ADT)

In DEQUE, insertion and deletion operations are performed at both ends of the Queue.
Exceptional Condition of DEQUE
(i) Input Restricted DEQUE
Here insertion is allowed at one end and deletion is allowed at both ends.

(vi)Output Restricted DEQUE

Here insertion is allowed at both ends and deletion is allowed at one end.

Operations on DEQUE
Four cases for inserting and deleting the elements in DEQUE are
1. Insertion At Rear End [ same as Linear Queue ]
2. Insertion At Front End
3. Deletion At Front End [ same as Linear Queue ]
4. Deletion At Rear End

/* The following program in C, implements the logic of Double ended queue, in which the
insertion & deletion from end as well as starting is allowed(circular array) */

#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#define SIZE 100 int queue[SIZE];
int F = -1; int R = -1;
/* To insert element in the rear of Double ended queue*/
void insert_r(int x)
{ if(F == (R+1)%SIZE)
{ printf("\nQueue Overflow"); }
else if(R == -1)
{ F = 0; R = 0; queue[R] =
x; } else
{ R = (R+1) %SIZE; queue[R] = x; } }

/* To insert element in the front of Double ended queue*/

void insert_f(int x)
{ if(F == (R+1)%SIZE)
{ printf("\nQueue Overflow"); }
else if(R == -1) { F = 0; R = 0;
queue[R] = x; }
else { F = (F+SIZE-1) %SIZE; queue[F] = x; }
}

/* To delete element in the rear of Double ended queue*/

int delete_r()
{ int x; if(F == -1)

{ printf("\nQueue Underflow"); }
else if(F == R)
{ x = queue[F];
F=-1;R=-1;}
else
{ x = queue[R];
R = (R+SIZE-1)%SIZE;
}
return x; }

/* To delete element in the front of Double ended queue*/ int

delete_f()
{ int x; if(F == -1)
{ printf("\nQueue Underflow"); }
else if(F == R)
{ x = queue[F];
F=-1;R=-1;}
else { x = queue[F];
F = (F+1)%SIZE;
}
return x;
}

void main()
{ char choice; int x;
while(1)
{ printf("1: Insert From Front\n");
printf("2: Insert From Rear\n");
printf("3: Delete From Front\n");
printf("4: Delete From Rear\n");
printf("5: Exit Program\n");
printf("Enter Your Choice:");
choice = getche();
switch(choice) { case '1': printf("\nEnter Integer Data :");
scanf("%d",&x); insert_f(x); break;
case '2': printf("\nEnter Integer Data :");
scanf("%d",&x); insert_r(x); break;
case '3': printf("\nDeleted Data From Front End: %d",delete_f()); break;
case '4': printf("\nDeleted Data From Back End: %d",delete_r()); break;
case '5': exit(0); break; } }}

Priority Queue (Heap or Binary Heap)

Need for priority queue
• The operating system uses Queue Data structures to schedule the jobs to the CPU.
• Jobs are initially placed at the end of the queue.
• The scheduler will repeatedly take the first job on the queue, run it until either it finishes or
its time limit is up
• Sometime, some jobs are still very important have precedence over others and need to be
executed first.
• This particular application seems to require a special kind of queue, known as priority
queue. Priority queue is also called as Heap or Binary Heap.

Definition:
A priority queue is a data structure that allows two operations:
• insert (enqueue operation) and
• delete_min (queue's dequeue operation with priroity), which finds, returns and removes the
minimum element in the heap.

Implementation of priority Queue : Binary Heap implementation

(Refer Unit3 Notes)