18CS32 DS Notes

MODULE-2

Linear Data Structures and their sequential storage Representation

Stacks: Definition, Stack Operations, Array Representation of Stacks, Stacks using Dynamic
Arrays, Stack Applications: Polish notation, Infix to postfix conversion, evaluation of postfix
expression, Recursion - Factorial, GCD, Fibonacci Sequence, Tower of Hanoi, Ackerman's
function.
Queues: Definition, Array Representation, Queue Operations, Circular Queues, Circular queues
using Dynamic arrays, Dequeues, Priority Queues, A Mazing Problem. Multiple Stacks and Queues.
Programming Examples.

Stack
Stack Definition and Examples

 Stack is an ordered list in which insertions (also called push) and deletions (also called pops )
are made at one end called the top.
 Given a stack S = (a0, ...., an-1), we say that a0 is the bottom element, an-1 is the top
element,and ai is on top of element ai-1, 0 < i < n.
 Since the last element inserted into a stack is the first element removed, a stack is also known
as a Last-In-First-Out (LIFO) list.

Illustration of stack operations

Fig: Illustration of the push and pop operations

Implementation of stack

Stack is implemented by using a one-dimensional array, stack [MAX_STACK_SIZE], where MAX

is the maximum number of entries.

 The first, or bottom, element of the stack is stored in stack [0], the second in stack [1], and the
ith in stack [i-1].
 Variable top points to the top element in the stack.
 Top= -1 to denote an empty stack.

ADTStack is
objects: a finite ordered list with zero or more elements.

functions: for all stack∈Stack, item∈element, maxStackSize∈ positive integer

Dept. of ISE, SVIT Page 1

18CS32 DS Notes

Stack CreateS(maxStackSize) ::= create an empty stack whose maximum size is

maxStackSize
BooleanIsFull(stack, maxStackSize) if (number of elements in stack == maxStackSize)
::= returnTRUE
else returnFALSE
StackPush(stack, item) ::= if (IsFull(stack)) stackFull
else insert item into top of stack and return
BooleanIsEmpty(stack) ::= if (stack ==
CreateS(maxStackSize))
returnTRUE
else returnFALSE
ElementPop(stack) ::= if (IsEmpty(stack)) return
else remove and return the element at the top of the stack.

Array Implementation of a stack of integers

}#include<stdio.h>
#define MAX 10
int top= -1,stack[MAX];

void push(int item)

{
if (top==MAX-1)
printf("Stack Overflow\n");
else
stack[++top]=item;
}

int pop()
{
int itemdel;
if (top==-1)
return 0;
else
{
itemdel=stack[top--];
return itemdel;
}
}

void display()
{
int i;
if(top==-1)
printf("Stack Empty\n");
else
{
printf("Elements Are:\n");
for(i=top;i>=0;i--)

Dept. of ISE, SVIT Page 2

18CS32 DS Notes

printf("%d\n",stack[i]);
}
}

void main()
{
int ch,item,num,itemdel;
while(1)
{
printf("\nEnter the Choice\n1.Push\n2.Pop\n3.Display\n4.Exit\n");
scanf("%d",&ch);
switch(ch)
{
case 1: printf("Enter item to be inserted\n");
scanf("%d",&item);
push(item);
break;

case 2: itemdel=pop();
if(itemdel)
printf("\n Deleted Item is:%d\n",itemdel);
else
printf("Stack Underflow\n");
break;
case 3: display();
break;
case 4: exit(0);
}
}

2.1.3 Stacks Using Dynamic Arrays

If we do not know the maximum size of the stack at compile time, space can be allocated for the
elements dynamically at run time and the size of the array can be increases as needed.

Creation of stack: Here the capacity of the stack is taken as 1. The value of the capacity can be altered
specific to the application

StackCreateS() ::=

int *stack
Stack=(int*)malloc(stack, sizeof(int));
int capacity = 1;
int top = -1;

BooleanIsEmpty(Stack) ::= top < 0;

BooleanIsFull(Stack) ::= top >= capacity-1;

Dept. of ISE, SVIT Page 3

18CS32 DS Notes

The function push remains the same except that MAX_STACK_SIZE is replaced with capacity

void push(element item)

{
if (top >=capacity-1)
stackFull();
stack[++top] = item;
}

The code for the pop function remains unchanged element

pop()
{/* delete and return the top element from the stack */
if (top == -1)
return stackEmpty(); /* returns an error key */
return stack[top--];
}

Stackfull with Array doubling:The code for stackFull is changed. The new code for stackFull
attempts to increase the capacity of the array stack so that we can add an additional element to the
stack. In array doubling, the capacity of the array is doubled whenever it becomes necessary to increase
the capacity of an array.

void stackFull()
{
stack=(int*)realloc(stack, 2 * capacity * sizeof(int))
capacity =capacity * 2;
}

Analysis

 In the worst case, the realloc function needs to allocate 2*capacity *sizeof (*stack) bytes of
memory and copy capacity*sizeof (*stack)) bytes of memory from the old array into the new
one.
 Under the assumptions that memory may be allocated in O(1) time and that a stack element
