Data structures and Applications 18CS32

MODULE-2
STACKS AND QUEUES

TOPICS
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, de queues, Priority Queues, A Mazing Problem. Multiple Stacks and Queues.
Programming Examples.

STACK
“Stack is an ordered collection of elements or items of same type can be inserted and deleted at only
one end called Top of stack”. (OR)
STACK is an ordered-list in which insertions (called push) and deletions (called pop) are
made at one end called the top. Since last element inserted into a stack is first element removed, a
stack is also known as a LIFO list (Last In First Out). Stack can be implemented using the Linked List
or Array.
Stack belongs to non-primitive linear data structure.
Consider a stack s=(a0,a1,….,an-1).here a0 is the bottom element , an-1 is the top element and
generally, element ai is on the top of element ai-1,0<i<n.
Top an-1
an-2
…..
….
a1
a0
Figure 1a: Stack S
If A, B, C, D, E are the elements added into stack in that order then E is the first element to be
deleted. Figure shows insertion and deletion of elements from the stack.

Figure 1b: Insertion and deletion of elements from the stack

Page 1
 Data structures and Applications 18CS32

Thus, Stack is LIFO Structure i,e Last in First Out as shown in figure 1. Example, we can place or
remove a card or plate from top of the stack only.

Figure 2: stack of cards and plates

Figure 3: Stack representation

Figure 2 shows the example stacks and figure 3 shows stack representation indicting LIFO operation.
EXAMPLES FOR STACKS:- a stack of coins, a stack of plates , a stack of books , a stack of flooded
towels , phone call log, tennis balls in a container, undo and redo operations etc.

2.1 SYSTEM STACK

 A stack used by a program at run-time to process function-calls is called system-stack (Fig. 4).
• When functions are invoked, programs create a stack-frame (or activation-record) & place the stack-
frame on top of system-stack
• Initially, stack-frame/activation record for invoked-function contains only pointer to previous
stack-frame & return-address.
• The previous stack-frame pointer points to the stack-frame of the invoking-function, while return-
address contains the location of the statement to be executed after the function terminates.

Page 2
 Data structures and Applications 18CS32

• If one function invokes another function, local variables and parameters of the invoking-function are
added to its stack-frame.
• A new stack-frame is then created for the invoked-function & placed on top of the system-stack.
• When this function terminates, its stack-frame is removed (and processing of the invoking-function,
which is again on top of the stack, continues).
• Frame-pointer(fp) is a pointer to the current stack-frame.

Figure 4: System stack before and after function a1 invoked

STACK ADT

Page 3
 Data structures and Applications 18CS32

2.2 STACK BASIC OPERATIONS

Stack operations may involve initializing the stack, using it and then de-initializing it. Apart from
these basic stuffs, a stack is used for the following two primary operations −
 push() − pushing (storing / inserting) an element on the stack.
 pop() − removing (accessing/ deleting) an element from the stack.
When data is pushed onto stack, to use a stack efficiently we need to check status of stack as well.
For the same purpose, the following functionality is added to stacks
 peek() − get the top data element of the stack, without removing it.
 isFull() − check if stack is full or overflow.
 isEmpty() − check if stack is empty or underflow.
At all times, we maintain a pointer to the last pushed data on the stack. As this pointer always
represents the top of the stack, hence named top. The top pointer provides top value of the stack without
actually removing it.
PUSH Operation
The process of putting a new data element onto stack is known as PUSH Operation. Push operation
involves series of steps −
 Step 1 − Check if stack is full.
 Step 2 − If stack is full, produce error and exit.
 Step 3 − If stack is not full, increment top to point next empty space.
 Step 4 − Add data element to the stack location, where top is pointing.
 Step 5 − return success.
if linked-list is used to implement stack, then in step 3, we need to allocate space dynamically. Push
operation is shown in figure 5.

Figure 5: Push operation

Page 4
 Data structures and Applications 18CS32

POP Operation
Accessing the content while removing it from stack, is known as pop operation. In array
implementation of pop() operation, data element is not actually removed, instead top is decremented to a
lower position in stack to point to next value. But in linked-list implementation, pop() actually removes
data element and deallocates memory space. Pop operation is shown in figure6.
A POP operation may involve the following steps −
 Step 1 − Check if stack is empty.
 Step 2 − If stack is empty, produce error and exit.
 Step 3 − If stack is not empty, access the data element at which top is pointing.
 Step 4 − Decrease the value of top by 1.
 Step 5 − return success.

Figure 6: pop operation

IMPLEMENTATION OF STACK OPERATIONS
The easiest way to implement stack ADT is using one-dimensional array.
stack[ MAX_STACK_SIZE],where MAX_STACK_SIZE =maximum number of entries in the stack.
• The first element of the stack is stored in stack [0],stack[1] is second element and stack[i-1] is the ith
element.
• ‟top‟ points to the top element in the stack (top=-1 to denote an empty stack).
• The CreateS() function can be implemented as follows and it creates stack of size 100.

