UNIT 4

STACKS

INTRODUCTION TO STACKS

Stack is an important data structure which stores its elements in an ordered manner. We will explain the
concept of stacks using an analogy. You must have seen a pile of plates where one plate is placed on top of
another as shown in Fig. 3.21.

Now, when you want to remove a plate, you remove the topmost plate first. Hence, you can add and remove
an element (i.e., a plate) only at/from one position which is the topmost position.

A stack is a linear data structure which uses the same principle, i.e., the elements in a stack are added and
removed only from one end, which is called the TOP.

Hence, a stack is called a LIFO (Last-In-First-Out) data structure, as the element that was inserted last is the
first one to be taken out.

ARRAY REPRESENTATION OF STACKS

In the computer’s memory, stacks can be represented as a linear array. Every stack has a variable called TOP
associated with it, which is used to store the address of the topmost element of the stack. It is this position
where the element will be added to or deleted from.

There is another variable called MAX, which is used to store the maximum number of elements that the stack
can hold. If TOP = NULL, then it indicates that the stack is empty and if TOP = MAX–1, then the stack is
full. (You must be wondering why we have written MAX–1. It is because array indices start from 0.) Look at
Fig. 3.22.

Fig. 3.22 Stack

OPERATIONS ON A STACK

A stack supports three basic operations: push, pop, and peek.

The push operation adds an element to the top of the stack and the pop operation removes the element from
the top of the stack. The peek operation returns the value of the topmost element of the stack.

Push Operation

 The push operation is used to insert an element into the stack.

 The new element is added at the topmost position of the stack.
 To insert an element with value 6, we first check if TOP=MAX–1.
 If the condition is false, then we increment the value of TOP and store the new element at
the position given by stack[TOP].

Pop Operation

 The pop operation is used to delete the topmost element from the stack.
 However, before deleting the value, we must first check if TOP=NULL because if that is the case,
then it means the stack is empty and no more deletions can be done.
 To delete the topmost element, we first check if TOP=NULL. If the condition is false, then
we decrement the value pointed by TOP.
Peek Operation

 Peek is an operation that returns the value of the topmost element of the stack without deleting it
from the stack.
 However, the Peek operation first checks if the stack is empty, i.e., if TOP = NULL, then
an appropriate message is printed, else the value is returned.
 Here, the Peek operation will return 5,as it is the value of the topmost element of the stack.

Example:

LINKED REPRESENTATION OF STACKS

We have seen how a stack is created using an array. This technique of creating a stack is easy, but the
drawback is that the array must be declared to have some fixed size. In case the stack is a very small one or its
maximum size is known in advance, then the array implementation of the stack gives an efficient
implementation. But if the array size cannot be determined in advance, then the other alternative, i.e., linked
representation, is used.
The storage requirement of linked representation of the stack with n elements is O(n), and the typical time
requirement for the operations is O(1).

In a linked stack, every node has two parts—one that stores data and another that stores the address of the next
node. The START pointer of the linked list is used as TOP. All insertions and deletions are done at the node
pointed by TOP. If TOP = NULL, then it indicates that the stack is empty. The linked representation of a stack
is shown in below figure.
Push Operation

The push operation is used to insert an element into the stack. The new element is added at the topmost
position of the stack. Consider the linked stack shown in below figure.

To insert an element with value 9, we first check if TOP=NULL. If this is the case, then we allocate memory
for a new node, store the value in its DATA part and NULL in its NEXT part. The new node will then be
called TOP. However, if TOP!=NULL, then we insert the new node at the beginning of the linked stack and
name this new node as TOP.

the algorithm to push an element into a linked stack. In Step 1, memory is allocated for the new node. In
Step 2, the DATA part of the new node is initialized with the value to be stored in the node. In Step 3, we
check if the new node is the first node of the linked list. is done by checking if TOP = NULL. In case the IF
statement evaluates to true, then NULL is stored in the NEXT part of the node and the new node is called
TOP. However, if the new node is not the first node in the list, then it is added before the first node of the list
(that is, the TOP node) and termed as TOP.

Pop Operation

The pop operation is used to delete the topmost element from a stack. However, before deleting the value, we
must first check if TOP=NULL, because if this is the case, then it means that the stack is empty and no more
deletions can be done. If an attempt is made to delete a value from a stack that is already empty, an
UNDERFLOW message is printed. Consider the stack shown in below figure.

In case TOP!=NULL, then we will delete the node pointed by TOP, and make TOP point to the second
element of the linked stack. Thus, the updated stack becomes as shown in below figure.

The algorithm to delete an element from a stack.

In Step 1, we first check for the UNDERFLOW condition. In

Step 2, we use a pointer PTR that points to TOP.
In Step 3, TOP is made to point to the next node in sequence.
In Step 4, the memory occupied by PTR is given back to the free
APPLICATIONS OF STACKS

In this section we will discuss typical problems where stacks can be easily applied for a simple and efficient
solution. The topics that will be discussed in this section include the following:
 Reversing a list
 Parentheses checker
 Conversion of an infix expression into a postfix expression
 Evaluation of a postfix expression
 Conversion of an infix expression into a prefix expression
 Evaluation of a prefix expression
 Recursion
 Tower of Hanoi

1. Reversing list

A list of numbers can be reversed by reading each number from an array starting from the first index and
pushing it on a stack. Once all the numbers have been read, the numbers can be popped one at a time and then
stored in the array starting from the first index.

Evaluation of Arithmetic Expressions

Polish Notations:

Infix, postfix, and prefix notations are three different but equivalent notations of writing algebraic expressions.
But before learning about prefix and postfix notations, let us first see what an infix notation is. We all are
familiar with the infix notation of writing algebraic expressions.

While writing an arithmetic expression using infix notation, the operator is placed in between the operands.
For example, A+B; here, plus operator is placed between the two operands A and B. Although it is easy for us
to write expressions using infix notation, computers find it difficult to parse as the computer needs a lot of
information to evaluate the expression. Information is needed about operator precedence and associativity
rules, and brackets which override these rules.
So, computers work more efficiently with expressions written using prefix and postfix notations. Postfix
notation was developed by Jan Łukasiewicz who was a Polish logician, mathematician, and philosopher. His
aim was to develop a parenthesis-free prefix notation (also known as Polish notation) and a postfix notation,
which is better known as Reverse Polish Notation or RPN.
In postfix notation, as the name suggests, the operator is placed after the operands. For example, if an
expression is written as A+B in infix notation, the same expression can be written as AB+ in postfix notation.
The order of evaluation of a postfix expression is always from left to right. Even brackets cannot alter the
order of evaluation.

The expression (A + B) * C can be written as:

[AB+]*C
AB+C* in the postfix notation

A postfix operation does not even follow the rules of operator precedence. The operator which occurs first in
the expression is operated first on the operands.

For example, given a postfix notation AB+C*. While evaluation, addition will be performed prior to
multiplication. Thus we see that in a postfix notation, operators are applied to the operands that are
immediately left to them. In the example, AB+C*, + is applied on A and B, then * is applied on the result of
addition and C.

Conversion of an Infix Expression into a Postfix Expression:

Let I be an algebraic expression written in infix notation. I may contain parentheses, operands, and operators.
For simplicity of the algorithm we will use only +, –, *, /, % operators.

The precedence of these operators can be given as follows:

 Higher priority *, /, %
 Lower priority +, –

No doubt, the order of evaluation of these operators can be changed by making use of parentheses. For
example, if we have an expression A + B * C, then first B * C will be done and the result will be added to A.
But the same expression if written as, (A + B) * C, will evaluate A + B first and then the result will be
multiplied with C.

