UNIT III

Stacks & Queues

Stacks & Queues: Stacks: Array and linked representation and implementation of stack,
Operations on Stacks: Push & Pop, Applications of stack: Conversion of Infix to Prefix and
Postfix Expressions, Evaluation of postfix expression using stack. Recursion: Introduction,
recursion in C, example of recursion, recursive functions. Queues: Array and linked
representation and implementation of queues, Operations on Queue: Create, Insert, Delete,
Full and Empty. Circular queue, Deques, and Priority Queues.

Stack
A stack is an Abstract Data Type (ADT), that is popularly used in most programming
languages. It is named stack because it has the similar operations as the real-world stacks, for
example – a pack of cards or a pile of plates, etc.

The stack follows the LIFO (Last in - First out) structure where the last element inserted
would be the first element deleted.

Stack Representation

A Stack ADT allows all data operations at one end only. At any given time, we can only
access the top element of a stack.
The following diagram depicts a stack and its operations −
A stack can be implemented by means of Array, Structure, Pointer, and Linked List. Stack
can either be a fixed size one or it may have a sense of dynamic resizing. Here, we are going
to implement stack using arrays, which makes it a fixed size stack implementation.

Basic Operations on Stacks

Stack operations usually are performed for initialization, usage and, de-initialization of the
stack ADT.
The most fundamental operations in the stack ADT include: push(), pop(), peek(), isFull(),
isEmpty(). These are all built-in operations to carry out data manipulation and to check the
status of the stack.
Stack uses pointers that always point to the topmost element within the stack, hence called as
the top pointer.
Insertion: push()
push() is an operation that inserts elements into the stack. The following is an algorithm that
describes the push() operation in a simpler way.
Algorithm
1 − Checks if the stack is full.
2 − If the stack is full, produces an error and exit.
3 − If the stack is not full, increments top to point next empty space.
4 − Adds data element to the stack location, where top is pointing.
5 − Returns success.
Example
Following are the implementations of this operation in various programming languages −
CC++Java
#include <stdio.h>
int MAXSIZE = 8;
int stack[8];
int top = -1;

/* Check if the stack is full*/

int isfull(){
if(top == MAXSIZE)
return 1;
else
return 0;
}

/* Function to insert into the stack */

int push(int data){
 if(!isfull()) {
top = top + 1;
stack[top] = data;
} else {
printf("Could not insert data, Stack is full.\n");
}
}

/* Main function */
int main(){
int i;
push(44);
push(10);
push(62);
push(123);
push(15);
printf("Stack Elements: \n");

// print stack data

for(i = 0; i < 8; i++) {
printf("%d ", stack[i]);
}
return 0;
}
Output
Stack Elements:
44 10 62 123 15 0 0 0
Note − In Java we have used to built-in method push() to perform this operation.
Deletion: pop()
pop() is a data manipulation operation which removes elements from the stack. The following
pseudo code describes the pop() operation in a simpler way.
Algorithm
1 − Checks if the stack is empty.
2 − If the stack is empty, produces an error and exit.
3 − If the stack is not empty, accesses the data element at which top is pointing.
4 − Decreases the value of top by 1.
5 − Returns success.
Example
Following are the implementations of this operation in various programming languages −
CC++JavaPython
#include <stdio.h>
int MAXSIZE = 8;
int stack[8];
int top = -1;

/* Check if the stack is empty */

int isempty(){
if(top == -1)
return 1;
else
return 0;
}

/* Check if the stack is full*/

int isfull(){
if(top == MAXSIZE)
return 1;
else
return 0;
}

/* Function to delete from the stack */

int pop(){
int data;
if(!isempty()) {
data = stack[top];
top = top - 1;
return data;
} else {
printf("Could not retrieve data, Stack is empty.\n");
}
}
/* Function to insert into the stack */
int push(int data){
if(!isfull()) {
top = top + 1;
stack[top] = data;
} else {
printf("Could not insert data, Stack is full.\n");
}
}

/* Main function */
int main(){
int i;
push(44);
push(10);
push(62);
push(123);
push(15);
printf("Stack Elements: \n");

// print stack data

for(i = 0; i < 8; i++) {
printf("%d ", stack[i]);
}
/*printf("Element at top of the stack: %d\n" ,peek());*/
printf("\nElements popped: \n");

// print stack data

while(!isempty()) {
int data = pop();
printf("%d ",data);
}
return 0;
}
Output
Stack Elements:
44 10 62 123 15 0 0 0
Elements popped:
15 123 62 10 44
Note − In Java we are using the built-in method pop().
peek()
The peek() is an operation retrieves the topmost element within the stack, without deleting it.
This operation is used to check the status of the stack with the help of the top pointer.
Algorithm
1. START
2. return the element at the top of the stack
3. END
Example
Following are the implementations of this operation in various programming languages −
CC++JavaPython
#include <stdio.h>
int MAXSIZE = 8;
int stack[8];
int top = -1;

/* Check if the stack is full */

int isfull(){
if(top == MAXSIZE)
return 1;
else
return 0;
}

/* Function to return the topmost element in the stack */

int peek(){
return stack[top];
}

/* Function to insert into the stack */

int push(int data){
if(!isfull()) {
top = top + 1;
 stack[top] = data;
} else {
printf("Could not insert data, Stack is full.\n");
}
}

/* Main function */
int main(){
int i;
push(44);
push(10);
push(62);
push(123);
push(15);
printf("Stack Elements: \n");

// print stack data

for(i = 0; i < 8; i++) {
printf("%d ", stack[i]);
}
printf("\nElement at top of the stack: %d\n" ,peek());
return 0;
}
Output
Stack Elements:
44 10 62 123 15 0 0 0
Element at top of the stack: 15
isFull()
isFull() operation checks whether the stack is full. This operation is used to check the status
of the stack with the help of top pointer.
Algorithm
1. START
2. If the size of the stack is equal to the top position of the stack, the stack is full. Return 1.
3. Otherwise, return 0.
4. END
Example
Following are the implementations of this operation in various programming languages −
CC++Java
#include <stdio.h>
int MAXSIZE = 8;
int stack[8];
int top = -1;

/* Check if the stack is full */

int isfull(){
if(top == MAXSIZE)
return 1;
else
return 0;
}

/* Main function */
int main(){
printf("Stack full: %s\n" , isfull()?"true":"false");
return 0;
}
Output
Stack full: false
isEmpty()
The isEmpty() operation verifies whether the stack is empty. This operation is used to check
the status of the stack with the help of top pointer.
Algorithm
1. START
2. If the top value is -1, the stack is empty. Return 1.
3. Otherwise, return 0.
4. END
Example
Following are the implementations of this operation in various programming languages −
CC++Java
#include <stdio.h>
int MAXSIZE = 8;
int stack[8];
int top = -1;

/* Check if the stack is empty */

int isempty() {
if(top == -1)
return 1;
else
return 0;
}

/* Main function */
int main() {
printf("Stack empty: %s\n" , isempty()?"true":"false");
return 0;
}
Output
Stack empty: true

What is a Stack?

A Stack is a linear data structure that follows the LIFO (Last-In-First-Out) principle. Stack
has one end, whereas the Queue has two ends (front and rear). It contains only one
pointer top pointer pointing to the topmost element of the stack. Whenever an element is
added in the stack, it is added on the top of the stack, and the element can be deleted only
from the stack. In other words, a stack can be defined as a container in which insertion and
deletion can be done from the one end known as the top of the stack.

Some key points related to stack

o It is called as stack because it behaves like a real-world stack, piles of books, etc.
o A Stack is an abstract data type with a pre-defined capacity, which means that it can
store the elements of a limited size.
o It is a data structure that follows some order to insert and delete the elements, and that
order can be LIFO or FILO.

Working of Stack

Stack works on the LIFO pattern. As we can observe in the below figure there are five
memory blocks in the stack; therefore, the size of the stack is 5.

Suppose we want to store the elements in a stack and let's assume that stack is empty. We
have taken the stack of size 5 as shown below in which we are pushing the elements one by
one until the stack becomes full.
Since our stack is full as the size of the stack is 5. In the above cases, we can observe that it
goes from the top to the bottom when we were entering the new element in the stack. The
stack gets filled up from the bottom to the top.

When we perform the delete operation on the stack, there is only one way for entry and exit
as the other end is closed. It follows the LIFO pattern, which means that the value entered
first will be removed last. In the above case, the value 5 is entered first, so it will be removed
only after the deletion of all the other elements.

Standard Stack Operations

The following are some common operations implemented on the stack:

o push(): When we insert an element in a stack then the operation is known as a push.
If the stack is full then the overflow condition occurs.
o pop(): When we delete an element from the stack, the operation is known as a pop. If
the stack is empty means that no element exists in the stack, this state is known as an
underflow state.
o isEmpty(): It determines whether the stack is empty or not.
o isFull(): It determines whether the stack is full or not.'
o peek(): It returns the element at the given position.
o count(): It returns the total number of elements available in a stack.
o change(): It changes the element at the given position.
o display(): It prints all the elements available in the stack.

PUSH operation

The steps involved in the PUSH operation is given below:

o Before inserting an element in a stack, we check whether the stack is full.

 o If we try to insert the element in a stack, and the stack is full, then
the overflow condition occurs.
o When we initialize a stack, we set the value of top as -1 to check that the stack is
empty.
o When the new element is pushed in a stack, first, the value of the top gets
incremented, i.e., top=top+1, and the element will be placed at the new position of
the top.
o The elements will be inserted until we reach the max size of the stack.

POP operation

The steps involved in the POP operation is given below:

o Before deleting the element from the stack, we check whether the stack is empty.
o If we try to delete the element from the empty stack, then the underflow condition
occurs.
o If the stack is not empty, we first access the element which is pointed by the top
o Once the pop operation is performed, the top is decremented by 1, i.e., top=top-1.
 Applications of Stack

The following are the applications of the stack:

o Balancing of symbols: Stack is used for balancing a symbol. For example, we have
the following program:

1. int main()
2. {
3. cout<<"Hello";
4. cout<<"javaTpoint";
5. }

As we know, each program has an opening and closing braces; when the opening braces
come, we push the braces in a stack, and when the closing braces appear, we pop the opening
braces from the stack. Therefore, the net value comes out to be zero. If any symbol is left in
the stack, it means that some syntax occurs in a program.

o String reversal: Stack is also used for reversing a string. For example, we want to
reverse a "javaTpoint" string, so we can achieve this with the help of a stack.
First, we push all the characters of the string in a stack until we reach the null
character.
After pushing all the characters, we start taking out the character one by one until we
reach the bottom of the stack.
o UNDO/REDO: It can also be used for performing UNDO/REDO operations. For
example, we have an editor in which we write 'a', then 'b', and then 'c'; therefore, the
text written in an editor is abc. So, there are three states, a, ab, and abc, which are
 stored in a stack. There would be two stacks in which one stack shows UNDO state,