Page 5
 Data structures and Applications 18CS32

Function push/add() checks to see if the stack is full. If it is, it calls stack_full(), which prints an
error message and terminates execution. When the stack is not full, we increment top and assign item to
stack[top].

Function pop/delete() checks to see if the stack is empty using top . If top reaches -1,then it
calls stack_empty(), which prints an error message and terminates execution. When the stack is not
empty, we return the top most element stack[top] and decrement top.
void stack_full()
{ printf(stderr,”stack is full, can‟t add element”);
exit(EXIT_FAILURE);
}
void stack_empty ()
{ printf(stderr,”stack is empty, can‟t delete element”);
exit(EXIT_FAILURE);
}

2.3 STACK USING DYNAMIC ARRAYS

Shortcoming of static stack implementation: is the need to know at compile-time, a good bound
(MAX_STACK_SIZE) on how large the stack will become.
• This shortcoming can be overcome by using a dynamically allocated array for the elements & then
increasing the size of the array as needed Initially, capacity=1 where capacity=maximum no. of stack-
elements that may be stored in array.
• The CreateS() function can be implemented as follows

Page 6
 Data structures and Applications 18CS32

void stack_full()
{ printf(stderr,”stack is full, can‟t add element”);
exit(EXIT_FAILURE);
}
void stack_empty ()
{ printf(stderr,”stack is empty, can‟t delete element”);
exit(EXIT_FAILURE);
}
Once the stack is full, realloc() function is used to increase the size of [Link] array-doubling,
we double array-capacity whenever it becomes necessary to increase the capacity of an array.
ANALYSIS
In 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. The total time

Page 7
 Data structures and Applications 18CS32

spent over all array doublings = O(2k) where capacity=2k. Since the total number of pushes is more than
2k-1, the total time spend in array doubling is O(n) where n=total number of pushes.

2.4 APPLICATIONS OF STACKS

1. Stack is used by compilers to check for balancing of parentheses, brackets and braces.
2. Stack is used to evaluate a postfix expression.
3. Stack is used to convert an infix expression into postfix/prefix form.
4. In recursion, all intermediate arguments and return values are stored on the processor‟s stack.
5. During a function call the return address and arguments are pushed onto a stack and on return
they are popped off.
EXPRESSIONS
 An algebraic expression is a legal combination of operators and operands. “The sequence of
operators and operands that reduces to a single value after evaluation is called Expression”.
 Operand is the quantity on which a mathematical operation is performed. Operand may be a
variable like x, y, z or a constant like 5, 4, 6 etc.
 Operator is a symbol which signifies a mathematical or logical operation between the operands.
Examples of familiar operators include +, -, *, /, ^ etc.
An algebraic expression can be represented using three different notations. They are infix,
postfix and prefix notations:
 Infix: It is the form of an arithmetic expression in which we fix (place) the arithmetic operator in
between the two operands. Example: (A + B) * (C - D)
 Prefix: It is the form of an arithmetic notation in which we fix (place) the arithmetic operator
before (pre) its two operands. The prefix notation is called as polish notation (due to the polish
mathematician Jan Lukasiewicz in the year 1920). Example: * + A B – C D
 Postfix: It is the form of an arithmetic expression in which we fix (place) the arithmetic operator
after (post) its two operands. The postfix notation is called as suffix notation and is also referred
to reverse polish notation. Example: A B + C D - *
The three important features of postfix expression are:
 Postfix expression is parenthesis-free expression.
 While evaluating the postfix expression the precedence and Associativity of the operators is no
longer required
 all expressions given to the system , will be converted into postfix form by the complier since it
is easy and more efficient to evaluate.

Page 8
 Data structures and Applications 18CS32

Converting expressions using Stack:

Let us convert the expressions from one type to another. These can be done as follows
1. Infix to postfix
2. Infix to prefix
3. Postfix to infix
4. Postfix to prefix
5. Prefix to infix
6. Prefix to postfix
We consider six binary arithmetic operations: +, -, *, / and % or ^ (power). For these binary operations,
the following in the order of precedence (highest to lowest):
Operators precedence
^ 4
* / % 3
+ - 2
# ( 1

CONVERSION FROM INFIX TO POSTFIX