Example: Convert the following infix expressions into postfix expressions.

Solution:
(a) (A–B) * (C+D)
[AB–] * [CD+]
AB–CD+*

(b) (A + B) / (C + D) – (D * E)
[AB+] / [CD+] – [DE*]
[AB+CD+/] – [DE*]
AB+CD+/DE*–
The algorithm given below transforms an infix expression into postfix expression. The algorithm accepts an
infix expression that may contain operators, operands, and parentheses.
For simplicity, we assume that the infix operation contains only modulus (%), multiplication (*), division (/),
addition (+), and subtraction (―) operators and that operators with same precedence are performed from left-
to-right.
The algorithm uses a stack to temporarily hold operators. The postfix expression is obtained from left-to-right
using the operands from the infix expression and the operators which are removed from the stack. The first
step in this algorithm is to push a left parenthesis on the stack and to add a corresponding right parenthesis at
the end of the infix expression. The algorithm is repeated until the stack is empty.

Example: Convert the following infix expression into postfix expression using the algorithm
A – (B / C + (D % E * F) / G)* H
A – (B / C + (D % E * F) / G)* H)
Evaluation of a Postfix Expression:

The ease of evaluation acts as the driving force for computers to translate an infix notation into a postfix
notation. That is, given an algebraic expression written in infix notation, the computer first converts the
expression into the equivalent postfix notation and then evaluates the postfix expression.

Both these tasks—converting the infix notation into postfix notation and evaluating the postfix expression—
make extensive use of stacks as the primary tool.

Using stacks, any postfix expression can be evaluated very easily. Every character of the postfix expression is
scanned from left to right. If the character encountered is an operand, it is pushed on to the stack. However, if
an operator is encountered, then the top two values are popped from the stack and the operator is applied on
these values. The result is then pushed on to the stack.

Algorithm to evaluate a postfix expression Evaluation of a postfix expression

Let us now take an example that makes use of this algorithm.

Consider the infix expression given as 9 – ((3 * 4) + 8) / 4. Evaluate the expression.
The infix expression 9 – ((3 * 4) + 8) / 4 can be written as 9 3 4 * 8 + 4 / – using postfix notation.

Factorial Calculation:
Evaluation of Expression
The way to write arithmetic expression is known as a notation. An arithmetic expression
can be written in three different but equivalent notations, i.e., without changing the essence
or output of an expression. These notations are –
 Infix Notation
 Prefix (Polish) Notation
 Postfix (Reverse-Polish) Notation
These notations are named as how they use operator in expression. We shall learn the same
here in this chapter.
Infix Notation
We write expression in infix notation, e.g. a - b + c, where operators are used in- between
operands. It is easy for us humans to read, write, and speak in infix notation but the same
does not go well with computing devices. An algorithm to
 process infix notation could be difficult and costly in terms of time and space consumption.
Prefix Notation
In this notation, operator is prefixed to operands, i.e. operator is written ahead of operands.
For example, +ab. This is equivalent to its infix notation a + b. Prefix notation is also known
as Polish Notation.
Postfix Notation
This notation style is known as Reversed Polish Notation. In this notation style, the
operator is postfixed to the operands i.e., the operator is written after the operands. For
example, ab+. This is equivalent to its infix notation a + b.
The following table briefly tries to show the difference in all three notations −

Sr.No. Infix Notation Prefix Notation Postfix Notation

1 a+b +ab ab+

2 (a + b) ∗ c ∗+abc ab+c∗

3 a ∗ (b + c) ∗a+bc abc+∗

4 a/b+c/d +/ab/cd ab/cd/+

5 (a + b) ∗ (c + d) ∗+ab+cd ab+cd+∗

6 ((a + b) ∗ c) - d -∗+abcd ab+c∗d-

Parsing Expressions
As we have discussed, it is not a very efficient way to design an algorithm or program to
parse infix notations. Instead, these infix notations are first converted into either postfix or
prefix notations and then computed.
To parse any arithmetic expression, we need to take care of operator precedence and
associativity also.

Precedence

When an operand is in between two different operators, which operator will take the operand
first, is decided by the precedence of an operator over others. For example
–
 a+b*c - a+(b*c)

As multiplication operation has precedence over addition, b * c will be evaluated first. A

table of operator precedence is provided later.

Associativity

Associativity describes the rule where operators with the same precedence appear in an
expression. For example, in expression a + b − c, both + and – have the same
precedence, then which part of the expression will be evaluated first, is determined by
associativity of those operators. Here, both + and − are left associative, so the
expression will be evaluated as (a + b) − c.
Precedence and associativity determines the order of evaluation of an expression.
Following is an operator precedence and associativity table (highest to lowest) −

Sr.No. Operator Precedence Associativity

1 Exponentiation ^ Highest Right Associative

2 Multiplication ( ∗ ) & Division ( / ) Second Highest Left Associative

3 Addition ( + ) & Subtraction ( − ) Lowest Left Associative

The above table shows the default behavior of operators. At any point of time in
expression evaluation, the order can be altered by using parenthesis. For example
–
In a + b*c, the expression part b*c will be evaluated first, with multiplication as precedence
over addition. We here use parenthesis for a + b to be evaluated first, like (a + b)*c.
Postfix Evaluation Algorithm
Step 1 − scan the expression from left to right Step 2 − if it is an
operand push it to stack
Step 3 − if it is an operator pull operand from stack and perform operation
Step 4 − store the output of step 3, back to stack
Step 5 − scan the expression until all operands are consumed Step 6 − pop the stack and
perform operation
A postfix expression is a collection of operators and operands in which the operator is placed
after the operands. That means, in a postfix expression the operator follows the operands.

Postfix Expression has following general structure...

 Operand1 Operand2 Operator
Example

Postfix Expression Evaluation using Stack Data

Structure
A postfix expression can be evaluated using the Stack data structure. To evaluate a postfix
expression using Stack data structure we can use the following steps...Read all the symbols
one by one from left to right in the given Postfix Expression

1. If the reading symbol is operand, then push it on to the Stack.

2. If the reading symbol is operator (+ , - , * , / etc.,), then perform TWO pop
operations and store the two popped oparands in two different variables
(operand1 and operand2). Then perform reading symbol operation using
operand1 and operand2 and push result back on to the Stack.
3. Finally! perform a pop operation and display the popped value as final result.
Example Consider the following Expression..
 QUEUES

3.2 INTRODUCTION TO QUEUES

Let us explain the concept of queues using the analogies given below.
 People moving on an escalator. The people who got on the escalator first will be the first one to step
out of it.
 People waiting for a bus. The first person standing in the line will be the first one to get into the bus.
 People standing outside the ticketing window of a cinema hall. The first person in the line will get the
ticket first and thus will be the first one to move out of it.
 Luggage kept on conveyor belts. The bag which was placed first will be the first to come out at the
other end.
 Cars lined at a toll bridge. The first car to reach the bridge will be the first to leave.

In all these examples, we see that the element at the first position is served first. Same is the case with queue
data structure. A queue is a FIFO (First-In, First-Out) data structure in which the element that is inserted
first is the first one to be taken out. The elements in a queue are added at one end called the REAR and
removed from the other end called the FRONT. Queues can be implemented by using either arrays or linked
lists. In this section, we will see how queues are implemented using each of these data structures.

3.3 ARRAY REPRESENTATION & IMPLEMENTATION OF QUEUES

Queues can be easily represented using linear arrays. As stated earlier, every queue has front and rear
variables that point to the position from where deletions and insertions can be done, respectively.
The array representation of a queue is shown in Fig. 3.1.
Operations on Queues