and the other shows REDO state.
If we want to perform UNDO operation, and want to achieve 'ab' state, then we
implement pop operation.
o Recursion: The recursion means that the function is calling itself again. To maintain
the previous states, the compiler creates a system stack in which all the previous
records of the function are maintained.
o DFS(Depth First Search): This search is implemented on a Graph, and Graph uses
the stack data structure.
o Backtracking: Suppose we have to create a path to solve a maze problem. If we are
moving in a particular path, and we realize that we come on the wrong way. In order
to come at the beginning of the path to create a new path, we have to use the stack
data structure.
o Expression conversion: Stack can also be used for expression conversion. This is
one of the most important applications of stack. The list of the expression conversion
is given below:
o Infix to prefix
o Infix to postfix
o Prefix to infix
o Prefix to postfix
Postfix to infix
o Memory management: The stack manages the memory. The memory is assigned in
the contiguous memory blocks. The memory is known as stack memory as all the
variables are assigned in a function call stack memory. The memory size assigned to
the program is known to the compiler. When the function is created, all its variables
are assigned in the stack memory. When the function completed its execution, all the
variables assigned in the stack are released.

Array implementation of Stack

In array implementation, the stack is formed by using the array. All the operations regarding
the stack are performed using arrays. Lets see how each operation can be implemented on the
stack using array data structure.

Adding an element onto the stack (push operation)

Adding an element into the top of the stack is referred to as push operation. Push operation
involves following two steps.

1. Increment the variable Top so that it can now refere to the next memory location.
2. Add element at the position of incremented top. This is referred to as adding new
element at the top of the stack.
 Stack is overflown when we try to insert an element into a completely filled stack therefore,
our main function must always avoid stack overflow condition.

Algorithm:

1. begin
2. if top = n then stack full
3. top = top + 1
4. stack (top) : = item;
5. end

Time Complexity : o(1)

implementation of push algorithm in C language

1. void push (int val,int n) //n is size of the stack

2. {
3. if (top == n )
4. printf("\n Overflow");
5. else
6. {
7. top = top +1;
8. stack[top] = val;
9. }
10. }

Deletion of an element from a stack (Pop operation)

Deletion of an element from the top of the stack is called pop operation. The value of the
variable top will be incremented by 1 whenever an item is deleted from the stack. The top
most element of the stack is stored in an another variable and then the top is decremented by
1. the operation returns the deleted value that was stored in another variable as the result.

The underflow condition occurs when we try to delete an element from an already empty
stack.

Algorithm :

1. begin
2. if top = 0 then stack empty;
3. item := stack(top);
4. top = top - 1;
5. end;

Time Complexity : o(1)

Implementation of POP algorithm using C language

1. int pop ()
2. {
3. if(top == -1)
4. {
5. printf("Underflow");
6. return 0;
7. }
8. else
9. {
10. return stack[top - - ];
11. }
12. }

Visiting each element of the stack (Peek operation)

Peek operation involves returning the element which is present at the top of the stack without
deleting it. Underflow condition can occur if we try to return the top element in an already
empty stack.

Algorithm :

PEEK (STACK, TOP)

1. Begin
2. if top = -1 then stack empty
3. item = stack[top]
4. return item
5. End

Time complexity: o(n)

Implementation of Peek algorithm in C language

1. int peek()
2. {
3. if (top == -1)
4. {
5. printf("Underflow");
6. return 0;
7. }
8. else
9. {
10. return stack [top];
11. }
12. }

C program
1. #include <stdio.h>
2. int stack[100],i,j,choice=0,n,top=-1;
3. void push();
4. void pop();
5. void show();
6. void main ()
7. {
8.
9. printf("Enter the number of elements in the stack ");
10. scanf("%d",&n);
11. printf("*********Stack operations using array*********");
12.
13. printf("\n----------------------------------------------\n");
14. while(choice != 4)
15. {
16. printf("Chose one from the below options...\n");
17. printf("\[Link]\[Link]\[Link]\[Link]");
18. printf("\n Enter your choice \n");
19. scanf("%d",&choice);
20. switch(choice)
21. {
22. case 1:
23. {
24. push();
25. break;
26. }
27. case 2:
28. {
29. pop();
30. break;
31. }
32. case 3:
33. {
34. show();
35. break;
36. }
37. case 4:
38. {
39. printf("Exiting....");
40. break;
41. }
42. default:
43. {
44. printf("Please Enter valid choice ");
45. }
46. };
47. }
48. }
49.
50. void push ()
51. {
52. int val;
53. if (top == n )
54. printf("\n Overflow");
55. else
56. {
57. printf("Enter the value?");
58. scanf("%d",&val);
59. top = top +1;
60. stack[top] = val;
61. }
62. }
63.
64. void pop ()
65. {
66. if(top == -1)
67. printf("Underflow");
68. else
69. top = top -1;
70. }
71. void show()
72. {
73. for (i=top;i>=0;i--)
74. {
75. printf("%d\n",stack[i]);
76. }
77. if(top == -1)
78. {
79. printf("Stack is empty");
80. }
81. }

Linked list implementation of stack

Instead of using array, we can also use linked list to implement stack. Linked list allocates the
memory dynamically. However, time complexity in both the scenario is same for all the
operations i.e. push, pop and peek.

In linked list implementation of stack, the nodes are maintained non-contiguously in the
memory. Each node contains a pointer to its immediate successor node in the stack. Stack is
said to be overflown if the space left in the memory heap is not enough to create a node.
The top most node in the stack always contains null in its address field. Lets discuss the way
in which, each operation is performed in linked list implementation of stack.

Adding a node to the stack (Push operation)

Adding a node to the stack is referred to as push operation. Pushing an element to a stack in
linked list implementation is different from that of an array implementation. In order to push
an element onto the stack, the following steps are involved.

1. Create a node first and allocate memory to it.

2. If the list is empty then the item is to be pushed as the start node of the list. This
includes assigning value to the data part of the node and assign null to the address
part of the node.
3. If there are some nodes in the list already, then we have to add the new element in
the beginning of the list (to not violate the property of the stack). For this purpose,
assign the address of the starting element to the address field of the new node and
make the new node, the starting node of the list.

Time Complexity : o(1)

 C implementation :

1. void push ()
2. {
3. int val;
4. struct node *ptr =(struct node*)malloc(sizeof(struct node));
5. if(ptr == NULL)
6. {
7. printf("not able to push the element");
8. }
9. else
10. {
11. printf("Enter the value");
12. scanf("%d",&val);
13. if(head==NULL)
14. {
15. ptr->val = val;
16. ptr -> next = NULL;
17. head=ptr;
18. }
19. else
20. {
21. ptr->val = val;
22. ptr->next = head;
23. head=ptr;
24.
25. }
26. printf("Item pushed");
27.
28. }
29. }

Deleting a node from the stack (POP operation)

Deleting a node from the top of stack is referred to as pop operation. Deleting a node
from the linked list implementation of stack is different from that in the array
implementation. In order to pop an element from the stack, we need to follow the
following steps :

Check for the underflow condition: The underflow condition occurs when
we try to pop from an already empty stack. The stack will be empty if the head
pointer of the list points to null.

Adjust the head pointer accordingly: In stack, the elements are popped
only from one end, therefore, the value stored in the head pointer must be
deleted and the node must be freed. The next node of the head node now
becomes the head node.

Time Complexity : o(n)

C implementation

1. void pop()
2. {
3. int item;
4. struct node *ptr;
5. if (head == NULL)
6. {
7. printf("Underflow");
8. }
9. else
10. {
11. item = head->val;
12. ptr = head;
13. head = head->next;
14. free(ptr);
15. printf("Item popped");
16.
17. }
18. }

Display the nodes (Traversing)

Displaying all the nodes of a stack needs traversing all the nodes of the linked list
organized in the form of stack. For this purpose, we need to follow the following steps.

19. Copy the head pointer into a temporary pointer.

20. Move the temporary pointer through all the nodes of the list and print the
value field attached to every node.

Time Complexity : o(n)

C Implementation

1. void display()
2. {
3. int i;
4. struct node *ptr;
5. ptr=head;
6. if(ptr == NULL)
7. {
8. printf("Stack is empty\n");
9. }
10. else
11. {
12. printf("Printing Stack elements \n");
13. while(ptr!=NULL)
14. {
15. printf("%d\n",ptr->val);
16. ptr = ptr->next;
17. }
18. }
19. }

Menu Driven program in C implementing all the stack operations using

linked list :

1. #include <stdio.h>
2. #include <stdlib.h>
3. void push();
4. void pop();
5. void display();
6. struct node
7. {
8. int val;
9. struct node *next;
10. };
11. struct node *head;
12.
13. void main ()
14. {
15. int choice=0;
16. printf("\n*********Stack operations using linked list*********\n");
17. printf("\n----------------------------------------------\n");
18. while(choice != 4)
19. {
20. printf("\n\nChose one from the below options...\n");
21. printf("\[Link]\[Link]\[Link]\[Link]");
22. printf("\n Enter your choice \n");
23. scanf("%d",&choice);
24. switch(choice)
25. {
26. case 1:
27. {
28. push();
29. break;
30. }
31. case 2:
32. {
33. pop();
34. break;
35. }
36. case 3:
37. {
38. display();
39. break;
40. }
41. case 4:
42. {
43. printf("Exiting....");
44. break;
45. }
46. default:
47. {
48. printf("Please Enter valid choice ");
49. }
50. };
51. }
52. }
53. void push ()
54. {
55. int val;
56. struct node *ptr = (struct node*)malloc(sizeof(struct node));
57. if(ptr == NULL)
58. {
59. printf("not able to push the element");
60. }
61. else
62. {
63. printf("Enter the value");
64. scanf("%d",&val);
65. if(head==NULL)
66. {
67. ptr->val = val;
68. ptr -> next = NULL;
69. head=ptr;
70. }
71. else
72. {
73. ptr->val = val;
74. ptr->next = head;
75. head=ptr;
76.
77. }
78. printf("Item pushed");
79.
80. }
81. }
82.
83. void pop()
84. {
85. int item;
86. struct node *ptr;
87. if (head == NULL)
88. {
89. printf("Underflow");
90. }
91. else
92. {
93. item = head->val;
94. ptr = head;
95. head = head->next;
96. free(ptr);
97. printf("Item popped");
98.
99. }
100. }
 101. void display()