can be copied in O(1) time, the time required by array doubling is O(capacity). The total time
spent in array doubling is of O(n) where n is the total number of push operations.
 Hence even with the time spent on array doubling in the total time of push over all n pushes in
O(n). This conclusion is valid even the stack array is resized by a factor c>1.

Application of stack

 Conversion of Expression
 Evaluation of expression
 Recursion

Dept. of ISE, SVIT Page 4

18CS32 DS Notes

Infix, postfix(Suffix) and Prefix(polish)

 Expression is a collection of operands and operators

 An expression can be represented in three different ways.
 Infix expression: operators are in between the two operands . Example a+b
 Prefix expression: operators are present before the operands. Example +ab
 Postfix expression: operators are present after the operands. Example ab+
 The prefixes “pre”, “post”, and “in” refer to the relative position of the operator with respect
to the two operands.

To convert an expression from infix to prefix or postfix we follow the rules of precedence.
 Precedence : The order in which different operators are evaluated in an expression is called
precendence
 Associativity : The order in which operators of same precedence are evaluated in an expression
is called Associativity.

The operators are listed in the order of higher precedence down to lower precedence

Operator Associativity
--,++ left-to-right
Unary operators ,!,-,+, &, *,sizeof Right to left
*,/,% left-to-right
+,- left-to-right

Converting an expression from infix to postfix

The operands in the infix and the postfix expression are in the same order. With respect to operators ,
precedence of operators plays an important role in converting an infix expression to postfix expression.
We make use of the stack to insert the operators according to their precedence.

The following operations are performed to convert an infix expression to postfix.

 Scan the symbol character by character

o If the symbol is an operand place it in the postfix string
o If the symbol is an opening parenthesis push it on to the stack
o If the symbol is a closing parenthesis pop the contents of the stack until we see an
opening parenthesis and place it in the postfix string. The opening parenthesis and the
closing parenthesis is not placed in the postfix string.
o If the symbol is an operator and if the precedence of the input symbol is more than the
precedence of the symbol on top of the stack, then the operator is pushed on to the
stack. If the precedence of the input symbol is lesser than the symbol on top of the stack
we pop each such operators and place it in the postfix string

Dept. of ISE, SVIT Page 5

18CS32 DS Notes

Algorithm Polish(Q,P)

Suppose Q is an arithmetic expression written in infix notation. This algorithm finds the equivalent
Postfix expression P.