In Fig. 3.1, FRONT = 0 and REAR = 5. Suppose we want to add another element with value 45, then REAR
would be incremented by 1 and the value would be stored at the position pointed by REAR.

The queue after addition would be as shown in Fig. 3.2. Here, FRONT = 0 and REAR = 6. Every time a new
element has to be added, we repeat the same procedure.

If we want to delete an element from the queue, then the value of FRONT will be incremented. Deletions are
done from only this end of the queue. The queue after deletion will be as shown in Fig. 3.3.
Here, FRONT = 1 and REAR = 6.

However, before inserting an element in a queue, we must check for overflow conditions. An overflow will
occur when we try to insert an element into a queue that is already full. When REAR = MAX – 1, where
MAX is the size of the queue, we have an overflow condition. Note that we have written MAX – 1 because
the index starts from 0. Similarly, before deleting an element from a queue, we must check for underflow
conditions. An underflow condition occurs when we try to delete an element from a queue that is already
empty. If FRONT = –1 and REAR = –1, it means there is no element in the queue.

Algorithm to insert an element in a queue Algorithm to delete an element from a queue

NOTE: The process of inserting an element in the queue is called enqueue, and the process of deleting an
element from the queue is called dequeue.

// Queue implementation in C

#include <stdio.h>
#define SIZE 5

void enQueue(int);
void deQueue();
void display();

int items[SIZE], front = -1, rear = -1;

int main() {
//deQueue is not possible on empty queue
deQueue();

//enQueue 5 elements
 enQueue(1);
enQueue(2);
enQueue(3);
enQueue(4);
enQueue(5);

// 6th element can't be added to because the queue is full

enQueue(6);

display();

//deQueue removes element entered first i.e. 1

deQueue();

//Now we have just 4 elements

display();

return 0;
}

void enQueue(int value) {

if (rear == SIZE - 1)
printf("\nQueue is Full!!");
else {
if (front == -1)
front = 0;
rear++;
items[rear] = value;
printf("\nInserted -> %d", value);
}
}

void deQueue() {
if (front == -1)
printf("\nQueue is Empty!!");
else {
printf("\nDeleted : %d", items[front]);
front++;
if (front > rear)
front = rear = -1;
}
}

// Function to print the queue

void display() {
if (rear == -1)
printf("\nQueue is Empty!!!");
else {
int i;
printf("\nQueue elements are:\n");
 for (i = front; i <= rear; i++)
printf("%d ", items[i]);
}
printf("\n");
}

3.4 LINKED REPRESENTATION & IMPLEMENTATION OF QUEUES

We have seen how a queue is created using an array. Although this technique of creating a queue is easy, its
drawback is that the array must be declared to have some fixed size. If we allocate space for 50 elements in
the queue and it hardly uses 20–25 locations, then half of the space will be wasted.

And in case we allocate less memory locations for a queue that might end up growing large and large, then a
lot of re-allocations will have to be done, thereby creating a lot of overhead and consuming a lot of time.

In case the queue is a very small one or its maximum size is known in advance, then the array implementation
of the queue gives an efficient implementation. But if the array size cannot be determined in advance, the
other alternative, i.e., the linked representation is used.

The storage requirement of linked representation of a queue with n elements is O(n) and the typical time
requirement for operations is O(1).
In a linked queue, every element has two parts, one that stores the data and another that stores the address of
the next element. The START pointer of the linked list is used as FRONT. Here, we will also use another
pointer called REAR, which will store the address of the last element in the queue.

All insertions will be done at the rear end and all the deletions will be done at the front end. If FRONT =
REAR = NULL, then it indicates that the queue is empty. The linked representation of a queue is shown in
Fig. 3.4.

Algorithm to insert an element in a linked queue

Insert Operation
The insert operation is used to insert an element into a queue. The new element is added as the last element of
the queue. Consider the linked queue shown in Fig. 3.5.
To insert an element with value 9, we first check if FRONT=NULL. If the condition holds, then the queue is
empty. So, we allocate memory for a new node, store the value in its data part and NULL in its next part. The
new node will then be called both FRONT and rear. However, if FRONT != NULL, then we will insert the
new node at the rear end of the linked queue and name this new node as rear. Thus, the updated queue
becomes as shown in Fig. 3.6.
The algorithm shows that inserting an element in a linked queue. In Step 1, the memory is allocated for the
new node. In Step 2, the DATA part of the new node is initialized with the value to be stored in the node. In
Step 3, we check if the new node is the first node of the linked queue. This is done by checking if FRONT =
NULL. If this is the case, then the new node is tagged as FRONT as well as REAR. Also NULL is stored in
the NEXT part of the node (which is also the FRONT and the REAR node). However, if the new node is not
the first node in the list, then it is added at the REAR end of the linked queue (or the last node of the queue).

Delete Operation
The delete operation is used to delete the element that is first inserted in a queue, i.e., the element whose
address is stored in FRONT. However, before deleting the value, we must first check if FRONT=NULL
because if this is the case, then the queue is empty and no more deletions can be done. If an attempt is made to
delete a value from a queue that is already empty, an underflow message is printed. Consider the queue shown
in Fig. 3.7.
// C program to implement the queue data structure using
// linked list
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>

// Node structure representing a single node in the linked

// list
typedef struct Node {
int data;
struct Node* next;
} Node;

// Function to create a new node

Node* createNode(int new_data)
{
Node* new_node = (Node*)malloc(sizeof(Node));
new_node->data = new_data;
new_node->next = NULL;
return new_node;
}

// Structure to implement queue operations using a linked

// list
typedef struct Queue {
 // Pointer to the front and the rear of the linked list
Node *front, *rear;
} Queue;

// Function to create a queue

Queue* createQueue()
{
Queue* q = (Queue*)malloc(sizeof(Queue));
q->front = q->rear = NULL;
return q;
}

// Function to check if the queue is empty

int isEmpty(Queue* q)
{

// If the front and rear are null, then the queue is

// empty, otherwise it's not
if (q->front == NULL && q->rear == NULL) {
return 1;
}
return 0;
}

// Function to add an element to the queue

void enqueue(Queue* q, int new_data)
{

// Create a new linked list node

Node* new_node = createNode(new_data);
 // If queue is empty, the new node is both the front
// and rear
if (q->rear == NULL) {
q->front = q->rear = new_node;
return;
}

// Add the new node at the end of the queue and

// change rear
q->rear->next = new_node;
q->rear = new_node;
}

// Function to remove an element from the queue

void dequeue(Queue* q)
{

// If queue is empty, return

if (isEmpty(q)) {
printf("Queue Underflow\n");
return;
}

// Store previous front and move front one node

// ahead
Node* temp = q->front;
q->front = q->front->next;

// If front becomes null, then change rear also

 // to null
if (q->front == NULL)
q->rear = NULL;

// Deallocate memory of the old front node

free(temp);
}

// Function to get the front element of the queue

int getFront(Queue* q)
{

// Checking if the queue is empty

if (isEmpty(q)) {
printf("Queue is empty\n");
return INT_MIN;
}
return q->front->data;
}

// Function to get the rear element of the queue

int getRear(Queue* q)
{

// Checking if the queue is empty

if (isEmpty(q)) {
printf("Queue is empty\n");
return INT_MIN;
}
return q->rear->data;
}

