ANURAG GROUP OF INSTITUTIONS

(CVSR COLLEGE OF ENGINEERING)

UNIT-IV(Data Structures)
Introduction to Data Structures:
Data Structure is a way of collecting and organising data in such a way that we
can perform operations on these data in an effective way. Data Structures is about
rendering data elements in terms of some relationship, for better organization and storage.
Defination : “Logical organisation of data is called Data Structures”.
For example, we have data player's name "Virat" and age 26. Here "Virat" is
of String data type and 26 is of integer data type.
We can organize this data as a record like Player record. Now we can collect and
store player's records in a file or database as a data structure. For example: "Dhoni" 30,
"Gambhir" 31, "Sehwag" 33.
In simple language, Data Structures are structures programmed to store ordered
data, so that various operations can be performed on it easily. Some examples of data
structures would be: an array, structs, lists, strings, stacks, queues, files. The underlying
theme here is that each structure has a defined organisation and a set of rules that
implement and control the organisation.
Types of Data Structures:
A data structure is classified into two categories: Linear and Non-Linear data
structures.
A data structure is said to be linear if the elements form a sequence, insertion and
deletion of elements can be done in linear fashion. The elements of linear data structure
represents by means of sequential memory locations, for example Array, Linked list,
queue etc.
A data structure is said to be non-linear if its elements a hierarchical relationship
between elements such as trees and graphs. All elements assign the memory as random
form and you can fetch data elements through random access process, for example Tree,
Hash tree, Binary tree, etc..

COMPUTER PROGRAMMING-II UNIT-IV Page 1

 ANURAG GROUP OF INSTITUTIONS
(CVSR COLLEGE OF ENGINEERING)

There are two ways of representing linear data structures in memory. One way is
to have the linear relationship between the elements by means of sequential memory
locations. Such linear structures are called arrays or static implementation by using
arrays. The other way is to have the linear relationship between the elements represented
by means of links using self referential structure concepts, such linear data structures are
called linked list or dynamic implementation by using Linked lists.

Data Structure Operations:

Basically there are six operations one can do on the data structures. They are Traversing,
Searching, Sorting, Insertion, Deletion and Merging.

(1) Traversing or Display: Accessing each records exactly once so that certain items in
the record may be processed.
(2) Searching: Finding the location of a particular record with a given key value, or
finding the location of all records which satisfy one or more conditions.
(3) Inserting: Adding a new record to the data structure.
(4) Deleting: Removing the record from the data structure.
(5) Sorting: Managing the data or record in some logical order (Ascending or descending
order).
(6) Merging: Combining the record in two different sorted files into a single sorted file.

COMPUTER PROGRAMMING-II UNIT-IV Page 2

 ANURAG GROUP OF INSTITUTIONS
(CVSR COLLEGE OF ENGINEERING)

Linked Lists:
Simply a list is a sequence of data, and linked list is a sequence of data linked
with each other.

Linked lists and arrays are similar since they both store collections of data. Array is the
most common data structure used to store collections of elements. Arrays are convenient
to declare and provide the easy syntax to access any element by its index number. Once
the array is set up, access to any element is convenient and fast. The disadvantages of
arrays are:
1. The size of the array is fixed. Most often this size is specified at compile time.
This makes the programmers to allocate arrays, which seems "large enough" than
required.
2. Inserting new elements at the front is potentially expensive because existing
elements need to be shifted over to make room.
3. Deleting an element from an array is not possible.

Linked lists have their own strengths and weaknesses, but they happen to be strong where
arrays are weak. Generally array's allocates the memory for all its elements in one block
whereas linked lists use an entirely different strategy. Linked lists allocate memory for
each element separately and only when necessary.

Linked List Concepts:

A linked list is a non-sequential collection of data items. It is a dynamic data structure.
For every data item in a linked list, there is an associated pointer that would give the
memory location of the next data item in the linked list.

The data items in the linked list are not in consecutive memory locations. They may be
anywhere, but the accessing of these data items is easier as each data item contains the
address of the next data item.

Advantages of linked lists:

Linked lists have many advantages. Some of the very important advantages are:
1. Linked lists are a dynamic data structure, which can grow and be
pruned, allocating and deallocating memory while the program is running.
2. Insertion and deletion node operations are easily implemented in a linked list.
3. Dynamic data structures such as stacks and queues can be implemented using a
linked list.
4. There is no need to define an initial size for a linked list.
5. Items can be added or removed from the middle of list.
6. Backtracking is possible in two way linked list.

COMPUTER PROGRAMMING-II UNIT-IV Page 3

 ANURAG GROUP OF INSTITUTIONS
(CVSR COLLEGE OF ENGINEERING)

Disadvantages of linked lists:

1. It consumes more space because every node requires a additional pointer to store
address of the next node.
2. Searching a particular element in list is difficult and also time consuming.

