Name of Faculty: Ritika Patel

Module-2

Stacks: Definition, Stack Operations, Array Representation of Stacks, Stacks using Dynamic
Arrays, Stack Applications: Polish notation, Infix to postfix conversion, evaluation of postfix
expression.

Recursion -Factorial, GCD, Fibonacci Sequence, Tower of Hanoi,

Queues: Definition, Array Representation, Queue Operations, Circular Queues, Circular queues
using Dynamic arrays, Deque, Priority Queues and its problems

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.

1
Some key points related to stack
○ It is called as stack because it behaves like a real-world stack, piles of books, etc.

○ A Stack is an abstract data type with a pre-defined capacity, which means that it can store
the elements of a limited size.

○ It is a data structure that follows some order to insert and delete the elements, and that
order can be LIFO.

2
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.

3
 ● 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:

○ 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.

○ 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.

4
 ○ isEmpty(): It determines whether the stack is empty or not.

○ isFull(): It determines whether the stack is full or not.'

○ peek(): It returns the element at the given position.

○ count(): It returns the total number of elements available in a stack.

○ change(): It changes the element at the given position.

○ display(): It prints all the elements available in the stack.

AD

PUSH operation
The steps involved in the PUSH operation is given below:

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

○ If we try to insert the element in a stack, and the stack is full, then the overflow condition
occurs.

○ When we initialize a stack, we set the value of top as -1 to check that the stack is empty.

○ 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.

○ The elements will be inserted until we reach the max size of the stack.

5
POP operation
The steps involved in the POP operation is given below:

○ Before deleting the element from the stack, we check whether the stack is empty.

○ If we try to delete the element from the empty stack, then the underflow condition
occurs.

○ If the stack is not empty, we first access the element which is pointed by the top ○ Once the

pop operation is performed, the top is decremented by 1, i.e., top=top-1.

6
Applications of Stack
The following are the applications of the stack:

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

int main()

cout<<"Hello"; cout<<"Parul";

7
 ○
○ 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 error occurs in
a program.
2. String reversal:

○ Stack is also used for reversing a string.

○ For example, we want to reverse a "Parul" 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.

8
3. UNDO/REDO:

9
○ 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.

10
4. 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.

11
 5. DFS(Depth First Search): This search is implemented on a Graph, and Graph uses the stack data
structure.

The following diagram illustrate depth first search traversal of a tree.

12
13
6. 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.

14
15
7. 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:

Infix to prefix
Infix to postfix
Prefix to infix

Prefix to postfix Postfix to

infix

8. Memory management:

16
 ● 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:
17
begin if top = n then stack

full top = top + 1 stack (top) :

= item; end

Time Complexity : o(1)

implementation of push algorithm in C language

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