// Driver code
int main()
{
Queue* q = createQueue();

// Enqueue elements into the queue

enqueue(q, 10);
enqueue(q, 20);

printf("Queue Front: %d\n", getFront(q));

printf("Queue Rear: %d\n", getRear(q));

// Dequeue elements from the queue

dequeue(q);
dequeue(q);

// Enqueue more elements into the queue

enqueue(q, 30);
enqueue(q, 40);
enqueue(q, 50);

// Dequeue an element from the queue

dequeue(q);

printf("Queue Front: %d\n", getFront(q));

printf("Queue Rear: %d\n", getRear(q));
 return 0;
}

Queue using Stacks

We are given a stack data structure with push and pop operations, the task is to implement a queue using
instances of stack data structure and operations on them.

A queue can be implemented using two stacks. Let queue to be implemented be q and stacks used to implement q
be stack1 and stack2. q can be implemented in two ways:

Method 1 (By making enQueue operation costly): This method makes sure that oldest entered element is
always at the top of stack 1, so that deQueue operation just pops from stack1. To put the element at top of stack1,
stack2 is used.
enQueue(q, x):
  While stack1 is not empty, push everything from stack1 to stack2.
 Push x to stack1 (assuming size of stacks is unlimited).
 Push everything back to stack1.
Here time complexity will be O(n)
deQueue(q):
 If stack1 is empty then error
 Pop an item from stack1 and return it
Here time complexity will be O(1)

Complexity Analysis:
 Time Complexity:

o Push operation: O(N).

In the worst case we have empty whole of stack 1 into stack 2.
o Pop operation: O(1).
Same as pop operation in stack.
 Auxiliary Space: O(N).
Use of stack for storing values.
Method 2 (By making deQueue operation costly): In this method, in en-queue operation, the new element is
entered at the top of stack1. In de-queue operation, if stack2 is empty then all the elements are moved to stack2
and finally top of stack2 is returned.
enQueue(q, x)
1) Push x to stack1 (assuming size of stacks is unlimited).
Here time complexity will be O(1)

deQueue(q)
1) If both stacks are empty then error.
2) If stack2 is empty
While stack1 is not empty, push everything from stack1 to stack2.
3) Pop the element from stack2 and return it.
Here time complexity will be O(n)
Method 2 is definitely better than method 1.
APPLICATIONS OF QUEUES

 Queues are widely used as waiting lists for a single shared resource like printer, disk, CPU.
 Queues are used to transfer data asynchronously (data not necessarily received at same rate as sent)
between two processes (IO buffers), e.g., pipes, file IO, sockets.
 Queues are used as buffers on MP3 players and portable CD players, iPod playlist.
 Queues are used in Playlist for jukebox to add songs to the end, play from the front of the list.
 Queues are used in operating system for handling interrupts. When programming a real-time system
that can be interrupted, for example, by a mouse click, it is necessary to process the interrupts
immediately, before proceeding with the current job. If the interrupts have to be handled in the order of
arrival, then a FIFO queue is the appropriate data structure.

3.5 TYPES OF QUEUES

A queue data structure can be classified into the following types:

1. Circular Queue 2. Deque 3. Priority Queue 4. Multiple
Queue We will discuss each of these queues in detail in the following
sections.

3.5.1 Circular Queues

In linear queues, we have discussed so far that insertions can be done only at one end called the REAR and
deletions are always done from the other end called the FRONT. Look at the queue shown in Fig. 3.9.

Here, FRONT = 0 and REAR = 9.

Now, if you want to insert another value, it will not be possible because the queue is completely full. There is
no empty space where the value can be inserted. Consider a scenario in which two successive deletions are
made. The queue will then be given as shown in Fig. 3.10.

Here, front = 2 and REAR = 9.

Suppose we want to insert a new element in the queue shown in Fig. 3.10. Even though there is space
available, the overflow condition still exists because the condition rear = MAX – 1 still holds true. This is a
major drawback of a linear queue.

To resolve this problem, we have two solutions. First, shift the elements to the left so that the vacant space can
be occupied and utilized efficiently. But this can be very time-consuming, especially when the queue is quite
large.

The second option is to use a circular queue. In the circular queue, the first index comes right after the last
index. Conceptually, you can think of a circular queue as shown in Fig. 3.11.
The circular queue will be full only when front = 0 and rear = Max – 1. A circular queue is implemented in the
same manner as a linear queue is implemented. The only difference will be in the code that performs insertion
and deletion operations.

For insertion, we now have to check for the following three conditions:
 If front = 0 and rear = MAX – 1, then the circular queue is full. Look at the queue given in Fig.
3.12 which illustrates this point.
 If rear != MAX – 1, then rear will be incremented and the value will be inserted as illustrated in
Fig. 3.13.
 If front != 0 and rear = MAX – 1, then it means that the queue is not full. So, set rear = 0 and insert
the new element there, as shown in Fig. 3.14.

Let us look at the algorithm to insert an element in a circular queue. In Step 1, we check for the overflow
condition. In Step 2, we make two checks. First to see if the queue is empty, and second to see if the REAR
end has already reached the maximum capacity while there are certain free locations before the FRONT end.
In Step 3, the value is stored in the queue at the location pointed by REAR.

Let us now discuss how deletions are performed in this case. To delete an element, again we check for three
conditions.

 Look at Fig. 3.15. If front = –1, then there are no elements in the queue. So, an underflow condition
will be reported.
 If the queue is not empty and front = rear, then after deleting the element at the front the queue
becomes empty and so front and rear are set to –1. This is illustrated in Fig. 3.16.
 If the queue is not empty and front = MAX–1, then after deleting the element at the front, front is set to
0. This is shown in Fig. 3.17.
Let us look at the algorithm to delete an element from a circular queue. In Step 1, we check for the underflow
condition. In Step 2, the value of the queue at the location pointed by FRONT is stored in VAL. In Step 3, we
make two checks. First to see if the queue has become empty after deletion and second to see if FRONT has
reached the maximum capacity of the queue. The value of FRONT is then updated based on the outcome of
these checks.
How Circular Queue Works
Circular Queue works by the process of circular increment i.e. when we try to increment the pointer and we
reach the end of the queue, we start from the beginning of the queue.
Here, the circular increment is performed by modulo division with the queue size. That is,
if REAR + 1 == 5 (overflow!), REAR = (REAR + 1)%5 = 0 (start of queue)

Circular Queue Operations

The circular queue work as follows:
 two pointers FRONT and REAR
 FRONT track the first element of the queue
 REAR track the last elements of the queue
 initially, set value of FRONT and REAR to -1
1. Enqueue Operation
 check if the queue is full
 for the first element, set value of FRONT to 0
 circularly increase the REAR index by 1 (i.e. if the rear reaches the end, next it would be at the start of
the queue)
 add the new element in the position pointed to by REAR
2. Dequeue Operation
 check if the queue is empty
 return the value pointed by FRONT
 circularly increase the FRONT index by 1
  for the last element, reset the values of FRONT and REAR to -1
However, the check for full queue has a new additional case:
 Case 1: FRONT = 0 && REAR == SIZE - 1
 Case 2: FRONT = REAR + 1
The second case happens when REAR starts from 0 due to circular increment and when its value is just 1 less
than FRONT, the queue is full.
Enque and Deque Operations
// Circular Queue implementation in C

#include <stdio.h>

#define SIZE 5

int items[SIZE];
int front = -1, rear = -1;

// check if the queue is full

int isFull() {
if ((front == (rear + 1) % SIZE) || (front == 0 && rear == SIZE - 1)) return 1;
return 0;
}

// check if the queue is empty

int isEmpty() {
if (front == -1) return 1;
return 0;
}

