Data Structures Unit - I

DATA STRUCTURES
Basically data are represented by data values held temporarily within a program’s data area or recorded
permanently on a file. So, the simple data is represented by data type. Data structure is often confused with
data types. Data type is a collection of finite set of permitted values, and a set operations on those values,
whereas, Data structure is a study about the organizing the related data to enable us to work efficiently with
data, exploring the relationships within the data. A data type can be defined as follows.
Data type = Permitted Data Values + Operations
Often the different data values are related to each other. To enable programs to make use of these relationships,
these data values must be in an organized form. So the organized collection of data is called a data structure.
Data Structure = Organized Data + Allowed Operations
Definition:
Data may be organized in many different ways; the logical or mathematical model of a particular
organization of data is called a data structure. The data structure can also be defined as methods to store the
information in a computer.
Study of Data Structures study covers the following
» Amount of memory require to store
» Amount of time require to process
» Representation of data in memory
» Operations performs on data
Need of Data Structures:
As applications are getting complex and data rich, common problems that applications face now-a-days are
» Data Search: As data grows, search will become slower.
» Processor speed: Processor speed although being very high, falls limited if the data grows to billion
records.
» Multiple requests: As thousands of users can search data simultaneously on a web server, even the fast
server fails while searching the data.
Advantages of Data Structures
» Efficiency: The efficiency of any program depends upon the chosen data structure and thus, the
efficiency of a particular program depends upon the specific selected data structure.
» Reusability: Data structures are reusable, i.e., once we have implemented a particular data structure, we
can use it at any other place. Implementation of data structures can be compiled into libraries which can
be used by different clients.
» Abstraction: Data Structure also provides an Abstraction feature which helps a user to use data structure
through an interface without knowing the details of implementation.
Applications of Data Structures:
» Ticket booking applications like book my show, abhibus etc., uses a two-dimensional array
» Navigation of Webpages in a Web Browser uses Stack Data structure
» Tokens in a Bank uses Queue Data Structure.
» Songs in a play list uses Single or Double Linked list or Circular Linked List
» File Explorer of Computer or Mobile uses Tree Data Structure.
» Navigation Systems like Google maps uses Graph data structure to find the path between two cities.
Department of Computer Science, SSBN Degree College, ATP 1
 Data Structures Unit - I

Classification of Data Structures:

Data Structures

Primitive Non- Primitive

Data Structures Data Structures

int float char

» Primitive data structure:

The primitive data structures are primitive data types. The int, char, float, double, and pointer are the
primitive data structures that can hold a single value.
» Non-Primitive Data structure:
The non-primitive data structure is divided into two types Linear and Non-linear data structures
» Linear Data structures:
A Linear data structure have data elements arranged in sequential manner and each member
element is connected to its previous and next element. This connection helps to traverse a linear data
structure in a single level and in single run.
Examples of linear data structures are Arrays, Stacks, Queues, Linked lists etc.,
» Non-Linear Data structures:
A non-linear data structure has no set sequence of connecting all its elements and each element
can have multiple paths to connect to other elements. Such data structures are not easy to implement
but are more efficient in utilizing computer memory.
Examples of non-linear data structures are Tree, Graphs etc.
Representing Linear Data Structures:
There are two basic ways of representing such linear structures. In the first case the linear relationship
between the elements represented by means of sequential memory location. This is also called as Array
representation.

Department of Computer Science, SSBN Degree College, ATP 2

 Data Structures Unit - I

In second case the linear relationship b/w the elements represented by means of pointers or links. These are
linked lists.

Operations: The operations performed on any linear structure are

» Traversal – Accessing or processing (visiting) each element in the list
» Insertion – Adding a new element in the list
» Deletion – Removing an element from the list
» Search – finding the location of the element with a given value in the list
» Sorting – Rearranging the elements of a list in a logical sequence
» Merging – Combining two lists into a single list
Arrays:
A linear array is the list of a finite number of data elements of the same type. The elements of the array
are reference respectively by an index. These are stored respectively in successive memory locations.
The number of elements in an array is called the length of an array. This is also known as the size of an
array. The elements of an array a may be denoted as A[1]A[2]……A[n].
Note: The number ‘k’ in A[k] is called as subscript or an index. Let A be an array and name of A denote the
address of the first element in A. then the address of any element a[k] can be calculated as address of A[k] =
base address of A + w(k-1). Where ‘w’ is the number of words per memory cell.
The array of elements are stored in sequential memory cells. So, the computer keeps track of the address
of the first element of the array called the base address.
Applications of Arrays:
» Contact lists on mobile phones.
» Matrices use arrays which are used in different fields like image processing, computer graphics, and
many more.
» Arrays are used in online ticket booking portals.
» Pages of book.
» IoT applications use arrays as we know that the number of values in an array will remain constant, and
also that the accessing will be faster.
» It is also utilized in speech processing, where each speech signal is represented by an array.
» The viewing screen of any desktop/laptop is also a multidimensional array of pixels.

