CEG's Linux User Group

Article Index
LINEAR QUEUE IMPLEMENTATION USING LINKED LIST
Introduction
Source Code
Documentation
All Pages

Introduction :
The linear queue is a data structure characterised by the fact that additions are made at the end, or tail, of the queue while removals are made from the front, or head, of the queue. For this reason, a queue is referred to as a FIFO structure (First-In First-Out).
The efficient and quick way for implementing queue is through Linked List.

Linked List :
Linked list is one of the fundamental data structures which can be used to implement other data structures. Each node consists of two fields. The first field, known as the data field holds the value or data and the second field, known as the address field holds the reference to the next node or is assigned NULL(if the linked list is empty).The elements in the linked list are not stored continuously in the memory.



The simplest way of accessing the linked is through header(as through it is not necessary). The header node will be the first node contains NULL in the data part and hold the address of the first element in the address field.


Technical Terms In Queue :
1.Enqueue - Inserting an item in the queue.
2.Dequeue - Deleting an item in the queue.



Main Features of Linked List :

Structure :

The structure is the user defined data type. This can have different data type together. The structure definition will not occupy any bytes in the memory. But the structure variable will occupy the space in the memory. The structure member cannot be accessed independently. It can be accessed only through the structure variable.

• If the structure variable is not a pointer then we have to access the

members through dot operator.

• If the structure variable is a pointer then we have to access the members through arrow operator.

Typedef :
The typedef is the predefined function in c language. The function of typedef is to make the user defined data types. Even we can give different name for the primitive data types like integer, float and character. The syntax is as follows


So after declaring like this we can replace int by rollnumber.


malloc :
The malloc is the also predefined function in c. This function is used to allocate the memory in runtime. Some information will be available only during the runtime. In those cases this malloc function will be very useful.The return type of the malloc function is a pointer. We have to pass only one parameter(size) to this function. The syntax of this function is as follows.


Queue Using Linked List :
In Linked List everything is node. So memory will be allocated in runtime for those nodes. So during inserting(Enqueue) and deleting(Dequeue) new node will be created in the memory . In queue the insertion of node has to be taken place at the end while the deletion has to be done in the front (i.e. after header node) .We can remember the queue concept simply , the enqueue and dequeue should be taken place in the opposite end of the list (i.e. Enqueue in the end and dequeue in the front ). The main advantage of the implementing queue in the linked list is it never satisfies the overflow condition ( although we can restrict the enqueue by getting the maximum size of the array and pass that to enqueue function).

Model Of Queue(Linked List) :

Initially The Appearance Of Queue In Linked List :
Initially the list will contain header with NULL in the data and address field.



Enqueue :
Enqueue is nothing but inserting a node at the end of the List. The node is always going to be inserted at the end so in the inserting node the address part will always contains NULL.

Before Inserting a node :



After inserting a node :



Dequeue :
Deleting a node at the front of the list is called dequeue. Header in the list will contain the address of the first node. In that address part of the header node we have to delete the address of the first node and replace it with the address of the second node. This will result in the deletion of first node in the list

Before deleting the node :




After deleting the node :



Underflow:

Delete(dequeue) all elements in the queue will result in underflow condition. If the address field in the header contains NULL. Then the list is said to be empty .

 

Source code:

#include"stdio.h"
#include"stdlib.h"

struct listnode
{
int element;
struct listnode *next;
};
typedef struct listnode *node;
typedef node list;
node ne,temp,prev,end;
list createlist()
{
list header;
header=malloc(sizeof(struct listnode));
header->next=NULL;
return header;
}
int isempty(list header)
{
return header->next==NULL;
}

list enqueue(list header,int e)
{
ne=malloc(sizeof(struct listnode));
ne->element=e;
if(isempty(header))
{
ne->next=NULL;
header->next=ne;
end=ne;
}
else
{
ne->next=NULL;
end->next=ne;
end=ne;
}
return header;
}

list dequeue(list header)
{
if(isempty(header))
{
printf("underflow\n");
return NULL;
}
else
{
header->next=(header->next)->next;
}
return header;
}
int frontanddelete(list header)
{
int e;
if(isempty(header))
{
printf("underflow\n");
return 0;
}
else
{
e=(header->next)->element;
dequeue(header);
return e;
}
}