// adding an element
void enQueue(int element) {
if (isFull())
printf("\n Queue is full!! \n");
else {
if (front == -1) front = 0;
rear = (rear + 1) % SIZE;
items[rear] = element;
printf("\n Inserted -> %d", element);
}
}

// removing an element
int deQueue() {
int element;
 if (isEmpty()) {
printf("\n Queue is empty !! \n");
return (-1);
} else {
element = items[front];
if (front == rear) {
front = -1;
rear = -1;
}
// Q has only one element, so we reset the
// queue after dequeing it. ?
else {
front = (front + 1) % SIZE;
}
printf("\n Deleted element -> %d \n", element);
return (element);
}
}

// display the queue

void display() {
int i;
if (isEmpty())
printf(" \n Empty Queue\n");
else {
printf("\n Front -> %d ", front);
printf("\n Items -> ");
for (i = front; i != rear; i = (i + 1) % SIZE) {
printf("%d ", items[i]);
}
printf("%d ", items[i]);
printf("\n Rear -> %d \n", rear);
}
}

int main() {
// fails because front = -1
deQueue();
 enQueue(1);
enQueue(2);
enQueue(3);
enQueue(4);
enQueue(5);

// fails to enqueue because front == 0 && rear == SIZE - 1

enQueue(6);

display();
deQueue();

display();

enQueue(7);
display();

// fails to enqueue because front == rear + 1

enQueue(8);

return 0;
}
#in case of link list implementation use circular link list.

3.5.2 Deques

A deque (pronounced as ‘deck’ or ‘dequeue’) is a list in which the elements can be inserted or deleted at either
end. It is also known as a head-tail linked list because elements can be added to or removed from either the
front (head) or the back (tail) end.

However, no element can be added and deleted from the middle. In the computer’s memory, a deque is
implemented using either a circular array or a circular doubly linked list.

In a deque, two pointers are maintained, LEFT and RIGHT, which point to either end of the deque. The
elements in a deque extend from the LEFT end to the RIGHT end and since it is circular, Dequeue[N–1] is
followed by Dequeue[0]. Consider the deques shown in Fig. 3.18.
 There are two variants of a double-ended queue. They include

 Input restricted deque In this dequeue, insertions can be done only at one of the ends, while deletions
can be done from both ends.

 Output restricted deque In this dequeue, deletions can be done only at one of the ends, while insertions
can be done on both ends.

Operations on a Deque
Before performing the following operations, these steps are followed.
1. Take an array (deque) of size n.
2. Set two pointers front = -1 and rear = 0.

Initialize an array and pointers for deque

1. Insert at the Front
This operation adds an element at the front.

1. Check if the deque is full.

 2. Check the position of front
3. If the deque is full (i.e. (front == 0 && rear == n - 1) || (front == rear + 1)), insertion operation cannot be
performed (overflow condition).
4. If the deque is empty, reinitialize front = 0. And, add the new key into array[front].

5. If front = 0, reinitialize front = n-1 (last index).

Shift front to the end
6. Else, decrease front by 1.

7. Add the new key 5 into array[front].

8. Insert the element at Front
2. Insert at the Rear
This operation adds an element to the rear.

1. Check if the deque is full.

2. Check if deque is full
3. If the deque is full, insertion operation cannot be performed (overflow condition).
4. If the deque is empty, reinitialize rear = 0. And, add the new key into array[rear].
5. If rear = n - 1, reinitialize real = 0 (first index).
 6. Else, increase rear by 1.
7. Increase the rear

8. Add the new key 5 into array[rear].

9. Insert the element at rear
3. Delete from the Front
The operation deletes an element from the front.

1. Check if the deque is empty.

2. Check if deque is empty
3. If the deque is empty (i.e. front = -1), deletion cannot be performed (underflow condition).
4. If the deque has only one element (i.e. front = rear), set front = -1 and rear = -1.
5. Else if front is at the last index (i.e. front = n - 1), set front = 0.
 6. Else, front = front + 1.
7. Increase the front
4. Delete from the Rear
This operation deletes an element from the rear.

1. Check if the deque is empty.

2. Check if deque is empty
3. If the deque is empty (i.e. front = -1), deletion cannot be performed (underflow condition).
4. If the deque has only one element (i.e. front = rear), set front = -1 and rear = -1, else follow the steps
below.
5. If rear is at the first index (i.e. rear = 0), reinitialize rear = n - 1.

6. Else, rear = rear - 1.

7. Decrease the rear
5. Check Empty
This operation checks if the deque is empty. If front = -1, the deque is empty.
6. Check Full
This operation checks if the deque is full. If front = 0 and rear = n - 1 OR front = rear + 1, the deque is full.
// Deque implementation in C

#include <stdio.h>

#define MAX 10

void addFront(int *, int, int *, int *);

void addRear(int *, int, int *, int *);
int delFront(int *, int *, int *);
int delRear(int *, int *, int *);
void display(int *);
int count(int *);

int main() {
int arr[MAX];
int front, rear, i, n;

front = rear = -1;

for (i = 0; i < MAX; i++)
arr[i] = 0;

addRear(arr, 5, &front, &rear);

addFront(arr, 12, &front, &rear);
addRear(arr, 11, &front, &rear);
addFront(arr, 5, &front, &rear);
addRear(arr, 6, &front, &rear);
addFront(arr, 8, &front, &rear);
 printf("\nElements in a deque: ");
display(arr);

i = delFront(arr, &front, &rear);

printf("\nremoved item: %d", i);

printf("\nElements in a deque after deletion: ");

display(arr);

addRear(arr, 16, &front, &rear);

addRear(arr, 7, &front, &rear);

printf("\nElements in a deque after addition: ");

display(arr);

i = delRear(arr, &front, &rear);

printf("\nremoved item: %d", i);

printf("\nElements in a deque after deletion: ");

display(arr);

n = count(arr);
printf("\nTotal number of elements in deque: %d", n);
}

void addFront(int *arr, int item, int *pfront, int *prear) {

int i, k, c;

if (*pfront == 0 && *prear == MAX - 1) {

printf("\nDeque is full.\n");
 return;
}

if (*pfront == -1) {
*pfront = *prear = 0;
arr[*pfront] = item;
return;
}

if (*prear != MAX - 1) {
c = count(arr);
k = *prear + 1;
for (i = 1; i <= c; i++) {
arr[k] = arr[k - 1];
k--;
}
arr[k] = item;
*pfront = k;
(*prear)++;
} else {
(*pfront)--;
arr[*pfront] = item;
}
}

void addRear(int *arr, int item, int *pfront, int *prear) {

int i, k;

if (*pfront == 0 && *prear == MAX - 1) {

printf("\nDeque is full.\n");
 return;
}

if (*pfront == -1) {
*prear = *pfront = 0;
arr[*prear] = item;
return;
}

if (*prear == MAX - 1) {
k = *pfront - 1;
for (i = *pfront - 1; i < *prear; i++) {
k = i;
if (k == MAX - 1)
arr[k] = 0;
else
arr[k] = arr[i + 1];
}
(*prear)--;
(*pfront)--;
}
(*prear)++;
arr[*prear] = item;
}

int delFront(int *arr, int *pfront, int *prear) {

int item;

if (*pfront == -1) {
printf("\nDeque is empty.\n");
 return 0;
}

item = arr[*pfront];
arr[*pfront] = 0;

if (*pfront == *prear)
*pfront = *prear = -1;
else
(*pfront)++;

return item;
}