Department of Computer Science, SSBN Degree College, ATP 3

 Data Structures Unit - I

Write a program to illustrate Array Data structure.

//Program to illustrate Array Data Structure
import java.util.*;
class MyArray
{
int a[];
int nElems;
MyArray(int size)
{
a=new int [size];
nElems=0;
}
public void insert(int item)
{
if(nElems>=a.length)
{
System.out.println("Array is full");
return;
}
a[nElems]=item;
nElems++;
}
public void display()
{
System.out.print("A:[");
for(int i=0;i<nElems;i++)
{
System.out.print(a[i]+" ");
}
System.out.println("]");
}
public int search(int key)
{
for(int i=0;i<nElems;i++)
{
if(a[i]==key)
return i;
}
return -1;
}
}

Department of Computer Science, SSBN Degree College, ATP 4

 Data Structures Unit - I

public class ArrayDemo

{
public static void main(String[] args)
{
Scanner sc=new Scanner(System.in);
System.out.println("Enter how many elements are there:");
int n=sc.nextInt();
MyArray A = new MyArray(n);
while(true)
{
System.out.println("********** MENU **********");
System.out.println("1.Insert\n2.Display\n3.Search\n4.Exit");
System.out.println("Please enter your option:");
int option =sc.nextInt();
switch(option)
{
case 1:
System.out.println("Enter an element into the Array");
int item=sc.nextInt();
A.insert(item);
break;
case 2:
A.display();
break;
case 3:
System.out.println("Enter an element to search:");
int key=sc.nextInt();
int pos=A.search(key);
if(pos==-1)
System.out.println(key+" is not found");
else
System.out.println(key+" is found at location :"+pos);
break;
case 4:
System.exit(0);
}
}
}
}

Department of Computer Science, SSBN Degree College, ATP 5

 Data Structures Unit - I

STACK
A stack is an ordered collection of items into which new items may be inserted and from which items
may be deleted at one end, called the top of the stack.
(OR)
The stack is the list of elements in which an element may be inserted or deleted only at the end called
only the top of the stack. This implies that the elements are removed from the stack in the reverse order of
insertion. Sometimes these are also known as LIFO lists. The stack work in the principle of last-in first-out [LIFO].
Unlike that of the array, the definition of array itself provides for the insertion and deletion of items. So,
the stack can be considered as a dynamic, constantly changing object.
Examples of such a data structure are a stack of books, bolls in a tube etc. here an item can be remove or inserted
only from the top of any of the stacks. This implies that the last item to be added to the stack is the first item to
be removed.

On a stack only two operations are performed they are insertion and deletion. These are known as push and
pop respectively.
Primitive Operations:
The two changes, which can be made to a stack, are given special name. When an item is added to a
stack, it is pushed onto the stack, and when an item is removed, it is popped from the stack.
» Push: Add an item to a stack, moving the stack pointer (top) up to accommodate the new item.
» Pop: Removes the most recently pushed item from the stack, moving the stack pointer (top) down.
To use a stack efficiently we need to check status of stack as well. For the same purpose, the following
functionality is added to stacks −
» peek − get the top data element of the stack, without removing it.
» isFull − check if stack is full.
» isEmpty − check if stack is empty.
Example:
The below figure shows the general model that there is some element that is at the top of the stack, and
it is the only element that is visible.

Push Pop
G Top
F Top F F
E E E Top
D D D
C C C
B B B
A A A

Department of Computer Science, SSBN Degree College, ATP 6

 Data Structures Unit - I

In this example, a stack contains the elements A, B, C, D, E, and F where F is on the top of the stack. When a new
element G is added (push), it is placed on the top of the stack and the top is now pointing to the element G.
When an item is deleted (pop) form the stack, that deleted element is G. This is because the deletion can be
made only from the top.
Representation of stack:
Stacks may be represented inside the memory in two ways.
1. Sequential Representation
2. Linked Representation
Sequential Representation:
A Stack can be represented using a single dimensional array. Here an integer variable is used called top
which hold the top elements position.
Linked Representation:
A Stack can be represented using single linked lists. Here a pointer is maintained called top used to point
the top most element.
Stack Exceptions
Stack Overflow:
Occurs when a push operation is performed on a Stack which is already full.
Condition: if top>=MAX-1 → stack overflow
Stack Underflow:
Occurs when a pop operation is performed on a empty Stack.
Condition: if top==-1 → stack underflow
Overflow, however, is not a condition that is applicable to a stack as an abstract data structure.
Abstractly, it is always possible to push an element onto a stack. A stack is just an ordered set, and there is no
limit to the number of elements that such a set can contain. The possibility of overflow is introduced when a
stack is implemented by an array with only a finite number of elements, thereby prohibiting the growth of the
stack beyond that number.
Implementing the Push & Pop operations:
Algorithms:
Push: This procedure inserts an element item to the top of the stack which is represented by an arrays & variable
top denoting the top element in the stack.
Push(S, Size, item)
Step 1: check for overflow condition
if top>= Size -1
Print ”Stack overflow”;
return;
Step 2: increment top
top=top+1
Step 3: insert the element
S[top]=item
Step 4: return