int front(list header)
{
if(isempty(header))
{
printf("underflow\n");
return 0;
}
else
{
return (header->next)->element;
}
}

void search(list header,int e)
{
int i;
if(isempty(header))
{
printf("underflow\n");
}
else
{
i=1;
temp=header->next;
while(temp!=NULL&&temp->element!=e)
{
i++;
temp=temp->next;
}
if(temp==NULL)
printf("no such element is present in the list\n");
else
{
printf("element is present in %dth position\n",i);
}
}
}

void display(list header)
{
temp=header->next;
while(temp!=NULL)
{
printf("%d\n",temp->element);
temp=temp->next;
}
printf("\n");
}
int main()
{
int e,s;
list header;
header=createlist();
while(1)
{
printf("\n1-enqueue\n2-dequeue\n3-frontanddelete\n4-front\n5-search\n6-display\n7-exit\n");
scanf("%d",&s);
switch(s)
{
case 1:
printf("element=");
scanf("%d",&e);
enqueue(header,e);
break;
case 2:
dequeue(header);
break;

case 3:
printf("frontanddelete=%d\n",frontanddelete(header));
break;
case 4:
printf("front=%d\n",front(header));
break;
case 5:
printf("element=");
scanf("%d",&e);
search(header,e);
break;
case 6:
printf("The elements in the queue\n");
display(header);
break;
default:
exit(0);
}
}
}


Goal :
The aim of this code is to perform the basic linear queue operations and has to inform underflow during necessary situation.

Variable Used :

Variable	Data Type	Task Of The Variable
ne	*node	Since the data type is a pointer, the variable ne is also a pointer. The variable ne is the pointer to a structure.
end	*node	Since the data type is a pointer, the variable end is also a pointer. The variable end is the pointer to a structure.
header	list(*node)	The list is a user defined data type. The header is the first node in the list
element	integer inside the structure	The element is present inside the structure. So it can be accessed only through the structure variables (ne,end,header). Since the ne and end are pointers, to access the element we have to use arrow operator (e.g ne->element,end->element) .
next	Structure pointer inside the structure	The next is present inside the structure. So it can be accessed only through the structure variables (ne,end,header). Since the ne,header and end are pointers, to access the next we have to use arrow operator (e.g ne->next,end->next,header->next) .
e	integer	Variable used for storing the integer in our program
i	integer	Loop variable
s	integer	Switch variable which will select any one of the cases

 

Function Used :

FUNCTION NAME	RETURN TYPE	PARAMETERS	TASK OF THE FUNCTION
createqueue	queue	-----	It will allocate memory for a header node (which contain data and address field)
isempty	int	header	Check whether the queue is empty or not(return 1 if the queue is full else it will return 0)
enqueue	void	header,e	Insert the element in the queue
dequeue	void	header	Delete the element in the queue
frontanddelete	int	Header	Delete the element in the queue and also display the deleted element
front	int	header	Display the front element in the queue
search	void	header,e	This function will search whether the element is present in the current list and display the current position if it is present in the list.
display	void	header	Display all the elements that present in the queue

Implementation :

• The main call the createqueue function which will built the header node and initialize as well.

• Then using Switch case we can select the task to perform.

• Each function will perform their own task.

 

Test Cases:

1.enqueue
2.dequeue
3.front and delete
4.front
5.display
1
element 5

1.enqueue
2.dequeue
3.front and delete
4.front
5.display
1
element 8

1.enqueue
2.dequeue
3.front and delete
4.front
5.display
5
The elements in the queue
5
8

1.enqueue
2.dequeue
3.front and delete
4.front
5.display
4
front=5

1.enqueue
2.dequeue
3.front and delete
4.front
5.display
3
front and delete=5

1.enqueue
2.dequeue
3.front and delete
4.front
5.display
4
front=8

Compatibility :
Compatible with all computers which is capable of running gcc-4.3.3-5.The program has been tested with the above version of gcc as well as in opensuse as of June 8.

References :
Data structures and Algorithm analysis in C-Mark Allen Weiss.

< Prev		Next >