102. {
103. int i;
104. struct node *ptr;
105. ptr=head;
106. if(ptr == NULL)
107. {
108. printf("Stack is empty\n");
109. }
110. else
111. {
112. printf("Printing Stack elements \n");
113. while(ptr!=NULL)
114. {
115. printf("%d\n",ptr->val);
116. ptr = ptr->next;
117. }
118. }
119. }
----------------------------------------------------------------------------------------------------------------
1. PUSH: PUSH operation implies the insertion of a new element into a Stack. A new element is always inserted from
the topmost position of the Stack; thus, we always need to check if the top is empty or not, i.e., TOP=Max-1 if this
condition goes false, it means the Stack is full, and no more elements can be inserted, and even if we try to insert the
element, a Stack overflow message will be displayed.
Algorithm:
Step-1: If TOP = Max-1
Print “Overflow”
Goto Step 4
Step-2: Set TOP= TOP + 1
Step-3: Set Stack[TOP]= ELEMENT
Step-4: END

2. POP: POP means to delete an element from the Stack. Before deleting an element, make sure to check if the Stack
Top is NULL, i.e., TOP=NULL. If this condition goes true, it means the Stack is empty, and no deletion operation can be
performed, and even if we try to delete, then the Stack underflow message will be generated.
Algorithm:
Step-1: If TOP= NULL
Print “Underflow”
Goto Step 4
Step-2: Set VAL= Stack[TOP]
Step-3: Set TOP= TOP-1
Step-4: END

3. PEEK: When we need to return the value of the topmost element of the Stack without deleting it from the Stack, the
Peek operation is used. This operation first checks if the Stack is empty, i.e., TOP = NULL; if it is so, then an
appropriate message will display, else the value will return.
Algorithm:
Step-1: If TOP = NULL
PRINT “Stack is Empty”
Goto Step 3
Step-2: Return Stack[TOP]
Step-3: END

Application of the Stack

1. A Stack can be used for evaluating expressions consisting of operands and operators.
2. Stacks can be used for Backtracking, i.e., to check parenthesis matching in an expression.
3. It can also be used to convert one form of expression to another form.
4. It can be used for systematic Memory Management.

Advantages of Stack
1. A Stack helps to manage the data in the ‘Last in First out’ method.
2. When the variable is not used outside the function in any program, the Stack can be used.
3. It allows you to control and handle memory allocation and deallocation.
4. It helps to automatically clean up the objects.

Disadvantages of Stack
1. It is difficult in Stack to create many objects as it increases the risk of the Stack overflow.
2. It has very limited memory.
3. In Stack, random access is not possible.

Notation:
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 −

[Link]. 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 −

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) −

[Link]. 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
We shall now look at the algorithm on how to evaluate postfix notation −
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

Convert Infix to Postfix notation

Before understanding the conversion from infix to postfix notation, we should know about the
infix and postfix notations separately.

An infix and postfix are the expressions. An expression consists of constants, variables, and
symbols. Symbols can be operators or parenthesis. All these components must be arranged
according to a set of rules so that all these expressions can be evaluated using the set of
rules.

Examples of expressions are:

5+6

PlayNext

Unmute

Current Time 0:00

Duration 18:10

Loaded: 0.37%

Fullscreen

Backward Skip 10sPlay VideoForward Skip 10s

A-B

(P * 5)

All the above expressions have a common structure, i.e., we have an operator between the
two operands. An Operand is an object or a value on which the operation is to be performed.
In the above expressions, 5, 6 are the operands while '+', '-', and '*' are the operators.

What is infix notation?

When the operator is written in between the operands, then it is known as infix notation.
Operand does not have to be always a constant or a variable; it can also be an expression
itself.

For example,

(p + q) * (r + s)

In the above expression, both the expressions of the multiplication operator are the operands,
i.e., (p + q), and (r + s) are the operands.

In the above expression, there are three operators. The operands for the first plus operator
are p and q, the operands for the second plus operator are r and s. While performing
the operations on the expression, we need to follow some set of rules to evaluate
the result. In the above expression, addition operation would be performed on the two
expressions, i.e., p+q and r+s, and then the multiplication operation would be performed.

Syntax of infix notation is given below:

<operand> <operator> <operand>

If there is only one operator in the expression, we do not require applying any rule. For
example, 5 + 2; in this expression, addition operation can be performed between the two
operands (5 and 2), and the result of the operation would be 7.

If there are multiple operators in the expression, then some rule needs to be followed to
evaluate the expression.

If the expression is:

4+6*2

If the plus operator is evaluated first, then the expression would look like:

10 * 2 = 20

If the multiplication operator is evaluated first, then the expression would look like:

4 + 12 = 16

The above problem can be resolved by following the operator precedence rules. In the
algebraic expression, the order of the operator precedence is given in the below table:

Operators Symbols

Parenthesis ( ), {}, [ ]

Exponents ^

Multiplication and Division *, /

Addition and Subtraction +,-

The first preference is given to the parenthesis; then next preference is given to the
exponents. In the case of multiple exponent operators, then the operation will be applied from
right to left.

For example:

2^2^3 = 2 ^ 8

= 256

After exponent, multiplication, and division operators are evaluated. If both the operators are
present in the expression, then the operation will be applied from left to right.

The next preference is given to addition and subtraction. If both the operators are available in
the expression, then we go from left to right.

The operators that have the same precedence termed as operator associativity. If we go
from left to right, then it is known as left-associative. If we go from right to left, then it is
known as right-associative.

Problem with infix notation

To evaluate the infix expression, we should know about the operator precedence rules, and
if the operators have the same precedence, then we should follow the associativity rules.
The use of parenthesis is very important in infix notation to control the order in which the
operation to be performed. Parenthesis improves the readability of the expression. An infix
expression is the most common way of writing expression, but it is not easy to parse and
evaluate the infix expression without ambiguity. So, mathematicians and logicians studied
this problem and discovered two other ways of writing expressions which are prefix and
postfix. Both expressions do not require any parenthesis and can be parsed without
ambiguity. It does not require operator precedence and associativity rules.

Postfix Expression

The postfix expression is an expression in which the operator is written after the operands.
For example, the postfix expression of infix notation ( 2+3) can be written as 23+.

Some key points regarding the postfix expression are:

o In postfix expression, operations are performed in the order in which they have written
from left to right.
o It does not any require any parenthesis.
o We do not need to apply operator precedence rules and associativity rules.

Algorithm to evaluate the postfix expression

o Scan the expression from left to right until we encounter any operator.
o Perform the operation
o Replace the expression with its computed value.
o Repeat the steps from 1 to 3 until no more operators exist.

Let's understand the above algorithm through an example.

Infix expression: 2 + 3 * 4
We will start scanning from the left most of the expression. The multiplication operator is an
operator that appears first while scanning from left to right. Now, the expression would be:

Expression = 2 + 34*

= 2 + 12

Again, we will scan from left to right, and the expression would be:

Expression = 2 12 +

= 14

Evaluation of postfix expression using stack.

o Scan the expression from left to right.

o If we encounter any operand in the expression, then we push the operand in the stack.
o When we encounter any operator in the expression, then we pop the corresponding
operands from the stack.
o When we finish with the scanning of the expression, the final value remains in the
stack.

Let's understand the evaluation of postfix expression using stack.

Example 1: Postfix expression: 2 3 4 * +

Input Stack

234*+ empty Push 2

34*+ 2 Push 3

4*+ 32 Push 4

*+ 432 Pop 4 and 3, and perform 4*3 = 12. Push 12 into the stack.

+ 12 2 Pop 12 and 2 from the stack, and perform 12+2 = 14. Push 14 into the stack.

The result of the above expression is 14.

Example 2: Postfix expression: 3 4 * 2 5 * +

Input Stack

34*25*+ empty Push 3

4*25*+ 3 Push 4
 *2 5 * + 43 Pop 3 and 4 from the stack and perform 3*4 = 12. Push 12 into the stack.

25*+ 12 Push 2

5*+ 2 12 Push 5

*+ 5 2 12 Pop 5 and 2 from the stack and perform 5*2 = 10. Push 10 into the stack.

+ 10 12 Pop 10 and 12 from the stack and perform 10+12 = 22. Push 22 into the stack.

The result of the above expression is 22.

Algorithm to evaluate postfix expression

1. Read a character
2. If the character is a digit, convert the character into int and push the integer into the
stack.
3. If the character is an operator,
o Pop the elements from the stack twice obtaining two operands.
o Perform the operation
o Push the result into the stack.

Conversion of infix to postfix

Here, we will use the stack data structure for the conversion of infix expression to prefix
expression. Whenever an operator will encounter, we push operator into the stack. If we
encounter an operand, then we append the operand to the expression.

Rules for the conversion from infix to postfix expression

1. Print the operand as they arrive.

2. If the stack is empty or contains a left parenthesis on top, push the incoming operator
on to the stack.
3. If the incoming symbol is '(', push it on to the stack.
4. If the incoming symbol is ')', pop the stack and print the operators until the left
parenthesis is found.
5. If the incoming symbol has higher precedence than the top of the stack, push it on the
stack.
6. If the incoming symbol has lower precedence than the top of the stack, pop and print
the top of the stack. Then test the incoming operator against the new top of the stack.
7. If the incoming operator has the same precedence with the top of the stack then use
the associativity rules. If the associativity is from left to right then pop and print the
 top of the stack then push the incoming operator. If the associativity is from right to
left then push the incoming operator.
8. At the end of the expression, pop and print all the operators of the stack.

Let's understand through an example.

Infix expression: K + L - M*N + (O^P) * W/U/V * T + Q

Input Expression Stack Postfix Expression

K K

+ +

L + KL

- - K L+

M - K L+ M

* -* K L+ M

N -* KL+MN

+ + K L + M N*
K L + M N* -