int delRear(int *arr, int *pfront, int *prear) {

int item;

if (*pfront == -1) {
printf("\nDeque is empty.\n");
return 0;
}

item = arr[*prear];
arr[*prear] = 0;
(*prear)--;
if (*prear == -1)
*pfront = -1;
return item;
}
void display(int *arr) {
int i;

printf("\n front: ");

for (i = 0; i < MAX; i++)
printf(" %d", arr[i]);
printf(" :rear");
}

int count(int *arr) {

int c = 0, i;

for (i = 0; i < MAX; i++) {

if (arr[i] != 0)
c++;
}
return c;
}

Implementation of Deque using doubly linked list

Operations on Deque :
Mainly the following four basic operations are performed on queue :
insertFront() : Adds an item at the front of Deque.
insertRear() : Adds an item at the rear of Deque.
deleteFront() : Deletes an item from front of Deque.
deleteRear() : Deletes an item from rear of Deque.

In addition to above operations, following operations are also supported :

getFront() : Gets the front item from queue.
getRear() : Gets the last item from queue.
isEmpty() : Checks whether Deque is empty or not.
size() : Gets number of elements in Deque.
erase() : Deletes all the elements from Deque.

Doubly Linked List Representation of Deque :

For implementing deque, we need to keep track of two pointers, front and rear. We enqueue (push) an item at
the rear or the front end of deque and dequeue(pop) an item from both rear and front end.
Working :
Declare two pointers front and rear of type Node, where Node represents the structure of a node of a doubly
linked list. Initialize both of them with value NULL.
Insertion at Front end :
1. Allocate space for a newNode of doubly linked list.
2. IF newNode == NULL, then
3. print "Overflow"
4. ELSE
5. IF front == NULL, then
6. rear = front = newNode
7. ELSE
8. newNode->next = front
9. front->prev = newNode
10. front = newNode

Insertion at Rear end :

1. Allocate space for a newNode of doubly linked list.
2. IF newNode == NULL, then
3. print "Overflow"
4. ELSE
5. IF rear == NULL, then
6. front = rear = newNode
7. ELSE
8. newNode->prev = rear
9. rear->next = newNode
10. rear = newNode

Deletion from Front end :

1. IF front == NULL
2. print "Underflow"
3. ELSE
4. Initialize temp = front
5. front = front->next
6. IF front == NULL
7. rear = NULL
8. ELSE
9. front->prev = NULL
10 Deallocate space for temp

Deletion from Rear end :

1. IF front == NULL
2. print "Underflow"
3. ELSE
4. Initialize temp = rear
5. rear = rear->prev
6. IF rear == NULL
7. front = NULL
8. ELSE
9. rear->next = NULL
10 Deallocate space for temp
3.5.3 Priority Queues

A priority queue is a data structure in which each element is assigned a priority. The priority of the element
will be used to determine the order in which the elements will be processed. The general rules of processing
the elements of a priority queue are
 An element with higher priority is processed before an element with a lower priority.
 Two elements with the same priority are processed on a first-come-first-served (FCFS) basis.

A priority queue can be thought of as a modified queue in which when an element has to be removed from the
queue, the one with the highest-priority is retrieved first. The priority of the element can be set based on
various factors. Priority queues are widely used in operating systems to execute the highest priority process
first. The priority of the process may be set based on the CPU time it requires to get executed completely.

A priority queue is a special type of queue in which each element is associated with a priority value. And,
elements are served on the basis of their priority. That is, higher priority elements are served first.
However, if elements with the same priority occur, they are served according to their order in the queue.
Assigning Priority Value
Generally, the value of the element itself is considered for assigning the priority. For example,
The element with the highest value is considered the highest priority element. However, in other cases, we can
assume the element with the lowest value as the highest priority element.
We can also set priorities according to our needs.

Removing Highest Priority Element

Difference between Priority Queue and Normal Queue

In a queue, the first-in-first-out rule is implemented whereas, in a priority queue, the values are removed on
the basis of priority. The element with the highest priority is removed first.
 Implementation of Priority Queue
Priority queue can be implemented using an array, a linked list, a heap data structure, or a binary search tree.
Among these data structures, heap data structure provides an efficient implementation of priority queues.

Implementation of a Priority Queue

There are two ways to implement a priority queue. We can either use a sorted list to store the elements so that
when an element has to be taken out, the queue will not have to be searched for the element with the highest
priority or we can use an unsorted list so that insertions are always done at the end of the list.

Every time when an element has to be removed from the list, the element with the highest priority will be
searched and removed. While a sorted list takes O(n) time to insert an element in the list, it takes only O(1)
time to delete an element. On the contrary, an unsorted list will take O(1) time to insert an element and O(n)
time to delete an element from the list.

Practically, both these techniques are inefficient and usually a blend of these two approaches is adopted that
takes roughly O(log n) time or less.

typedef struct {
int items[MAX];
int size;
} PriorityQueue;
Basic Operations of the Priority Queue in C
1. Enqueue Operation
This operation can be used to add the new element to the priority queue with the given priority.
Algorithm
 Add the element to end of the heap.
 Restore the heap property by the comparing the added element with its parent. If it can violates the heap
property, swap them.
 Continues this process up the heap until the correct position is found or root is reached.
2. Dequeue (Extract - Min/Max)
This operation can be used to removes and return the elements with the highest max in the max-heap and min in
the min-heap of the priority queue.
Algorithms
1. Replace the root of heap with the last element in the heap.
2. Reduce the size of the heap by the one.
3. Restore the heap property by the recursively comparing the new root with its children and swapping it
4. with the higher priority child in the max-heap or the lower priority child in the min heap.
5. Continues this process down the heap until the correct position is found or the leaf is reached.
3. Peek
This operation can be used to returns the element with the highest priority without the removing it from the
priority queue.
Algorithm
1. Return the element at the root of the heap.
4. Increase/Decrease Key
This operation can be used to change the priority of the element in the priority queue.
Algorithm
1. Locate the element whose the priority needs to be updated.
2. Update the priority of the element.
3. If the priority is increased in the max-heap or decreased in the min-heap and it can restore the heap
property by the heapifying up from the element.
4. If the priority is decreased in the max-heap or increased in the min-heap and restore the heap property by
the heapifying down from element.
C Program to Implement Priority Queue
C
1
#include <stdio.h>
2
#include <stdlib.h>
3

4
// Define maximum size of the priority queue
5
#define MAX 100
6

7
// Define PriorityQueue structure
8
typedef struct {
9
int items[MAX];
10
int size;
11
} PriorityQueue;
12

13
// Define swap function to swap two integers
14
void swap(int* a, int* b)
15
{
16
int temp = *a;
17
*a = *b;
18
*b = temp;
19
}
20

21
// Define heapifyUp function to maintain heap property
22
// during insertion
23
void heapifyUp(PriorityQueue* pq, int index)
24
{
25
if (index
26
&& pq->items[(index - 1) / 2] > pq->items[index]) {
27
swap(&pq->items[(index - 1) / 2],
28
&pq->items[index]);
29
heapifyUp(pq, (index - 1) / 2);
30
}
31
}
32

33
// Define enqueue function to add an item to the queue
34
void enqueue(PriorityQueue* pq, int value)
35
{
36
if (pq->size == MAX) {
37
printf("Priority queue is full\n");
38
return;
39
}
40

41
pq->items[pq->size++] = value;
42
heapifyUp(pq, pq->size - 1);
43
}
44