Applications of Linked List:

1. Linked Lists can be used to implement Stacks , Queues.
2. Linked Lists can also be used to implement Graphs.
3. Implementing Hash Tables .
4. Undo functionality in Photoshop or Word . Linked list of states.
5. Linked lists are useful for dynamic memory allocation.
6. The real life application where the circular linked list is used is our Personal
Computers, where multiple applications are running.

Types of Linked Lists:

Basically we can put linked lists into the following four items:
1. Single Linked List.
2. Double Linked List.
3. Circular Linked List.
4. Circular Double Linked List.

Single linked list:

The formal definition of a single linked list is as follows...
“Single linked list is a sequence of elements in which every element has link to its
next element in the sequence”.
In any single linked list, the individual element is called as "Node".
Every "Node" contains two fields, data and next. The data field is used to store actual
value of that node and next field is used to store the address of the next node in the
sequence.

The graphical representation of a node in a single linked list is as follows...

 In a single linked list, the address of the first node is always stored in a reference
node known as "front" (Some times it is also known as "head").
 Always next part (reference part) of the last node must be NULL.

A single linked list is one in which all nodes are linked together in some sequential
manner. Hence, it is also called as linear linked list.

COMPUTER PROGRAMMING-II UNIT-IV Page 4

 ANURAG GROUP OF INSTITUTIONS
(CVSR COLLEGE OF ENGINEERING)

Example

iIn a single linked list we perform the following operations...

1. Insertion
2. Deletion
3. Display
Before we implement actual operations, first we need to setup empty list. First perform
the following steps before implementing actual operations.
Step 1: Include all the header files which are used in the program.
Step 2: Declare all the user defined functions.
Step 3: Define a Node structure with two members data and link or next
Step 4: Define a Node pointer 'head' and set it to NULL.
Step 4: Implement the main method by displaying operations menu and make suitable
function calls in the main method to perform user selected operation.

Insertion
In a single linked list, the insertion operation can be performed in three ways. They are as
follows...
1. Inserting At Beginning of the list
2. Inserting At End of the list
3. Inserting At Specific location in the list

Inserting At Beginning of the list

We can use the following steps to insert a new node at beginning of the single linked
list...
Step 1: Create a newNode with given value.
Step 2: Check whether list is Empty (head == NULL)
Step 3: If it is Empty then, set newNode→next = NULL and head = newNode.
Step 4: If it is Not Empty then, set newNode→next = head and head = newNode.

Inserting At End of the list

We can use the following steps to insert a new node at end of the single linked list...
Step 1: Create a newNode with given value and newNode → next as NULL.
Step 2: Check whether list is Empty (head == NULL).

COMPUTER PROGRAMMING-II UNIT-IV Page 5

 ANURAG GROUP OF INSTITUTIONS
(CVSR COLLEGE OF ENGINEERING)

Step 3: If it is Empty then, set head = newNode.

Step 4: If it is Not Empty then, define a node pointer temp and initialize with head.
Step 5: Keep moving the temp to its next node until it reaches to the last node in the list
(until temp → next is equal to NULL).
Step 6: Set temp → next = newNode.

Inserting At Specific location in the list (After a Node)

We can use the following steps to insert a new node after a node in the single linked list...
Step 1: Create a newNode with given value.
Step 2: Check whether list is Empty (head == NULL)
Step 3: If it is Empty then, set newNode → next = NULL and head = newNode.
Step 4: If it is Not Empty then, define a node pointer temp and initialize with head.
Step 5: Keep moving the temp to its next node until it reaches to the node after which we
want to insert the newNode (until temp1 → data is equal to location, here location is the
node value after which we want to insert the newNode).
Step 6: Every time check whether temp is reached to last node or not. If it is reached to
last node then display 'Given node is not found in the list!!! Insertion not
possible!!!' and terminate the function. Otherwise move the temp to next node.
Step 7: Finally, Set 'newNode → next = temp → next' and 'temp → next = newNode'

Deletion
In a single linked list, the deletion operation can be performed in three ways. They are as
follows...
1. Deleting from Beginning of the list
2. Deleting from End of the list
3. Deleting a Specific Node

Deleting from Beginning of the list

We can use the following steps to delete a node from beginning of the single linked list...
Step 1: Check whether list is Empty (head == NULL)
Step 2: If it is Empty then, display 'List is Empty!!! Deletion is not possible' and
terminate the function.
Step 3: If it is Not Empty then, define a Node pointer 'temp' and initialize with head.
Step 4: Check whether list is having only one node (temp → next == NULL)
Step 5: If it is TRUE then set head = NULL and delete temp (Setting Empty list
conditions)
Step 6: If it is FALSE then set head = temp → next, and delete temp.

Deleting from End of the list