( +( K L + M N *-

O +( KL+MN*-O

^ +(^ K L + M N* - O

P +(^ K L + M N* - O P

) + K L + M N* - O P ^

* +* K L + M N* - O P ^

W +* K L + M N* - O P ^ W

/ +/ K L + M N* - O P ^ W *

U +/ K L + M N* - O P ^W*U

/ +/ K L + M N* - O P ^W*U/
 V +/ KL + MN*-OP^W*U/V

* +* KL+MN*-OP^W*U/V/

T +* KL+MN*-OP^W*U/V/T

+ + KL+MN*-OP^W*U/V/T*
KL+MN*-OP^W*U/V/T*+

Q + KL+MN*-OP^W*U/V/T*Q

KL+MN*-OP^W*U/V/T*+Q+

The final postfix expression of infix expression(K + L - M*N + (O^P) * W/U/V * T + Q) is

KL+MN*-OP^W*U/V/T*+Q+.

Convert infix to prefix notation

What is infix notation?

An infix notation is a notation in which an expression is written in a usual or normal format. It

is a notation in which the operators lie between the operands. The examples of infix notation
are A+B, A*B, A/B, etc.

As we can see in the above examples, all the operators exist between the operands, so they
are infix notations. Therefore, the syntax of infix notation can be written as:

<operand> <operator> <operand>

Parsing Infix expressions

In order to parse any expression, we need to take care of two things, i.e., Operator
precedence and Associativity. Operator precedence means the precedence of any operator
over another operator. For example:

PlayNext

Unmute

Current Time 0:00

Duration 18:10
 Loaded: 0.37%

Fullscreen

Backward Skip 10sPlay VideoForward Skip 10s

A + B * C → A + (B * C)

As the multiplication operator has a higher precedence over the addition operator so B * C
expression will be evaluated first. The result of the multiplication of B * C is added to the A.

Precedence order

Operators Symbols

Parenthesis { }, ( ), [ ]

Exponential notation ^

Multiplication and Division *, /

Addition and Subtraction +, -

Associativity means when the operators with the same precedence exist in the expression.
For example, in the expression, i.e., A + B - C, '+' and '-' operators are having the same
precedence, so they are evaluated with the help of associativity. Since both '+' and '-' are
left-associative, they would be evaluated as (A + B) - C.

Associativity order

Operators Associativity

^ Right to Left

*, / Left to Right

+, - Left to Right

Let's understand the associativity through an example.

1 + 2*3 + 30/5

Since in the above expression, * and / have the same precedence, so we will apply the
associativity rule. As we can observe in the above table that * and / operators have the left to
right associativity, so we will scan from the leftmost operator. The operator that comes first
will be evaluated first. The operator * appears before the / operator, and multiplication would
be done first.
1+ (2*3) + (30/5)

1+6+6 = 13

What is Prefix notation?

A prefix notation is another form of expression but it does not require other information such
as precedence and associativity, whereas an infix notation requires information of precedence
and associativity. It is also known as polish notation. In prefix notation, an operator comes
before the operands. The syntax of prefix notation is given below:

<operator> <operand> <operand>

For example, if the infix expression is 5+1, then the prefix expression corresponding to this
infix expression is +51.

If the infix expression is:

a*b+c

*ab+c

+*abc (Prefix expression)

Consider another example:

A+B*C

First scan: In the above expression, multiplication operator has a higher precedence than
the addition operator; the prefix notation of B*C would be (*BC).

A + *BC

Second scan: In the second scan, the prefix would be:

+A *BC

In the above expression, we use two scans to convert infix to prefix expression. If the
expression is complex, then we require a greater number of scans. We need to use that
method that requires only one scan, and provides the desired result. If we achieve the desired
output through one scan, then the algorithm would be efficient. This is possible only by using
a stack.

Conversion of Infix to Prefix using Stack

K + L - M * N + (O^P) * W/U/V * T + Q

If we are converting the expression from infix to prefix, we need first to reverse the
expression.

The Reverse expression would be:

Q + T * V/U/W * ) P^O(+ N*M - L + K

To obtain the prefix expression, we have created a table that consists of three columns, i.e.,
input expression, stack, and prefix expression. When we encounter any symbol, we simply
add it into the prefix expression. If we encounter the operator, we will push it into the stack.

Input expression Stack Prefix expression

Q Q

+ + Q

T + QT

* +* QT

V +* QTV

/ +*/ QTV

U +*/ QTVU

/ +*// QTVU

W +*// QTVUW

* +*//* QTVUW

) +*//*) QTVUW

P +*//*) QTVUWP

^ +*//*)^ QTVUWP

O +*//*)^ QTVUWPO

( +*//* QTVUWPO^

+ ++ QTVUWPO^*//*

N ++ QTVUWPO^*//*N

* ++* QTVUWPO^*//*N

M ++* QTVUWPO^*//*NM
 - ++- QTVUWPO^*//*NM*

L ++- QTVUWPO^*//*NM*L

+ ++-+ QTVUWPO^*//*NM*L

K ++-+ QTVUWPO^*//*NM*LK

QTVUWPO^*//*NM*LK+-++

The above expression, i.e., QTVUWPO^*//*NM*LK+-++, is not a final expression. We need to

reverse this expression to obtain the prefix expression.

Rules for the conversion of infix to prefix expression:

o First, reverse the infix expression given in the problem.

o Scan the expression from left to right.
o Whenever the operands arrive, print them.
o If the operator arrives and the stack is found to be empty, then simply push the
operator into the stack.
o If the incoming operator has higher precedence than the TOP of the stack, push the
incoming operator into the stack.
o If the incoming operator has the same precedence with a TOP of the stack, push the
incoming operator into the stack.
o If the incoming operator has lower precedence than the TOP of the stack, pop, and
print the top of the stack. Test the incoming operator against the top of the stack
again and pop the operator from the stack till it finds the operator of a lower
precedence or same precedence.
o If the incoming operator has the same precedence with the top of the stack and the
incoming operator is ^, then pop the top of the stack till the condition is true. If the
condition is not true, push the ^ operator.
o When we reach the end of the expression, pop, and print all the operators from the
top of the stack.
o If the operator is ')', then push it into the stack.
o If the operator is '(', then pop all the operators from the stack till it finds ) opening
bracket in the stack.
o If the top of the stack is ')', push the operator on the stack.
o At the end, reverse the output.

Pseudocode of infix to prefix conversion

1. Function InfixtoPrefix( stack, infix)

2. infix = reverse(infix)
3. loop i = 0 to [Link]
4. if infix[i] is operand → prefix+= infix[i]
5. else if infix[i] is '(' → [Link](infix[i])
6. else if infix[i] is ')' → pop and print the values of stack till the symbol ')' is not found
7. else if infix[i] is an operator(+, -, *, /, ^) →
8.
9. if the stack is empty then push infix[i] on the top of the stack.
10. Else →
11. If precedence(infix[i] > precedence([Link]))
12. → Push infix[i] on the top of the stack
13. else if(infix[i] == precedence([Link]) && infix[i] == '^')
14. → Pop and print the top values of the stack till the condition is true
15. → Push infix[i] into the stack
16. else if(infix[i] == precedence([Link]))
17. → Push infix[i] on to the stack
18. Else if(infix[i] < precedence([Link]))
19. → Pop the stack values and print them till the stack is not empty and infix[i] < precedence(st
[Link])
20. → Push infix[i] on to the stack
21. End loop
22. Pop and print the remaining elements of the stack
23. Prefix = reverse(prefix)
24. return

Conversion of Prefix to Postfix expression

Before understanding the conversion of prefix to postfix conversion, we should know about
the prefix and postfix expressions separately.

What is Prefix conversion?

An infix expression is an expression in which the operators are written between the two
operands. If we move the operator before the operands then it is known as a prefix
expression. In other words, prefix expression can be defined as an expression in which all the
operators precede the two operands.

For example:

If the infix expression is given as: A + B * C

As we know that the multiplication operator * has a higher precedence than the addition
operator. First, multiplication operator will move before operand B shown as below:

A+*BC

Once the multiplication operator is moved before 'B' operand, addition operator will move
before the operand 'A' shown as below:

+A*BC

Evaluation of Prefix Expression using Stack

Step 1: Initialize a pointer 'S' pointing to the end of the expression.

Step 2: If the symbol pointed by 'S' is an operand then push it into the stack.

Step 3: If the symbol pointed by 'S' is an operator then pop two operands from the stack.
Perform the operation on these two operands and stores the result into the stack.

Step 4: Decrement the pointer 'S' by 1 and move to step 2 as long as the symbols left in the
expression.

Step 5: The final result is stored at the top of the stack and return it.

Step 6: End

Let's understand the evaluation of prefix expression through an example.

Expression: +, -, *, 2, 2, /, 16, 8, 5

First, we will reverse the expression given above.

Expression: 5, 8, 16, /, 2, 2, *, -, +

We will use the stack data structure to evaluate the prefix expression.

Symbol Scanned Stack

5 5

8 5, 8

16 5, 8, 16

/ 5, 2

2 5, 2, 2

2 5, 2, 2, 2

* 5, 2, 4

- 5, 2

+ 7

The final result of the above expression is 7.

What is Postfix expression?

If we move the operators after the operands then it is known as a postfix expression. In other
words, postfix expression can be defined as an expression in which all the operators are
present after the operands.

For example:

If the infix expression is A + B * C

As we know that the multiplication operator has a higher precedence than the addition
operator, so multiplication operator will move after the operands B and C shown as below:

A+BC*

Once the multiplication operator is moved after the operand C, then the addition operator will
come after the multiplication operator shown as below:

ABC*+

Evaluation of Postfix expression using Stack

Algorithm for the evaluation of postfix expression using stack:

Step 1: Create an empty stack used for storing the operands.

Step 2: Scan each element of an expression one be one and do the following:

o If the element is an operand then push it into the stack.

o If the element is an operator then pop two operands from the stack. Perform operation
on these operands. Push the final result into the stack.

Step 3: When the expression is scanned completely, the value available in the stack would
be the final output of the given expression.

Let's understand the evaluation of postfix expression using stack through an

example.

If the expression is: 5, 6, 2, +, *, 12, 4, /, -

Symbol Scanned Stack

5 5

6 5, 6

2 5, 6, 2

+ 5, 8

* 40

12 40, 12
 4 40, 12, 4

/ 40, 3

- 37

The result of the above expression is 37.

Conversion of Prefix to Postfix Expression

Here, we will see the conversion of prefix to postfix expression using a stack data structure.

Rules for prefix to postfix expression using stack data structure:

o Scan the prefix expression from right to left, i.e., reverse.

o If the incoming symbol is an operand then push it into the stack.
o If the incoming symbol is an operator then pop two operands from the stack. Once the
operands are popped out from the stack, we add the incoming symbol after the
operands. When the operator is added after the operands, then the expression is
pushed back into the stack.
o Once the whole expression is scanned, pop and print the postfix expression from the
stack.

Pseudocode for prefix to postfix conversion

1. Function PrefixToPostfix(string prefix)

2. 1. Stack s
3. 2. Loop: i = [Link]-1 to 0
4. • if prefix[i] is operand ->
5. [Link](prefix[i])
6. • else if prefix[i] is operator->
7. op1 = [Link]()
8. [Link]()
9. op2 = [Link]()
10. [Link]()
11. exp = op1 + op2 + prefix[i]
12. [Link](exp)
13. End Loop
14. 3. Return [Link]

Let's understand the conversion of Prefix to Postfix expression using Stack through
an example.

If the expression is: * - A / B C - / A K L

Symbols to be Action Stack Description

 scanned

L Push L into the stack L

K Push K into the stack L, K

A Push A into the stack L, K, A

/ Pop A from the stack L, A K / Pop two operands from the stack, i.e., A and K.
Pop K from the stack Add '/' operator after K operand, i.e., AK/. Push
Push A K / into the stack AK/ into the stack.

- Pop A K / and L from the AK/L- Pop two operands from the stack, i.e., AK/ and
stack. L. Add '-' operator after 'L' operand.
Push (A K / L -) into the stack

C Push C into the stack AK/L-, C

B Push B into the stack AK/L-,

C, B

/ Pop B and C from the stack. AK/L-, Pop two operands from the stack, i.e., B and C.
Push BC/ into the stack. BC/ Add '/' operator after C operator, i.e., BC/. Push
BC/ into the stack.

A Push A into the stack AK/L-,

BC/, A

- Pop BC/ and A from the stack. AK/L-, Pop two operands from the stack, i.e., A and
Push ABC/- into the stack. ABC/- BC/. Add '-' operator after '/'.

* Pop ABC/- and AK/L- from the ABC/- Pop two operands from the stack, i.e., ABC/-,
stack. Push ABC/AK/L-* into AK/L-* and AK/L- . Add '*' operator after L and '-'
the stack. operator, i.e., ABC/-AK/L-*.

Queue
Queue, like Stack, is also an abstract data structure. The thing that makes queue different from stack is
that a queue is open at both its ends. Hence, it follows FIFO (First-In-First-Out) structure, i.e. the data item
inserted first will also be accessed first. The data is inserted into the queue through one end and deleted
from it using the other end.
A real-world example of queue can be a single-lane one-way road, where the vehicle enters first, exits first.
More real-world examples can be seen as queues at the ticket windows and bus-stops.

Representation of Queues
Similar to the stack ADT, a queue ADT can also be implemented using arrays, linked lists, or pointers. As a
small example in this tutorial, we implement queues using a one-dimensional array.

Basic Operations
Queue operations also include initialization of a queue, usage and permanently deleting the data from the
memory.
The most fundamental operations in the queue ADT include: enqueue(), dequeue(), peek(), isFull(),
isEmpty(). These are all built-in operations to carry out data manipulation and to check the status of the
queue.
Queue uses two pointers − front and rear. The front pointer accesses the data from the front end (helping
in enqueueing) while the rear pointer accesses data from the rear end (helping in dequeuing).

Insertion operation: enqueue()

The enqueue() is a data manipulation operation that is used to insert elements into the stack. The following
algorithm describes the enqueue() operation in a simpler way.

Algorithm
1 − START
2 – Check if the queue is full.
3 − If the queue is full, produce overflow error and exit.
4 − If the queue is not full, increment rear pointer to point the next empty space.
5 − Add data element to the queue location, where the rear is pointing.
6 − return success.
7 – END
Example
Following are the implementations of this operation in various programming languages −
CC++JavaPython
#include <stdio.h>

#include <string.h>

#include <stdlib.h>

#include <stdbool.h>

#define MAX 6

int intArray[MAX];

int front = 0;

int rear = -1;

int itemCount = 0;

bool isFull(){

return itemCount == MAX;

bool isEmpty(){

return itemCount == 0;

int removeData(){

int data = intArray[front++];

if(front == MAX) {

front = 0;

itemCount--;

return data;

void insert(int data){

if(!isFull()) {

if(rear == MAX-1) {

rear = -1;

intArray[++rear] = data;

itemCount++;

int main(){

insert(3);

insert(5);

insert(9);

insert(1);
 insert(12);

insert(15);

printf("Queue: ");

while(!isEmpty()) {

int n = removeData();

printf("%d ",n);

Output
Queue: 3 5 9 1 12 15
Deletion Operation: dequeue()
The dequeue() is a data manipulation operation that is used to remove elements from the stack. The
following algorithm describes the dequeue() operation in a simpler way.

Algorithm
1 – START
2 − Check if the queue is empty.
3 − If the queue is empty, produce underflow error and exit.
4 − If the queue is not empty, access the data where front is pointing.
5 − Increment front pointer to point to the next available data element.
6 − Return success.
7 – END
Example
Following are the implementations of this operation in various programming languages −
CC++JavaPython
#include <stdio.h>

#include <string.h>

#include <stdlib.h>

#include <stdbool.h>

#define MAX 6

int intArray[MAX];

int front = 0;

int rear = -1;

int itemCount = 0;

bool isFull(){

return itemCount == MAX;

bool isEmpty(){

return itemCount == 0;

void insert(int data){

if(!isFull()) {

if(rear == MAX-1) {
 rear = -1;

intArray[++rear] = data;

itemCount++;

int removeData(){

int data = intArray[front++];

if(front == MAX) {

front = 0;

itemCount--;

return data;

int main(){

int i;

/* insert 5 items */

insert(3);

insert(5);

insert(9);

insert(1);

insert(12);

insert(15);

printf("Queue: ");

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

printf("%d ", intArray[i]);

// remove one item

int num = removeData();

printf("\nElement removed: %d\n",num);

printf("Updated Queue: ");

while(!isEmpty()) {

int n = removeData();

printf("%d ",n);

}
Output
Queue: 3 5 9 1 12 15
Element removed: 3
Updated Queue: 5 9 1 12 15
The peek() Operation
The peek() is an operation which is used to retrieve the frontmost element in the queue, without deleting it.
This operation is used to check the status of the queue with the help of the pointer.

Algorithm
1 – START
2 – Return the element at the front of the queue
3 – END
Example
Following are the implementations of this operation in various programming languages −
CC++JavaPython
#include <stdio.h>

#include <string.h>

#include <stdlib.h>

#include <stdbool.h>

#define MAX 6

int intArray[MAX];

int front = 0;

int rear = -1;

int itemCount = 0;

int peek(){

return intArray[front];

bool isFull(){

return itemCount == MAX;

void insert(int data){

if(!isFull()) {

if(rear == MAX-1) {

rear = -1;

intArray[++rear] = data;

itemCount++;

int main(){

int i;
 /* insert 5 items */

insert(3);

insert(5);

insert(9);

insert(1);

insert(12);

insert(15);

printf("Queue: ");

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

printf("%d ", intArray[i]);

printf("\nElement at front: %d\n",peek());

Output
Queue: 3 5 9 1 12 15
Element at front: 3
The isFull() Operation
The isFull() operation verifies whether the stack is full.

Algorithm
1 – START
2 – If the count of queue elements equals the queue size, return true
3 – Otherwise, return false
4 – END
Example
Following are the implementations of this operation in various programming languages −
CC++Java
#include <stdio.h>

#include <string.h>

#include <stdlib.h>

#include <stdbool.h>

#define MAX 6

int intArray[MAX];

int front = 0;

int rear = -1;

int itemCount = 0;

bool isFull(){

return itemCount == MAX;

void insert(int data){

if(!isFull()) {

if(rear == MAX-1) {
 rear = -1;

intArray[++rear] = data;

itemCount++;

int main(){

int i;

/* insert 5 items */

insert(3);

insert(5);

insert(9);

insert(1);

insert(12);

insert(15);

printf("Queue: ");

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

printf("%d ", intArray[i]);

printf("\n");

if(isFull()) {

printf("Queue is full!\n");

Output
Queue: 3 5 9 1 12 15
Queue is full!
The isEmpty() operation
The isEmpty() operation verifies whether the stack is empty. This operation is used to check the status of
the stack with the help of top pointer.

Algorithm
1 – START
2 – If the count of queue elements equals zero, return true
3 – Otherwise, return false
4 – END
Example
Following are the implementations of this operation in various programming languages −
CC++Java
#include <stdio.h>

#include <string.h>

#include <stdlib.h>

#include <stdbool.h>
#define MAX 6

int intArray[MAX];

int front = 0;

int rear = -1;

int itemCount = 0;

bool isEmpty(){

return itemCount == 0;

int main(){

int i;

printf("Queue: ");

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

printf("%d ", intArray[i]);

printf("\n");

if(isEmpty()) {

printf("Queue is Empty!\n");

Output
Queue: 0 0 0 0 0 0
Queue is Empty!

Implementation of Queue
In this chapter, the algorithm implementation of the Queue data structure is performed in four programming
languages.
CC++JavaPython
#include <stdio.h>

#include <string.h>

#include <stdlib.h>

#include <stdbool.h>

#define MAX 6

int intArray[MAX];

int front = 0;

int rear = -1;

int itemCount = 0;

int peek(){

return intArray[front];

bool isEmpty(){
 return itemCount == 0;

bool isFull(){

return itemCount == MAX;

int size(){

return itemCount;

void insert(int data){

if(!isFull()) {

if(rear == MAX-1) {

rear = -1;

intArray[++rear] = data;

itemCount++;

int removeData(){

int data = intArray[front++];

if(front == MAX) {

front = 0;

itemCount--;

return data;

int main(){

/* insert 5 items */

insert(3);

insert(5);

insert(9);

insert(1);

insert(12);

// front : 0

// rear : 4

// ------------------
// index : 0 1 2 3 4

// ------------------

// queue : 3 5 9 1 12

insert(15);

// front : 0

// rear : 5

// ---------------------

// index : 0 1 2 3 4 5

// ---------------------

// queue : 3 5 9 1 12 15

if(isFull()) {

printf("Queue is full!\n");

// remove one item

int num = removeData();

printf("Element removed: %d\n",num);

// front : 1

// rear : 5

// -------------------

// index : 1 2 3 4 5

// -------------------

// queue : 5 9 1 12 15

// insert more items

insert(16);

// front : 1

// rear : -1

// ----------------------

// index : 0 1 2 3 4 5

// ----------------------

// queue : 16 5 9 1 12 15

// As queue is full, elements will not be inserted.

insert(17);

insert(18);
 // ----------------------

// index : 0 1 2 3 4 5

// ----------------------

// queue : 16 5 9 1 12 15

printf("Element at front: %d\n",peek());

printf("----------------------\n");

printf("index : 5 4 3 2 1 0\n");

printf("----------------------\n");

printf("Queue: ");

while(!isEmpty()) {

int n = removeData();

printf("%d ",n);

Output
Queue is full!
Element removed: 3
Element at front: 5
----------------------
index : 5 4 3 2 1 0
----------------------
Queue: 5 9 1 12 15 16

Queue
1. A queue can be defined as an ordered list which enables insert operations to be performed
at one end called REAR and delete operations to be performed at another end called FRONT.

2. Queue is referred to be as First In First Out list.

3. For example, people waiting in line for a rail ticket form a queue.
Applications of Queue
Due to the fact that queue performs actions on first in first out basis which is quite fair for the
ordering of actions. There are various applications of queues discussed as below.

1. Queues are widely used as waiting lists for a single shared resource like printer, disk,
CPU.
2. Queues are used in asynchronous transfer of data (where data is not being transferred
at the same rate between two processes) for eg. pipes, file IO, sockets.
3. Queues are used as buffers in most of the applications like MP3 media player, CD
player, etc.
4. Queue are used to maintain the play list in media players in order to add and remove
the songs from the play-list.
5. Queues are used in operating systems for handling interrupts.

Complexity

Data Structure Time Complexity Space Compleity

Average Worst Worst

Acces Searc Insertio Deletio Acces Searc Insertio Deletio

s h n n s h n n

Queue θ(n) θ(n) θ(1) θ(1) O(n) O(n) O(1) O(1) O(n)

Types of Queue
What is a Queue?
Queue is the data structure that is similar to the queue in the real world. A queue is a data
structure in which whatever comes first will go out first, and it follows the FIFO (First-In-First-
Out) policy. Queue can also be defined as the list or collection in which the insertion is done
from one end known as the rear end or the tail of the queue, whereas the deletion is done
from another end known as the front end or the head of the queue.

The real-world example of a queue is the ticket queue outside a cinema hall, where the
person who enters first in the queue gets the ticket first, and the last person enters in the
queue gets the ticket at last. Similar approach is followed in the queue in data structure.

The representation of the queue is shown in the below image -

Now, let's move towards the types of queue.

Types of Queue

There are four different types of queue that are listed as follows -

o Simple Queue or Linear Queue

o Circular Queue
o Priority Queue
o Double Ended Queue (or Deque)

Let's discuss each of the type of queue.

Simple Queue or Linear Queue

In Linear Queue, an insertion takes place from one end while the deletion occurs from another
end. The end at which the insertion takes place is known as the rear end, and the end at
which the deletion takes place is known as front end. It strictly follows the FIFO rule.

The major drawback of using a linear Queue is that insertion is done only from the rear end. If
the first three elements are deleted from the Queue, we cannot insert more elements even
though the space is available in a Linear Queue. In this case, the linear Queue shows the
overflow condition as the rear is pointing to the last element of the Queue.

Circular Queue

In Circular Queue, all the nodes are represented as circular. It is similar to the linear Queue
except that the last element of the queue is connected to the first element. It is also known as
Ring Buffer, as all the ends are connected to another end. The representation of circular
queue is shown in the below image -

The drawback that occurs in a linear queue is overcome by using the circular queue. If the
empty space is available in a circular queue, the new element can be added in an empty
space by simply incrementing the value of rear. The main advantage of using the circular
queue is better memory utilization.

Priority Queue

It is a special type of queue in which the elements are arranged based on the priority. It is a
special type of queue data structure in which every element has a priority associated with it.
Suppose some elements occur with the same priority, they will be arranged according to the
FIFO principle. The representation of priority queue is shown in the below image -
Insertion in priority queue takes place based on the arrival, while deletion in the priority
queue occurs based on the priority. Priority queue is mainly used to implement the CPU
scheduling algorithms.

There are two types of priority queue that are discussed as follows -

o Ascending priority queue - In ascending priority queue, elements can be inserted in

arbitrary order, but only smallest can be deleted first. Suppose an array with elements
7, 5, and 3 in the same order, so, insertion can be done with the same sequence, but
the order of deleting the elements is 3, 5, 7.
o Descending priority queue - In descending priority queue, elements can be
inserted in arbitrary order, but only the largest element can be deleted first. Suppose
an array with elements 7, 3, and 5 in the same order, so, insertion can be done with
the same sequence, but the order of deleting the elements is 7, 5, 3.

Deque (or, Double Ended Queue)

In Deque or Double Ended Queue, insertion and deletion can be done from both ends of the
queue either from the front or rear. It means that we can insert and delete elements from
both front and rear ends of the queue. Deque can be used as a palindrome checker means
that if we read the string from both ends, then the string would be the same.

Deque can be used both as stack and queue as it allows the insertion and deletion operations
on both ends. Deque can be considered as stack because stack follows the LIFO (Last In First
Out) principle in which insertion and deletion both can be performed only from one end. And
in deque, it is possible to perform both insertion and deletion from one end, and Deque does
not follow the FIFO principle.

The representation of the deque is shown in the below image -

There are two types of deque that are discussed as follows -

o Input restricted deque - As the name implies, in input restricted queue, insertion
operation can be performed at only one end, while deletion can be performed from
both ends.

o Output restricted deque - As the name implies, in output restricted queue, deletion
operation can be performed at only one end, while insertion can be performed from
both ends.

Now, let's see the operations performed on the queue.

Operations performed on queue

The fundamental operations that can be performed on queue are listed as follows -

o Enqueue: The Enqueue operation is used to insert the element at the rear end of the
queue. It returns void.
 o Dequeue: It performs the deletion from the front-end of the queue. It also returns the
element which has been removed from the front-end. It returns an integer value.
o Peek: This is the third operation that returns the element, which is pointed by the
front pointer in the queue but does not delete it.
o Queue overflow (isfull): It shows the overflow condition when the queue is
completely full.
o Queue underflow (isempty): It shows the underflow condition when the Queue is
empty, i.e., no elements are in the Queue.

Array representation of Queue

We can easily represent queue by using linear arrays. There are two variables i.e. front and
rear, that are implemented in the case of every queue. Front and rear variables point to the
position from where insertions and deletions are performed in a queue. Initially, the value of
front and queue is -1 which represents an empty queue. Array representation of a queue
containing 5 elements along with the respective values of front and rear, is shown in the
following figure.

The above figure shows the queue of characters forming the English word "HELLO". Since, No
deletion is performed in the queue till now, therefore the value of front remains -1 . However,
the value of rear increases by one every time an insertion is performed in the queue. After
inserting an element into the queue shown in the above figure, the queue will look something
like following. The value of rear will become 5 while the value of front remains same.
After deleting an element, the value of front will increase from -1 to 0. however, the queue
will look something like following.

Algorithm to insert any element in a queue

Check if the queue is already full by comparing rear to max - 1. if so, then return an overflow
error.

If the item is to be inserted as the first element in the list, in that case set the value of front
and rear to 0 and insert the element at the rear end.

Otherwise keep increasing the value of rear and insert each element one by one having rear
as the index.

Algorithm
 o Step 1: IF REAR = MAX - 1
Write OVERFLOW
Go to step
[END OF IF]
o Step 2: IF FRONT = -1 and REAR = -1
SET FRONT = REAR = 0
ELSE
SET REAR = REAR + 1
[END OF IF]
o Step 3: Set QUEUE[REAR] = NUM
o Step 4: EXIT

C Function

1. void insert (int queue[], int max, int front, int rear, int item)
2. {
3. if (rear + 1 == max)
4. {
5. printf("overflow");
6. }
7. else
8. {
9. if(front == -1 && rear == -1)
10. {
11. front = 0;
12. rear = 0;
13. }
14. else
15. {
16. rear = rear + 1;
17. }
18. queue[rear]=item;
19. }
20. }

Algorithm to delete an element from the queue

If, the value of front is -1 or value of front is greater than rear , write an underflow message
and exit.

Otherwise, keep increasing the value of front and return the item stored at the front end of
the queue at each time.

Algorithm

o Step 1: IF FRONT = -1 or FRONT > REAR

Write UNDERFLOW
 ELSE
SET VAL = QUEUE[FRONT]
SET FRONT = FRONT + 1
[END OF IF]
o Step 2: EXIT

C Function

1. int delete (int queue[], int max, int front, int rear)
2. {
3. int y;
4. if (front == -1 || front > rear)
5.
6. {
7. printf("underflow");
8. }
9. else
10. {
11. y = queue[front];
12. if(front == rear)
13. {
14. front = rear = -1;
15. else
16. front = front + 1;
17.
18. }
19. return y;
20. }
21. }

Menu driven program to implement queue using array

1. #include<stdio.h>
2. #include<stdlib.h>
3. #define maxsize 5
4. void insert();
5. void delete();
6. void display();
7. int front = -1, rear = -1;
8. int queue[maxsize];
9. void main ()
10. {
11. int choice;
12. while(choice != 4)
13. {
14. printf("\n*************************Main Menu*****************************\n");
15. printf("\
n=======================================================
==========\n");
16. printf("\[Link] an element\[Link] an element\[Link] the queue\[Link]\n");
17. printf("\nEnter your choice ?");
18. scanf("%d",&choice);
19. switch(choice)
20. {
21. case 1:
22. insert();
23. break;
24. case 2:
25. delete();
26. break;
27. case 3:
28. display();
29. break;
30. case 4:
31. exit(0);
32. break;
33. default:
34. printf("\nEnter valid choice??\n");
35. }
36. }
37. }
38. void insert()
39. {
40. int item;
41. printf("\nEnter the element\n");
42. scanf("\n%d",&item);
43. if(rear == maxsize-1)
44. {
45. printf("\nOVERFLOW\n");
46. return;
47. }
48. if(front == -1 && rear == -1)
49. {
50. front = 0;
51. rear = 0;
52. }
53. else
54. {
55. rear = rear+1;
56. }
57. queue[rear] = item;
58. printf("\nValue inserted ");
59.
60. }
61. void delete()
62. {
63. int item;
64. if (front == -1 || front > rear)
65. {
66. printf("\nUNDERFLOW\n");
67. return;
68.
69. }
70. else
71. {
72. item = queue[front];
73. if(front == rear)
74. {
75. front = -1;
76. rear = -1 ;
77. }
78. else
79. {
80. front = front + 1;
81. }
82. printf("\nvalue deleted ");
83. }
84.
85.
86. }
87.
88. void display()
89. {
90. int i;
91. if(rear == -1)
92. {
93. printf("\nEmpty queue\n");
94. }
95. else
96. { printf("\nprinting values .....\n");
97. for(i=front;i<=rear;i++)
98. {
99. printf("\n%d\n",queue[i]);
100. }
101. }
102. }

Output:
*************Main Menu**************

==============================================

[Link] an element
[Link] an element
[Link] the queue
[Link]

Enter your choice ?1

Enter the element

123

Value inserted

*************Main Menu**************

==============================================

[Link] an element
[Link] an element
[Link] the queue
[Link]

Enter your choice ?1

Enter the element

90

Value inserted

*************Main Menu**************

===================================

[Link] an element
[Link] an element
[Link] the queue
[Link]

Enter your choice ?2

value deleted

*************Main Menu**************
==============================================

[Link] an element
[Link] an element
[Link] the queue
[Link]

Enter your choice ?3

printing values .....

90

*************Main Menu**************
==============================================

[Link] an element
[Link] an element
[Link] the queue
[Link]

Enter your choice ?4

Drawback of array implementation

Although, the technique of creating a queue is easy, but there are some drawbacks of using
this technique to implement a queue.

o Memory wastage : The space of the array, which is used to store queue elements,
can never be reused to store the elements of that queue because the elements can
only be inserted at front end and the value of front might be so high so that, all the
space before that, can never be filled.

The above figure shows how the memory space is wasted in the array representation of
queue. In the above figure, a queue of size 10 having 3 elements, is shown. The value of the
front variable is 5, therefore, we can not reinsert the values in the place of already deleted
element before the position of front. That much space of the array is wasted and can not be
used in the future (for this queue).

o Deciding the array size

On of the most common problem with array implementation is the size of the array which
requires to be declared in advance. Due to the fact that, the queue can be extended at
runtime depending upon the problem, the extension in the array size is a time taking process
and almost impossible to be performed at runtime since a lot of reallocations take place. Due
to this reason, we can declare the array large enough so that we can store queue elements as
enough as possible but the main problem with this declaration is that, most of the array slots
(nearly half) can never be reused. It will again lead to memory wastage.

Linked List implementation of Queue

Due to the drawbacks discussed in the previous section of this tutorial, the array
implementation can not be used for the large scale applications where the queues are
implemented. One of the alternative of array implementation is linked list implementation of
queue.
 The storage requirement of linked representation of a queue with n elements is o(n) while the
time requirement for operations is o(1).

In a linked queue, each node of the queue consists of two parts i.e. data part and the link
part. Each element of the queue points to its immediate next element in the memory.

In the linked queue, there are two pointers maintained in the memory i.e. front pointer and
rear pointer. The front pointer contains the address of the starting element of the queue while
the rear pointer contains the address of the last element of the queue.

Insertion and deletions are performed at rear and front end respectively. If front and rear both
are NULL, it indicates that the queue is empty.

The linked representation of queue is shown in the following figure.

Operation on Linked Queue

There are two basic operations which can be implemented on the linked queues. The
operations are Insertion and Deletion.

Insert operation

The insert operation append the queue by adding an element to the end of the queue. The
new element will be the last element of the queue.

Firstly, allocate the memory for the new node ptr by using the following statement.

1. Ptr = (struct node *) malloc (sizeof(struct node));

There can be the two scenario of inserting this new node ptr into the linked queue.

In the first scenario, we insert element into an empty queue. In this case, the condition front
= NULL becomes true. Now, the new element will be added as the only element of the queue
and the next pointer of front and rear pointer both, will point to NULL.

1. ptr -> data = item;

2. if(front == NULL)
3. {
4. front = ptr;
5. rear = ptr;
6. front -> next = NULL;
7. rear -> next = NULL;
8. }

In the second case, the queue contains more than one element. The condition front = NULL
becomes false. In this scenario, we need to update the end pointer rear so that the next
pointer of rear will point to the new node ptr. Since, this is a linked queue, hence we also
need to make the rear pointer point to the newly added node ptr. We also need to make the
next pointer of rear point to NULL.

1. rear -> next = ptr;

2. rear = ptr;
3. rear->next = NULL;

In this way, the element is inserted into the queue. The algorithm and the C implementation is
given as follows.

Algorithm
o Step 1: Allocate the space for the new node PTR
o Step 2: SET PTR -> DATA = VAL
o Step 3: IF FRONT = NULL
SET FRONT = REAR = PTR
SET FRONT -> NEXT = REAR -> NEXT = NULL
ELSE
SET REAR -> NEXT = PTR
SET REAR = PTR
SET REAR -> NEXT = NULL
[END OF IF]
o Step 4: END

C Function
1. void insert(struct node *ptr, int item; )
2. {
3.
4.
5. ptr = (struct node *) malloc (sizeof(struct node));
6. if(ptr == NULL)
7. {
8. printf("\nOVERFLOW\n");
9. return;
10. }
11. else
12. {
13. ptr -> data = item;
14. if(front == NULL)
15. {
16. front = ptr;
17. rear = ptr;
18. front -> next = NULL;
19. rear -> next = NULL;
20. }
21. else
22. {
23. rear -> next = ptr;
24. rear = ptr;
25. rear->next = NULL;
26. }
27. }
28. }

Deletion

Deletion operation removes the element that is first inserted among all the queue elements.
Firstly, we need to check either the list is empty or not. The condition front == NULL becomes
true if the list is empty, in this case , we simply write underflow on the console and make exit.

Otherwise, we will delete the element that is pointed by the pointer front. For this purpose,
copy the node pointed by the front pointer into the pointer ptr. Now, shift the front pointer,
point to its next node and free the node pointed by the node ptr. This is done by using the
following statements.

1. ptr = front;
2. front = front -> next;
3. free(ptr);

The algorithm and C function is given as follows.

Algorithm
o Step 1: IF FRONT = NULL
Write " Underflow "
Go to Step 5
[END OF IF]
o Step 2: SET PTR = FRONT
o Step 3: SET FRONT = FRONT -> NEXT
o Step 4: FREE PTR
o Step 5: END

C Function
1. void delete (struct node *ptr)
2. {
3. if(front == NULL)
4. {
5. printf("\nUNDERFLOW\n");
6. return;
7. }
8. else
9. {
10. ptr = front;
11. front = front -> next;
12. free(ptr);
13. }
14. }

Menu-Driven Program implementing all the operations on Linked

Queue
1. #include<stdio.h>
2. #include<stdlib.h>
3. struct node
4. {
5. int data;
6. struct node *next;
7. };
8. struct node *front;
9. struct node *rear;
10. void insert();
11. void delete();
12. void display();
13. void main ()
14. {
15. int choice;
16. while(choice != 4)
17. {
18. printf("\n*************************Main Menu*****************************\n");
19. printf("\
n=======================================================
==========\n");
20. printf("\[Link] an element\[Link] an element\[Link] the queue\[Link]\n");
21. printf("\nEnter your choice ?");
22. scanf("%d",& choice);
23. switch(choice)
24. {
25. case 1:
26. insert();
27. break;
28. case 2:
29. delete();
30. break;
31. case 3:
32. display();
33. break;
34. case 4:
35. exit(0);
36. break;
37. default:
38. printf("\nEnter valid choice??\n");
39. }
40. }
41. }
42. void insert()
43. {
44. struct node *ptr;
45. int item;
46.
47. ptr = (struct node *) malloc (sizeof(struct node));
48. if(ptr == NULL)
49. {
50. printf("\nOVERFLOW\n");
51. return;
52. }
53. else
54. {
55. printf("\nEnter value?\n");
56. scanf("%d",&item);
57. ptr -> data = item;
58. if(front == NULL)
59. {
60. front = ptr;
61. rear = ptr;
62. front -> next = NULL;
63. rear -> next = NULL;
64. }
65. else
66. {
67. rear -> next = ptr;
68. rear = ptr;
69. rear->next = NULL;
70. }
71. }
72. }
73. void delete ()
74. {
75. struct node *ptr;
76. if(front == NULL)
77. {
78. printf("\nUNDERFLOW\n");
79. return;
80. }
81. else
82. {
83. ptr = front;
84. front = front -> next;
85. free(ptr);
86. }
87. }
88. void display()
89. {
90. struct node *ptr;
91. ptr = front;
92. if(front == NULL)
93. {
94. printf("\nEmpty queue\n");
95. }
96. else
97. { printf("\nprinting values .....\n");
98. while(ptr != NULL)
99. {
100. printf("\n%d\n",ptr -> data);
101. ptr = ptr -> next;
102. }
103. }
104. }

Output:

***********Main Menu**********

==============================

[Link] an element
[Link] an element
[Link] the queue
[Link]

Enter your choice ?1

Enter value?
123

***********Main Menu**********

==============================

[Link] an element
[Link] an element
[Link] the queue
[Link]
Enter your choice ?1

Enter value?
90

***********Main Menu**********

==============================

[Link] an element
[Link] an element
[Link] the queue
[Link]

Enter your choice ?3

printing values .....

123

90

***********Main Menu**********

==============================

[Link] an element
[Link] an element
[Link] the queue
[Link]

Enter your choice ?2

***********Main Menu**********

==============================
[Link] an element
[Link] an element
[Link] the queue
[Link]

Enter your choice ?3

printing values .....

90

***********Main Menu**********

==============================

[Link] an element
[Link] an element
[Link] the queue
[Link]

Enter your choice ?4

 Recursion in C
Recursion is the process which comes into existence when a function calls a copy of itself to
work on a smaller problem. Any function which calls itself is called recursive function, and
such function calls are called recursive calls. Recursion involves several numbers of recursive
calls. However, it is important to impose a termination condition of recursion. Recursion code
is shorter than iterative code however it is difficult to understand.

Recursion cannot be applied to all the problem, but it is more useful for the tasks that can be
defined in terms of similar subtasks. For Example, recursion may be applied to sorting,
searching, and traversal problems.

Generally, iterative solutions are more efficient than recursion since function call is always
overhead. Any problem that can be solved recursively, can also be solved iteratively.
However, some problems are best suited to be solved by the recursion, for example, tower of
Hanoi, Fibonacci series, factorial finding, etc.

In the following example, recursion is used to calculate the factorial of a number.

1. #include <stdio.h>
2. int fact (int);
3. int main()
4. {
5. int n,f;
6. printf("Enter the number whose factorial you want to calculate?");
7. scanf("%d",&n);
8. f = fact(n);
9. printf("factorial = %d",f);
10. }
11. int fact(int n)
12. {
13. if (n==0)
14. {
15. return 0;
16. }
17. else if ( n == 1)
18. {
19. return 1;
20. }
21. else
22. {
23. return n*fact(n-1);
24. }
25. }

Output
Enter the number whose factorial you want to calculate?5
factorial = 120
 We can understand the above program of the recursive method call by the figure given
below:

Recursive Function
A recursive function performs the tasks by dividing it into the subtasks. There is a termination
condition defined in the function which is satisfied by some specific subtask. After this, the
recursion stops and the final result is returned from the function.

The case at which the function doesn't recur is called the base case whereas the instances
where the function keeps calling itself to perform a subtask, is called the recursive case. All
the recursive functions can be written using this format.

Pseudocode for writing any recursive function is given below.

1. if (test_for_base)
2. {
3. return some_value;
4. }
5. else if (test_for_another_base)
6. {
7. return some_another_value;
8. }
9. else
10. {
11. // Statements;
12. recursive call;
13. }

Example of recursion in C
 Let's see an example to find the nth term of the Fibonacci series.

1. #include<stdio.h>
2. int fibonacci(int);
3. void main ()
4. {
5. int n,f;
6. printf("Enter the value of n?");
7. scanf("%d",&n);
8. f = fibonacci(n);
9. printf("%d",f);
10. }
11. int fibonacci (int n)
12. {
13. if (n==0)
14. {
15. return 0;
16. }
17. else if (n == 1)
18. {
19. return 1;
20. }
21. else
22. {
23. return fibonacci(n-1)+fibonacci(n-2);
24. }
25. }

Output
Enter the value of n?12
144

Memory allocation of Recursive method

Each recursive call creates a new copy of that method in the memory. Once some data is
returned by the method, the copy is removed from the memory. Since all the variables and
other stuff declared inside function get stored in the stack, therefore a separate stack is
maintained at each recursive call. Once the value is returned from the corresponding
function, the stack gets destroyed. Recursion involves so much complexity in resolving and
tracking the values at each recursive call. Therefore we need to maintain the stack and track
the values of the variables defined in the stack.

Let us consider the following example to understand the memory allocation of the recursive
functions.

1. int display (int n)

2. {
3. if(n == 0)
4. return 0; // terminating condition
5. else
6. {
7. printf("%d",n);
8. return display(n-1); // recursive call
9. }
10. }

Explanation

Let us examine this recursive function for n = 4. First, all the stacks are maintained which
prints the corresponding value of n until n becomes 0, Once the termination condition is
reached, the stacks get destroyed one by one by returning 0 to its calling stack. Consider the
following image for more information regarding the stack trace for the recursive functions.

Recursive
What is Recursion?
The process in which a function calls itself directly or indirectly is called recursion and the
corresponding function is called a recursive function. Using a recursive algorithm, certain problems
can be solved quite easily. Examples of such problems are Towers of Hanoi
(TOH), Inorder/Preorder/Postorder Tree Traversals , DFS of Graph, etc. A recursive function solves a
particular problem by calling a copy of itself and solving smaller subproblems of the original
problems. Many more recursive calls can be generated as and when required. It is essential to know
that we should provide a certain case in order to terminate this recursion process. So we can say
that every time the function calls itself with a simpler version of the original problem.
Need of Recursion

Recursion is an amazing technique with the help of which we can reduce the length of our code and
make it easier to read and write. It has certain advantages over the iteration technique which will be
discussed later. A task that can be defined with its similar subtask, recursion is one of the best
solutions for it. For example; The Factorial of a number.
Properties of Recursion:
Performing the same operations multiple times with different inputs.

In every step, we try smaller inputs to make the problem smaller.

Base condition is needed to stop the recursion otherwise infinite loop will occur.
Algorithm: Steps

The algorithmic steps for implementing recursion in a function

are as follows:

Step1 - Define a base case: Identify the simplest case for

which the solution is known or trivial. This is the stopping
condition for the recursion, as it prevents the function from
infinitely calling itself.

Step2 - Define a recursive case: Define the problem in terms

of smaller subproblems. Break the problem down into smaller
versions of itself, and call the function recursively to solve
each subproblem.

Step3 - Ensure the recursion terminates: Make sure that the

recursive function eventually reaches the base case, and does
not enter an infinite loop.

step4 - Combine the solutions: Combine the solutions of the

subproblems to solve the original problem.
A Mathematical Interpretation

Let us consider a problem that a programmer has to determine the sum of first n natural numbers,
there are several ways of doing that but the simplest approach is simply to add the numbers starting
from 1 to n. So the function simply looks like this,
approach(1) – Simply adding one by one

f(n) = 1 + 2 + 3 +……..+ n

but there is another mathematical approach of representing this,

approach(2) – Recursive adding

f(n) = 1 n=1

f(n) = n + f(n-1) n>1

There is a simple difference between the approach (1) and approach(2) and that is
in approach(2) the function “ f( ) ” itself is being called inside the function, so this phenomenon is
named recursion, and the function containing recursion is called recursive function, at the end, this
is a great tool in the hand of the programmers to code some problems in a lot easier and efficient
way.
How are recursive functions stored in memory?

Recursion uses more memory, because the recursive function adds to the stack with each recursive
call, and keeps the values there until the call is finished. The recursive function uses LIFO (LAST IN
FIRST OUT) Structure just like the stack data structure.

What is the base condition in recursion?

In the recursive program, the solution to the base case is provided and the solution to the bigger
problem is expressed in terms of smaller problems.

int fact(int n)
{
if (n < = 1) // base case
return 1;
else
return n*fact(n-1);
}
In the above example, the base case for n < = 1 is defined and the larger value of a number can be
solved by converting to a smaller one till the base case is reached.

How a particular problem is solved using recursion?

The idea is to represent a problem in terms of one or more smaller problems, and add one or more
base conditions that stop the recursion. For example, we compute factorial n if we know the
factorial of (n-1). The base case for factorial would be n = 0. We return 1 when n = 0.

Why Stack Overflow error occurs in recursion?

If the base case is not reached or not defined, then the stack overflow problem may arise. Let us
take an example to understand this.

int fact(int n)
{
// wrong base case (it may cause
// stack overflow).
if (n == 100)
return 1;

else
return n*fact(n-1);
}
If fact(10) is called, it will call fact(9), fact(8), fact(7), and so on but the number will never reach 100.
So, the base case is not reached. If the memory is exhausted by these functions on the stack, it will
cause a stack overflow error.

What is the difference between direct and indirect recursion?

A function fun is called direct recursive if it calls the same function fun. A function fun is called
indirect recursive if it calls another function say fun_new and fun_new calls fun directly or indirectly.
The difference between direct and indirect recursion has been illustrated in Table 1.
// An example of direct recursion

void directRecFun()
{
// Some code....

directRecFun();

// Some code...
}

// An example of indirect recursion

void indirectRecFun1()
{
// Some code...

indirectRecFun2();

// Some code...
}
void indirectRecFun2()
{
// Some code...

indirectRecFun1();
 // Some code...
}
What is the difference between tailed and non-tailed recursion?
A recursive function is tail recursive when a recursive call is the last thing executed by the function.

How memory is allocated to different function calls in recursion?

When any function is called from main(), the memory is allocated to it on the stack. A recursive
function calls itself, the memory for a called function is allocated on top of memory allocated to the
calling function and a different copy of local variables is created for each function call. When the
base case is reached, the function returns its value to the function by whom it is called and memory
is de-allocated and the process continues.
Let us take the example of how recursion works by taking a simple function.

CPP

// A C++ program to demonstrate working of

// recursion

#include <bits/stdc++.h>

using namespace std;

void printFun(int test)

if (test < 1)

return;

else {

cout << test << " ";

printFun(test - 1); // statement 2

cout << test << " ";

return;

// Driver Code

int main()

int test = 3;
 printFun(test);

Output

3 2 1 1 2 3
Time Complexity: O(1)
Auxiliary Space: O(1)

When printFun(3) is called from main(), memory is allocated to printFun(3) and a local variable test
is initialized to 3 and statement 1 to 4 are pushed on the stack as shown in below diagram. It first
prints ‘3’. In statement 2, printFun(2) is called and memory is allocated to printFun(2) and a local
variable test is initialized to 2 and statement 1 to 4 are pushed into the stack.
Similarly, printFun(2) calls printFun(1) and printFun(1) calls printFun(0). printFun(0) goes to if
statement and it return to printFun(1). The remaining statements of printFun(1) are executed and
it returns to printFun(2) and so on. In the output, values from 3 to 1 are printed and then 1 to 3 are
printed. The memory stack has been shown in below diagram.
Recursion VS Iteration

SR
Recursion Iteration
No.

Terminates when the base case becomes Terminates when the condition
1)
true. becomes false.

2) Used with functions. Used with loops.

 Every recursive call needs extra space in Every iteration does not require
3)
the stack memory. any extra space.

4) Smaller code size. Larger code size.

Now, let’s discuss a few practical problems which can be solved by using recursion and understand
its basic working. For basic understanding please read the following articles.
Basic understanding of Recursion.
Problem 1: Write a program and recurrence relation to find the Fibonacci series of n where n>2 .
Mathematical Equation:

n if n == 0, n == 1;
fib(n) = fib(n-1) + fib(n-2) otherwise;
Recurrence Relation:

T(n) = T(n-1) + T(n-2) + O(1)

Recursive program:

Input: n = 5
Output:

Fibonacci series of 5 numbers is : 0 1 1 2 3

Implementation:

// C code to implement Fibonacci series

#include <stdio.h>

// Function for fibonacci

int fib(int n)

// Stop condition

if (n == 0)

return 0;

// Stop condition

if (n == 1 || n == 2)

return 1;
 // Recursion function

else

return (fib(n - 1) + fib(n - 2));

// Driver Code

int main()

// Initialize variable n.

int n = 5;

printf("Fibonacci series "

"of %d numbers is: ",

n);

// for loop to print the fibonacci series.

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

printf("%d ", fib(i));

return 0;

Output

Fibonacci series of 5 numbers is: 0 1 1 2 3

Time Complexity: O(2n)
Auxiliary Space: O(n)

Here is the recursive tree for input 5 which shows a clear picture of how a big problem can be solved
into smaller ones.
fib(n) is a Fibonacci function. The time complexity of the given program can depend on the function
call.

fib(n) -> level CBT (UB) -> 2^n-1 nodes -> 2^n function call -> 2^n*O(1) -> T(n) = O(2^n)

For Best Case.

T(n) = θ(2^n\2)
Working:
Problem 2: Write a program and recurrence relation to find the Factorial of n where n>2 .
Mathematical Equation:

1 if n == 0 or n == 1;
f(n) = n*f(n-1) if n> 1;
Recurrence Relation:

T(n) = 1 for n = 0
T(n) = 1 + T(n-1) for n > 0
Recursive Program:
Input: n = 5
Output:
factorial of 5 is: 120
Implementation:

Implementation:

// C code to implement factorial

#include <stdio.h>

// Factorial function
int f(int n)
{
// Stop condition
if (n == 0 || n == 1)
return 1;

// Recursive condition
else
 return n * f(n - 1);
}

// Driver code
int main()
{
int n = 5;
printf("factorial of %d is: %d", n, f(n));
return 0;
}

Output

factorial of 5 is: 120

Time complexity: O(n)
Auxiliary Space: O(n)

Working:

Diagram of factorial Recursion function for user input 5.

Example: Real Applications of Recursion in real problems

Recursion is a powerful technique that has many applications in computer science and
programming. Here are some of the common applications of recursion:

Tree and graph traversal: Recursion is frequently used for traversing and searching data structures
such as trees and graphs. Recursive algorithms can be used to explore all the nodes or vertices of a
tree or graph in a systematic way.
Sorting algorithms: Recursive algorithms are also used in sorting algorithms such as quicksort and
merge sort. These algorithms use recursion to divide the data into smaller subarrays or sublists, sort
them, and then merge them back together.

Divide-and-conquer algorithms: Many algorithms that use a divide-and-conquer approach, such as

the binary search algorithm, use recursion to break down the problem into smaller subproblems.

Fractal generation: Fractal shapes and patterns can be generated using recursive algorithms. For
example, the Mandelbrot set is generated by repeatedly applying a recursive formula to complex
numbers.

Backtracking algorithms: Backtracking algorithms are used to solve problems that involve making a
sequence of decisions, where each decision depends on the previous ones. These algorithms can be
implemented using recursion to explore all possible paths and backtrack when a solution is not
found.

Memoization: Memoization is a technique that involves storing the results of expensive function
calls and returning the cached result when the same inputs occur again. Memoization can be
implemented using recursive functions to compute and cache the results of subproblems.