UNIT- I: Introduction to Data Structures: Abstract Data Types (ADTs), The List ADT:

Simple Array Implementation of Lists, Simple Linked Lists, Doubly Linked Lists,
Circularly Linked Lists. The Stack ADT: The Stack Model, Implementation of Stacks,
Applications of Stack. The Queue ADT: Queue Model, Array Implementation of
Queues, Application of Queues. Stacks and Queue implementation using linked list.

An abstract data type (ADT) is the way we look at a data structure, focusing on what it does
and ignoring how it does its job. For example, stacks and queues are perfect examples of an
ADT. We can implement both these ADTs using an array or a linked list. This demonstrates
the ‘abstract’ nature of stacks and queues.

Data type of a variable is the set of values that the variable can take. We have already read the
basic data types in C include int, char, float, and double. When we talk about a primitive type
(built-in data type), we actually consider two things: a data item with certain characteristics
and the permissible operations on that data. For example, an int variable can contain any
whole-number value from –32768 to 32767 and can be operated with the operators +, –, *, and
/. In other words, the operations that can be performed on a data type are an inseparable part
of its identity. Therefore, when we declare a variable of an abstract data type (e.g., stack or a
queue), we also need to specify the operations that can be performed on it.

The word ‘abstract’ in the context of data structures means considered apart from the detailed
specifications or implementation. In C, an abstract data type can be a structure considered
without regard to its implementation. It can be thought of as a ‘description’ of the data in the
structure with a list of operations that can be performed on the data within that structure. The
end-user is not concerned about the details of how the methods carry out their tasks. They are
only aware of the methods that are available to them and are only concerned about calling
those methods and getting the results. They are not concerned about how they work. For
example, when we use a stack or a queue, the user is concerned only with the type of data and
the operations that can be performed on it. Therefore, the fundamentals of how the data is
stored should be invisible to the user. They should not be concerned with how the methods
work or what structures are being used to store the data.

Advantage of using ADTs In the real world, programs evolve as a result of new requirements
or constraints, so a modification to a program commonly requires a change in one or more of
its data structures. For example, if you want to add a new field to a student’s record to keep
track of more information about each student, then it will be better to replace an array with a
linked structure to improve the program’s efficiency. In such a scenario, rewriting every
procedure that uses the changed structure is not desirable. Therefore, a better alternative is to
separate the use of a data structure from the details of its implementation.
www.Jntufastupdates.com 2
www.Jntufastupdates.com 3
www.Jntufastupdates.com 4
www.Jntufastupdates.com 5
www.Jntufastupdates.com 6
www.Jntufastupdates.com 7
www.Jntufastupdates.com 8
www.Jntufastupdates.com 9
www.Jntufastupdates.com 10
www.Jntufastupdates.com 11
www.Jntufastupdates.com 12
www.Jntufastupdates.com 13
www.Jntufastupdates.com 14
www.Jntufastupdates.com 15
www.Jntufastupdates.com 16
www.Jntufastupdates.com 17
www.Jntufastupdates.com 18
www.Jntufastupdates.com 19
www.Jntufastupdates.com 20
www.Jntufastupdates.com 28
www.Jntufastupdates.com 29
www.Jntufastupdates.com 30
www.Jntufastupdates.com 31
www.Jntufastupdates.com 32
www.Jntufastupdates.com 33
www.Jntufastupdates.com 34
www.Jntufastupdates.com 35
www.Jntufastupdates.com 36
www.Jntufastupdates.com 37
www.Jntufastupdates.com 38
www.Jntufastupdates.com 39
 QUEUE :
Queue is a linear data structure in which elements can be inserted from one end calledrear and
deleted from other end called front.

● The deletion or insertion of elements can take place only at the front or rear end called
dequeue and enqueue respectively. The first element that gets added into the queue is
the first one to get removed from the queue. Hence the queue is referred to as First-
InFirst-Out list (FIFO).

Operations performed on Queue:

There are two possible operations performed on a queue. They are

✔ enqueue: Allows inserting an element at the rear of the queue.

✔ dequeue: Allows removing an element from the front of the queue.
REPRESENTATION OF QUEUEs:

ARRAYs: Queues can be easily

represented using linear arrays. Every
queue has front and rear variables that
point to the position from where deletions
and insertions can be done, respectively.
The array representation of a queue is
shown
Drawback: The array must be declared to
have some fixed size. If we allocate space
for 50 elements in the queue and it hardly uses 20–25 locations, then half of the space will be
wasted.