Procedure to convert from infix expression to postfix expression is as follows:
1. Scan the infix expression from left to right.
2. If the scanned symbol is left parenthesis, push it onto the stack.
3. If the scanned symbol is an operand, then place directly in the postfix expression (output).
4. If the symbol scanned is a right parenthesis, then go on popping all the items from the stack and
place them in the postfix expression till we get the matching left parenthesis.
5. If the scanned symbol is an operator, then go on removing all the operators from the stack and
place them in the postfix expression, if and only if the precedence of the operator which is on the
top of the stack is greater than (or greater than or equal) to the precedence of the scanned
operator and push the scanned operator onto the stack otherwise, push the scanned operator onto
the stack.

Page 9
 Data structures and Applications 18CS32

Example 1:
Convert ((A – (B + C)) * D) ↑ (E + F) infix expression to postfix form:

Page 10
 Data structures and Applications 18CS32

Example 2:
Convert the following infix expression A + B * C – D / E * H into its equivalent postfix expression

EVALUATION OF POSTFIX EXPRESSION

The postfix expression is evaluated easily by the use of a stack. When a number is seen, it is
pushed onto the stack; when an operator is seen, the operator is applied to the two numbers that are
popped from the stack and the result is pushed onto the stack. When an expression is given in postfix
notation, there is no need to know any precedence rules; this is our obvious advantage. Although infix
notation is the most common way of writhing expressions, it is not the one used by compilers to evaluate
expressions. Instead compilers typically use a parenthesis-free postfix notation.
Steps for evaluating postfix expression
1) Scan the symbol from left to right.
2) If the scanned-symbol is an operand, push it on to the stack.
3) If the scanned-symbol is an operator, pop two operands from the stack. The first popped operand
acts as operand2 and the second popped operand act as operand [Link] perform the indicated
operation and Push the result on to the stack.
4) Repeat the above procedure till the end of input is encountered

Page 11
 Data structures and Applications 18CS32

Example 1:
Evaluate the postfix expression: 6 5 2 3 + 8 * + 3 + *

2.5 RECURSION
Recursion is the process of repeating items in a self-similar way. In programming languages, if a
program allows you to call a function inside the same function, then it is called a recursive call of the
function.

Page 12
 Data structures and Applications 18CS32

void recursion()
{
recursion(); /* function calls itself */
}
void main()
{
recursion();
}
The C programming language supports recursion, i.e., a function to call itself.
A recursive function is a function that calls itself during its execution.
But while using recursion, programmers need to be careful to define an exit condition from the function;
otherwise it will go into an infinite loop.
Recursive functions are very useful to solve many mathematical problems, such as calculating the
factorial of a number, generating Fibonacci series, etc.
RECURSION PROPERTIES
A recursive function can go infinite like a loop. To avoid infinite running of recursive function,
there are two properties that a recursive function must have −
 Base criteria − There must be at least one base criteria or condition, such that, when this
condition is met the function stops calling itself recursively.
 Recursive criteria − the recursive calls should progress in such a way that each time a recursive
call is made it comes closer to the base criteria.
1. FACTORIAL NUMBER
The product of the positive integers from 1 to n, inclusive is called n factorial and is usually
denoted by n!
n!=1*2*3*4*………*(n-2)*(n-1)*n.
Factorial function may be defined as
a. if n=0 then return 1
b. if n>0, then return n*(n-1)!
The following example calculates the factorial of a given number using a recursive function
#include <stdio.h>
int factorial(unsigned int n)
{
if(n <= 1)
{
return 1;
}
return n * factorial(n - 1);
}

Page 13
 Data structures and Applications 18CS32

void main()
{
int n,res;
printf(“\n enter the value for n”);
scanf(“%d”,&n);
res=factorial(n);
printf("Factorial of %d is %d\n", n, res);
}
When the above code is compiled and executed, it produces the following result − Factorial of 15 is
2004310016

2. GCD OF TWO NUMBERS