1. Push ‘(’ on to STACK to identify the end of the stack

2. Scan Q from Left to right and repeat steps 3 to 6 for each character of Q until the end of the
string
3. If an operand is encountered add it to P
4. If a left parenthesis is encountered ,push it to onto STACK.
5. If an operator  is encountered then
a. Repeatedly pop each operator that has equal or higher precedence and add to P.
b. Add  to Stack
6. If a right Parenthesis is encountered, then
a. Repeatedly pop from stack and add to P each operator on top of stack until until a left
parenthesis is encountered.
b. Remove the left Paranthesis.[ do not add left parenthesis to stack]
[End of If Structure.]

[End of Step 2 loop]

7. Repeatedly pop stack until it is empty and add to P

8. Exit

Function to convert an infix expression to postfix

Assume the stack and the top is declared globally

char s[25];
int top=-1;

int precd(char op)

{
int r;
switch(op)
{
Case ‘^’:
Case ‘$’ r=3; break;
case '*':
case '/': r=2;break;
case '+':
case '-': r=1;break;
case '(': r=0;break;
case '#': r=-1;break;
}
return(r);
}

void infix_postfix(char infix[],char postfix[])

{
int i,p=0;

Dept. of ISE, SVIT Page 6

18CS32 DS Notes

char symbol,item;
push('#');
for (i=0;infix[i]!='\0';i++)
{
symbol=infix[i];
switch(symbol)
{
case '(': push(symbol);
break;

case ')':item=pop();
while(item!='(')
{
postfix[p++]=item;
item=pop();
}
break;
case '+':
case '-':
case '*':
case '/':
case '%':while(precd(s[top])>=precd(symbol))
{
item=pop();
postfix[p++]=item;
}
push(symbol);
break;

case '^': while(precd(s[top])>precd(symbol))

{
item=pop();
postfix[p++]=item;
}
push(symbol);
break;
default: postfix[p++]=symbol;
break;
}
}
while(top>0)
{
item=pop();
postfix[p++]=item;
}
postfix[p]='\0';
}

Dept. of ISE, SVIT Page 7

18CS32 DS Notes

Example: Translation of the infix string a*(b+c)*d to postfix

Infix Stack Postfix

Token [0] [1] [2] [3]
a # a
* # * a
( # * ( a
b # * ( ab
+ # * ( + ab
c # * ( + abc
) # * abc+
* # * abc+*
d # * abc+*d
Eos(\0) # abc+*d*

Analysis: Let n be length of the infix string. (n) time is spent extracting tokens . There are two while
loop where the total time spent is (n) since the number of tokens that get stacked and unstacked is
linear in n . So the complexity of the function is (n)

Evaluating a postfix expression

Each operator in a postfix string refers to the previous two operands in the string. If we are parsing a
string, each time we read operands we push it to the stack and when we read a operator, its operands
will be the two topmost elements in the stack. We can then pop these two operands and perform the
indicated operation and push the result back to the stack so that it can be used by the next operator.

Example: Evaluation of postfix string 6 2 3 + - 3 8 2 / + * 2 $ 3 +

Token Stack content Operand1 Operand2 Result

[0] [1] [2] [3]
6 6
2 6 2
3 6 2 3
+ 6 5 2 3 5
- 1 6 5 1
3 1 3
8 1 3 8
2 1 3 8 2
/ 1 3 4 8 2 4
+ 1 7 3 4 7
* 7 1 7 7
2 7 2
$ 49 7 2 49
3 49 3
+ 52 49 3 52

Dept. of ISE, SVIT Page 8

18CS32 DS Notes

The following function evaluates a postfix expression using a stack and a stack of float elements is
declared globally

float s[25];
int top;

float Evaluate(char *postfix)

{
int i=0;
float res=0,op1,op2;
char symbol;
while(postfix[i]!=’\0’)
{
symbol=postfix[i];
if isdigit(symbol)
{
push(symbol-‘0’);
}
else
{
op2=pop();
op1=pop();
res=operation(symbol,op1,op2);
push(res);
}
}
res=pop();
return(res);
}

float operation(char op, float op1,float op2)

{
float res;
switch(op)
{
case '+': res= op1+op2;
case '-': res= op1-op2;
case '*': res= op1*op2;
case '/': res= op1/op2;
case '^': res= pow(op1,op2);
}
return (res);
}

Limitations of the program

 It does not check if the postfix expression is valid or not. If we input erroneous expression it
returns wrong result
 We cannot enter negative numbers, as the symbol to indicate negation will be misinterpreted
as subtraction operation

Dept. of ISE, SVIT Page 9

18CS32 DS Notes

Analysis: Let n be length of the postfix string then the complexity of the function is (n)

Algorithm PostfixEval(P)

This algorithm finds the VALUE of an arithmetic expression P written in postfix notation

1. Scan P from Left to righ

2. Repeats steps 3 and 4 until we reach the end of P
3. If an operand is encountered put it on stack
4. If an operator  is encountered then:
a) remove two top elements of STACK, where A is the top element and B is the next
top- element
b) Evaluate B  A
c) Place the result of (4) in STACK.
[End of If structure]
[End of step 2 Loop]
5. Set VALUE equal to the top element of STACK.
6. EXit