LINKED LISTs:

• In a linked queue, every element has two parts, one that stores the data and another that
stores the address of the next element.
• The START pointer of the linked list is used as FRONT. Here, we will also use another
pointer called REAR, which will store the address of the last element in the queue. All
insertions will be done at the rear end and all the deletions will be done at the front end.
• If FRONT = REAR = NULL, then it indicates that the queue is empty.

IMPLEMENTATION OF QUEUEs:
Using Arrays:
Algorithm for ENQUEUE operation
1. Check whether queue is FULL. (rear >= SIZE-1)
 2. If it is FULL, then display an error message "Queue is FULL!!! Insertion is not possible!!!"
and terminate the function.
3. If it is NOT FULL, then increment rear value by one
(rear++) and set queue[rear] = value.

Algorithm for DEQUEUE operation

1. Check whether queue is EMPTY. (front == -1)
2. If it is EMPTY, then display "Queue is EMPTY!!! Deletion is not possible!!!" and
terminate the function.
3. If it is NOT EMPTY, then display queue[front] as deleted element, increment the front
value by one (front ++). If we are deleting last element both front and rear are equal (front
== rear), then set both front and rear to '-1' (front = rear = -1).

Implementation:
• Let us consider a queue, which can hold
maximum of five elements.
• Initially the queue is empty. An element can be
added to the queue only at the rear end of the
queue.
• Before adding an element in the queue, it is
checked whether queue is full. If the queue is full,
then addition cannot take place. Otherwise, the
element is added to the end of the list at the rear
end. If
we are
inserting first element into the queue then change
front to 0 (Zero).
• Now, delete an element 1. The element
deleted is the element at the front of the queue.
So the status of the queue is:
• When the last element delete 5. The
element deleted at the front of the queue. So the
status of the queue is empty. So change the
values of front and rear to -1 (front=rear= -1)
 • The dequeue operation deletes the element from the front of the queue. Before deleting
and element, it is checked if the queue is empty. If not the element pointed by front is
deleted from the queue and front is now made to point to the next element in the queue.
• Drawback: If we implement the queue using an array, we need to specify the array size
at the beginning (at compile time). We can't change the size of an array at runtime. So, the
queue will only work for a fixed number of elements.

Using Linked List:

• In a linked queue, each node of the queue consists of two parts i.e. data part and the next
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. Initially

struct node *front = NULL, *rear = NULL;

Operation on Linked Queue: There are two basic operations which can be implemented on the
linked queues. The operations are Enqueue and Dequeue.

Enqueue function: Enqueue function will add the element at the end of the linked list.

1. Declare a new node and allocate memory for it.

2. If front == NULL, make both front and rear points to the new node.

3. Otherwise, add the new node in rear->next (end of the list) and make the new node as
the rear node. i.e. rear = new node

Dequeue function: Dequeue function will remove the first element from the queue.

1. Check whether the queue is empty or not

2. If it is the empty queue (front == NULL), We can't dequeue the element.

 3. Otherwise, Make the front node points to the next node. i.e front = front->next;

if front pointer becomes NULL, set the rear pointer also NULL.

Free the front node's memory.

Example: Enqueue()

Dequeue()

TYPES OF QUEUES:
A queue data structure can be classified into the following types:
1. Circular Queue 2. Deque 3. Priority Queue 4. Multiple Queue

CIRCULAR QUEUEs:
• In a Linear queue, once the queue is completely full, it's not possible to insert any more
elements. When we dequeue any element to remove it from the queue, we are actually
moving the front of the queue forward, but rear is still pointing to the last element of the
queue, we cannot insert new elements.
• Circular Queue is also a linear data structure, which follows the principle of FIFO(First
In First Out), but instead of ending the queue at the last position, it again starts from the
first position after the last, hence making the queue behave like a circular data structure.
Operations on Circular Queue: The following are the operations that can be performed o
enQueue(value): This function is used to insert the new value in the Queue. The
new element is always inserted from the rear end.
o deQueue(): This function deletes an element from the Queue. The deletion in a Queue
always takes place from the front end.

Enqueue operation: The steps of enqueue operation are given below:

o First, we will check whether the Queue is full or not.
o Initially the front and rear are set to -1. When we insert the first element in a Queue, front
and rear both are set to 0.
o From 2nd element onwards, When we insert a new element, the rear gets incremented, i.e.,
rear=rear+1.

Queue is not full:

o If rear != max - 1, then rear will be incremented and the new value will be inserted at the
rear end of the queue.
o If front != 0 and rear = max - 1, it means that queue is not full, then set the value of rear
to 0 and insert the new element there.

Queue is full:
o When front ==0 && rear = max-1, which means that front is at the first position of the
Queue and rear is at the last position of the Queue.
o front== rear + 1;

Dequeue Operation: The steps of dequeue operation are given below:

o First, we check whether the Queue is empty or not. If the queue is empty, we cannot perform
the dequeue operation.
o When the element is deleted, the value of front gets decremented by 1. o If there is
only one element left which is to be deleted, then the front and rear are reset -1.

Let's understand the enqueue and dequeue operation through the diagrammatic
representation.
Applications of Queue:
1. Queues are widely used as waiting lists for a single shared resource like printer, disk, CPU.
2. Queues are used to transfer data asynchronously between two processes
3. Queues are used as buffers on MP3 players and portable CD players, iPod playlist.
4. Queues are used in Playlist for jukebox to add songs to the end, play from the front.
5. Queues are used in operating system for handling interrupts. The interrupts are handled in
the same order as they arrive i.e First come first served.

DEQUE:

Deque or Double Ended Queue is a

type of queue in which insertion and
removal of elements can be performed
from either from the front or rear.
Thus, it does not follow FIFO rule
 (First In First Out).

Types of Deque:
1. Input Restricted Deque: In this deque, input is restricted at a single end but allows
deletion at both the ends.
2. Output Restricted Deque: In this deque, output is restricted at a single end but allows
insertion at both the ends.

Operations on a Deque
Initially take an array (deque) of size n. and Set two pointers at the first position and set
front = -1 and rear = -1.
1. Insert at the Front: This operation adds an element at the front.
• Check the position of front, If front < 1, we can’t add elements in the front end.
Otherwise decrement the front and at front location we can insert the element.
2. Insert at the Rear: This operation adds an element to the rear.
• Check if the array is full. Then the queue is overflow. Otherwise, reinitialize rear = 0
& front=0 for the first insertion, Else, increase rear by 1.and at rear location we can
insert the element.
3. Delete from the Front: The operation deletes an element from the front.
• Check If the deque is empty (i.e. front = -1), deletion cannot be performed (underflow
condition). If the deque has only one element (i.e. front = rear), set front = -1 and
rear = -1. Else, front = front + 1.
4. Delete from the Rear: This operation deletes an element from the rear.
• If the deque is empty (i.e. front = -1), deletion cannot be performed (underflow
condition). If the deque has only one element (i.e. front = rear), set front = -1 and
rear = -1. Else, rear = rear - 1.

Priority Queue:-
:-
• A priority queue is a data structure in which each element is assigned a priority. The
priority of the element will be used to determine the order in which the elements will be
processed.
 • The general rules of processing the elements of a priority queue are o An element with
higher priority is processed before an element with a lower priority.
o Two elements with the same priority are processed on a first-come-first-served (FCFS)
basis.
Array Representation of a Priority Queue:
• When arrays are used to implement a priority queue, then a separate queue for each priority
number is maintained. Each of these queues will be implemented using circular arrays or
circular queues. Every individual queue will have its own FRONT and REAR pointers.
• We use a two-dimensional array for this purpose where each queue will be allocated the
same amount of space.
• FRONT[P] and REAR[P] contain the front and rear values of row P, where P is the priority
number.

Insertion:
• To insert a new element with priority P in the priority queue, add the element at the rear
end of row P, where P is the row number as well as the priority number of that element.
• For example, if we have to insert an element X with priority number 2, then the priority
queue will be given as shown in Fig.

Deletion:
• To delete an element, we find the first nonempty queue and then process the front element
of the first non-empty queue.
• In our priority queue, the first non-empty queue is the one with priority number 6 and the
front element is K, so K will be deleted and processed first.
 Multiple Queues:-
:-
• When we implement a queue using an array, the size of the array must be known in advance.
If the queue is allocated less space, then frequent overflow conditions will be encountered.
To deal with this problem, the code will have to be modified to reallocate more space for
the array.
• In case we allocate a large amount of space for the queue, it will result in sheer wastage of
the memory. So a better solution to deal with this problem is to have multiple queues or to
have more than one queue in the same array of sufficient size.
• An array Queue[n] is used to represent two queues, Queue A and Queue B. The value of n
is such that the combined size of both the queues will never exceed n. While operating on
these queues, it is important to note one thing—queue A will grow from left to right, whereas
queue B will grow from right to left at the same time.
Example:

• In the above example the array consists two queues like QA and QB. For QA there are
pointers like fA(front of QA) and rA(rear of A). similarly for QB are fB & rB.
• Initially for QA, the pointer values of fA=rA= -1. For QB, the pointer values are
fB=rB=SIZE. Because initially QA and QB are empty.
• For the first insertion in QA, the values of fA=rA=0. Similarly for QB, the values are
fB=rB=SIZE-1.
• From the second insertion onwards we can increment only the rear pointer rA for QA and
decrement the rear rB for QB.
• Delete the elements from queue only at front end. In QA, the elements can delete from fA,
if you delete the element then increment fA. In QB, the elements can delete from fB, if you
delete the element then decrement fB.
• When the condition rA=rB-1 or rA+1=rB meets then the entire queue is full. If you try to
insert the element in either of queues it says that QUEUE is OVERFLOW.
 Stack:-

:-
● Stack is a linear data structure in which insertion and
deletion can perform at the same end called top of stack.

● When an item is added to a stack, the operation is called

push, and when an item is removed from the stack the
operation is called pop.

● Stack is also called as Last-In-First-Out (LIFO) list which

means that the last element that is inserted will be the first
element to be removed from the stack.
● When a stack is completely full, it is said to be Stack is Overflow and if stack is completely
empty, it is said to be Stack is Underflow.

REPRESENTATION & IMPLEMENTATION STACK:

Array Representation of Stacks:

• Every stack has a variable called TOP associated with it, which is used to pointing the
topmost element of the stack. It is this position where the element will be inserted to or
deleted from.
• There is another variable called MAX, which is used to store the maximum number of
elements that the stack can hold.
• If TOP = NULL, then it indicates that the stack is empty and if TOP = MAX–1, then the
stack is full.

Array Implementation of Stack:

The basic operations performed in a Stack:

1. Push(x) - add element x at the top of the stack
2. Pop( ) - remove top element from the stack
3. peek() - get top element of the stack without removing it Algorithm for

PUSH operation:

1. Check if the stack is full or not.

2. If the stack is full, then print error of overflow and exit the program.
3. If the stack is not full, then increment the top and add the element at top location.

Algorithm for POP operation

1. Check if the stack is empty or not.

2. If the stack is empty, then print error of underflow and exit the program.
3. If the stack is not empty, then print the element at the top and decrement the top.

Algorithm for PEEK operation

1. Check if the stack is empty or not.

2. If the stack is empty, then print error of underflow and exit the program.
3. If the stack is not empty, then print the element at the top without removing it.
Linked Representation of Stacks:

• The drawback in that the array must be declared to have some fixed size. In case the stack is
a very small one or its maximum size is known in advance
 • In a linked stack, every node has two parts, one that stores data and another that stores the
address of the next node. The START pointer of the linked list is used as TOP.
• All insertions and deletions are done at the TOP (similar to insertion at beginning).
• If TOP = NULL, then it indicates that the stack is empty.
• The linked representation of a stack is

Linked Implementation of Stack:

• In a linked stack, each node of the stack consists of two parts i.e. data part and the next part.
Each element of the stack points to its immediate next element in the memory.
• In the linked stack, there one pointer maintained in the
memory i.e. TOP pointer. The TOP pointer contains the
address of the starting element of the STACK.
• Both Insertion and deletions are performed at only one end
called TOP. If TOP is NULL, it indicates that the stack is empty. Initially

struct node *TOP = NULL ;

Operation on Linked STACK: There are two basic operations which can be implemented on the
linked queues. The operations are PUSH and POP.

PUSH function: PUSH function will add the element at the beginning of the linked list.
1. Declare a new node and allocate memory for it.
2. If TOP == NULL, make TOP points to the new node.
3. Otherwise, add the new node at TOP end and makes the next of new node is previous TOP.

POP function: POP function will remove the TOP element from the STACK.
1. Check whether the stack is empty or not
2. If it is the stack is empty (TOP == NULL), We can't POP the element.
3. Otherwise, Make the TOP node points to the next node. i.e TOP = TOP->next; Free the TOP
node's memory
 Applications of Stacks
✔ Stack is used to reversing the given string.
✔ Stack is used to evaluate a postfix expression.

✔ Stack is used to convert an infix expression into postfix/prefix form.