We can use the following steps to delete a node from end of the single linked list...
Step 1: Check whether list is Empty (head == NULL)
Step 2: If it is Empty then, display 'List is Empty!!! Deletion is not possible' and
terminate the function.

COMPUTER PROGRAMMING-II UNIT-IV Page 6

 ANURAG GROUP OF INSTITUTIONS
(CVSR COLLEGE OF ENGINEERING)

Step 3: If it is Not Empty then, define two Node pointers 'temp1' and 'temp2' and
initialize 'temp1' with head.
Step 4: Check whether list has only one Node (temp1 → next == NULL)
Step 5: If it is TRUE. Then, set head = NULL and delete temp1. And terminate the
function. (Setting Empty list condition)
Step 6: If it is FALSE. Then, set 'temp2 = temp1 ' and move temp1 to its next node.
Repeat the same until it reaches to the last node in the list. (until temp1 →
next == NULL)
Step 7: Finally, Set temp2 → next = NULL and delete temp1.
Deleting a Specific Node from the list
We can use the following steps to delete a specific node from the single linked list...
Step 1: Check whether list is Empty (head == NULL)
Step 2: If it is Empty then, display 'List is Empty!!! Deletion is not possible' and
terminate the function.
Step 3: If it is Not Empty then, define two Node pointers 'temp1' and 'temp2' and
initialize 'temp1' with head.
Step 4: Keep moving the temp1 until it reaches to the exact node to be deleted or to the
last node. And every time set 'temp2 = temp1' before moving the 'temp1' to its next
node.
Step 5: If it is reached to the last node then display 'Given node not found in the list!
Deletion not possible!!!'. And terminate the function.
Step 6: If it is reached to the exact node which we want to delete, then check whether list
is having only one node or not
Step 7: If list has only one node and that is the node to be deleted, then
set head = NULL and delete temp1 (free(temp1)).
Step 8: If list contains multiple nodes, then check whether temp1 is the first node in the
list (temp1 == head).
Step 9: If temp1 is the first node then move the head to the next node (head = head →
next) and delete temp1.
Step 10: If temp1 is not first node then check whether it is last node in the list (temp1 →
next == NULL).
Step 11: If temp1 is last node then set temp2 → next = NULL and
delete temp1 (free(temp1)).
Step 12: If temp1 is not first node and not last node then set temp2 → next = temp1 →
next and delete temp1 (free(temp1)).
Displaying a Single Linked List
We can use the following steps to display the elements of a single linked list...
Step 1: Check whether list is Empty (head == NULL)
Step 2: If it is Empty then, display 'List is Empty!!!' and terminate the function.
Step 3: If it is Not Empty then, define a Node pointer 'temp' and initialize with head.
Step 4: Keep displaying temp → data with an arrow (--->) until temp reaches to the last
node
Step 5: Finally display temp → data with arrow pointing to NULL (temp → data --->
NULL).

COMPUTER PROGRAMMING-II UNIT-IV Page 7

 ANURAG GROUP OF INSTITUTIONS
(CVSR COLLEGE OF ENGINEERING)

Program to implent single linked list:

#include<stdio.h>
#include<stdlib.h>
void create(int);
void display();
void insertend(int);
void insertpos(int,int);
void insertbegin(int);
void deletebegin();
void deleteend();

struct node
{
int info;
struct node *link;
}*start=NULL;

void create(int no)

{
int i,data;
struct node *temp;
temp=(struct node*)malloc(sizeof(structnode));
for(i=0;i<no;i++)
{
if(start==NULL)
{
printf("enter data for node %d\n",i);
scanf("%d",&data);
temp->info=data;
temp->link=NULL;
start=temp;
}
else
{
printf("enter data for node %d\n",i);
scanf("%d",&data);
insertend(data);
}
}
}

COMPUTER PROGRAMMING-II UNIT-IV Page 8

 ANURAG GROUP OF INSTITUTIONS
(CVSR COLLEGE OF ENGINEERING)

void insertpos(int data,int pos)

{
int i;
struct node *temp,*p;
p=start;
for(i=0;i<pos;i++)
{
if(p==NULL)
{
printf("invalid position\n");
return;
}
p=p->link;
}
if(p->link==NULL)
{
insertend(data);
}
else
{
temp=(struct node*)malloc(sizeof(struct node));
temp->info=data;
temp->link=p->link;
p->link=temp;
}
}

void display()
{
struct node *p;
p=start;
if(start==NULL)
{
printf("list is empty\n");
return;
}
printf("linked list\n");
while(p!=NULL)
{
printf("%d ",p->info);
p=p->link;
}
printf("end of list\n");
}

COMPUTER PROGRAMMING-II UNIT-IV Page 9

 ANURAG GROUP OF INSTITUTIONS