Recursion: Recursion is the process of defining an object in terms of a simpler case of itself.

Suppose p is a function containing either a call statement to itself (direct recursion) or a call statement
to a second function that may eventually result in a call statement back to the original function
P(indirect recursion). Then the function P is called a recursive function.

A recursive function must have the following two properties.

 There must be a certain argument called the base value for which the function will not call
itself.
 Each time the function refers to itself the argument of the function must be closer to the base
value.

Factorial function: The factorial of a number n is got by finding the product of all the number form
1 to n. ie 1*2*3…*n.. It is represented as n!

Example 4!=4*3*2*1=24

5!=5*4*3*2*1=120

0!=1

From a close observation it can be observed that 5!= 5*4! . Therefore n!=n*(n-1)!

Accordingly the factorial function can be defined as

Factorial function definition

a) If n=0, then n!=1

b) If n>0, then n!=n*(n-1)!

Dept. of ISE, SVIT Page 10

18CS32 DS Notes

 The definition is recursive since the function refers to itself for all value of n>0.
 The value of n! is explicitly given as 1 when the value of n=0 which can be taken as the base
value.
 This can be implemented by the code
factorial(int n)
{
f=1;
for(i=1;i<=n;i++)
f=f*i;
return(f)
}
This is the iterative implementation of the factorial function

The factorial function can be implemented as a recursive function.

For example
factorial (5)=5*factorial(4)
factorial (4)=4*factorial(3)
factorial (3)=3*factorial(2)
factorial(2)=2*factorial(1)

factorial(int n)
{
if (n==0 )
return(1);
else
return(n*factorial(n-1))
}

Fibonacci numbers in C

 Fibonacci sequence is a sequence of integers. 0 1 1 2 3 5 8 ….. fib(0) =0 and fib(1)=1 then

each element in this sequence is the sum of the previous two numbers.
 fib(n)=n if n=0 or if n=1
 fib(n)=fib(n-2)+ fib(n-1) if n>=2

Recursive function to generate the nth Fibonacci number

int fib(int n)
{
if (n<=1)
return(n);
else
return(fibo(n-1)+fibo(n-2));
}

Example:
Fibo(4)= fibo(3)+fibo(2)
=fibo(2)+fibo(1)+fibo(2)
=fibo(1)+fibo(0)+fibo(1)+ fibo(2)
= 1+ fibo(0)+fibo(1)+ fibo(2)
=1+0 + fibo(1)+ fibo(2)
Dept. of ISE, SVIT Page 11
18CS32 DS Notes

=1+0+1+fibo(2)
=2+ fibo(1)+ fibo(0)
=2+1+fibo(0)
=2+1+0= 3

GCD of two numbers: The function accepts two numbers as input and returns the gcd of the two
numbers
gcd(int m, int n)
{
if (n==0)
return m;
retrun(gcd(n,m%n))
}

Example:
gcd(2,0)=2
gcd(0,2)= gcd(2,0)=2
gcd(4,2)= gcd(2,0)=2
gcd(7,3)= gcd(3,1)= gcd(1,0)=1

Binary search in C
int binsearch(int *a , int key, int low, int high)
{
If (low>high)
return(-1);
mid=(low+high)/2;
if (key==a[mid])
return(mid)
else
if (key>a[mid])
return(binsearch(a,key,mid+1,high));
else
return(binsearch(a,key,low,mid-1));
}

The Tower of Hanoi problem :

 We have to move n disks from peg A to peg C using peg B as auxiliary disk.
 The disks are placed in such a way that the larger disks are always below a smaller disk.
 Only the top disk on any peg can be moved to any other peg.
 Larger disk should never rest on a smaller disk.

A recursive solution to the tower of Hanoi problem is given as follows

 To move n disks from A to c using B as auxiliary
 If n==1 move the single disk from A to C and stop
 Move the top n-1 disks form A to B using C as auxiliary
 Move the nth disk from A to C
 Move n-1 disk from B to C using A as auxiliary