GCD is calculated by using GCD(a,b)=GCD(b,a mod b).
Euclid‟s algorithm
1. Take a and b, and calculate the remainder by performing a%b.
2. Assign the value of b to a and value of remainder to b.
3. Repeat the steps 1 & 2 until value of b becomes 0.
4. If b=0, then return value of „a‟ as the GCD value of a & b.
#include <stdio.h>
int gcd(int m, int n);
void main()
{
int a, b,res;
printf("Enter two positive integers: ");
scanf("%d %d", &a, &b);
res=gcd(a,b);
printf("G.C.D of %d and %d is %d.", n1, n2, res);
}
int gcd(int a, int b)
{
int rem;
if (b==0)
return a;
else
{
rem=a%b;
a=b;
b=rem;
return gcd(a,b);
}
Output
Enter two positive integers:
366 60
G.C.D of 366 and 60 is 6

Page 14
 Data structures and Applications 18CS32

3. FIBONACCI SERIES
The Fibonacci sequence is the sequence of integers, where each number in this sequence is the
sum of two preceding elements.
A formal definition is
a. If n=0 or 1,return n(0/1)
b. If n>1,return fib(n-1)+fib(n-2)
#include <stdio.h>
int fib(int i)
{
if(i == 0)
{
return 0;
}
if(i == 1)
{
return 1;
}
return (fib(i-1) + fib(i-2));
}
void main()
{
int i;
for (i = 0; i < 10; i++)
{
printf("%d\t", fib(i));
}
}
When the above code is compiled and executed, it produces the following result −
0 1 1 2 3 5 8 13 21 34

4. TOWER OF HANOI PROBLEM

Tower of Hanoi, is a mathematical puzzle which consists of three tower (pegs) and more than
one rings; as depicted in below figure 7

Figure 7: Tower of Hanoi

Page 15
 Data structures and Applications 18CS32

These rings are of different sizes and stacked upon in ascending order i.e. the smaller one sits
over the larger one. There are other variations of puzzle where the number of disks increase, but the
tower count remains the same.
Rules
The mission is to move all the disks to some another tower without violating the sequence of
arrangement. The below mentioned are few rules which are to be followed for tower of hanoi −
 Only one disk can be moved among the towers at any given time.
 Only the "top" disk can be removed.
 No large disk can sit over a small disk.
Here is an animated representation in figure 8 of solving a tower of hanoi puzzle with three disks
−Tower of hanoi puzzle with n disks can be solved in minimum 2n−1 steps. This presentation shows
that a puzzle with 3 disks has taken 23−1 = 7 steps.
Algorithm
To write an algorithm for Tower of Hanoi, first we need to learn how to solve this problem with lesser
amount of disks, say → 1 or 2. We mark three towers with name, source, destination and aux (only to
help moving disks). If we have only one disk, then it can easily be moved from source to destination
peg.
If we have 2 disks −
 First we move the smaller one (top) disk to aux peg
 Then we move the larger one (bottom) disk to destination peg
 And finally, we move the smaller one from aux to destination peg.
So now we are in a position to design algorithm for Tower of Hanoi with more than two disks. We
divide the stack of disks in two parts. The largest disk (nthdisk) is in one part and all other (n-1) disks
are in second part. Our ultimate aim is to move disk n from source to destination and then put all other
(n-1) disks onto it. Now we can imagine to apply the same in recursive way for all given set of disks.
So steps to follow are −
 Step 1 − Move n-1 disks from source to aux
 Step 2 − Move nth disk from source to dest
 Step 3 − Move n-1 disks from aux to dest
A recursive algorithm for Tower of Hanoi can be driven as follows −
START
Procedure tower(disk, source, dest, aux)
if n == 1, THEN
move disk from source to dest

Page 16
 Data structures and Applications 18CS32

else
tower(n - 1, source, aux, dest) // Step 1
move disk from source to dest // Step 2
tower(n - 1, aux, dest, source) // Step 3
END IF
END Procedure
STOP

PROGRAM:
#include<stdio.h>
#include<conio.h>
#include <stdio.h>
void towers(int, char, char, char);
int main()
{
int num;
printf("Enter the number of disks : ");
scanf("%d", &num);
printf("The sequence of moves involved in the Tower of Hanoi are :\n");
towers(num, 'A', 'C', 'B');
getch();
return 0;
}
void towers(int num, char source, char dest, char aux)
{
if (num == 1)
{
printf("\n Move disk 1 from peg %c to peg %c", source,dest);
return;
}
towers(num - 1, source, aux,dest);
printf("\n Move disk %d from peg %c to peg %c", num, source, dest);
towers(num - 1, aux, dest, source);
}
The below figure shows the disks movements in tower of Hanoi for 3 disks

Figure 8: Disk movements

Page 17
 Data structures and Applications 18CS32

The below figure shows the recursive function calls in tower of Hanoi for 3 disks

ACKERMANN'S FUNCTION
Ackermann–Péter function, is defined as follows for nonnegative integers m and n:

To solve A(2,1) using Ackerman‟s function: (m=2, n=1)

A(2,1) = A(1,A(2,0))
= A(1,A(1,1))
=A(1,A(0,A(1,0)))
=A(1,A(0,A(0,1)))
=A(1,A(0,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)
A(2,1) = 5
Program:-
#include<stdio.h>
int ackerman(int m, int n)
{
if(m==0)
return (n+1);
if(n==0 && m>0)
return ackerman(m-1,1);
if(m>0 && n>0)
return ackerman(m-1,ackerman(m,n-1));
}
void main()

Page 18
 Data structures and Applications 18CS32

{
int m,n;
printf(“Enter the value of m and n\n”);
scanf(“%d %d”,&m,&n);
printf(“%d”,ackerman(m,n));
}

2.6 QUEUES
Queue is an ordered-list in which insertions & deletions take place at different ends. The end at
which new elements are added is called the rear &the end from which old elements are deleted is called
the front. Since first element inserted into a queue is first element removed, queues are known as FIFO
lists.
(OR)
Queue is an abstract data structure, somewhat similar to Stack. In contrast to Queue, queue is opened at
both ends. One end is always used to insert data (enqueue) and the other is used to remove data
(dequeue). Queue follows First-In-First-Out methodology, i.e., the data item stored first will be accessed
first.(as shown in figure 9)

Figure 9: Queue insertion and deletion

Figure 10: Real time example for queue

A real world example of queue (figure 10)can be a single-lane one-way road, where the vehicle enters
first, exits first. More real-world example can be seen as queues at ticket windows & bus stops.
Queue, queue can also be implemented using Array, Linked-list, Pointer and Structures. For the sake of
simplicity , queue is implemented using one-dimensional array as shown in figure11.

Figure 11: Queue representation

Page 19
 Data structures and Applications 18CS32

ADT QUEUE

ADT:-QUEUE
APPLICATIONS OF QUEUE
Queue, as the name suggests is used whenever we need to have any group of objects in an order in
which the first one coming in, also gets out first while the others wait for there turn, like in the following
scenarios :
1. Serving requests on a single shared resource, like a printer, CPU task scheduling etc.
2. In real life, Call Center phone systems will use Queues, to hold people calling them in an order, until
a service representative is free.
3. Handling of interrupts in real-time systems. The interrupts are handled in the same order as they
arrive, First come first served
2.7 QUEUE BASIC OPERATIONS
Queue operations may involve initializing or defining the queue, utilizing it and then completing erasing
it from memory. Here we shall try to understand basic operations associated with queues −
 enqueue() − add (store) an item to the queue.

 dequeue() − remove (access) an item from the queue.

Page 20
 Data structures and Applications 18CS32

Few more functions are required to make above mentioned queue operation efficient. These are −
 peek() − get the element at front of the queue without removing it.

 isfull() − checks if queue is full.

 isempty() − checks if queue is empty.

In queue, we always dequeue (or access) data, pointed by front pointer and while enqueing (or storing)
data in queue we take help of rear pointer.
peek() Like Queues, this function helps to see the data at the front of the queue. Code for the peek()
function −
int peek()
{
return queue[front];
}
isfull()
As we are using single dimension array to implement queue, we just check for the rear pointer to reach
at MAXSIZE to determine that queue is full. In case we maintain queue in a circular linked-list, the
algorithm will differ. Implementation of isfull() function in C programming language −
bool isfull()
{
if(rear == MAXSIZE - 1)
return true;
else
return false;
}
isempty()
Here's the C programming code −
bool isempty()
{
if(front < 0 || front > rear)
return true;
else
return false;
}
Enqueue (Insert) Operation
As queue maintains two data pointers, front and rear, its operations are comparatively more difficult to
implement than Queue.(as shown in figure 12)
The following steps should be taken to enqueue (insert) data into a queue −
 Step 1 − Check if queue is full.

Page 21
 Data structures and Applications 18CS32

 Step 2 − If queue is full, produce overflow error and exit.

 Step 3 − If queue is not full, increment rear pointer to point next empty space.

 Step 4 − Add data element to the queue location, where rear is pointing.

 Step 5 − return success.

Figure 12: Queue Enqueue

Implementation of enqueue() in C programming language −
void enqueue(int data)
{
if(isfull())
return 0;
rear = rear + 1;
queue[rear] = data;
}
Dequeue (Delete) Operation
Accessing data from queue is a process of two tasks − access the data where front is pointing and
remove the data after access. (As shown in figure 13).The following steps are taken to perform dequeue
operation −
 Step 1 − Check if queue is empty.
 Step 2 − If queue is empty, produce underflow error and exit.
 Step 3 − If queue is not empty, access data where front is pointing.
 Step 4 − Increment front pointer to point next available data element.
 Step 5 − return success.

Figure 13: Queue Dequeue

Page 22
 Data structures and Applications 18CS32

Implementation of dequeue() in C programming language −

int dequeue()
{
if(isempty())
return 0;
int data = queue[front];
front = front + 1;
return data;
}
IMPLEMENTATION OF QUEUE
The implementation of queue is given below

JOB SCHEDULING
Queues are used for the creation of a job-queue by an operating-system (Figure 14). If operating-system
does not use, then the jobs are processed in the order they enter the system.

Figure 14: Job queue

When the jobs start entering, the queue gradually shifts to right. Eventually the rear index equals
MAX_QUEUE_SIZE-1,it indicates queue is full. Then if the jobs leave the system, then also it is not
possible to insert the jobs in queue, since rear end has already reached the maximum size. Thus, it
results in serious disadvantage of ordinary normal queue. This queue problem can be overcome by using

Page 23
 Data structures and Applications 18CS32

a. shifting the jobs as the job leaves the queue and recalculating front and rear values, but shifting is very
time consuming b. another solution to the above problem is using circular queue.
2.8 CIRCULAR QUEUE
Circular queue is a linear data structure. It follows FIFO principle. In circular queue the last node is
connected back to the first node to make a circle. Circular linked list follow the First In First Out
principle.(as shown in figure 15) Elements are added at the rear end and the elements are deleted at front
end of the queue. The queue is considered as a circular queue when the positions 0 and MAX-1 are
adjacent. Any position before front is also after rear.
A circular queue looks like

Figure 15: Circular queue

The addition and deletion operations on circular queue are given below

2.9 CIRCULAR QUEUES USING DYNAMICALLY ALLOCATED ARRAYS

Shortcoming of static queue implementation: is the need to know at compile-time, a good bound
(MAX_QUEUE _SIZE) on how large the queue will become.

Page 24
 Data structures and Applications 18CS32

This shortcoming can be overcome by using a dynamically allocated array for the elements & then
increasing the size of the array as needed. In array-doubling, double array-capacity is used whenever it
becomes necessary to increase the capacity of an array (Figure 16). [ Program A and Program B contains
code for circular array implementation using dynamic array]
Program A: Addition operation on CQ
void addq(element item)
{
rear= (rear+1) % capacity;
if(front == rear)
queueFull();
queue[rear]=item;
}

Figure 16: Circular queue

Page 25
 Data structures and Applications 18CS32

Program B : Array doubling operation during queue full on CQ

void queueFull( )
{
element *newqueue;
MALLOC(newqueue, 2 * capacity * sizeof(queue));
/*copy from queue to newqueue*/
int start=(front+1)%capacity;
if (start < 2)
/* no wrap around */
copy(queue+start, queue+start+capacity-1, newqueue);
else
{
/* queue wraps around*/
copy(queue+start, queue+start+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;
}

2.10 DEQUEUES
The word dequeue is short form of double ended queue. In a dequeue, insertion as well as deletion can
be carried out either at the rear end or the front end.(as shown in figure 17)
Operations on a Dequeue
 initialize(): Make the queue empty

 empty(): Determine if queue is empty

 full(): Determine if queue is full

 enqueueF(): Insert an element at the front end of the queue

 enqueueR(): Insert an element at the rear end of the queue

 dequeueR(): Delete the rear element

 dequeueF(): Delete the front element

 print(): Print elements of the queue

Page 26
 Data structures and Applications 18CS32

Figure 17: Dequeue

There are various ways of representing dequeue namely:
 An input-restricted dequeue is one where deletion can be made from both ends, but insertion
can be made at one end only.

 An output-restricted dequeue is one where insertion can be made at both ends, but deletion can
be made from one end only.

Both the basic and most common list types in computing, queues and stacks can be considered
specializations of dequeues, and can be implemented using deques.
2.11 PRIORITY QUEUE
Priority Queue is more specialized data structure than Queue. Like ordinary queue, priority queue has
same method but with a major difference. In Priority queue items are ordered by key value so that item
with the lowest value of key is at front and item with the highest value of key is at rear or vice versa. So
we're assigned priority to item based on its key value. Lower the value, higher the priority. Following
are the principal methods of a Priority Queue.(as shown in figure 18)
Basic Operations
 insert / enqueue − add an item to the rear of the queue.
 remove / dequeue − remove an item from the front of the queue.
Representations of priority queue
1. Priority Queue array Representation

Figure 18: Priority queue

Page 27
 Data structures and Applications 18CS32

There is few more operations supported by queue which are following.

 Peek − get the element at front of the queue.

 isFull − check if queue is full.

 isEmpty − check if queue is empty.

Insert / Enqueue Operation

Whenever an element is inserted into queue, priority queue inserts the item according to its order. Here
we're assuming that data with high value has low priority.( as shown in figure 19)

Figure 19: Insert / Enqueue Operation

Remove / Dequeue Operation
Whenever an element is to be removed from queue, queue get the element using item count. Once the
element is removed, Item count is reduced by one.(as shown in figure 20)

Figure 20: Remove / Dequeue Operation

One-Way List Representation of a Priority Queue
[1] Each node in the list will contain three items of information: an information Field INFO, a priority
number PRN, and a link number LINK
[2] A node X precedes a node Y in the list

Page 28
 Data structures and Applications 18CS32

(a) when X has higher priority than Y or

(b) when both have same priority but X was added to the list before Y

Figure 21: One way list priority queue

1. Algorithm deletes and processes the first element in a priority queue which appears in memory as
a one way list
1. Set ITEM=INFO [START]
2. Delete first node from the list
3. Process ITEM
4. exit

2. Algorithm that adds an item with priority number N to a priority queue which is maintained in
memory as a one-way list.
1. Traverse the one-way list until finding a node X, whose priority number exceeds N. Insert
ITEM in front of node X.

2. If no such node is found , insert ITEM as the last element of the list.

2.12 MAZE PROBLEM

 Mazes have been an intriguing subject for many years. Experimental psychologists train rats to
search mazes for food.
 In computer science, maze presents a nice application of stacks. Here, a program is developed that
runs a maze. The program maze can take many false paths before it finds a correct one, once found it
can correctly rerun the maze without taking false paths.
 The representation of maze is done using 2D array in which 0‟s represent the open paths and 1‟s the
barriers.

Figure 22: An example maze

Page 29
 Data structures and Applications 18CS32

 The rat starts at the top left and is to exit at the bottom right. With the maze represented as 2D array,
the location of the rat in the maze can at any time be described by the row and column position,

 If X is the spot of our current position, maze[row][col]. Following figure represents the possible
moves from this position. It points to specify the 8 directions of movements:- N, NE, E, SE, S, SW,
W, NW as shown.

 The border conditions of the maze can be represented by a border of ones. Thus, an mxp maze will
require an (m+2)x(p+2) array. The entrance is at position[1][1] and exit at [m][p].

N[i‐1][j]
NW[i‐1][j‐1] NE[i‐1][j+1]

W[i][j‐1] E[i][j+1]
[i][j]

SE[i+1][j+1]
SW[i+1][j‐1] S[i+1][j]
Figure 23: Allowable moves
 The possible directions of movement can be predefined in the move array as shown in following
table. The 8 possible directions of movement are given by 0 to 7.

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

 The C declaration needed to create this table are:-

typedef struct
{
short int vert;
short int horiz;

Page 30
 Data structures and Applications 18CS32

}offsets;
offsets moves[8];
 If the rat is at position maze[row][col] and the next move position can be obtained as follows:-

maze[nextRow][nextCol], where nextRow = row+move[dir].vert;

nextCol = col+move[dir].horoz;
 Here, the best possible direction is not predictable. So, the current position of the rat is saved and
arbitrarily pick a possible move.

 By saving the current position, it is possible to return to it back and try another path if it is a hopeless
path.

 Thus, all possible moved starting from the north and moving clockwise are examined.

 A 2D array, mark is used to record the maze positions already checked.

 Initially, all the array enteries are 0.

 When a position maze[row][col] is visited, then mark[row][col] is changed to 1.

 Initial maze traversal is shown in the above Figure. EXIT_ROW & EXIT_COL gives the
coordinates of maze exit.

 Stack is used to solve the problem.

Element is defined as:
typedef struct
{
short int row;
short int col;
short int dir;
}Element;
 Each position in the maze is visited no more than once, the stack need to have only as many
positions as there are 0‟s in the maze.

 The maze has only 1 entrance and 1 exit path.

 When searching the maze from entrance to exit, all positions with 0 will be on the stack when the
exit is reached.

 Since, an mxp maze can have at most mp zeros, it is sufficient for the stack to have this capacity.

 Initialize a stack to the maze‟s entrance coordinates and direction to north.

Initial maze algorithm:-

while(stack is not empty)
{ /* move at position at top of stack*/
while(there are moves from current position)
{

Page 31
 Data structures and Applications 18CS32

<nextRow, nextCol>=coordinates of next move;

dir=direction of move;
if(nextRow == EXIT_ROW) && (nextCol == EXIT_COL))
success;
if(maze[nextRow][nextCol] == 0 && mark[nextRow][nextCol] == 0)
{ /* legal move and haven‟t been there */
mark[nextRow][nextCol] = 1;
/* save current position & direction */
add <row, col, dir> to the top of the stack;
row = nextRow;
col = nextCol;
dir = North;
}
}
}
printf(“No path found\n”);
 The next function contains the maze search algorithm implementation. Here maze, mark, move and
stack, arrays, along with the constants EXIT_ROW, EXIT_COL, TRUE & FALSE , variable top are
declared as global.

 The function uses a variable found that is initially set to 0 (FALSE). If we find a path through the
maze, then set this variable to TRUE, thereby allowing to exit both while loops.

Maze Search function:-

void path()
{ /* output a path through the maze if such a path exists*/
int i, row, col, nextRow, nextCol, dir, found = FALSE;
Element position;
mark[1][1]=1;
top=0;
stack[0].row=1;
stack[0].col=stack[0].dir=1;
while (top>-1 && !found)
{
position = pop();
row=[Link];
col=[Link];
dir=[Link];
while(dir<8 && !found)
{
/*move in direction dir */
nextRow = row+move[dir].vert;
nextCol = col+move[dir].horiz;
if(nextRow == EXIT_ROW && nextCol == EXIT_COL)
found – TRUE;
elseif(!maze[nextRow][nextCol] && !mark[nextRow][nextCol])
{

Page 32
 Data structures and Applications 18CS32

mark[nextRow][nextCol] = 1;
[Link] = row;
[Link] = col;
[Link] = ++dir;
push(position);
row=nextRow;
col=nextCol;
dir=0;
}
else ++dir;
}
}
if(found)
{
printf(“the path is:\n”);
printf(“row col\n”);
for(i=0;i<=top;i++)
printf(“%2d %5d\n”, stack[i].row, stack[i].col);
printf(“%2d %5d\n”, row, col);
printf(“%2d %5d\n”, EXIT_ROW, EXIT_COL);
}
else
printf(“The maze doesnot have a path”);
}

2.13 MULTIPLE STACKS AND QUEUES

Assume that we have „n‟ stacks, we can divide the available memory into „n‟ segments (Figure:24).Let
„i‟ = stack number of one of n stacks. Let boundary[i] (0<=i<MAX_STACKS) points to position
immediately to left of bottom element of stack i, while top[i] (0<=i<MAX_STACKS) points to top
element. Stack i is empty iff boundary[i]=top[i]
The relevant declaration are:
#define MEMORY_SIZE 100 /* size of memory */
#define MAX_STACKS 10 /* max number of stacks plus 1 */
element memory[MEMORY_SIZE];
int top[MAX_STACKS];
int n; /* number of stacks entered by the user */
To divide the array into equal segment, we use the following code:
top[0]=boundary[0]=-1;
for(j=1;j<n;j++)
top[j]=boundary[j]=(MEMORY_SIZE/n)*j;
boundary[n]=MEMORY_SIZE-1;

Page 33
 Data structures and Applications 18CS32

Figure 24: initial configuration for n stacks in memory

void push(int i,element item)
{
if(top[i]==boundary[i+1])
stackfull(i);
memory[++top[i]]=item;
}
Element pop(int i)
{
if(top[i]==boundary[i])
return stackempty(i);
return memory[top[i]--];
}

Figure 25 :configuration when stack I meets stack i+1,but the memory is not full
In push function, top[i]==boundary[i+1] condition implies only that a particular stack ran out of
memory, not that the entire memory is full.(In fact, there may be a lot of unused space between other
stacks in array memory).(as shown in figure 24).Therefore, an error recovery function is created,
stackFull, which determines if there is any free space in memory. If there is space available, it should
shift the stacks so that space is allocated to the full stack. We can guarantee that stackFull adds elements
as long as there is free space in array memory if we:
1) Determine the least j, i<j<n such that there is free space between stacks j and j+1 i.e.
top[j]<boundary[j+1]. If there is such a j, then move stacks i+1,i+2 . . . . . .j one position to the right.
This creates a space between stacks i and i+1.
2) If there is no j as in (i),then look to the left of stack i. Find the largest j such that 0<=j<I and there is
space between stacks j and j+1 i.e. top[j]<boundary[j+1]. If there is such a j, then move stacks j+1,j+2. .
. . . .i one space to the left. This also creates a space between stacks I and i+1.

3) If there is no j satisfying either (i) or (ii),then all MEMORY_SIZE spaces of memory utilized and
there is no free space. In this case, stackFull terminates with an error message.
----------------------Module2----------------------------
 Data structures and Applications 18CS32

Module2 Questions Bank

1. Define Stack. List the operations performed on Stack.
2. Write an algorithm to convert infix expression to postfix expression.
3. Convert the below Expression to postfix using stack.(a+b)*((b^c)*f)/g
4. Define Recursion. Illustrate with an example how stack is used in recursion.
5. Write an algorithm for Evaluation of postfix expression.
6. Given the following expressions give their postfix and prefix forms
(i) (A+B)*(D-C)
(ii) X$Y*Z-M+N+P|Q|(R+S)
7. Write a Recursive C program for each of the following:
(i) Tower of Hanoi
(ii) Computing GCD of two numbers.
(iii) Fibonacci series
(iv) To compute factorial of N.
8. What is maze problem? How maze is represented?
9. Write a note on Dequeue and Queue priority.
10. What is Queue. What are the various operations that can be performed on queues?
11. What is the disadvantage of using arrays to implement queue operations?
12. What is a double ended queue or deque? What are the operations that can be performed on double-
ended queues?
13. What is circular queue? How it is different from an ordinary queue?
14. With a neat diagram explain ONE-WAY list representation of a priority queue.
15. Explain with a suitable example, how would you implement circular queue using dynamically
allocated arrays.