45
// Define heapifyDown function to maintain heap property
46
// during deletion
47
int heapifyDown(PriorityQueue* pq, int index)
48
{
49
int smallest = index;
50
int left = 2 * index + 1;
51
int right = 2 * index + 2;
52

53
if (left < pq->size
54
&& pq->items[left] < pq->items[smallest])
55
smallest = left;
56

57
if (right < pq->size
58
&& pq->items[right] < pq->items[smallest])
59
smallest = right;
60

61
if (smallest != index) {
62
swap(&pq->items[index], &pq->items[smallest]);
63
heapifyDown(pq, smallest);
64
}
65
}
66
67
// Define dequeue function to remove an item from the queue
68
int dequeue(PriorityQueue* pq)
69
{
70
if (!pq->size) {
71
printf("Priority queue is empty\n");
72
return -1;
73
}
74

75
int item = pq->items[0];
76
pq->items[0] = pq->items[--pq->size];
77
heapifyDown(pq, 0);
78
return item;
79
}
80

81
// Define peek function to get the top item from the queue
82
int peek(PriorityQueue* pq)
83
{
84
if (!pq->size) {
85
printf("Priority queue is empty\n");
86
return -1;
87
}
88
return pq->items[0];
89
}
90
91
// Define main function
92
int main()
93
{
94
// Initialize priority queue
95
PriorityQueue pq = { { 0 }, 0 };
96
// Add items to the queue
97
enqueue(&pq, 3);
98
enqueue(&pq, 2);
99
enqueue(&pq, 15);
100
enqueue(&pq, 5);
101
enqueue(&pq, 4);
102
enqueue(&pq, 45);
103

104
// Dequeue an item and print it
105
printf("%d dequeued from queue\n", dequeue(&pq));
106
// Print the top item of the queue
107
printf("Top element is %d\n", peek(&pq));
108

109
return 0;
110
}
Output
2 dequeued from queue
Top element is 3
Time and Space Complexity
 Time complexity: O(log n), where n is the number of nodes.
 Space complexity: O(n), where n is the number of elements in the priority queue.
 RECURSION

Recursion
Recursion is the technique of making a function call itself. This technique provides a way to break complicated
problems down into simple problems which are easier to solve.
Recursion may be a bit difficult to understand. The best way to figure out how it works is to experiment with it.

Recursion Example
Adding two numbers together is easy to do, but adding a range of numbers is more complicated. In the following
example, recursion is used to add a range of numbers together by breaking it down into the simple task of adding
two numbers:
Example
int sum(int k);

int main() {
int result = sum(10);
printf("%d", result);
return 0;
}

int sum(int k) {
if (k > 0) {
return k + sum(k - 1);
} else {
return 0;
}
}

Types of Recursions:
Recursion are mainly of two types depending on whether a function calls itself from within itself or more than
one function call one another mutually. The first one is called direct recursion and another one is
called indirect recursion. Thus, the two types of recursion are:
1. Direct Recursion: These can be further categorized into four types:
 Tail Recursion: If a recursive function calling itself and that recursive call is the last statement in the
function then it’s known as Tail Recursion. After that call the recursive function performs nothing. The
function has to process or perform any operation at the time of calling and it does nothing at returning
 time.
Example:

// Code Showing Tail Recursion

#include <stdio.h>

// Recursion function
void fun(int n)
{
if (n > 0) {
printf("%d ", n);

// Last statement in the function

fun(n - 1);
}
}

// Driver Code
int main()
{
int x = 3;
fun(x);
return 0;
}

Output
321
Let’s understand the example by tracing tree of recursive function. That is how the calls are made and how the
outputs are produced.
Time Complexity For Tail Recursion : O(n)
Space Complexity For Tail Recursion : O(n)
Note: Time & Space Complexity is given for this specific example. It may vary for another example.
Let’s now converting Tail Recursion into Loop and compare each other in terms of Time & Space Complexity
and decide which is more efficient.

// Converting Tail Recursion into Loop

#include <stdio.h>

void fun(int y)
{
while (y > 0) {
printf("%d ", y);
y--;
 }
}

// Driver code
int main()
{
int x = 3;
fun(x);
return 0;
}

Output
321
Time Complexity: O(n)
Space Complexity: O(1)
Note: Time & Space Complexity is given for this specific example. It may vary for another example.
So it was seen that in case of loop the Space Complexity is O(1) so it was better to write code in loop instead of
tail recursion in terms of Space Complexity which is more efficient than tail recursion.
Why space complexity is less in case of loop ?
Before explaining this I am assuming that you are familiar with the knowledge that’s how the data stored in main
memory during execution of a program. In brief,when the program executes,the main memory divided into three
parts. One part for code section, the second one is heap memory and another one is stack memory. Remember
that the program can directly access only the stack memory, it can’t directly access the heap memory so we
need the help of pointer to access the heap memory.
Let’s now understand why space complexity is less in case of loop ?
In case of loop when function “(void fun(int y))” executes there only one activation record created in stack
memory(activation record created for only ‘y’ variable) so it takes only ‘one’ unit of memory inside stack so it’s
space complexity is O(1) but in case of recursive function every time it calls itself for each call a separate
activation record created in stack.So if there’s ‘n’ no of call then it takes ‘n’ unit of memory inside stack so it’s
space complexity is O(n).
 Head Recursion: If a recursive function calling itself and that recursive call is the first statement in the
function then it’s known as Head Recursion. There’s no statement, no operation before the call. The
function doesn’t have to process or perform any operation at the time of calling and all operations are
done at returning time.
Example:

/ C program showing Head Recursion

 #include <stdio.h>

// Recursive function
void fun(int n)
{
if (n > 0) {

// First statement in the function

fun(n - 1);

printf("%d ", n);

}
}

// Driver code
int main()
{
int x = 3;
fun(x);
return 0;
}

Output
123
Let’s understand the example by tracing tree of recursive function. That is how the calls are made and how the
outputs are produced.
Time Complexity For Head Recursion: O(n)
Space Complexity For Head Recursion: O(n)
Note: Time & Space Complexity is given for this specific example. It may vary for another example.
Note: Head recursion can’t easily convert into loop as Tail Recursion but it can. Let’s convert the above code into
the loop.

// Converting Head Recursion into Loop

#include <stdio.h>

// Recursive function
void fun(int n)
{
int i = 1;
 while (i <= n) {
printf("%d ", i);
i++;
}
}

// Driver code
int main()
{
int x = 3;
fun(x);
return 0;
}

Output
123
 Tree Recursion: To understand Tree Recursion let’s first understand Linear Recursion. If a recursive
function calling itself for one time then it’s known as Linear Recursion. Otherwise if a recursive
function calling itself for more than one time then it’s known as Tree Recursion.
Example:
Pseudo Code for linear recursion
fun(n)
{
// some code
if(n>0)
{
fun(n-1); // Calling itself only once
}
// some code
}
Program for tree recursion
 // C program to show Tree Recursion

#include <stdio.h>

// Recursive function
void fun(int n)
{
if (n > 0) {
printf("%d ", n);

// Calling once
fun(n - 1);

// Calling twice
fun(n - 1);
}
}

// Driver code
int main()
{
fun(3);
return 0;
}

Output
3211211
Let’s understand the example by tracing tree of recursive function. That is how the calls are made and how the
outputs are produced.
Time Complexity For Tree Recursion: O(2^n)
Space Complexity For Tree Recursion: O(n)
Note: Time & Space Complexity is given for this specific example. It may vary for another example.
 Nested Recursion: In this recursion, a recursive function will pass the parameter as a recursive call. That
means “recursion inside recursion”. Let see the example to understand this recursion.

// C program to show Nested Recursion

#include <stdio.h>
int fun(int n)
{
if (n > 100)
return n - 10;

// A recursive function passing parameter

// as a recursive call or recursion
// inside the recursion
return fun(fun(n + 11));
}
 // Driver code