✔ Stack is used to matching the parentheses in an expression.

Evaluation of Expressions:-

● An expression is defined as the combination of operands (variables, constants) and operators

arranged as per the syntax of the language.
● An expression can be represented using three different notations. They are infix, postfix and
prefix notations:

Prefix: An arithmetic expression in which we fix (place) the arithmetic operator before (pre) its two
operands. The prefix notation is called as polish notation. Example: + A B
Infix: An arithmetic expression in which we fix (place) the arithmetic operator in between the two
operands. Example: A + B
Postfix: An arithmetic expression in which we fix (place) the arithmetic operator after (post) its two
operands. The postfix notation is called as suffix notation OR reverse polish notation.
Example: A B +
Operator Precedence: When an expression consist different level of operators we follow it. We
consider five binary operations: +, -, *, / and ^ (exponentiation). For these binary operations, the
following in the order of precedence (highest to lowest): ^ , * , /, +, -

Operator Associativity: When an expression consist more than one same level precedence operators
we follow it.
Basically we have Left to Right associativity and Right to Left Associativity. Most of the operators
are follows Left to Right but some of the operators are follow Right to left Associativity like Unary
(+/-), ++/-- , Logical negation (!), Pointer and address (*,&), Conditional Operators and Assignment
operators(=,+=,-=,*=,/=,%=).
Example: x=a/b–c+d*e–a*c

Let a = 4, b = c = 2, d = e = 3 then the value of x is found as

= ((4 / 2) – 2) + (3 * 3) – (4 * 2) =0+9–8 =1

EVALUATION OF POSTFIX EXPRESSION:

The standard representation for writing expressions is infix notation. But the compiler uses
the postfix notation for evaluating the expression rather than the infix notation. It is an easy task for
evaluating the postfix expression than infix expression because there are no parentheses. To evaluate
 an expression we scan it from left to right. The postfix expression is evaluated easily by the use of a
stack.

To evaluate a postfix expression use the following steps...

1. Read the poststring from left to right

2. Initialize an empty Stack
3. Repeat until end of the poststring
i. If the scanned character is operand, then push it on to the Stack.
ii. If the scanned character is operator (+ , - , * , / etc.,), then pop top two elements from
the stack, perform the operation with the operator then push result back on to the Stack.
4. Finally! We have one element in the stack, perform a pop operation and display the popped
value as final result.

ostfix Expression is 5 3 + 8 2 - *
Symbol Stack Evaluation

Initially

Stack is5 empty

Push(5)

3
3 5
Push(3)

Value1=3
8 Value2=5
+
Value1=pop() Result=5+3=8
Value2=pop() Push(8)
Result=Value2+Value1
Push(Result)
 8 8
8
Push(8)

2
2 8
8
Push(2)

Value1=2
6 Value2=8
8 Result=8-2=6
-
Push(6)
Value1=pop()
Value2=Pop()
Result=Value2-Value1
Push(Result)

Value1=6
48 Value2=8
*
Value1=pop() Result=8*6=48
Value2=Pop() Push(48)
Result=Value2*Value1
Push(Result)

End of Expression Final Result is 48

48
Result=pop()

Conversion of INFIX to POSTFIX:

 Scan all the symbols one by one from left to right in the given Infix Expression.
 If the reading symbol is an operand, then immediately append it to the Postfix Expression.
 If the reading symbol is left parenthesis ‘( ‘, then Push it onto the Stack.
 If the reading symbol is right parenthesis ‘)’, then Pop all the contents of the stack until the
respective left parenthesis is popped and append each popped symbol to Postfix Expression.
 If the reading symbol is an operator (+, –, *, /), then Push it onto the Stack. However, first,
pop the operators which are already on the stack that have higher or equal precedence than
the current operator and append them to the postfix. If an open parenthesis is there on top of
the stack then push the operator into the stack.
 If the input is over, pop all the remaining symbols from the stack and append them to the
postfix.

Operators Associativity Precedence

Highest
^ followed by
Right to left
exponentiation *Multiplication
and /division

Highest
*Multiplication, followed by +
Left to right
/division addition and –
subtraction

+ addition, –
Left to right Lowest
subtraction

Example: a * (b + c) *d)

Token Stack Postfix String

(
a A

* ( * A

( *
( ( A
 ( *
b ( Ab

( *
+ ( + Ab

( *
c ( + Abc

( *
) abc+

( *
* abc+*

( *
d abc+*d

) abc+*d*