(CVSR COLLEGE OF ENGINEERING)

void insertbegin(int data)

{
struct node *temp;
temp=(struct node*)malloc(sizeof(struct node));
temp->info=data;
temp->link=start;
start=temp;
}
void insertend(int data)
{
struct node *p,*temp;
p=start;
while(1)
{
if(p->link!=NULL)
p=p->link;
else
break;
}
temp=(struct node*)malloc(sizeof(struct node));
temp->info=data;
temp->link=NULL;
p->link=temp;
}
void deletebegin()
{
if(start==NULL)
printf("\n list is empty\n");
else
{
struct node *p=start;
if(start->link==NULL)
{
start=NULL;
free(p);
}
else
{
start=p->link;
free(p);
printf("\n node deleted\n");
}
}
}

COMPUTER PROGRAMMING-II UNIT-IV Page 10

 ANURAG GROUP OF INSTITUTIONS
(CVSR COLLEGE OF ENGINEERING)

void deleteend()
{
if(start==NULL)
printf("\n list empty");
else
{
struct node *p,*temp=start;
if(start->link==NULL)
start==NULL;
else
{
while(temp->link!=NULL)
{
p=temp;
temp=temp->link;
}
p->link=NULL;
}
free(temp);
printf("\n node deleted ");
}
}