int main()
{
int r;
r = fun(95);
printf("%d\n", r);
return 0;
}

Output
91
Let’s understand the example by tracing tree of recursive function. That is how the calls are made and how the
outputs are produced.
2. Indirect Recursion: In this recursion, there may be more than one functions and they are calling one another
in a circular manner.
From the above diagram fun(A) is calling for fun(B), fun(B) is calling for fun(C) and fun(C) is calling for fun(A)
and thus it makes a cycle.
Output
20 19 9 8 4 3 1
Let’s understand the example by tracing tree of recursive function. That is how the calls are made and how the
outputs are produced.
C Program to Print Fibonacci Series
The Fibonacci series is the sequence where each number is the sum of the previous two
numbers of the sequence. The first two numbers are 0 and 1 which are used to generate the
whole series.
Example
Input: n = 5
Output: 0 1 1 2 3
Explanation: The first 5 terms of the Fibonacci series are 0, 1, 1, 2, 3.
Input: N = 7
Output: 0 1 1 2 3 5 8
Explanation: The first 7 terms of the Fibonacci series are 0, 1, 1, 2, 3, 5, 8.
In this article, we will learn how to print the Fibonacci series upto given number of Terms
Table of Content
 Print Fibonacci Series Using Loops
 Print Fibonacci Series Using Recursion
There are two major ways to compute and print the Fibonacci series in C:
Print Fibonacci Series Using Loops
We can use one of the C loops to iterate and print the given number of terms. The first two
terms, F1 and F2 should be handled separately. After that, we can use two variables to store
the previous two terms and print the current term by adding these two. We have to keep
updating the previous terms as we move to print the next term in the series.
Program to Print Fibonacci Series Upto n Terms
C
// C Program to print the fibonacci series using loops
#include <stdio.h>

void printFib(int n) {

// If the number of terms is smaller than 1

if (n < 1) {
printf("Invalid Number of terms\n");
return;
}
 // First two terms of the series
int prev1 = 1;
int prev2 = 0;

// for loop that prints n terms of fibonacci series

for (int i = 1; i <= n; i++) {

// Print current term and update previous terms

if (i > 2) {
int curr = prev1 + prev2;
prev2 = prev1;
prev1 = curr;
printf("%d ", curr);
}
else if (i == 1)
printf("%d ", prev2);
else (i == 2)
printf("%d ", prev1);
}
}

int main() {
int n = 9;

// Printing first n fibonacci terms

printFib(n);
return 0;
}

Output
0 1 1 2 3 5 8 13 21
Time Complexity: O(n), where n is the number of terms to be printed.
Space Complexity: O(1).
Print Fibonacci Series Using Recursion
We can also print Fibonacci series using recursion. This method is as much as popular as
iteration method.
We will use a function that prints the first two terms, and then call the recursive function that
handles the rest of the terms. In recursive function, we pass the previous two terms
Program to Print Fibonacci Series Upto n Terms Using Recursion
C
1
// C Program to print the Fibonacci series using recursion
2
#include <stdio.h>
3

4
// Recursive function to print the fibonacci series
5
void fib(int n, int prev1, int prev2) {
6
// Base Case: when n gets less than 3
7
if (n < 3) {
8
return;
9
}
10

11
int curr = prev1 + prev2;
12
prev2 = prev1;
13
prev1 = curr;
14
printf("%d ", curr);
15
return fib(n - 1, prev1, prev2);
16
}
17

18
// Function that handles the first two terms and calls the
19
// recursive function
20
void printFib(int n) {
21

22
// When the number of terms is less than 1
23
if (n < 1) {
24
printf("Invalid number of terms\n");
25
}
26
// When the number of terms is 1
27
else if (n == 1) {
28
printf("%d ", 0);
29
}
30
// When the number of terms is 2
31
else if (n == 2) {
32
printf("%d %d", 0, 1);
33
}
34
// When number of terms greater than 2
35
else {
36
printf("%d %d ", 0, 1);
37
fib(n, 0, 1);
38
}
39
return;
40
}
41
42
int main() {
43
int n = 9;
44

45
// Printing first 9 fibonacci series terms
46
printFib(n);
47

48
return 0;
49
}

Output
0 1 1 2 3 5 8 13 21
Time complexity: O(n), where n is the number of terms to be printed.
Space Complexity: O(n) for recursive stack space.

C Program for Tower of Hanoi

Tower of Hanoi is a mathematical puzzle where we have three rods and n disks. The objective
of the puzzle is to move the entire stack to another rod, obeying the following simple rules:
1) Only one disk can be moved at a time.
2) Each move consists of taking the upper disk from one of the stacks and placing it on top of
another stack i.e. a disk can only be moved if it is the uppermost disk on a stack.
3) No disk may be placed on top of a smaller disk.
  C

#include <stdio.h>

// C recursive function to solve tower of hanoi puzzle

void towerOfHanoi(int n, char from_rod, char to_rod, char aux_rod)
{
if (n == 1)
{
printf("\n Move disk 1 from rod %c to rod %c", from_rod, to_rod);
return;
}
towerOfHanoi(n-1, from_rod, aux_rod, to_rod);
printf("\n Move disk %d from rod %c to rod %c", n, from_rod, to_rod);
towerOfHanoi(n-1, aux_rod, to_rod, from_rod);
}

int main()
{
 int n = 4; // Number of disks
towerOfHanoi(n, 'A', 'C', 'B'); // A, B and C are names of rods
return 0;
}

Output:
Move disk 1 from rod A to rod B
Move disk 2 from rod A to rod C
Move disk 1 from rod B to rod C
Move disk 3 from rod A to rod B
Move disk 1 from rod C to rod A
Move disk 2 from rod C to rod B
Move disk 1 from rod A to rod B
Move disk 4 from rod A to rod C
Move disk 1 from rod B to rod C
Move disk 2 from rod B to rod A
Move disk 1 from rod C to rod A
Move disk 3 from rod B to rod C
Move disk 1 from rod A to rod B
Move disk 2 from rod A to rod C
Move disk 1 from rod B to rod C
Time Complexity: O(2n)
Auxiliary Space: O(n)

Difference between Iteration and Recursion

Property Recursion Iteration

A set of instructions repeatedly

Function calls itself.
Definition executed.
Property Recursion Iteration

Application For functions. For loops.

Through base case, where there When the termination condition for the
Termination will be no function call. iterator ceases to be satisfied.

Used when code size needs to be Used when time complexity needs to
small, and time complexity is not be balanced against an expanded code
Usage an issue. size.

Code Size Smaller code size Larger Code Size.

Relatively lower time

Very high(generally exponential)
Time complexity(generally polynomial-
time complexity.
Complexity logarithmic).

Space The space complexity is higher

Space complexity is lower.
Complexity than iterations.

Here the stack is used to store

local variables when the function Stack is not used.
Stack is called.

Execution is slow since it has the

Normally, it is faster than recursion as
overhead of maintaining and
it doesn’t utilize the stack.
Speed updating the stack.

Recursion uses more memory as Iteration uses less memory as

Memory compared to iteration. compared to recursion.

Possesses overhead of repeated No overhead as there are no function

Overhead function calls. calls in iteration.

Infinite If the recursive function does not If the control condition of the iteration
Property Recursion Iteration

meet to a termination condition

statement never becomes false or the
or the base case is not defined or
control variable does not reach the
is never reached then it leads to a
termination value, then it will cause
stack overflow error and there is
infinite loop. On the infinite loop, it
a chance that the an system may
uses the CPU cycles again and again.
Repetition crash in infinite recursion.