if (top == n ) printf("\n

Overflow"); else

top = top +1; stack[top]

= val;

18
Deletion of an element from a stack (Pop operation)
Deletion of an element from the top of the stack is called pop operation. 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 :

begin if top = 0 then stack

empty; item := stack(top); top =

top - 1; end;

Time Complexity : o(1)

Implementation of POP algorithm using C language

19
 int pop ()

if(top == -1)

{ printf("Underflow"); return

0;

else

return stack[top - - ];

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)

20
 Begin if top = -1 then stack

empty item = stack[top]

return item

End

Time complexity: o(1) -> For Peek & o(n) -> for visiting each element

21
Implementation of Peek algorithm in C language

int peek()

if (top == -1)

{ printf("Underflow"); return

0;

else

return stack [top];

Array Representation of Stacks in C:

22
#include <stdio.h> int

stack[100],i,j,choice=0,n,top=-1; void

push(); void pop(); void show(); void main

()

printf("Enter the number of elements in the stack ");

scanf("%d",&n); printf("*********Stack operations using

array*********");

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

!= 4)

printf("Chose one from the below options...\n");

printf("\n1.Push\n2.Pop\n3.Show\n4.Exit"); printf("\n

Enter your choice \n"); scanf("%d",&choice);

switch(choice)

23
case 1:

push(); break;

case 2:

pop(); break;

case 3:

show(); break;

case 4:

{ printf("Exiting....");

break;

default:

printf("Please Enter valid choice ");

24
 }

};

void push ()

{ int val; if (top == n )

printf("\n Overflow"); else

printf("Enter the value?"); scanf("%d",&val); top

= top +1; stack[top]

= val;

void pop ()

if(top == -1) printf("Underflow");

25
 else top = top

-1;

void show()

{ for (i=top;i>=0;i--)

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

if(top == -1)

printf("Stack is empty");

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.

26
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.

We’ll discuss the below points after completion of our module- 3 (LinkedList):

● Adding a node to the stack (Push operation)

● Deleting a node from the stack (POP operation)
● Display the nodes (Traversing)

● Menu Driven program in C implementing all the stack operations using linked lis t

Stack Applications: Polish notation

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

● Prefix expression is also called Polish Notation.

● Postfix expression is also called Reverse-Polish Notation.
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.

27
Examples of expressions are:

5+6A

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

AD

28
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

29
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 notation:

Syntax of postfix notation is given below:

<operand> <operand> <operator>

30
31
32
20 practice questions on the conversion of “Infix to Postfix”:

1. A + B * C - D
2. (A + B) * (C - D) / E
3. A * (B + C) - D / (E + F)
4. (A + B * C) - D / E
5. A * B + C / (D - E) * F
6. A + (B - C) * D + E
7. (A + B) * C + D - E / F
8. A * (B - C) + D / (E * F)
9. A + B * C - D / (E + F) * G
10. (A + B * C) - D / (E + F) * G 11. A * (B + C - D) - E / F + G
12. (A + B) * (C - D) + E / F - G
13. A + (B - C) * (D + E) - F / G
14. (A * B + C) - D / (E - F) * (G + H)
15. A * (B + C) - (D / E) + F * G - H
16. (A + B * C - D) / (E - F * G) + H
17. A * B + (C - D) / (E + F) - G * H + I
18. (A + B) * (C - D * E + F) - G + H / I
19. A + B * C - (D / E + F) * G - H + I * J
20. (A + B * C - D) / (E - F * G + H) * I - J

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.
33
 ● 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.

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

#include <stdio.h>

int fact (int); int main()

{ int n,f; printf("Enter the number whose factorial you want to

calculate?"); scanf("%d",&n); f = fact(n);

34
 printf("factorial = %d",f);

int fact(int n)

if (n==0)

return 0;

} else if ( n ==

1)

return 1;

else

return n*fact(n-1);

Output:

Enter the number whose factorial you want to calculate?5 factorial =

120
35
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.

Pseudocode for writing any recursive function is given below.

if (test_for_base)

return some_value;

36
 }

else if (test_for_another_base)

return some_another_value;

else

// Statements; recursive

call;

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

37
#include<stdio.h> int

fibonacci(int); void main

()

{ int n,f; printf("Enter the value of

n?"); scanf("%d",&n); f =

fibonacci(n); printf("%d",f);

int fibonacci (int n)

if (n==0)

return 0;

38
 }

else if (n == 1)

return 1;

else

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

Output
Enter the value of n?12
144
Let's see an example to find the nth term of the GCD (Greatest Common Divisor).

● GCD (Greatest Common Divisor) is the largest positive integer that divides two or
more integers without leaving a remainder.
● We can compute the GCD of two numbers using recursion and the Euclidean
algorithm.
● The Euclidean algorithm states that the GCD of two numbers a and b is equal to
the GCD of b and the remainder of dividing a by b.
● This process is repeated until the remainder becomes 0, at which point the GCD is
found.

39
 #include <stdio.h>

// Recursive function to compute the GCD int gcd(int

a, int b) { if (b == 0) { return a; // Base case:
GCD is a when b becomes 0
} else { return gcd(b, a % b); // Recursive case: GCD is computed
using Euclidean algorithm
}
}

int main() { int

num1, num2; printf("Enter two

numbers: "); scanf("%d %d",

&num1, &num2); int result =

gcd(num1, num2); printf("GCD:

%d\n", result);

return 0;
}

Tower of Hanoi
1. It is a classic problem where you try to move all the disks from one peg to another peg
using only three pegs.

2. Initially, all of the disks are stacked on top of each other with larger disks under the smaller
disks.

3. You may move the disks to any of three pegs as you attempt to relocate all of the disks,
but you cannot place the larger disks over smaller disks and only one disk can be transferred at
a time.

40
In the above 7 step all the disks from peg A will be transferred to C given Condition:

1. Only one disk will be shifted at a time.

2. Smaller disk can be placed on larger disk

41
#include <stdio.h>

// Recursive function to solve Tower of Hanoi problem

void towerOfHanoi(int numDisks, char source, char auxiliary, char destination) { if
(numDisks == 1) { printf("Move disk 1 from %c to %c\n", source, destination); return;
}

// Move numDisks-1 disks from source to auxiliary using destination as the auxiliary peg
towerOfHanoi(numDisks - 1, source, destination, auxiliary);

// Move the bottom disk from source to destination

printf("Move disk %d from %c to %c\n", numDisks, source, destination);

// Move the numDisks-1 disks from auxiliary to destination using source as the
auxiliary peg towerOfHanoi(numDisks - 1, auxiliary, source, destination);
}

int main() { int numDisks;

printf("Enter the number of disks: "); scanf("%d",

&numDisks);

printf("Tower of Hanoi solution:\n"); towerOfHanoi(numDisks, 'A',

'B', 'C');

return 0;
}

42
 Queues
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.

43
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, or
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.

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.

44
 ●

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

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

Operations performed on queue

The fundamental operations that can be performed on queue are listed as follows -
○ Enqueue: The Enqueue operation is used to insert the element at the rear end of the
queue. It returns void.

○ 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.

○ 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.

○ Queue overflow (isfull): It shows the overflow condition when the queue is completely
full.

45
 ○ Queue underflow (isempty): It shows the underflow condition when the Queue is empty,
i.e., no elements are in the Queue.

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

○ Simple Queue or Linear Queue

○ Circular Queue

○ Priority Queue

○ Double Ended Queue (or Deque)

1. 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.

46
 ● 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 -

So, to overcome such limitations, the concept of the circular queue was introduced.

47
 ● 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.

Operations on Circular Queue

The following are the operations that can be performed on a circular queue:

○ Front: It is used to get the front element from the Queue.

○ Rear: It is used to get the rear element from the Queue.

○ enQueue(value): This function is used to insert the new value in the Queue. The new
element is always inserted from the rear end.

48
 ○ deQueue(): This function deletes an element from the Queue. The deletion in a Queue
always takes place from the front end.

Enqueue operation
The steps of enqueue operation are given below:

○ First, we will check whether the Queue is full or not.

○ Initially the front and rear are set to -1. When we insert the first element in a Queue, front
and rear both are set to 0.

○ When we insert a new element, the rear gets incremented, i.e., rear=rear+1.

Scenarios for inserting an element

There are two scenarios in which queue is not full:

○ If rear != max - 1, then rear will be incremented to mod(maxsize) and the new value will
be inserted at the rear end of the queue.

○ If front != 0 and rear = max - 1, it means that queue is not full, then set the value of rear
to 0 and insert the new element there.

There are two cases in which the element cannot be inserted:

○ When front ==0 && rear = max-1, which means that front is at the first position of the
Queue and rear is at the last position of the Queue.

○ front== rear + 1;

Let's understand the enqueue and dequeue operation through

the diagrammatic representation.

49
50
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 -

51
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.

Characteristics of a Priority queue

A priority queue is an extension of a queue that contains the following characteristics:

○ Every element in a priority queue has some priority associated with it.

○ An element with the higher priority will be deleted before the deletion of the lesser
priority.

○ If two elements in a priority queue have the same priority, they will be arranged using the
FIFO principle.

Let's understand the priority queue through an example.

We have a priority queue that contains the following values:

1, 3, 4, 8, 14, 22

All the values are arranged in ascending order. Now, we will observe how the priority queue will
look after performing the following operations:

52
 ○ poll(): This function will remove the highest priority element from the priority queue. In
the above priority queue, the '1' element has the highest priority, so it will be removed
from the priority queue.

○ add(2): This function will insert '2' element in a priority queue. As 2 is the smallest
element among all the numbers so it will obtain the highest priority.

○ poll(): It will remove '2' element from the priority queue as it has the highest priority
queue.

○ add(5): It will insert 5 element after 4 as 5 is larger than 4 and lesser than 8, so it will
obtain the third highest priority in a priority queue.

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 -

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

AD

○ 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.

○ 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.

54
Operations performed on deque
There are the following operations that can be applied on a deque -

○ Insertion at front

○ Insertion at rear

○ Deletion at front

○ Deletion at rear

Addition to the above operations, the following operations are also supported in deque -

○ Get the front item from the deque

○ Get the rear item from the deque

○ Check whether the deque is full or not ○

Checks whether the deque is empty or not

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.

● Initially, the value of front and queue is -1 which represents an empty queue.

55
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".

After deleting an element, the value of front will increase from 0 to 1. however, the queue will
look something like following.

56
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

○ Step 1: IF REAR = MAX - 1

Write OVERFLOW
Go to step
[END OF IF]

○ Step 2: IF FRONT = -1 and REAR = -1

SET FRONT = REAR = 0

ELSE
SET REAR = REAR + 1

57
 [END OF IF]

○ Step 3: Set QUEUE[REAR] = NUM

○ Step 4: EXIT

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

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

Write UNDERFLOW
ELSE
SET VAL = QUEUE[FRONT]
SET FRONT = FRONT + 1
[END OF IF]

○ Step 2: EXIT

Menu driven program to implement queue using array

#include<stdio.h>

58
#include<stdlib.h> #define

maxsize 5 void insert(); void

delete(); void display(); int front

= -1, rear = -1; int

queue[maxsize]; void main

()

59
{

int choice; while(choice

!= 4)

printf("\n*************************Main Menu*****************************\n");

printf("\n1.insert an element\n2.Delete an element\n3.Display the

queue\n4.Exit\n"); printf("\nEnter your

choice ?"); scanf("%d",&choice);

switch(choice)

case 1:

insert();

break; case

2:

delete(); break;

60
 case 3:

display();

break; case

4:

exit(0); break;

default:

printf("\nEnter valid choice??\n");

void insert()

int item; printf("\nEnter the

element\n");

Name of Faculty: RITIKA PATEL 61

 scanf("\n%d",&item); if(rear ==

maxsize-1)

printf("\nOVERFLOW\n"); return;

if(front == -1 && rear == -1)

front = 0; rear

= 0;

else

rear = rear+1;

Name of Faculty: RITIKA PATEL 62

 queue[rear] = item; printf("\nValue

inserted ");

void delete()

int item; if (front == -1 ||

front > rear)

printf("\nUNDERFLOW\n"); return;

else

item = queue[front]; if(front

== rear)

front = -1; rear

Name of Faculty: RITIKA PATEL 63

 = -1 ;

else

front = front + 1;

printf("\nvalue deleted ");

void display()

{ int i; if(rear

== -1)

printf("\nEmpty queue\n");

Name of Faculty: RITIKA PATEL 64

 else

{ printf("\nprinting values .....\n");

for(i=front;i<=rear;i++)

Name of Faculty: RITIKA PATEL 65

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

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.

○ 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

Name of Faculty: RITIKA PATEL 66

 inserted at the front end and the value of the front might be so high so that, all the
space before that, can never be filled.

○ Deciding the array size

○ One of the most common problems with array implementation is the array size,
which must be declared in advance.

○ 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.

Name of Faculty: RITIKA PATEL 67