void main()
{
int choice,data,pos,no;
while(1)
{
Printf(“\n *********Linked list operations Menu:::************”);
printf(" \n [Link] list \[Link] list \[Link] begining \[Link] end \n [Link] at
position \n [Link] node at begining \[Link] node at end \n [Link] ");
printf(" \n enter choice\n");
scanf("%d",&choice);
switch(choice)
{
case 1: printf("enter no of nodes\n");
scanf("%d",&no);
create(no);break;
case 2: dislpay();break;
case 3: printf("enter data\n");
scanf("%d",&data);
insertbegin(data);break;
case 4: printf("enter data for node\n");
scanf("%d",&data);

COMPUTER PROGRAMMING-II UNIT-IV Page 11

 ANURAG GROUP OF INSTITUTIONS
(CVSR COLLEGE OF ENGINEERING)

insertend(data);break;
case 5: printf("enter data\n");
scanf("%d",&data);
printf("enter position\n");
scanf("%d",&pos);
insertpos(data,pos);break;
case 6: deletebegin();break;
case 7: deleteend();break;
case 8: exit(0);break;
}
}
}
A double linked list is one in which all nodes are linked together by multiple links which
helps in accessing both the successor node (next node) and predecessor node (previous
node) from any arbitrary node within the list. Therefore each node in a double linked list
has two link fields (pointers) to point to the left node (previous) and the right node (next).
This helps to traverse in forward direction and backward direction.
A circular linked list is one, which has no beginning and no end. A single linked list
can be made a circular linked list by simply storing address of the very first node in the
link field of the last node.
A circular double linked list is one, which has both the successor pointer and
predecessor pointer in the circular manner.
In our syllabus we have only Single linked list concept, remaining lists we discuss
further.
Comparison between array and linked list:

ARRAY LINKED LIST

Size of an array is fixed Size of a list is not fixed

Memory is allocated from stack Memory is allocated from heap

It is necessary to specify the number of elements It is not necessary to specify the number of
during declaration (i.e., during compile time). elements during declaration (i.e., memory is
allocated during run time).
It occupies less memory than a linked list for the It occupies more memory.
same number of elements.
Inserting new elements at the front is potentially Inserting a new element at any position can
expensive because existing elements need to be be carried out easily.
shifted over to make room.
Deleting an element from an array is not Deleting an element is possible.
possible.

COMPUTER PROGRAMMING-II UNIT-IV Page 12

 ANURAG GROUP OF INSTITUTIONS
(CVSR COLLEGE OF ENGINEERING)

STACK:
A stack is a list of elements in which an element may be inserted or deleted only at one
end, called the top of the stack. Stacks are sometimes known as LIFO (last in, first out) order. As
the items can be added or removed only from the top i.e. called top of the stack or stack pointer.

REPRESENTATION OF STACK:

Two standard methods of representing a stack are in terms of an array and a

pointer linked list which is a away of representation using pointer.
The figure below illustrates an array implementation of a stack of 5 elements B,
A, M, K, S.

The Stack pointer is pointing to the top of the stack (called the top of the stack).
The size of the array is fixed at the time of its declaration itself.

a stack is used for the following two primary operations −

push() − Pushing (storing) an element on the stack.
pop() − Removing (accessing) an element from the stack.

A stack can be implemented using array as follows...

A stack data structure can be implemented using one dimensional array. But stack
implemented using array, can store only fixed number of data values. This
implementation is very simple, just define a one dimensional array of specific size and
insert or delete the values into that array by using LIFO principle with the help of a
variable 'top'. Initially top is set to -1. Whenever we want to insert a value into the stack,
increment the top value by one and then insert. Whenever we want to delete a value from
the stack, then delete the top value and decrement the top value by one.

Before implementing actual operations, first follow the below steps to create an
empty stack.
Step 1: Include all the header files which are used in the program and define a
constant 'SIZE' with specific value.
Step 2: Declare all the functions used in stack implementation.
Step 3: Create a one dimensional array with fixed size (int stack[SIZE])

COMPUTER PROGRAMMING-II UNIT-IV Page 13

 ANURAG GROUP OF INSTITUTIONS
(CVSR COLLEGE OF ENGINEERING)

Step 4: Define a integer variable 'top' and initialize with '-1'. (int top = -1)
Step 5: In main method display menu with list of operations and make suitable function
calls to perform operation selected by the user on the stack.

push(value) - Inserting value into the stack

In a stack, push() is a function used to insert an element into the stack. In a stack, the new
element is always inserted at top position. Push function takes one integer value as
parameter and inserts that value into the stack. We can use the following steps to push an
element on to the stack...
Step 1: Check whether stack is FULL. (top == SIZE-1)
Step 2: If it is FULL, then display "Stack is FULL!!! Insertion is not possible!!!" and
terminate the function.
Step 3: If it is NOT FULL, then increment top value by one (top++) and set stack[top]
to value (stack[top] = value).

pop() - Delete a value from the Stack

In a stack, pop() is a function used to delete an element from the stack. In a stack, the
element is always deleted from top position. Pop function does not take any value as
parameter. We can use the following steps to pop an element from the stack...
Step 1: Check whether stack is EMPTY. (top == -1)
Step 2: If it is EMPTY, then display "Stack is EMPTY!!! Deletion is not
possible!!!" and terminate the function.
Step 3: If it is NOT EMPTY, then delete stack[top] and decrement top value by one
(top--).

display() - Displays the elements of a Stack

We can use the following steps to display the elements of a stack...
Step 1: Check whether stack is EMPTY. (top == -1)
Step 2: If it is EMPTY, then display "Stack is EMPTY!!!" and terminate the function.
Step 3: If it is NOT EMPTY, then define a variable 'i' and initialize with top.
Display stack[i] value and decrement i value by one (i--).
Step 3: Repeat above step until i value becomes '0'.

Program to implement stack operations

#include<stdio.h>
#include<conio.h>
#define SIZE 5
void push(int);
void pop();
void display();
int stack[SIZE], top = -1;

COMPUTER PROGRAMMING-II UNIT-IV Page 14

 ANURAG GROUP OF INSTITUTIONS
(CVSR COLLEGE OF ENGINEERING)

void main()
{
int value, choice;
while(1)
{
printf("\n\n***** STACK OPERATIONS MENU USING ARRAYS *****\n");
printf("\n1. Push\n2. Pop\n3. Display\n4. Exit");
printf("\nEnter your choice: ");
scanf("%d",&choice);
switch(choice)
{
case 1: printf("Enter the value to be insert: ");
scanf("%d",&value);
push(value);break;
case 2: pop(); break;
case 3: display(); break;
case 4: exit(0);
default: printf("\nWrong selection!!! Try again!!!");
}
}
}

void push(int value)

{
if(top == SIZE-1)
printf("\nStack is Full!!! Insertion is not possible!!!");
else
{
top++;
stack[top] = value;
printf("\nInsertion success!!!");
}
}

void pop()
{
if(top == -1)
printf("\nStack is Empty!!! Deletion is not possible!!!");
else
{
printf("\nDeleted : %d", stack[top]);
top--;
}
}

COMPUTER PROGRAMMING-II UNIT-IV Page 15

 ANURAG GROUP OF INSTITUTIONS
(CVSR COLLEGE OF ENGINEERING)

void display()
{
if(top == -1)
printf("\nStack is Empty!!!");
else
{
int i;
printf("\nStack elements are:\n");
for(i=top; i>=0; i--)
printf("%d\n",stack[i]);
}
}

STACK IMPLEMENTATION BY LINKED LIST:

The major problem with the stack implemented using array is, it works only for fixed
number of data values. That means the amount of data must be specified at the beginning
of the implementation itself. Stack implemented using array is not suitable, when we
don't know the size of data which we are going to use. A stack data structure can be
implemented by using linked list data structure. The stack implemented using linked list
can work for unlimited number of values. That means, stack implemented using linked
list works for variable size of data. So, there is no need to fix the size at the beginning of
the implementation. The Stack implemented using linked list can organize as many data
values as we want.

COMPUTER PROGRAMMING-II UNIT-IV Page 16

 ANURAG GROUP OF INSTITUTIONS
(CVSR COLLEGE OF ENGINEERING)

In linked list implementation of a stack, every new element is inserted as 'top' element.
That means every newly inserted element is pointed by 'top'. Whenever we want to
remove an element from the stack, simply remove the node which is pointed by 'top' by
moving 'top' to its next node in the list. The next field of the first element must be
always NULL.
Example

In above example, the last inserted node is 99 and the first inserted node is 25. The order
of elements inserted is 25, 32,50 and 99.
Operations
To implement stack using linked list, we need to set the following things before
implementing actual operations.
Step 1: Include all the header files which are used in the program. And declare all
the user defined functions.
Step 2: Define a 'Node' structure with two members data and next.
Step 3: Define a Node pointer 'top' and set it to NULL.
Step 4: Implement the main method by displaying Menu with list of operations and
make suitable function calls in the main method.

push(value) - Inserting an element into the Stack

We can use the following steps to insert a new node into the stack...
Step 1: Create a newNode with given value.
Step 2: Check whether stack is Empty (top == NULL)
Step 3: If it is Empty, then set newNode → next = NULL.
Step 4: If it is Not Empty, then set newNode → next = top.
Step 5: Finally, set top = newNode.

COMPUTER PROGRAMMING-II UNIT-IV Page 17

 ANURAG GROUP OF INSTITUTIONS
(CVSR COLLEGE OF ENGINEERING)

pop() - Deleting an Element from a Stack

We can use the following steps to delete a node from the stack...
Step 1: Check whether stack is Empty (top == NULL).
Step 2: If it is Empty, then display "Stack is Empty!!! Deletion is not possible!!!" and
terminate the function
Step 3: If it is Not Empty, then define a Node pointer 'temp' and set it to 'top'.
Step 4: Then set 'top = top → next'.
Step 7: Finally, delete 'temp' (free(temp)).

display() - Displaying stack of elements

We can use the following steps to display the elements (nodes) of a stack...
Step 1: Check whether stack is Empty (top == NULL).
Step 2: If it is Empty, then display 'Stack is Empty!!!' and terminate the function.
Step 3: If it is Not Empty, then define a Node pointer 'temp' and initialize with top.
Step 4: Display 'temp → data --->' and move it to the next node. Repeat the same
until temp reaches to the first node in the stack (temp → next != NULL).
Step 4: Finally! Display 'temp → data ---> NULL'.

Stack implementation by using linked list

#include<stdio.h>
struct node
{
int data;
struct node *link;
}*top = NULL;

void push(int);
void pop();
void display();

void main()
{
int choice, value;
printf("\n:: Stack using Linked List ::\n");
while(1)
{
printf("\n****** MENU ******\n");
printf("1. Push\n2. Pop\n3. Display\n4. Exit\n");
printf("Enter your choice: ");
scanf("%d",&choice);

COMPUTER PROGRAMMING-II UNIT-IV Page 18

 ANURAG GROUP OF INSTITUTIONS
(CVSR COLLEGE OF ENGINEERING)

switch(choice){
case 1: printf("Enter the value to be insert: ");
scanf("%d", &value);
push(value); break;
case 2: pop(); break;
case 3: display(); break;
case 4: exit(0);
default: printf("\nWrong selection!!! Please try again!!!\n");
}
}
}

void push(int value)

{
struct node *p;
p = (struct node*)malloc(sizeof(struct node));
p->data = value;
if(top == NULL)
p->link= NULL;
else
p->link= top;
top = p;
printf("\nInsertion is Success!!!\n");
}

void pop()
{
if(top == NULL)
printf("\nStack is Empty!!!\n");
else
{
struct node *temp= top;
printf("\nDeleted element: %d", temp->data);
top = temp->link;
free(temp);
}
}

void display()
{
if(top == NULL)
printf("\nStack is Empty!!!\n");

COMPUTER PROGRAMMING-II UNIT-IV Page 19

 ANURAG GROUP OF INSTITUTIONS
(CVSR COLLEGE OF ENGINEERING)

else
{
struct node *temp = top;
while(temp->link != NULL)
{
printf("%d--->",temp->data);
temp = temp -> link;
}
printf("%d--->NULL",temp->data);
}
}

COMPUTER PROGRAMMING-II UNIT-IV Page 20

 ANURAG GROUP OF INSTITUTIONS
(CVSR COLLEGE OF ENGINEERING)

Application of Stack:
1. Expression Evolution
2. Expression conversion
 Infix to Postfix
 Infix to Prefix
 Postfix to Infix
 Prefix to Infix
3. Parsing
4. Simulation of recursion
5. Fuction call

QUEUES:
A queue is an ordered collection of elements, where the elements can be inserted
at one end and deleted from another end. It works on the principle called First–In–First–
Out (FIFO).
The information we retrieve from a queue comes in the same order that it was
placed on the queue. The examples of queues are checkout line at supermarket cash
register, line of cars waiting to proceed in some fixed direction at an intersection of
streets. The queue can be implemented using arrays and linked lists.

COMPUTER PROGRAMMING-II UNIT-IV Page 21

 ANURAG GROUP OF INSTITUTIONS
(CVSR COLLEGE OF ENGINEERING)

OPERATIONS ON QUEUES:
Insertion: The operation of adding new items on the queue occurs only at one end of
the queue called the rear end.
Deletion: The operation of removing items of the queue occurs at the other end called
the front end.

Queue data structure using array can be implemented as follows...

Before we implement actual operations, first follow the below steps to create an empty
queue.
Step 1: Include all the header files which are used in the program and define a
constant 'SIZE' with specific value.
Step 2: Declare all the user defined functions which are used in queue implementation.
Step 3: Create a one dimensional array with above defined SIZE (int queue[SIZE])
Step 4: Define two integer variables 'front' and 'rear' and initialize both with '-1'. (int
front = -1, rear = -1)
Step 5: Then implement main method by displaying menu of operations list and make
suitable function calls to perform operation selected by the user on queue.

enQueue(value) - Inserting value into the queue

In a queue data structure, enQueue() is a function used to insert a new element into the
queue. In a queue, the new element is always inserted at rear position. The enQueue()
function takes one integer value as parameter and inserts that value into the queue. We
can use the following steps to insert an element into the queue...
Step 1: Check whether queue is FULL. (rear == SIZE-1)
Step 2: If it is FULL, then display "Queue is FULL!!! Insertion is not possible!!!" and
terminate the function.
Step 3: If it is NOT FULL, then increment rear value by one (rear++) and
set queue[rear] = value.

deQueue() - Deleting a value from the Queue

In a queue data structure, deQueue() is a function used to delete an element from the
queue. In a queue, the element is always deleted from front position. The deQueue()
function does not take any value as parameter. We can use the following steps to delete
an element from the queue...
Step 1: Check whether queue is EMPTY. (front == rear)
Step 2: If it is EMPTY, then display "Queue is EMPTY!!! Deletion is not
possible!!!" and terminate the function.
Step 3: If it is NOT EMPTY, then increment the front value by one (front ++). Then
display queue[front] as deleted element. Then check whether both front and rear are
equal (front == rear),
if it TRUE, then set both front and rear to '-1' (front = rear = -1).

COMPUTER PROGRAMMING-II UNIT-IV Page 22

 ANURAG GROUP OF INSTITUTIONS
(CVSR COLLEGE OF ENGINEERING)

display() - Displays the elements of a Queue

We can use the following steps to display the elements of a queue...
Step 1: Check whether queue is EMPTY. (front == rear)
Step 2: If it is EMPTY, then display "Queue is EMPTY!!!" and terminate the function.
Step 3: If it is NOT EMPTY, then define an integer variable 'i' and set 'i = front+1'.
Step 3: Display 'queue[i]' value and increment 'i' value by one (i++). Repeat the same
until 'i' value is equal to rear (i <= rear).

QUEUE IMPLEMENTATION BY USING ARRAYS

#include<stdio.h>
#include<conio.h>
#define SIZE 10

void enQueue(int); // INSERT FUNCTION

void deQueue(); // DELETE FUNCTION
void display();
int queue[SIZE], front = -1, rear = -1;

void main()
{
int value, choice;
clrscr();
while(1)
{
printf("\n\n*****QUEUE OPERATIONS MENU BY USING ARRAYS *****\n");
printf("1. Insertion\n2. Deletion\n3. Display\n4. Exit");
printf("\nEnter your choice: ");
scanf("%d",&choice);
switch(choice)
{
case 1: printf("Enter the value to be insert: ");
scanf("%d",&value);
enQueue(value);
break;
case 2: deQueue();
break;
case 3: display();
break;
case 4: exit(0);
default: printf("\nWrong selection!!! Try again!!!");
}
}
}

COMPUTER PROGRAMMING-II UNIT-IV Page 23

 ANURAG GROUP OF INSTITUTIONS
(CVSR COLLEGE OF ENGINEERING)

void enQueue(int value)

{
if(rear == SIZE-1)
printf("\nQueue is Full!!! Insertion is not possible!!!");
else
{
if(front == -1)
front = 0;
rear++;
queue[rear] = value;
printf("\nInsertion success!!!");
}
}

void deQueue()
{
if(front == rear)
printf("\nQueue is Empty!!! Deletion is not possible!!!");
else
{
printf("\nDeleted : %d", queue[front]);
front++;
if(front == rear)
front = rear = -1;
}
}

void display()
{
if(rear == -1)
printf("\nQueue is Empty!!!");
else
{
int i;
printf("\nQueue elements are:\n");
for(i=front; i<=rear; i++)
printf("%d\t",queue[i]);
}
}

COMPUTER PROGRAMMING-II UNIT-IV Page 24

 ANURAG GROUP OF INSTITUTIONS
(CVSR COLLEGE OF ENGINEERING)

Queue implementation by using Linked List:

In linked list implementation of a queue, the last inserted node is always pointed by 'rear'
and the first node is always pointed by 'front'.
Example

In above example, the last inserted node is 50 and it is pointed by 'rear' and the first
inserted node is 10 and it is pointed by 'front'. The order of elements inserted is 10, 15,
22 and 50.
Operations
To implement queue using linked list, we need to set the following things before
implementing actual operations.
Step 1: Include all the header files which are used in the program. And declare all
the user defined functions.
Step 2: Define a 'Node' structure with two members data and next.
Step 3: Define two Node pointers 'front' and 'rear' and set both to NULL.
Step 4: Implement the main method by displaying Menu of list of operations and make
suitable function calls in the main method to perform user selected operation.

COMPUTER PROGRAMMING-II UNIT-IV Page 25

 ANURAG GROUP OF INSTITUTIONS
(CVSR COLLEGE OF ENGINEERING)

enQueue(value) - Inserting an element into the Queue

We can use the following steps to insert a new node into the queue...
Step 1: Create a newNode with given value and set 'newNode → next' to NULL.
Step 2: Check whether queue is Empty (rear == NULL)
Step 3: If it is Empty then, set front = newNode and rear = newNode.
Step 4: If it is Not Empty then, set rear → next = newNode and rear = newNode.

deQueue() - Deleting an Element from Queue

We can use the following steps to delete a node from the queue...
Step 1: Check whether queue is Empty (front == NULL).
Step 2: If it is Empty, then display "Queue is Empty!!! Deletion is not possible!!!" and
terminate from the function
Step 3: If it is Not Empty then, define a Node pointer 'temp' and set it to 'front'.
Step 4: Then set 'front = front → next' and delete 'temp' (free(temp)).

display() - Displaying the elements of Queue

We can use the following steps to display the elements (nodes) of a queue...
Step 1: Check whether queue is Empty (front == NULL).
Step 2: If it is Empty then, display 'Queue is Empty!!!' and terminate the function.
Step 3: If it is Not Empty then, define a Node pointer 'temp' and initialize with front.
Step 4: Display 'temp → data --->' and move it to the next node. Repeat the same until
'temp' reaches to 'rear' (temp → next != NULL).
Step 4: Finally! Display 'temp → data ---> NULL'.

Queue implementation by using linked list

#include<stdio.h>
struct node
{
int data;
struct node *link;
}*front = NULL, *rear = NULL;

void insert(int);
void delete();
void display();

COMPUTER PROGRAMMING-II UNIT-IV Page 26

 ANURAG GROUP OF INSTITUTIONS
(CVSR COLLEGE OF ENGINEERING)

void main()
{
int choice, value;
printf("\n:: Queue Implementation using Linked List ::\n");
while(1)
{
printf("\n****** MENU ******\n");
printf("1. Insert\n2. Delete\n3. Display\n4. Exit\n");
printf("Enter your choice: ");
scanf("%d",&choice);
switch(choice){
case 1: printf("Enter the value to be insert: ");
scanf("%d", &value);
insert(value); break;
case 2: delete(); break;
case 3: display(); break;
case 4: exit(0);
default: printf("\nWrong selection!!! Please try again!!!\n");
}
}
}

void insert(int value)

{
struct node *p;
p = (struct node*)malloc(sizeof(struct node));
p->data = value;
p -> link = NULL;
if(front == NULL)
front = rear = p;
else
{
rear -> link= p;
rear = p;
}
printf("\nInsertion is Success!!!\n");
}

void delete()
{
if(front == NULL)
printf("\nQueue is Empty!!!\n");

COMPUTER PROGRAMMING-II UNIT-IV Page 27

 ANURAG GROUP OF INSTITUTIONS
(CVSR COLLEGE OF ENGINEERING)

else
{
struct node *temp = front;
front = front -> link;
printf("\nDeleted element: %d\n", temp->data);
free(temp);
}
}
void display()
{
if(front == NULL)
printf("\nQueue is Empty!!!\n");
else{
struct node *temp = front;
while(temp->link != NULL){
printf("%d--->",temp->data);
temp = temp -> link;
}
printf("%d--->NULL\n",temp->data);
}
}

COMPUTER PROGRAMMING-II UNIT-IV Page 28

 ANURAG GROUP OF INSTITUTIONS
(CVSR COLLEGE OF ENGINEERING)

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

******** I WISH YOU ALL THE BEST********

COMPUTER PROGRAMMING-II UNIT-IV Page 29