Dept. of ISE, SVIT Page 12

18CS32 DS Notes

Write a program to solve the Tower of Hanoi problem using a recursive function
void tower(int n,char source,char temp,char dest)
{
if(n==1)
{
printf("Move disc 1 from %c to %c\n",source,dest);
count++;
return;
}
tower(n-1,source,dest,temp);
printf("Move disc %d from %c to %c\n",n,source,dest);
count++;
tower(n-1,temp,source,dest);
}

Void main()
{
int n,count;
printf("Enter the number of discs\n");
scanf("%d",&n);
tower(n,'A','B','C');
printf("The number of moves=%d\n",count);
}

Example: n=3 disks

Tracing of function with n=3 disks

The moves for n=3 disk is summarized below.

Move 1 from A to C
Move 2 from A to B
Move 1 from C to B
Move 3 from A to C
Move 1 from B to A
Move 2 from B to C
Move 1 from A to C

Note: Ideal number of moves to solve Tower of Hanoi is given as 2n -1 where n is the total number of
disks

Dept. of ISE, SVIT Page 13

18CS32 DS Notes

Problem solved with n=3 disks

Ackermann Function
The Ackermann function is a function with two arguments each of which can be assigned any non
negative integer 0,1,2… .......... This function finds its application in mathematical logic.
This function is defined as follows
a) If m = 0 then A(m,n) = n + 1
b) If m != 0 but n = 0 then A(m,n) = A(m - 1,1)
c) If m != 0 and n != 0 then A(m,n) = A(m - 1, A(m,n - 1))

The function is given as follows

int A(int m,int n)
{
if (m == 0)
return(n+1);
if ((m !=0) && (n== 0 ))
return(A(m-1,1));
if ((m!= 0) && (n != 0))
return(A(m-1, A(m,n-1)));
}