Department of Computer Science, SSBN Degree College, ATP 7

 Data Structures Unit - I

Pop: This procedure deletes the top element of the stack and assigns it to the variable item.
Pop(S,item)
Step 1: check for stack underflow
if(top==-1)
Print ”Stack underflow”
return
Step 2: assign top element to x
item=S[top];
Step 3: decrement top
top=top-1
Step 4: return
Stack as an abstract type:
class Stack
{
long stk[];
int top;
public Stack(int size)
{
stk=new long[size];
top=-1;
}
public boolean isFull()
{
return (top>=stk.length-1);
}
public boolean isEmpty()
{
return (top==-1);
}
public void push(long item)
{
if(isFull())
{
System.out.println("Stack is Full");
return;
}
stk[++top]=item;
}
public void pop()
{
if(isEmpty())
{
System.out.println("Stack is empty");
return;
}
long item=stk[top--];
System.out.println("Popped element from Stack is :"+item);
}
public void display()
{
System.out.print("Stack :[ ");
for(int i=top;i>=0;i--)
System.out.print(stk[i]+" ");
System.out.println("]");
}
}

Department of Computer Science, SSBN Degree College, ATP 8

 Data Structures Unit - I

Program: Write a program to implement Stack using Arrays

//Program to implement Stack operations using Arrays
//ProjName :- StackApp //ClassName :- StackApp
import java.util.*;
class MyStack
{
long stk[];
int top;
public MyStack(int size)
{
stk=new long[size];
top=-1;
}
public boolean isFull()
{
return (top>=stk.length-1);
}
public boolean isEmpty()
{
return (top==-1);
}
public void push(long item)
{
if(isFull())
{
System.out.println("Stack is Full");
return;
}
stk[++top]=item;
}
public void pop()
{
if(isEmpty())
{
System.out.println("Stack is empty");
return;
}
long item=stk[top--];
System.out.println("Popped element from Stack is :"+item);
}
public void display()
{
System.out.print("Stack :[ ");
for(int i=top;i>=0;i--)
System.out.print(stk[i]+" ");
System.out.println("]");
}
}

Department of Computer Science, SSBN Degree College, ATP 9

 Data Structures Unit - I
public class StackApp
{
public static void main(String args[])
{
Scanner s=new Scanner(System.in);
MyStack ST=new MyStack(5);
long item;
while(true)
{
System.out.println("********** MENU **********");
System.out.println("1. Push\n2. Pop\n3. Display\n4. Exit");
System.out.println("Please enter your option:");
int choice =s.nextInt();
switch(choice)
{
case 1:
System.out.println("Enter an element into the Stack:");
item=s.nextLong();
ST.push(item);
break;
case 2:
ST.pop();
break;
case 3:
ST.display();
break;
case 4:
System.exit(0);
default:
System.out.println("Wrong option");
}
}
}

Department of Computer Science, SSBN Degree College, ATP 10

 Data Structures Unit - I

Applications of Stack:
» Conversion of expressions.
» Evaluating expressions
» Implementing function calls
» Maintaining the UNDO list for an application
» Checking the nesting of parentheses in an expression
Postponed Decision: - This is one of the applications of stack. Stacks are frequently used to indicate the order
of processing of data when some steps in processing must be postponed until some other conditions are
fulfilled.

D top
C
B
main

This can be explained by taking a main program which calls B and that calls C, which is internally calling
D functions. In this situation while processing main A, we required to move to B which is required in A. Then B
places A on to a stack and begin execution of B while processing B if C is required we move to C after placing B
on to a stack above A. Similarly, we place C over B and start processing D.
After completing D we can process only C from the stack which calls B is on the top of the stock. Then
we take B and after completing B we can go to the main program A. here at each stage the stack automatically
maintained the order that is require to complete the processing.
Example: Infix, Postfix and Prefix
Basic Definitions & Examples:
An arithmetic expression can be represented in three forms. They are
Infix Postfix Prefix
• Infix Notation: In an expression if the relative position of the operator is between the two operands then it
is known as Infix notation.
Examples: A+B, A+(B*C), (A+B)*C, (A+B)*(C-D)
• Postfix Notation: In this notation the operator follows the two operands.
Examples: AB+, ABC*+, AB+C*, AB+CD-*
• Prefix Notation: In this notation the operator follows the two operator precedes the two operands.
Examples: +AB, +A*BC, *+ABC, *+AB-CD

Department of Computer Science, SSBN Degree College, ATP 11

