UNIT – III
(ABSTRACT DATA TYPE)
What is a Data Structure?
A Data Structure is a way of organizing data, so that it can be used effectively. By effectively we mean, the ease with which data can be stored, updated and retrieved.
Why we use Data Structures?
The basic reason of using data structures are:
1. They are basic building blocks for creating fast and powerful algorithms.
2. They help us to manage and organize data.
3. They make code cleaner and easier to understand.
Now, as we have understood as to what is data structures and why do we use them we would like to define Abstract Data Types (ADTs).
Abstract Data Types (ADTs)
An Abstract Data Type is an abstraction of a data structure which provides only the interface to which a data structure must adhere to. The interface do not give any specific details about how something should be implemented or in what programming language.
We can represent ADT as
Fig 1. Representation of ADT Data Properties
Operations
The dash-line in Fig. 1. Indicate operations that can be performed on the data properties.
Let’s, take an example and understand how to create an ADT. Say, we need to create an ADT for a SET. So first of all we need to define the data properties of the SET ADT.
A SET is a group of elements. For example a set of integers can have values as {2, 4, 6, 8, 10}
or set of characters can have {a, b, c, d, e} etc. Also we can perform different operations on SET like:
a. Union: It takes two SET as input and returns the union of the same.
i. SET Union (SET a, SET b)
b. Intersection: It takes two SET as input and returns the intersection of the same.
i. SET Intersection (SET a, SET b)
c. Difference: It takes two SET as input and returns the difference of the same.
i. SET difference (SET a, SET b)
Fig 2. Example of SET ADT.
From the above example, we have defined SET ADT which will contain a group of elements and preform operations like Union, Intersection and Difference. However this definition do not tell us about how we are going to implement these operations or in what programming language.
Properties:
Group of Elements
Operations:
Union, Intersection and difference
Implementation of ADT
We can implement an ADT by writing a program in any programming language and data structure deals with the implementation of various ADTs. In a software module, ADT can be viewed as layer between application and implementation as shown below
Fig. 3: ADT view of Software Module.
Most of the programming language provide some built-in features to implement these Abstract Data Types (ADTs), like:
1. Language C has a built-in feature struct to implement ADT.
2. In C++, a Class Construct can be used to implement ADT.
3. In Java, an ADT can be expressed as an Interface.
Advantages of ADT:
1. ADT is reusable and based on Object Oriented Programming (OOP) and Software Engineering (SE) concept.
2. Reusability in-turn reduces coding efforts and make the program efficient.
3. Encapsulation of Data Structure by ADT ensures that the data cannot be corrupted or tampered by any application program.
4. ADT ensures a robust data structure.
Application Layer ADT Layer Implementation Layer
Classification of Data Structure
Fig. 4: Classification of Data Structure
Data structure can be broadly classified into two types: Primitive Data Structure and Non- Primitive Data Structure. Primitive data types are part of programming language and do not need anything special to use them. These type of data structures are used to store data values, examples are primitive data types are integer, character, float, double etc. On the other hand non-primitive data types not part of programming and they store references to the values instead of just values.
The non-primitive data structures can further be classified into two types: Linear and Non-linear.
Linear non-primitive data structure stores values at a particular reference in a linear fashion i.e.
either horizontally or vertically, on the other hand non-linear non-primitive data structure stores data in hierarchical fashion or random fashion. Examples of Linear non-primitive data structures are Arrays, Stacks, Queues and Linked List. Where as examples of non-linear non-primitive data structures are Tree, Heap and Graph.
Data Structure
Primitive Data Structure Non-Primitive Data Structure
Integer Character Float Double
Linear Data Structure Non-Linear Data Structure
Array Stacks Queues Linked List
Tree Heap Graph
Question for Students:
Write an ADT for an array list?
Answer:
Properties of an Array list are:
1. An array list stores a sequence of arbitrary objects.
2. An element can be accessed, inserted or removed by specifying its index.
3. An exception is thrown, if any incorrect index is given.
Operations that an array list supports are:
1. get(integer i): Returns the element at index i, without removing it.
2. set(integer i, object o): Replace the element at index i with value o and returns the old element at index i.
3. add(integer i, object o): Insert a new element o on index i.
4. remove(integer i): Remove and return the element at index i.
STACK: Definition and examples
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.
Fig. 5: A Stack representation
If any new items is added to the stack, they are placed on top of the item D in Fig. 4, and if any item is deleted, D is the first to be deleted i.e. item that is inserted last is deleted first, for this reason a stack implementation is also called as Last-In First-Out (LIFO).
Primitive operations on Stack
The two changes which can be made to a stack are given special names. When an item is added to a stack it is pushed onto stack and when an item is removed/deleted it is popped from the stack.
So, given a stack s, and an item i performing the operation push(s, i) adds the item i on the top of the stack s. Similarly, pop(s) will remove the top most item and return it as a function value.
i = pop(s); //removes the top of the stack and save it in variable i
We can assume that push operation increment the top of the stack as top = ++top and then assign the value to new top and pop operation simply decrement the top as top-- and return its value.
However, before applying the pop operation to a stack, we must ensure that the stack is not empty. The operation empty(s) can be used to check whether a stack is empty of not.
True, if stack is empty False, if stack is not-empty
D C B A
Top
empty(s)
The result of an illegal attempt to pop an item from an empty stack is called underflow.
Another operation that can be performed on a stack is to determine what the top item on the stack is without removing it. The operation is written as stacktop(s) and returns the top of the stack s.
i = stacktop(s); // Returns top of the stack without removing it from the stack.
This single operation is accomplished by one pop and one push operation internally.
i = pop(s);
push(s, i)
Like pop operation, stacktop operation is also not defined for an empty stack.
Question: Consider the following code for pop operation and find out 1. What this pop function will return, if initially pstop is 87?
2. What is the value of new pstop?
Code:
int pop(struct stack *ps) {
if(empty(ps)) {
printf(“Stack Underflow”);
exit(1);
}/*end if*/
return(psitem[pstop--]) }/*end pop*/
Applications of Stack
Stack can be used in the following situations:
1. It can be used to process function calls.
2. It can be used in implementing recursive functions in high level languages 3. Converting and evaluating expressions.
Function calls
A stack is useful for the compiler or operating system to store local variables used inside a function block, so that they can be discarded once the control comes out of the functional call.
Recursive function
The stack is very useful while implementing recursive functions. The return values and address of the function will be pushed into the stack, and last invoked function will first return the value by poping the stack.
Representation of expression
In general there are 3 kinds of expressions available depending upon the placement of the operators and operands.
1. Infix expression: It is the general notation used for representing expressions, where operator is placed between operands.
Example: if A and B are two operands and ‘+’ is the operator that needs to be applied between the operands then the infix notation will be A + B.
2. Postfix expression: These types of expressions are also called as Reverse Polish Notations and in these types of expressions the operators are placed after the operands.
Example: if A and B are two operands and ‘+’ is the operator that needs to be applied then the postfix notation will be AB+.
3. Prefix expression: These type of expressions are also called as Polish Notations and in these types of expressions the operators are placed before operands.
Example: if A and B are two operands and ‘+’ is the operator that needs to be applied then the prefix notation will be +AB.
When we have infix notations available to us, then why do we use postfix or prefix notations?
We use these notations because:
1. In postfix and prefix notations there is no operator priority i.e. it simplify the expression evaluation rule.
2. In these types of notations we do not need any parenthesis i.e. no ambiguity in the order of evaluation.
3. Evaluation can be carried out using a single scan over the expression string using stack.
Some user level applications of stack are as follows:
1. In case you need to reverse a word, we can use stack. Let’s say we need to reverse a work EXAMPLE, then we will just push the work EXAMPLE is a stack. As we know the stack follows a LIFO approach the first letter to be popped out of stack is the last letter of the work EXAMPLE i.e. E. Similarly when will pop the items out of the stack we will get a string as ELPMAXE i.e. reverse of EXAMPLE.
2. Backtracking: In a puzzle maze game, in which you need to trace a path from reach the end each path points can be pushed to a stack and in case you reach a dead-end and need to backtrack, the endpoint can be popped out to reach the beginning of the path.
Consider the following mathematical expression that consist of several sets of nested parenthesis, for example
7 – ( ( X * ( ( X + Y ) / ( J – 3 ) ) + Y ) / (4 – 2.5 )) ….. (1)
Problem Statement: We want to ensure that the parenthesis are nested correctly that is, we want to check that
Condition 1: There are equal numbers of right and left parenthesis.
Condition 2: Every right parenthesis is preceded by a matching left parenthesis.
Now consider the two expressions:
Expression 1: ( ( A + B) Expression 2: A + B (
Expression 3 :) A + B ( - C Expression 4: ( A + B ) ) – ( C + D
Considering Expression 1 and 2, we found that condition 1 is violated. Whereas condition 2 is violated in Expression 2 and 3.
To solve the above mentioned problem statement, let’s think of left parenthesis as opening scope and each right parenthesis as closing scope. The nesting depth at a particular point is an expression is the number of scopes that have been opened but not yet closed at that particular point.
Now, let us define the parenthesis count at a particular point in an expression as the number of left parenthesis less than the number of right parenthesis that have been encountered in scanning the expression.
The two conditions that must hold true if the parenthesis in an expression form an admissible pattern are as follows:
1. The parenthesis count at the end of the expression is 0. This implies that no scopes have been left open or that exactly as many right parentheses as left parenthesis have been found.
2. The parenthesis count at each point in the expression is non-negative. This implies that no right parenthesis is encountered for which a matching left parenthesis had not previously been encountered.
7 - ( ( X * ( ( X + Y ) / ( J - 3 ) ) + Y ) / ( 4 - 2.5 ) ) 0 0 1 2 2 2 3 4 4 4 4 3 3 4 4 4 4 3 2 2 2 1 1 2 2 2 2 1 0
Computer utility programs like compilers make use of stack in checking the syntax for matching parenthesis in a program. An algorithm for the checking whether a string is valid or not is presented below:
Algorithm for the above mentioned procedure 1. valid=true;
2. s=the empty stack;
3. while(we have not read the entire string) {
4. read the next symbol (symb) of the string;
5. if(symb==’(‘ || symb==’[‘ || symb==’{‘) 6. push(s,symb);
7. if(symb==’)’ || symb==’]’ || symb==’}’) {
8. if(empty(s)) 9. valid=false;
10. else {
11. i=pop(s);
12. if(i is not the matching opener of symb) 13. valid=false;
}/*end else*/
}/*end while*/
14. if(!empty(s)) 15. valid=false;
16. if(valid)
17. print the string is valid 18. else
19. print the string is not valid
This algorithm initially assumes that the string is valid, that is why we mentioned “valid=true”
in line 1. We initialize an empty stack and start reading the string in line 2 and 3. The symbol of the string is captured in a variable “symb” as per line 4.
We then match this symbol to check whether this symbol is the opening parenthesis (, [ or { and in case it is true then we push that symbol to stack in line 5 and 6. However in we encounter ), ] or } we need to pop the top of the stack. But before popping we need to check whether the stack is empty or not, this is done as per line 8.
In case we encounter any closing parenthesis like ), ] or } however the stack is empty then in that case it means that the string do not being with a opening parenthesis and this we make
“valid=false” in line 9. Example: The string mentioned below will set valid=false in line 9:
Expression: A + B ) or A + B ] or A + B } etc.
Line 10 is the other condition in case we encounter a closing parenthesis and the stack is not empty. Line 11 will pop the top of the stack and assign the same to a variable i. Now in case the popped item is not equal to symbol (line 12) then in that case we states that the string is not valid and we again set “valid=false” in line 13. Example: The string mentioned below will set valid=false in line 13:
Expression: (A + B] or [A + B} or (A + B} etc.
After traversing the complete string if still the stack is not empty (line 14), then this means that left parenthesis in the string is more than the right parenthesis, so we again set the string to be invalid by “valid=false” in line 15.
Line 16 and 17 is just printing whether the string is a valid string or not based on the flag “valid”.
Now, let’s check whether the following string is a valid string or not.
{ X + ( Y - [ A + B ] ) * C - [ ( D + E ) ] } ….. (2)
Symbol (Parenthesis) Stack Action Remark
- - - Empty stack
{ { Push(s, { )
( {,( Push(s, ( )
[ {,(,[ Push(s,[ )
] {,( Pop(s) As symbol is correct opener the
string is still valid.
) { Pop(s) As symbol is correct opener the
string is still valid.
[ {, [ Push(s,[ )
( {, [, ( Push(s, ( )
) {, [ Pop(s) As symbol is correct opener the
string is still valid.
] { Pop(s) As symbol is correct opener the
string is still valid.
} - Pop(s) As symbol is correct opener the
string is still valid.
As we can see that at the end of the string traversal, our stack is again empty. So the string as mentioned in (2) is a valid string.
Let us know see how stacks work in function call and recursion function call.
int A(int a) {
printf(“%d”,a);
}
void main() {
int x=10;
x++;
A(x);
}
Before we explain the working of stack in case of function call and recursion call it is necessary to understand the memory block and its components. The Fig. 6 describes the memory partition.
Heap
Stack
Static Variables Code
Fig. 6: Memory partition
The functions of the program or code of the program is kept in code section. In stack section we keep the data of the function or variable of the function. We also have a heap section, which is used for dynamic allocation of memory. In case a code is having static or global variable declared then it is allocated to static variable section.
So if we load the program shown above in the memory block it will be like as shown in Fig. 7
Heap
X=10 Static Variables
Fig. 7. Memory block after loading the program
Now when the instruction x++ is executed the stack variable x is modified to x=11.
Heap
X=11 Static Variables
Fig. 8 Stack variable updated after increment.
void main() {
x++;
A(x);
}
int A (int a) {
printf(“%d”,a) }
Stack
void main() {
x++;
A(x);
}
int A (int a) {
printf(“%d”,a) }
Stack
Heap
a=11 x=11 Static Variables
Fig. 9 Function calling and parameter loading in stack.
After loading of parameter “a” in stack, the next instruction is printing of the value “a” so 11 will be printed. Once execution of function A is over the local variable “a” is popped off the stack.
Heap
Static Variables
Fig. 10 popping of parameter(s) “a” and “x” after function calls.
As we do not have any further instruction in main() function, the execution ends at this point and both variable “x” also pops out of stack.
void main() {
x++;
A(x);
}
int A (int a) {
printf(“%d”,a) }
Stack
void main() {
x++;
A(x);
}
int A (int a) {
printf(“%d”,a) }
Stack
For a recursive call, let us consider the example calculating a factorial.
int fact (int n) {
if(n= = 0) return 1;
else
return n*fact(n-1);
}
void main() {
int num=4;
printf(“%d”,fact(num));
}
Fig. 11. Stack section function calls
Initially when main() function is called, the variable num is loaded into stack with value as 4.
The next instruction in main() function is printing the value of “fact(num)” i.e. fact(4). As fact(4) is a function call, so that fact (4) is loaded into code section and stack section is loaded with n=4, next instruction in fact() is return with “n*fact(3)” i.e. function calling itself (which is recursion).
So now a again fact(3) will be loaded in to code section and subsequently n=3 is loaded into stack. Like it n=2 and n=1 is also loaded into stack section.
Once fact(0) is called, n=0 is loaded is loaded in stack and when n=0, the fact(0) code returns 1, so fact(0) pops out of the stack and ends. Similarly fact(1) will return 1 and ends, fact(2) will return 2*1 and end, fact(3) will return 3*2*1 and end and fact(4) will return 4*3*2*1 and end.
So finally the main() function now has the value of fact(4) with is 4*3*2*1 i.e. 24, hence the program will print 24 and exit.
n=0 return 1 n=1 1*fact(0) n=2 2*fact(1) n=3 3*fact(2) n=4 4*fact(3) Num=4 fact(4)
fact(0)=1 fact(1)=1 fact(2)=2*1 fact(3)=3*2*1 fact(4)=4*3*2*1
We consider five basic binary operations: addition, subtraction, multiplication, division and exponentiation. These five operations are represented as +,-,*,/ and $ respectively.
The order of precedence from highest to lowest is as follows:
1. Exponentiation.
2. Multiplication or Division 3. Addition or Subtraction.
When un-parenthesized the operators of same precedence are scanned from left to right except in case of exponentiation where the order is assumed to be right to left.
The Postfix and Prefix of Infix expressions are shown below
S. No. Infix Prefix Postfix
1 A + B +AB AB+
2 A + (B + C) +A+BC ABC++
3 A+B+C ++ABC AB+C+
4 (A+B)*(C-D) *+AB-CD AB+CD-*
5 A$B*C-D+E/F/(G+H) ?? ??
Explanation of 2nd Infix operation A + (B + C)
We first resolve the expression within the braces ( ) i.e. (B+C) as +BC for prefix and BC+ for postfix.
The converting the braces expression looks like A+(+BC). If we consider +BC as single operand say X, the expression will become A+X and prefix of the same will be +AX or AX+ will be its postfix.
Now to obtain the prefix and postfix of A+(B+C), just replace X with +BC we will get the final prefix expression i.e. +A+BC or ABC++ as postfix expression.
Question: Convert the 5th infix expression mentioned and write the prefix and postfix for the same.
Algorithm to evaluate value of a postfix expression
1. opndstk=the empty stack;
2. while(not end of input) {
3. symb=next input character;
4. if(symb is an operand) 5. push(opndstk, symb);
6. else {
7. opnd 2 = pop (opndstk); /* assign stacktop to operand 2*/
8. opnd 1=pop (opndstk);/*assign stacktop to operand 1*/
9. value=result of applying symb to opnd1 & opnd 2;
10. push(opndstk, value);
} }
11. return(pop(opndstk));
We know that if AB+ is a postfix expression its infix will be A+B. If opndstk is an empty stack and when we push A and B into the stack (as per line 3, 4 and 5 of the algorithm) then it will look like as shown in Fig. 12.
Fig. 12 Stack representation for AB+
Now as soon as “+” operator is encountered, you need to pop the operands and apply the operator. For a general postfix expression <operand1><operand2><operator>, the infix is
<operand1><operator><operand2>. As we can see the top of the operator is B and next is A, B
A
we first pop “B” and put is in operand2 (line 7) and then we pop “A” and put is operand1 (line 8). So that when we apply <operand1><operator><operand2> it takes the correct infix expression i.e. A+B (line 9) instead of B+A and push the result back to stack opndstk (line 10).
Once the entire string is evaluated, the result is in the stack, so we need to return the result by popping opndstk (line 11).
Let us evaluate the postfix string 6 2 3 + - 3 8 2 / + * 2 $ 3 +
Symbol Action Stack
6 Push 6 6
2 Push 2 6,2
3 Push 3 6,2,3
+ Pop 3 in opnd2 and 2 in opnd1 apply 2+3=5 and
push 5 to stack 6.5
- Pop 5 in opnd2 and 6 in opnd1 apply 6-5=1 and
push 1 to stack 1
3 Push 3 1,3
8 Push 8 1,3,8
2 Push 2 1,3,8,2
/ Pop 2 in opnd2 and 8 in opnd1 apply 8/2=4 and
push 4 to stack 1,3,4
+ Pop 4 in opnd2 and 3 in opnd1 apply 3+4=7 and
push 7 to stack 1,7
* Pop 7 in opnd2 and 1 in opnd1 apply 1*7=7 and
push 7 to stack 7
2 Push 2 7,2
$ Pop 2 in opnd2 and 7 in opnd1 apply 72=49 and
push 49 to stack 49
3 Push 3 49,3
+ Pop 3 in opnd2 and 49 in opnd1 apply 49+3=52
and push 52 to stack 52
No symbol return(52) -
The value of the postfix expression is 52.
Question: Evaluate the value of postfix expression 3 5 7 4 – 2 $ * +?
Procedure to convert an infix expression to postfix expression 1. Create an empty stack.
2. Start reading the input symbol and keep reading till end of the input.
3. Add the symbol to postfix string if it is an operand.
4. In case the symbol is not an operand, then
a. Check that the stack should not be empty.
b. Check operator precedence.
i. In case stacktop has a higher precedence that input symbol, pop the item and add it to postfix string.
ii. Otherwise, push the symbol to the stack.
5. After reading the complete string in case we have some operator left in the stack, then pop them out and add the same to postfix string.
We consider the following precedence rules while converting a postfix expression to infix expression:
1. No two operators of same priority can stay together in the stack.
2. A low priority operator cannot be pushed on top of a high priority operator.
Let explain the rules with some scenarios:
1. Say we have + as the stacktop and we want to push – on to stack, then as per rule 1 we need to pop + before pushing – onto stack.
2. Say we have / in the stacktop and want to push + or – on to stack, then as per rule 2 we need to pop / before pushing + or – onto stack.
3. If we have + or – as the stacktop and want to push $ or / or * on to stack, none of the rule (1 and 2) is violated, so it is permissible to pust $ or / or * on top of + or -.
Algorithm for converting infix expression to postfix expression 1. opndstk=the empty stack
2. while(not end of input) {
3. symb=next input character 4. if(symb is an operand)
add symb to the postfix string 5. else
{
6. while(!empty(opndstk) && prcd (stacktop(opndstk), symb)) {
7. topsymb=pop(opndstk);
8. add topsymb to the postfix string }/*end while*/
9. push(opndstk, symb);
} /* end else*/
} /*end while*/
10. while(!empty(opndstk)) {
11. topsymb=pop(opndstk);
12. add topsymb to postfix string;
}/*end while*/
In case our infix expression consist of parenthesis then step 9 above will have to modified as mentioned below:
9’. if(empty(opndstk) || symb!=’)’) push(opndstk, symb);
else /*pop the open parenthesis and discard it*/
topsymb=pop(opndstk);
The prcd (stacktop(opndstk), symb) function is explain in 4 (b) above.
Example of Infix to Postfix conversion with and without parenthesis
Infix String: A + B * C
Symbol Postfix String Stack Remark
A A Add A to postfix string
+ A + Push + to stack
B AB + Add B to postfix string
* AB +, * * has higher precedence than +. So it can be pushed.
C ABC +,* Add C to postfix string
- ABC* + Pop * from stack
- ABC*+ Pop + from stack
Postfix string is ABC*+.
Now, consider the same string with parenthesis. Infix string: (A + B) * C.
Symbol Postfix String Stack Remark
( ( Push ( to stack as per 9’ of algorithm.
A A ( Add A to postfix string
+ A (+ Push + to stack
B AB (+ Add B to postfix string
) Pop +, add it to postfix string and discard ( (refer 9’)
* AB+ * Push * to stack
C AB+C * Add C to postfix string
- AB+C* Pop * from stack
Postfix string is AB+C*.
Queues
A queue is an ordered list or collection of items from which items may be deleted at one end (called as front of the queue) and into which items may be inserted at the other end (called the rear of the queue).
Fig. 13: Representation of a linear queue
If the element ‘A’ is deleted from the queue, the front pointer now points to B.
Fig. 14: Representation of a linear queue after deletion of ‘A’
In case we add D & E to the queue as shown in Fig. 14. Rear now will be pointing to element E.
Fig. 15: Representation of a linear queue after inserting ‘D’ & ‘E’.
Since D is inserted in queue before E, it will also be deleted or removed earlier. That is, the element inserted in the queue is the first element to be removed. For this reason a queue is called First-In First-Out (FIFO) unlike Stack, which is called Last-In First-Out (LIFO). At any instance total element is a queue can be calculated as rear-front+1.
A B C
Rear Front
B C
Rear Front
B C D E
Rear Front
Operations on a queue
The following are some basic operations that can be performed on a queue.
1. insert (q,x): This operation will insert an item ‘x’ at the rear end of the queue ‘q’.
2. remove(q): This operation will remove the element pointed by front and set its value to x i.e. x=remove(q).
3. empty(q): This operation will check whether an queue is empty or not and will return true or false accordingly.
4. peek(): This operation will return the front element of the queue without removing it from the queue.
Insert operation is sometime also called as enqueue operation and remove operation is also called as dequeuer operation.
Queue is used at all those places where:
1. We have a shared resource to serve some request.
2. There is a constraint that the shared resource can serve one request at a time.
Examples:
1. A shared printer maintains a printing queue for different print request.
2. Process scheduling is done via maintaining a process queue.
Consider the following scenario using a linear queue.
An empty queue
Queue after inserting 2, 5.
2 5
Rear Front
If we now execute insert(q, 3), insert(q, 7) and insert(q, 4) the resulting queue will look like
So, at this point front is 0 and rear is 4. Now if we execute remove(q) two times the resulting queue will look like
After executing the remove command, the front is now 2 and rear is 4.
We can see that index 0 and 1 of the queue is empty, so if we try to execute the command insert(q, 8) will it be inserted?. No, even if some cells of the linear queue is empty we will not be able to insert any new item, because our rear pointer has reached to it maximum value i.e. size of the array – 1.
At this point is we try to insert any item it will result in an overflow condition.
To overcome this issue, we enhance the implementation of queue from linear array to circular array. In a circular implementation of a queue, the last element is followed by the first element.
This implies that even if last index of the array is occupied, we can insert a new element at first index (if the first index is available).
Fig. 16: Circular representation of a queue.
2 5 3 7 4
3 7 4
0 1 2 3 …… n-3 n-2 n-1
Rear Front
Rear Front
Like Overflow, a similar condition can occur in which we try to remove from an empty queue.
Such a situation is called as Underflow. So we need to ensure that before we execute a remove operation, we make a check for empty queue.
IsEmpty() {
If front = = -1 and rear = = -1 then return true;
else
return false;
}
Here, we have assumed that we initialize an empty queue with value front = rear = -1.
Algorithm of insertion in a linear queue is:
Enqueue(q, x) {
if(rear = = MAXSIZE – 1) //where MAXSIZE is last element of the array return;
else if (IsEmpty()) //if the queue is empty we need to update front and rear pointers.
front=rear=0;
else
rear=rear+1;
q[rear] = x //insert item x at the rear end of the queue }
Algorithm of deletion in a linear queue is:
Dequeue() {
if(IsEmpty()) //In case the queue is empty, do not run dequeuer command.
return;
else if (front= = rear) //array has only single element x= item at location 0;
front = rear = -1;
else
front = front + 1;
}
If i is the current position of rear pointer for a circular array of N elements, the next position is computed as (i + 1) % N and previous position is computed as (i + N-1)%N.
The condition rear = MAXSIZE -1 that was used for checking whether a linear queue is full or not, is not valid in case of circular queue.
Fig. 17: A Circular Queue with 8 elements.
In a linear queue, when rear reaches MAXSIZE – 1, it means that the queue is full as we cannot insert any item after last cell i.e. MAXSIZE – 1. However in circular queue, if first cell is empty then we can insert data even after last cell (i.e. MAXSIZE – 1). So how would we check whether a circular queue is full or not?
0 1 2 4 3
5 5 6 6 7
7 8
The circular queue as shown is Fig. 17, will be full if rear = 7 and front = 0. Next position is calculated as (rear + 1) % N and if this position is equal to front, then we can deduce that the circular queue is full.
So, condition for checking whether circular queue is full or not is (rear + 1) % N = = front instead of just rear = = MAXSIZE – 1.
Algorithm of insertion in a circular queue is:
Enqueue(q, x) {
if((rear + 1)%N = = front) //condition for checking whether circular queue is full return;
else if (IsEmpty()) //if the queue is empty we need to update front and rear pointers.
front=rear=0;
else
rear=(rear+1)%N; //next value of rear in circular queue.
q[rear] = x //insert item x at the rear end of the queue }
Algorithm of deletion in a circular queue is:
Dequeue() {
if(IsEmpty()) //In case the queue is empty, do not run dequeuer command.
return;
else if (front= = rear) //array has only single element x= item at location 0;
front = rear = -1;
else
front = (front + 1)%N;//next value of front in circular queue.
}
Both stack and queue (linear and circular) are data structures whose elements are ordered based on the sequence in which they have been inserted.
pop (s) operation retrieves the last element inserted, and remove(q) operation retrieves the first element inserted..
The intrinsic order among the elements is ignored in both stack and queue operations. Priority Queue is a data structure in which intrinsic order of the elements does determine the result of its basic operations. It implements a set S of elements, and each of these elements is associated with a key.
There are two types of priority queues:
1. Ascending priority queue: It is a collection of items into which items can be inserted arbitrarily and from which only the smallest item can be removed.
2. Descending priority queue: It is similar to ascending priority queue, however allows deletion of only the largest item.
We will study the application of priority queue i.e. Heap, in details in coming section.
Linked List
Before proceeding to linked list, lets analyze the drawbacks of using sequential storages like stacks and queues mentioned below:
1. Fixed amount of storage remains allocated to stack or queue even when the structure is actually using a smaller amount or no storage at all.
2. Not more than allocated amount of storage may be allocated, thus introducing the possibility of overflow.
In stacks and queues items are implicitly ordered by the sequential order of storage. By implicitly ordered we mean that if q.items[x] is an element of a queue the next element will be q.item[x+1].
Suppose that items of stack or queues were explicitly ordered, that is, each item contained within itself the address of the next item, such an explicit ordering give rise to a data structure known as linear linked list. A linked list is represented as shown is Fig. 18.
Fig. 18: Linked List representation In Fig. 18, we can see that there are three pointers:
1. Next pointer: This pointer contains the address of next node.
2. Null pointer: This pointer indicates that the linked list has ended.
3. List pointer: It is an external pointer (i.e. it is not included within a node) to the linked list.
A linked list with no nodes is called an empty list or null list and can be initialized by list=null.
If list is a pointer to a node as shown in Fig. 18, so node(list) will refer to the node pointed by list. Info(list) refers to the information contained in the node pointed by list. Next(list) refers to the address portion and it therefore a pointer.
Let us study insertion and removal of nodes from a list with an example. Suppose, we have a list of integers as shown below:
Fig. 19: Linked list of integers
We wish to add a integer 6 to the front of the list. As unlike an array, a list does not come with a pre-supplied set of storage locations into which elements can be placed. So the first step is to obtain a node into which we can store 6. Let us assume the existence of a mechanism for obtaining an empty node as:
Null List
Info Next
Node
5 3 8 Null
List
Info Next
Node
p = getnode();
The mechanism getnode() will generate a new node and assign a pointer p to that node.
The next step is to insert item 6 into this empty node, this can be done as:
info(p) = 6;
In case now we want to insert this new node in front of linked list shown in Fig. 19 we need to point Next(p) to list i.e. Next(p) = list;
We still have two external pointers, p and list. So we must modify p to list by instruction list = p;
So, collectively we can say that for inserting a node we have four basic steps.
1. p = getnode();
2. info(p) = 6;
3. next(p) = list;
4. list = p;
p
Info Next
p 6
Info Next
p 6
Info Next
5 3 8 Null
List
Info Next
List 6
Info Next
5 3 8 Null
In case we want to generalize the procedure, the we need to change step 2 as info(p) = x;
Now in case you wish to remove the front node from the linked list we follow the basic steps:
1. p = list; // initialize a external pointer ‘p’ to the first node.
2. List = next(p); //Move the ‘list’ pointer to next node.
3. x = info(p); //Take the information part of node pointed by ‘p’ in a variable x.
4. freenode(p); //Free or delete node p, as it do not contain any data now.
Linked implementation of Stacks
The operation of adding an element to the front of a linked list is quite similar to that of pushing an element onto a stack. A stack can only be accessed through its top element and a list can be accessed only from the pointer to its first element.
Similarly, the operation of removing the first element from a linked list is analogous to popping of stack, as in both the cases the only immediately accessible item of a collection is removed from that collection, and the next item becomes immediately accessible.
Thus, a stack may be represented by a linear linked list wherein the first node of the list is the top of the stack. If a external pointer ‘s’ points to such a linked list the operation push(s, x) and pop(s) may be implemented as :
1. p = getnode(); 1. p = s;
2. info(p) = x; 2. s = next(p);
3. next(p) = s; 3. x = info(p);
4. s = p; 4. freenode(p)
The advantage of the list implementation of stacks is that all stacks being used by a program can share the same available list. When any stack needs a node, it can obtain it from the single available list.
Push(s, x) pop (s)
Queue implementation of linked list
Under the link list representation a queue ‘q’ consist of a list and two set of pointers q.front and q.rear as shown below.
In case we wish to delete a node from a queue, the deletion will be done from front end. The steps involved in dequeue operation are:
1. p = q.front;
2. q.front = next(p);
3. x = info(p);
4. if(q.front = = null) q.rear = null;
5. freenode(p);
We first initialize a new pointer ‘p’ to the first node ‘q.front’ and then move forward ‘q.front’ to point to ‘next(p)’ so that it bypasses the first node. Now as p is now pointing to the node we fetch the information part before deleting the node.
Once we have fetched the value, then we need to check whether the list has some more node of the deleted node was the only node in the list. The statement if(q.front = = null) is checking whether the new q.front have any address or not. In case it does not have any address, it will have null i.e. the node was the only node in the list. So in this case we need to assign q.rear = null as the complete list is now empty and for empty list we have seen before that list pointer must be null.
Enqueue in a linked list can be done as:
1. p = getnode();
2. info(p) = x;
5 3 8 Null
Info Next
Node q.front
q.rear
3. next(p) = null;
4. if(q.rear = = null) q.front = p;
5. else
next(q.rear) = p;
6. q.rear = p;
Step 1, 2, 3 create an empty node insert the data value in it and assign null into next of the node.
As enqueue can only be done at the rear end. The next field of the new node needs to have null, as it will the last node of the list.
Step 4 is checking whether there is any pre-existing rear node or not with q.rear = = null condition. In case if q.rear !=null, then we must assign p to next of q.rear i.e. next(q.rear) = p;
If the condition in step 4 is true i.e. q.rear = = null, then it means there was not rear node and the list was initially empty. So the new pointer ‘p’ must be assigned to q.front (step 4) and the same should be assigned to q.rear (Step 6).
Now, if ‘p’ points to an element of the list, inserting a new element after node(p) involves allocating a node, inserting the information and adjusting the two pointers.
1. q = getnode(); //generated a new node and initialize a pointer ‘q’.
2. info(q) = x; //assign a value x to info part of ‘q’.
3. next(q) = next(p) //pointer adjustment 4. next(p) = q; //pointer adjustment.
Similarly deleting a node from linked implementation of a queue is as follows:
1. q = next(p); //initialize a pointer ‘q’ to the node pointed by ‘p’ that needs to be deleted.
2. x = info(p); //retrieve the value of node pointed by ‘p’
3. next(p) = next(q); //adjust the pointer 4. freenode(q); //free the node.
Other link structures
Given a pointer ‘p’ to a node in a linear linked list, we cannot reach any nodes that precede node(p). This short coming can be handled by a small change to the structure of linear list.
If next field in the last node contains a pointer back to the first node rather than “null” pointer, we can reach the preceding node of ‘p’. Such a list is called a circular linked list.
Fig. 20: A circular linked list.
As per convention, we have pointed the external pointer ‘list’ to the last node in order to allow the following node to be the first node. One can access the last node as node(list) and the first node as node(next(list)). Also this convention provides the advantage of adding or removing an element conveniently from either end of the list. We also established the convention that a null pointer represents an empty circular list.
Header Nodes
Suppose we want to traverse a circular list, that can be done by repeatedly executing p = pnext, where p is initially a pointer to the beginning of the list.
The problem with this traversal is we will not know when the entire list has been traversed, as we do not have any flag or indication as where the list starts.
One solution to this problem is to use two pointers pointing to the first node of circular linked list, say ‘p’ and ‘list’, and a test can be made for the condition p = = list to establish the fact that the circular list is completely traversed.
Another solution is to place a header node as the first node of a circular list. This header may be recognized by a special value in its info field that cannot be the valid contents of a list node in the context of the problem or it may contain a flag in its header.
6 5 3
List
Advantage of this approach is we can traverse the list using a single pointer, with traversal halting when the header node is reached.
Fig. 21: Circular link list with header node.
Although, a circular linked list has advantages over linear linked list it still has several drawbacks:
1. One cannot traverse the list backwards.
2. Deletion of a node is not possible, given only a pointer to that node.
In case where these facilities are required, a new modified data structure can be used which is called as Doubly-Linked List (DLL). Each node in DLL contains two pointer on to its
predecessor and other to its successor.
Fig. 22: A Doubly Linked List (DLL)
Header Node
5 3
List
3 5 3 Null
List
Algorithm for deleting a node with a given item of information
For deleting a node with a given item of information, we need two pointers LOC and LOCP.
LOC = Pointer to the item location, & LOCP = Pointer to the parent of item.
We need these two pointers as when we delete a node, we will need to process the following command:
next(LOCP) = next(LOC);
Step 1: Find the location of the item that needs to be deleted in the list.
If (list = = NULL) /* list do not exist */
Set LOC = NULL & LOCP = NULL and Return;
Else if (info(list) = = item) /* 1st item of the list is matched */
Set LOC = list and LOCP = NULL and Return;
Else
SAVE = list and PTR = next(list) /* initialize pointers to traverse the list*/
While (PTR != NULL) {
if (info(PTR) = = item)
set LOC = PTR and LOCP = SAVE; Return;
set SAVE = PTR and PTR = next(PTR);
}
Set LOC = NULL;
Return;
Step 2: Remove the node that contains the item and adjust the pointers accordingly.
If LOC = = NULL
Write item not present in the list & exit;
If LOCP = = NULL Set list = next(list);
Else
next(LOCP) = next(LOC);