Example1:
A(1,2) =A(0,A(1,1))
=A(0,A(0,A(1,0)))
= A(0,A(0,A(0,1))
=A(0,A(0,2)
=A(0,3)
4

Example 2:

A(1,3) = A(0,A(1,2))
=A(0,A(0,A(1,1)))
=A(0,A(0,A(0,A(1,0))))
=A(0,A(0,A(0,A(0,1))))
=A(0,A(0,A(0,2)
=A(0,A(0,3)
=A(0,4)
5

Dept. of ISE, SVIT Page 14

18CS32 DS Notes

Disadvantages of using Recursion

 Non recursive version of the program is more efficient when compared to recursive version in
terms of time and space
 Non recursive versions do not have the overhead of entering and exiting from the block.
 In recursive program the local variables have to be maintained using a stack,which can be
avoided in an iterative(non recursive) version

Advantage of using Recursion

 Recursive program is the most natural and logical way of solving some of the problems
 If a stack can be eliminated in a recursive program without having any local variables then
they can be as fast its non recursive version,

Difference between iterative and recursive functions

Iterative Recursive
Implemented using looping Implemented using recursive calls to
statements functions
Executes faster Takes more time to execute
Memory utilization is Less Memory utilization is more
Lines of code are more Lines of code are lesser
Does not require stack Implementation requires stack

Queues:
A queue is an ordered list in which insertions and deletions take place at different ends. The end at
which new elements are added is called the rear, and that from which old elements are deleted is called
the front. Queues are also known as First-In-First-Out (FIFO) lists.

The ADT specification of the queue

objects: a finite ordered list with zero or more elements.
functions: for all queue∈Queue, item∈element, maxQueueSize∈ positive integer

Queue CreateQ(maxQueueSize) ::= create an empty queue whose maximum size is

maxQueueSize
BooleanIsFullQ(queue, if (number of elements in queue == maxQueueSize)
maxQueueSize) ::= returnTRUE
else returnFALSE

QueueAddQ(queue, item) ::= if (IsFullQ(queue)) queueFull

else insert item at rear of queue and return queue

BooleanIsEmptyQ(queue) ::= if (queue == CreateQ(maxQueueSize))

returnTRUE
else return FALSE

Element DeleteQ(queue) ::= if (IsEmptyQ(queue)) return

else remove and return the item at front of queue.

Dept. of ISE, SVIT Page 15

18CS32 DS Notes

Example
Initially f =-1 r=-1 queue empty

Element
index [0] [1] [2] [3] [4] [5]

f=-1
Insert 3
Element 3

index [0] [1] [2] [3] [4] [5]

,r

f=-1
Insert 5
Element 3 5

index [0] [1] [2] [3] [4] [5]

r

f=-1
Insert 7
Element 3 5 7

Index [0] [1] [2] [3] [4] [5]

r

delete
Element 5 7

Index [0] [1] [2] [3] [4] [5]

F r

Deleted item =3

C implementation of queues for an integer array: A queue can be represented by using an array to
hold the elements of the array and to use two variables to hold the position of the first and last element
of the queue.

#define size 10
int q[size];
int front=-1 ,rear=-1;
Dept. of ISE, SVIT Page 16
18CS32 DS Notes

 The condition where the queue is empty is called queue underflow.

 When we define the size of the array, we cannot insert elements more than the size of the array,
this condition where the queue is full is called as queue overflow.

Insert operation
The insert operation first checks for queue overflow. If the queue is not full it inserts one element into
the queue at the rear.
Void insert(int item)
{
If rear==size-1)
Printf(“queue overflow”);
else
{
rear++;
q[rear]=item;
}
}

Delete operation: Delete operation checks for queue underflow condition and if the queue is not
empty it will remove the element at the front.
int delete()
{
int itemdel;
if (front ==rear)
{
Printf(“queue underflow”);
return(0);
}
else
{
front++
itemdel=q[front];
return(itemdel);
}
}

Display operation: The display operation will display the elements of the queue if the queue is not
empty.

void display(s)
{
if (front==rear)
printf(“queue empty”);
else
{
for(i=front+1;i<=rear;i++)
printf(“%d”,q[i]);
}
}

Dept. of ISE, SVIT Page 17

18CS32 DS Notes

Disadvantage of linear queue: The following example illustrates the disadvantage of linear queue

f r Q[0] Q[1] Q[2] Q[3] Q[4] Comment

- -1 Queue is empty
-1 0 2 Insert 2
-1 1 2 3 Insert 3
-1 2 2 3 4 Insert 4
-1 3 2 3 4 5 Insert 5
-1 4 2 3 4 5 6 Insert 6
0 4 3 4 5 6 Delete- item deleted=2
1 4 4 5 6 Delete- item deleted=3
Insert 3(disadvantage)
Queue full. Element cannot
be inserted since rear= size-1

Even if the queue is empty since the value of rear= size-1 elements cannot be inserted into the queue.
This is the disadvantage of linear queue.

Circular Queue: In a circular queue the queue is arranged in a circular fashion. It is a

moreefficient representation of queue.

Example:

Fig: Implementation of circular queue for an array of integers

Modification in code to implement circular queue

 Initial value of front and rear=0
 To advance the pointer from size-1 to 0 the code rear++ is modified to rear=(rear +1)%size
and the code front++ is modified to front=(front+1)%size

Dept. of ISE, SVIT Page 18

18CS32 DS Notes

 Initially when front=0 rear=0 i.e when front == rear the queue is empty now after 6 insertions
are made again fron=0 and rear= 0 that is the queue is full. So, we cannot distinguish between
an empty and a full queue.
 To avoid the resulting confusion, the value of the rear is incremented before we check for the
condition front == rear for queue overflow.

#define MAX_QUEUE_SIZE 6
int q[size];
int front=0 ,rear=0;

Insert operation: The insert operation first checks for queue overflow. If the queue is not full it inserts
one element into the queue at the rear.

void addq(element item)

{
if (front == (rear+1) % MAX_QUEUE_SIZE )
printf(“Queue full”);
else
{
rear= (rear+1) % MAX_QUEUE_SIZE
queue[rear] = item;
}
}

Delete operation: Delete operation checks for queue underflow condition and if the queue is not
empty it will remove the element at the front.

element deleteq()
{
element item;
if (front == rear)
return queueEmpty();
front = (front+1) % MAX_QUEUE_SIZE;
return queue[front];
}

Circular Queues Using Dynamically Allocated Arrays

 To add an element to a full queue, we must first increase the size of this array using a function
such as realloc.
 As with dynamically allocated stacks, we use array doubling. However, it isn't sufficient to
simply double array size using realloc.
 Consider the full queue . This figure shows a queue with seven elements in an array whose
capacity is 8. To visualize array doubling when a circular queue is used, the array is flattened
out as shown in the array of Figure (b).

Dept. of ISE, SVIT Page 19

18CS32 DS Notes

Figure (c) shows the array after array doubling by realloc.

To get a proper circular queue configuration, The number of elements copied can be limited to capacity
- 1 by customizing the array doubling code so as to obtain the configuration as shown below.

This configuration may be obtained as follows:

1. Create a new array newQueue of twice the capacity.
2. Copy the second segment (i.e., the elements queue [front + 1] through queue [capacity -
1 ]) to positions in newQueuebeginning at 0.
3. Copy the first segment (i.e., the elements queue [0] through queue [rear]) to positions
in newQueue beginning at capacity-front-1.

Function to add to a circular queue has no change

void addq(int item)
{
rear = (rear+1) % capacity;
if (front == (rear+1) % capacity)
queueFull(); /* double capacity */
else
{
rear = (rear+1) % capacity;
queue[rear] = item;
}
}

Dept. of ISE, SVIT Page 20

18CS32 DS Notes

Function to double queue capacity

void queueFull()
{
int* newQueue;
newQueue=(int*)malloc( 2 * capacity * sizeof(int));
/* copy from queue to newQueue */
int start = (front+1) % capacity;
if (start < 2)
copy(queue+start, queue+start+capacity-1, newQueue);
else
{ /* queue wraps around */
copy(queue+start, queue+capacity, newQueue);
copy(queue, queue+rear+1, newQueue+capacity-start);
}

/* switch to newQueue */
front= 2 * capacity - 1;
rear = capacity - 2;
capacity *= 2;
free(queue);
queue = newQueue;
}

The function copy(a,b,c) copies elements from locations a through b-1 to locations beginning at c

Deques: A deque (pronounced either as deck or dequeue) is a linear list in which elements
can be added or removed at either end but not in the middle. The term deque is a contraction
of the namedouble ended queue.

Representation: It is represented as a circular array deque with pointers left and right, which point to
the two ends of the queue. It is assumed that the elements extend from the left end to the right end in
the array. The term circular comes from the fact that DEQUE[0] comes after DEQUE[n-1] in the array.

Example1:
Left=2 A B C
Right=4

[0] [1] [2] [3] [4] [5] [6]

Example2:
Left=5 A B D E
Right=1
[0] [1] [2] [3] [4] [5] [6]

There are two types of deque:

 Input restricted:- insertion is allowed only at one end, deletion is allowed at both ends.
 Output restricted: deletion is allowed only at one end, insertion is allowed at both ends

Dept. of ISE, SVIT Page 21

18CS32 DS Notes

Priority queue: A priority queue is a collection of elements such that each element has been
assigned a priority such that the order in which the elements are deleted and processed comes
from the following rules.
1. An element of higher priority is processed before any element of lower priority.
2. Two elements with the same priority are processed according to the order in which they were
added to the queue.

Example: Time sharing system: programs of higher priority are processed first and programs with the
same priority form a standard queue.

Representation using multiple queue: Use a separate queue for each level of priority. Each queue
will appear in its own circular array and must have its own pair of pointers, front and rear. If each
queue is allocated the same amount of space, a two dimensional array can be used instead of the linear
arrays.

Example : Consider the queue given below with the jobs and its priorities and its representation. A
job with priority 1 is considered to have the highest priority

J1 1
J2 1
J3 2
J4 4
J5 4
J6 6

The queue is represented as a two dimensional array as shown below

Front rear 1 2 3 4 5 6
1 1 2 1 J1 J2
2 2 3 2 J3
3 3
4 4 5 4 J4 J5
5 5
6 6 6 6 J6

Delete operation
Algorithm:
1. Find the smallest k such that front[k]!=rear[k] ie Find the first non empty queue
2. Delete the process at the front of the queue
3. Exit

Insert operation
Algorithm: this algorithm adds an ITEM with priority number P to a priority queue maintained by a
two dimensional array
1. Inset ITEM as the rear element in row P-1 of queue
2. exit

Dept. of ISE, SVIT Page 22

18CS32 DS Notes

Multiple Stacks and Queues

 If there is a single stack, the starting point is top=-1 and maximum size is SIZE-1
 If there are two stacks to be represented in a single array then we use stack [0] for the bottom
element of the first stack, and stack[MEMORY_SIZE - 1] for the bottom element of the second
stack. The first stack grows toward stack[MEMORY_SIZE - 1] and the second grows toward
stack[0]. With this representation, we can efficiently use all the available space.
 Representing more than two stacks within the same array poses problems since we no longer
have an obvious point for the bottom element of each stack. Assuming that we have n stacks,
we can divide the available memory into n segments. This initial division may be done in
proportion to the expected sizes of the various stacks, if this is known. Otherwise, we may
divide the memory into equal segments.
 Assume that i refers to the stack number of one of the n stacks.To establish this stack, we must
create indices for both the bottom and top positions of this stack.The convention we use is that
o bottom [i], 0 ≤ i < MAX_STACKS, points to the position immediately to the left of the
bottom element of stack i.
o top[i], 0 ≤ i < MAX_STACKS points to the top element.
o Stack i is empty if bottom[i] = top[i].

The relevant declarations are:

#define MEMORY_SIZE 100 /* size of memory */
#define MAX_STACKS 10 /* max number of stacks */
/* global memory declaration */
element stack[MEMORY_SIZE];
int top[MAX_STACKS];
int bottom[MAX_STACKS];
int n; /* number of stacks entered by the user */

To divide the array into roughly equal segments we use the following code:

top[0] = bottom[0] = -1;

for (j = 1; j < n; j++)
top[j] = bottom[j] = (MEMORY_SIZE/n)*j-1;
bottom[n] = MEMORY_SIZE-1;

Stack i can grow from bottom[i] + 1 to bottom [i + 1 ] before it is full. Boundary for the last stack,
boundary [n] is set to MEMORY_SIZE- 1

Initial configuration of the stack is shown below m is the size of the memory

Fig: All stacks are empty and roughly divided equally

Dept. of ISE, SVIT Page 23

18CS32 DS Notes

Function to add an item to the ith stack

void push(int i, element item)

{
if (top[i] == bottom[i+1])
stackFull(i);
stack[++top[i]] = item;
}

Function to delete an item from the ith stack

element pop(int i)
{
if (top[i] == bottom[i])
return stackEmpty(i);
return stack[top[i]--];
}

Mazing Problem

Representation: Maze is represented as a two dimensional array in which zeros represent the open
paths and ones the barriers. The location in the maize can be determined by the row number and
column number Figure below shows a simple maze.

From each location there are eight directions of movement N, NE,E,SE,S,SW,W,NW.

Dept. of ISE, SVIT Page 24

18CS32 DS Notes

If the position is on the border then there are less than eight directions. To avoid checking for border
conditions the maze can be surrounded by a border of ones. Thus an m*p maize will require an
(m+2)*(p+2) array the entrance is at position [1][1] and exit is at [m][p]. The possible direction to
move can be predefined in an array move as shown below where the eight possible directions are
numbered from 0 to 7. For each direction we indicate the vertical and horizontal offset.

typedef struct offset

{
Int vert;
Int horiz;
};

Offset move[8];

Table of moves: The array moves is initialized according to the table given below.

Name Dir Move[dir].vert Move[dir].horiz

N 0 -1 0
NE 1 -1 1
E 2 0 1
SE 3 1 1
S 4 1 0
SW 5 1 -1
W 6 0 -1
NW 7 -1 -1

As we move through the maze, we may have the choice of several directions of movement. Since we
do not know the best choice we save our current position and arbitrarily pick a possible move. By
saving the current position we can return to it and try another path. A second two dimensional array
can be maintained to keep track of the visited locations. The maze can be implemented by making use
of a stack where the element is defined as follows.

typedef struct element

{
int row;
int col;
int dir;
};

Dept. of ISE, SVIT Page 25