 Data Structures Unit - I

Conversion from Infix to Postfix Expression:

• The advantage of infix notation is the ability to note at a glance the operands associated with a
particular operator.
• But, in postfix notation, the unambiguous form of the original expression can be gained without the
use of cumbersome parentheses. And also this notation is well suited in evaluating this expression
using computers because it uses the stack data structure. Manually, when we convert an infix
expression to postfix expression, we follow two rules they are
• Apply the rules of precedence, first we convert the portion of the expression that is evaluated first,
and then next and so on.
• During the conversion process, the operations with highest precedence are converted first and that
after a portion of the expression has been converted to postfix it is to be treated as a single operand.
Examples:
(i) A+ B*C (ii) (A+B)*C (iii) (A+B)*(C-D) (iv) ((A+B)*C-(D-E)^(F+G)
A+(BC*) (AB+)*C (AB+)*(CD-) (AB+)*c-(DE-)^(FG+)
A(BC*)+ (AB+)C* (AB+CD-)* AB+C*-DE-FG+^
ABC*+ AB+C* AB+CD-* AB+C*DE—FG+^
Conversion from Infix to Prefix Expression:
The conversion from infix to postfix is same as that of infix to postfix, the only difference is the operator
precedes the operands.
Examples:
(ii) A+ B*C (ii) (A+B)*C (iii) (A+B)*(C-D) (iv) ((A+B)*C-(D-E)^(F+G)
A+(*BC) (+AB)*C (+AB)*(-CD) (+AB)*C-(-DE)^(+FG)
+A(*BC) *(+AB)C *(+AB-CD) (*(+AB)C-(-DE))^(+FG)
+A*BC * + ABC *+AB-CD (*+ABC)-(-DE))^(+FG)
-(*+ABC)(-DE)^(+FG)
(-*+ABC-DE)^(+FG)
^-*+ABC-DE+FG
Converting an Expression from Infix to Postfix
In our previous discussion we mentioned that expressions within innermost parentheses must first be
converted to postfix so that they can then be treated as single operands. In this fashion parentheses can be
successively eliminated until the entire expression is converted. The last pair of parentheses to be opened within
a group of parentheses encloses the first expression within that group to be transformed. This last-in, first-out
behavior should immediately suggest the use of a stack.
Since precedence plays such an important role in transforming infix to postfix, let us assume the
existence of a function prcd(op1,op2), where op1 and op2 are characters representing operators.
Prcd(op1,op2) = TRUE if op1 has precedence over op2
Prcd(op1,op2) = FALSE if op2 has precedence over op1
For example, prcd(‘*’,’+’) and prcd(‘+’,’+’) are TRUE, whereas prcd(‘+’,’*’) is FALSE.

Department of Computer Science, SSBN Degree College, ATP 12

 Data Structures Unit - I

Algorithm to convert an infix expression to postfix without parenthesis::

opStack = the empty stack;
while (not end of input)
{
symb = next input character;
if (symbol is an operand)
add symbol to the postfix string
else
{
while(!opStack.isEmpty() && prcd(opStack.peek(), symbol))
{
topsymbol = opStack.pop();
add topsymbol to the postfix string;
} /* end while */
opStack.push(symbol);
} /* end else */
} /* end while */
/* output any remaining operators */
while (!opStack.isEmpty())
{
topsymbol = opStack.pop()
add topsymbol to the postfix string;
} /* end while */

Modification must be made to this algorithm to accommodate parentheses? When an opening parenthesis is
read, it must be pushed onto the stack. This can be done by establishing the convention that prcd(op,’(‘) equals
FALSE, for any operator symbol op other than a right parenthesis. In addition, we define prcd(‘(‘,op) to be FALSE
for any operator symbol op. This ensures that an operator symbol appearing after a left parenthesis is pushed
onto the stack.
When a closing parenthesis is read, all operators up to the first opening parenthesis must be popped
from the stack into the postfix string. This can be done by defining prcd(op, ‘)’) as TRUE for all operators op
other than a left parenthesis.
prcd(‘(‘,op) = FALSE for any operator op
prcd(op,’(‘) = FALSE for any operator op rather than ‘)’
prcd(op,’)’) = TRUE for any operator op other than ‘(‘
prcd(‘)’,op) = undefined for any operator op (an attempt to compare the two indicates an error)

Department of Computer Science, SSBN Degree College, ATP 13

 Data Structures Unit - I

Algorithm to convert an infix expression to postfix with parenthesis:

opStack = the empty stack;
while (not end of input)
{
symbol = next input character;
if (symbol is an operand)
add symbol to the postfix string
else
{
while(!opStack.isEmpty() && prcd(opStack.peek(), symbol))
{
topsymbol = opStack .pop();
add topsymbol to the postfix string;
}
if (opStack.isEmpty() || symbol != ‘)’ )
opStack .push(symbol);
else /* pop the open parenthesis and discard it */
topsymbol= opStack .pop();
}
}
/* output any remaining operators */
while (!opStack .isEmpty())
{
topsymbol = opStack.pop()
add topsymbol to the postfix string;
}
Example 1: A+B*C
The contents of symbol, the postfix string, and opStack are shown after scanning each symbol. OpStack
is shown with its top to the right.
Symbol Postfix string OpStack
1 A A
2 + A +
3 B AB +
4 * AB +*
5 C ABC +*
6 ABC* +
7 ABC*+
Lines 1, 3, and 5 correspond to the scanning of an operand; therefore the symbol (symbol) is immediately placed
on the postfix string. In line 2 an operator is scanned and the stack is found to be empty, and the operator is
therefore placed on the stack. In line 4 the precedence of the new symbol (*) is greater than the precedence of
the symbol on the top of the stack (+); therefore the new symbol is pushed onto the stack. In steps 6 and 7 the
input string is empty, and the stack is therefore popped and it contents are placed on the postfix string.

Department of Computer Science, SSBN Degree College, ATP 14

 Data Structures Unit - I

Example 2: (A + B) * C
Symb Postfix string OpStack
( (
A A (
+ A (+
B AB (+
) AB+
* AB+ *
C AB + C *
AB + C*
In this example, when the right parenthesis is encountered the stack is popped until a left parenthesis is
encountered, at which point both parentheses are discarded. By using parentheses to force an order of
precedence different than the default, the order of appearance of the operators in the postfix string is different
than in example 1.
Example 3: ((A – (B + C)) * D) $ (E + F)

Symb Postfix string OpStack

( (
( ((
A A ((
- A (( -
( A (( - (
B AB (( - (
+ AB (( - ( +
C ABC (( - ( +
) ABC + (( -
) ABC + - (
* ABC + - (*
D ABC + - D (*
) ABC + - D *
$ ABC + - D * $
( ABC + - D * $(
E ABC + - D * E $(
+ ABC + - D * E $(+
F ABC + - D *EF $(+
) ABC + - D *EF + $
ABC + -D*EF + $

Department of Computer Science, SSBN Degree College, ATP 15

 Data Structures Unit - I

Evaluating a Postfix Expression:

While executing the infix expression, computer first it converts the expression to postfix and then
evaluates. The easiest way to postfix expression is to use a stack.
Each operator in a postfix string refers to the previous two operands in the string. Each time when we
read an operand we push if on the stack. When we reach an operator, its operands will be the top two elements
on the stack. We can then pop these two elements to, perform the indicated operation on them, and push the
result on the stack so that if will be available for use as an operand of the next operator.
Algorithm
Opndstk = the empty stack;
/* scan the input string reading one */
/*element at a time into symb */
while (not end of input)
{
symbol=next input character;
if (symbol is an operand)
opndStack.push(symbol);
else
{
/* symbol is an operator */
opnd2 = opndStack.pop();
opnd1 = opndStack.pop();
value = result of applying symbol to opnd1 and opnd2;
opndStack.push(value);
} /* end else */
} /* end while */
return(opndStack.pop());
Why does the conversion algorithm seem so involved, whereas the evaluation algorithm seems so
simple? The answer is that the former converts from one order of precedence (governed by the prcd function
and the presence of parentheses) to the natural order (that is, the operation to be executed first appears first).
Because of the many combinations of elements at the top of the stack (if not empty) and possible incoming
symbol, a large number of statements, are necessary to ensure that every possibility is covered. In the latter
algorithm, on the other hand, the operators appear in precisely the order they are to be executed. For this
reason the operands can be stacked until an operator is found, at which point the operation is performed
immediately.

Evaluating postfix Expression: While executing the infix expression computer first it converts the expression to
postfix and then evaluates. The easiest way to evaluate postfix expression is to use a stack. When a number is
seen it is pushed on to the stack, when an operator is seen the top 2 elements are popped from the stack and
the operator is obtained and the result is pushed on to the stack.

Department of Computer Science, SSBN Degree College, ATP 16

 Data Structures Unit - I

Ex: Evaluation of the following postfix expression involves the following steps.
Postfix: 6 5 2 3 + 8* + 3 + *
Step 1: Since the first 4 are operands they are pushed on to stack 6->5->2->3->top,
Step 2: next + is read, so 3 and 2 are popped from the stack and added result 5 is placed or pushed into the stack
6 -> 5 -> 5 ->top;
Step 3: next 8 is pushed into the stack. Then stack is
6 -> 5 -> 5 -> 8 ->top;
step 4: now * is read, so 8 and 5 are popped and multiplied and the result 40 is pushed on to the stack.
Then the stack is…
6 -> 5 -> 40 ->top;
step 5:Again the operator + is read. So 40 & 5 are popped added and result 45 is pushed on to the stack.
Then the stack is..
6->45->top;
step 6: Next 3 read and is pushed into the stock. Then the stack is…
6-> 45 ->3->top;
step 7: Next + is read so 3 & 45 are added and the result 48 is pushed into the stack. Then the stack is
6->48->top
finally, the * is read so, 48 and 6 are multiplied and the result 288 is pushed which is the result of the expression.

More Applications of Stack:

1. Syntax Parsing: Many compilers use a stack for parsing the syntax of expressions, program blocks etc.
before translating into low level code.
2. Backtracking: solving problems like maze games require backtracking this can be done with Stacks
3. Parenthesis Checking: Stack is used to check the proper opening and closing of parenthesis.
4. String Reversal: Stack is used to reverse a string. We push the characters of string one by one into
stack and then pop character from stack.

Department of Computer Science, SSBN Degree College, ATP 17

 Data Structures Unit - I

QUEUE
A queue is a linear list in which items may be added at one end and items may be removed only at the
other end. In queues the two ends are called front and rear. The end in which items may be added is called rear
and the other end in which deletions are done are called front.
Queues are also called first in first out lists, since the order in which elements enter a queue is the order
in which they live. This is contrast to stacks, which works on the principle of LIFO. There are so many examples,
in day to day life for queues. Coming to the computers the time saving system in which programs with the same
priority form a view while waiting for execution.

A B C

Front Rear

A B C D E

Front Rear

C D E

Front Rear

The basic operations insertion and deletion can be performed on queue. Here, when the array value
exceeds the size of view then the overflow occurs and an attempt to remove on element from any empty queue
can give an underflow.
Conditions of a queue:
1. front: The front pointer is used to delete an element from queue
2. rear: Rear pointer is used to insert an element in the queue
3. if rear= Size and front=0 (Size is capacity of queue) then queue full
4. if front=-1: queue is empty
5. if front=rear: then queue has only one element
Representation of Queues:
Queues may be represented inside the memory mainly in 2 ways by means of one way is linear arrays.
When a queue is maintained by a linear array Q it needs two pointer variables f and r to store the location of
front element and to store the location of rear element respectively.
When deleting an element f is incremented by 1 and whenever an element is inserted r is incremented
by 1. If Q size is n, after n insertions the near element of the queue will occupy Q(n). This happens even though
the queue itself may not containing many elements i.e. a shown below.
If we want to insert an element into ‘Q’ front rear the queue at this stage i.e. when n=r it is not possible.
One way to overcome this is to simply move the entire queue to the beginning of the array and changing front
and rear. But this process is very expensive so, the method is to assume queue as circular.

Department of Computer Science, SSBN Degree College, ATP 18

 Data Structures Unit - I

Algorithm to insert an element into the Queue:

Let Q is the given queue, front and rear be the pointer variables to indicate the front and rear of the
queue respectively. Size is the max capacity and item is an element.
insert(Q, front, rear, item)
1. If rear>= Size -1
Print “Queue overflow”
Return.
2. increment rear = rear+1
3. insert the element Q[rear]=item
4. check front if queue is empty
if front =-1 then front=0
5. Exit

delete (Q, front, rear)

1. if front=-1
Print “Queue underflow”
Return.
2. remove the element item = Q[front]
3. if front=rear then
rear=front=-1
else
front=front+1
4. return(item)
Queue as ADT
class Queue
{
long que[];
int front,rear;
public Queue(int size)
{
que=new long[size];
front=rear=-1;
}
public boolean isFull()
{
return (rear>=que.length-1);
}
public boolean isEmpty()
{
return (front==-1);
}
public void insert(long item)
{
if(isFull())
{
System.out.println("Queue is Full");
return;
}

Department of Computer Science, SSBN Degree College, ATP 19

 Data Structures Unit - I
que[++rear]=item;
if(front==-1)
front++;
}
public void delete()
{
if(isEmpty())
{
System.out.println("Queue is Empty");
return;
}
long item=que[front];
if(front==rear)
front=rear=-1;
else
front++;
System.out.println("Removed element from Queue is :"+item);
}
public void display()
{
if(isEmpty())
{
System.out.println("Queue is Empty");
return;
}
System.out.print("Queue :[ ");
for(int i=front;i<=rear;i++)
System.out.print(que[i]+" ");
System.out.println("]");
}
}
Program: Write a program to implement Queue using Arrays
//Program to implement Queue operations using Arrays
import java.util.*;
class Queue
{
long que[]; int front,rear;
public Queue(int size)
{
que=new long[size];
front=rear=-1;
}
public boolean isFull()
{
return (rear>=que.length-1);
}
public boolean isEmpty()
{
return (front==-1);
}
public void insert(long item)
{
if(isFull())
{
System.out.println("Queue is Full");
return;
}
que[++rear]=item;
if(front==-1)
front++;
}

Department of Computer Science, SSBN Degree College, ATP 20

 Data Structures Unit - I
public void delete()
{
if(isEmpty())
{
System.out.println("Queue is Empty");
return;
}
long item=que[front];
if(front==rear)
front=rear=-1;
else
front++;
System.out.println("Removed element from Queue is :"+item);
}
public void display()
{
if(isEmpty())
{
System.out.println("Queue is Empty");
return;
}
System.out.print("Queue :[ ");
for(int i=front;i<=rear;i++)
System.out.print(que[i]+" ");
System.out.println("]");
}
}

public class QueueApp

{
public static void main(String args[])
{
Scanner s=new Scanner(System.in);
Queue Q=new Queue(5);
long item;
while(true)
{
System.out.println("********** MENU **********");
System.out.println("1. Insert\n2. Delete\n3. Display\n4. Exit");
System.out.println("Please enter your option:");
int choice =s.nextInt();
switch(choice)
{
case 1:
System.out.println("Enter an element into the Queue:");
item=s.nextLong();
Q.insert(item);
break;
case 2:
Q.delete();
break;
case 3:
Q.display();
break;
case 4:
System.exit(0);
default:
System.out.println("Wrong option");
}
}
}
}

Department of Computer Science, SSBN Degree College, ATP 21

 Data Structures Unit - I

Circular Queue:
In the case of straight queue as the elements are deleted from the queue the remaining element doesn’t
shift forward. Hence, lot of memory space is wasted. When the elements are added up to the last location of
the queue no more elements can be added even though free memory locations are presented in the beginning
of the queue. To overcome, this circular queues are used. If the queue is circular q[1] comes after q[n] in the
array, i.e as soon as all reaches n, instead of increasing r to n+1 be reset r=0. Similarly if f=n and an element is
deleted be reset front=0.

Operations on Queue:
» Insert or Enqueue : adding an element at the rear end of the Circular Queue.
» Delete or Dequeue: removing an element from the fronty end of the Circular Queue.

Exceptions:
» Queue Overflow: Occurs when an insert operation is performed on a Circular Queue which is already full
Condition: (front == 0 && rear == MAX-1 ) || (front == rear +1 )
» Queue Underflow: Occurs when a delete operation is performed on an empty Circular Queue.
Condition: front == -1
Note: when front=rear then queue has only one element

Department of Computer Science, SSBN Degree College, ATP 22

 Data Structures Unit - I

Algorithms to insert & delete an element into circular queue:

Let Q be a circular queue rear and front represent the rear and front ends of queue. MAX is the capacity
and item is the element to be inserted.
CQinsert(Q, front, rear, item)
1. check for overflow
If (front=0 and rear= Size -1 ) or front=rear+1 then
Print “Queue Overflow:
Return.
2. set rear
if front =-1 then
front=rear=0
else if rear=MAX-1 then
rear=0
else
rear=rear+1
3. Q[rear]=item
4. return

CQdelete(Q, front, rear, item)

1. Check for underflow
If front=-1 then
Print “Queue Underflow”
Return.
2. Delete an element
item=Q[front]
3. find new value of front
If front=rear then
front =rear=-1
else if (front=MAX-1) then
front=0
else
front=front+1
4. return item
Circular Queue as an ADT:
class CircularQueue
{
long que[];
int front,rear;
public CircularQueue(int size)
{
que=new long[size];
front=rear=-1;
}

Department of Computer Science, SSBN Degree College, ATP 23

 Data Structures Unit - I
public boolean isEmpty()
{
return (front==-1);
}
public boolean isFull()
{
return ((front==0&&rear==que.length-1)|| (front==rear+1));
}
public void insert(long item)
{
if(isFull())
{
System.out.println("Queue is Full");
return;
}
if(front==-1)
front=rear=0;
else if(rear==que.length-1)
rear=0;
else
rear=rear+1;
que[rear]=item;
}
public void delete()
{
if(isEmpty())
{
System.out.println("Queue is Empty");
return;
}
long item=que[front];
if(front==rear)
front=rear=-1;
else if(front==que.length-1)
front=0;
else
front=front+1;
System.out.println("Removed element is :"+item);
}
public void display()
{
if(isEmpty())
{
System.out.println("Queue is empty");
return;
}
int i = front;
System.out.print("[");
while(i!=rear)
{
System.out.print(que[i]+" ");
i = (i+1)%que.length;
}
System.out.println(que[rear]+"]");
}
}

Department of Computer Science, SSBN Degree College, ATP 24

 Data Structures Unit - I
Program: Write a program to implement Circular Queues using Arrays.
//Program to implement Circular Queues using Arrays
import java.util.*;
class CircularQueue
{
long que[];
int front,rear;
public CircularQueue(int size)
{
que=new long[size];
front=rear=-1;
}
public boolean isEmpty()
{
return (front==-1);
}
public boolean isFull()
{
return ((front==0&&rear==que.length-1)|| (front==rear+1));
}
public void insert(long item)
{
if(isFull())
{
System.out.println("Queue is Full");
return;
}
if(front==-1)
front=rear=0;
else if(rear==que.length-1)
rear=0;
else
rear=rear+1;
que[rear]=item;
}
public void delete()
{
if(isEmpty())
{
System.out.println("Queue is Empty");
return;
}
long item=que[front];
if(front==rear)
front=rear=-1;
else if(front==que.length-1)
front=0;
else
front=front+1;
System.out.println("Removed element is :"+item);
}
public void display()
{
if(isEmpty())
{
System.out.println("Queue is empty");
return;
}
int i = front;
System.out.print("[");
while(i!=rear)
{
System.out.print(que[i]+" ");
i = (i+1)%que.length;
}
System.out.println(que[rear]+"]");
}
}

Department of Computer Science, SSBN Degree College, ATP 25

 Data Structures Unit - I
public class CircularQueueApp
{
public static void main(String[] args)
{
Scanner sc=new Scanner(System.in);
CircularQueue CQ=new CircularQueue(3);
long item;
while(true)
{
System.out.println("************MENU************");
System.out.println("1.Inser\n2.Delete\n3.Display\n4.Exit");
System.out.println("Enter yout option:");
int choice=sc.nextInt();
switch(choice)
{
case 1:
System.out.println("Enter an element:");
item=sc.nextLong();
CQ.insert(item);
break;
case 2:
CQ.delete();
break;
case 3:
CQ.display();
break;
case 4:
System.exit(0);
default:
System.out.println("Wrong Option");
}
}
}

}
Priority Queue:
A priority queue is a collection of elements such that each element has been assigned a priority and such
that the order in which elements are deleted and protest comes under the following rules.
1. An element of higher priority is processed before any element of lower priority
2. Two elements with same priority are processed according to the order in they were added to the queue.
The best example for priority queue is time sharing system. Programs of higher priority processed first
and the programs with same priority form straight queue.
Array implementation of a Priority Queue
A stack and a queue can be implemented in an array so that each insertion or deletion involves
accessing only a single element of the array. Unfortunately, this is not possible for a priority queue.
Suppose that the n elements of a priority queue pq are maintained in positions 0 to n-1 of an array
pq.items of size maxpq, and suppose that pq.rear equals the first empty array position, n. Then pqinsert(pq,x)
would seem to be a fairly straightforward operation:
If (pq.rear >= maxpq)
{
Print (“Priority Queue overflow”)
exit(1)
}
pq.items[pq.rear] = x;
pq.rear++;
Note that under this insertion method the elements of the priority queue are not kept ordered in the array.

Department of Computer Science, SSBN Degree College, ATP 26

 Data Structures Unit - I

As long as only insertions take place, this implementation works well. Suppose, however, that we
attempt the operation pqmindelete(pq) on an ascending priority queue. This raises two issues. First, to locate
the smallest element, every element of the array from pq.items[0] through pq.items[pq.rear-1] must be
examined. Therefore a deletion requires accessing every element of the priority queue. Priority queue
deletion under this implementation requires both searching for the element to be deleted and removal of an
element in the middle of an array.
1. A special “empty” indicator can be placed into a deleted position. This indicator can be a value that is
invalid as an element (for example, --1 in a priority queue of nonnegative numbers), or a separate field
can be contained in each array element to indicate whether it is empty. Insertion proceeds as before,
but when pq.rear reaches maxpq the array elements are compacted into the front of the array
disadvantages to this approach. First, the search process to locate the maximum or minimum element
must examine all the deleted array positions in addition to the actual priority queue elements. If many
items have been deleted but no compaction has yet taken place, the deletion operation accesses many
more array elements than exist in the priority queue. Second, once in awhile insertion requires
accessing every single position of the array, as it runs out of room and begins compaction.
2. The deletion operation labels a position empty as in the previous solution, but insertion is modified to
insert a new item in the first “empty” position. Insertion then involves accessing every array element
up to the first one that has been deleted. This decreased efficiency of insertion is a major drawback to
this solution.
3. Each deletion can compact the array by shifting all elements past the deleted element by one position
and then decrementing pq.rear by 1. Insertion remains unchanged . On the average, half of all priority
queue elements are shifted for each deletion , so that deletion becomes quite inefficient. A slightly
better alternative is to shift either all preceding elements forward or all succeeding elements
backward, depending on which group is smaller. This would require maintaining both front and rear
indicators and treating the array as a circular structure, as we did for the queue.
4. Instead of maintaining the priority queue as an unordered array, maintain it is an ordered, circular
array as follows;
class pqueue
{
private int items [];
private int front, rear;
public pqueue(int size)
{
Items=new int[size];
front=rear=-1;
}
}
pqueue pq=new pqueue(10);
pq.front is the position of the smallest element, pq.rear is 1 greater than the position of the largest. Deletion
involves merely increasing pq.front (for the ascending queue) or decreasing pq.rear (for a descending queue).
However, insertion requires locating the proper position of the new element and shifting the preceding or
succeeding elements (again, the technique of shifting whichever group is smaller is helpful). This method
moves the work of searching and shifting from the deletion operation to the insertion

Department of Computer Science, SSBN Degree College, ATP 27