MODULE 2

STACKS
 STACKS

• A Stack is a linear data structure that follows the LIFO (Last-In-First-

Out) principle.

• Stack has one end. 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.

• 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.
 Stack operations
• 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.
• isEmpty(): It determines whether the stack is empty or not.
• isFull(): It determines whether the stack is full or not.
• display(): It prints all the elements available in the stack.
 PUSH Operation
• 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.
void push() //Inserting element into the stack
{
if(top==(max_size-1))
{
printf("\nStack Overflow:");
}
else
{
printf("Enter the element to be inserted:\t");
scanf("%d",&item);
top=top+1;
stack[top]=item;
}
}
 POP operation

• 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.
void pop() //deleting an element from the stack
{
if(top==-1)
{
printf("Stack Underflow:");

}
else
{
item=stack[top];
top=top-1;
}
}
 Stack display()
void display()
{
int i;
top=temp;

if(top==-1)
{
printf("\nStack is Empty:");
}
else
{
printf("\nThe stack elements are:\n" );
for(i=top;i>=0;i--)
{
printf("%d\n",stack[i]);
}
}
Conversion from infix to postfix
 Evaluation of suffix/postfix

Evaluation rule of a Postfix Expression states:

1.While reading the expression from left to right, push the element in the stack
if it is an operand.

2.Pop the two operands from the stack, if the element is an operator and then
evaluate it.

3.Push back the result of the evaluation. Repeat it till the end of the expression.
Infix Expression: (A+B)+C-(D-E)^F
 Prefix to infix
• Iterate the given expression from right to left (in reverse order), one
character at a time
1.If character is operand, push it to stack.
2.If character is operator,
1. pop operand from stack, say it’s s1.
2. pop operand from stack, say it’s s2.
3. perform (s1 operator s2) and push it to stack.
3.Once the expression iteration is completed, initialize result string and
pop out from stack and add it to result.
4.Return the result.
 Recursion

• 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

 Why to use recursion

1.Recursion adds clarity and (sometimes) reduces the time needed to

write and debug code (but doesn't necessarily reduce space
requirements or speed of execution).

2.Reduces time complexity.

3.Performs better in solving problems based on tree structures.

#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);
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);
 Tower of Hanoi
• Tower of Hanoi consists of three pegs or towers with n disks placed one
over the other.
• The objective of the puzzle is to move the stack to another peg following
these simple rules.
• Only one disk can be moved at a time.
• Each move consists of taking the upper disk from one of the stacks and
placing it on top of another stack i.e. a disk can only be moved if it is the
uppermost disk on a stack.
• No disk can be placed on top of the smaller disk
• The minimal number of moves required to solve a Tower of Hanoi puzzle
is 2n − 1, where n is the number of disks.
#include <stdio.h>
void towers(int, char, char, char); int main()
{
int num;
printf("Enter the number of disks : ");
scanf("%d", &num);
printf("The sequence of moves involved in the Tower of Hanoi are :\n");
towers(num, 'A', 'C', 'B');
return 0;
}
void towers(int num, char frompeg, char topeg, char auxpeg)
{
if (num == 1)
{
printf("\n Move disk 1 from peg %c to peg %c", frompeg, topeg);
return;
}
towers(num - 1, frompeg, auxpeg, topeg);
printf("\n Move disk %d from peg %c to peg %c", num, frompeg, topeg);
towers(num - 1, auxpeg, topeg, frompeg);
}
#include <stdio.h>
#include <math.h>
#define MAX 20
struct stack{
int top;
float str[MAX];
}s;//stack
char postfix[MAX];//postfix
void push(float);
float pop();
int isoperand(char);
float operate(float,float,char);
int main()
{
int i=0;
printf("Enter Expression:");
scanf("%s",postfix);
float ans,op1,op2;
while(postfix[i]!='\0')
{
if(isoperand(postfix[i]))
push(postfix[i]-48);
else
{
op1=pop(); op2=pop();
ans=operate(op1,op2,postfix[i]);
push(ans);
printf("%f %c %f = %f\n",op2,postfix[i],op1,ans);
}
i++;
}
printf("%f",s.str[s.top]);
}
int isoperand(char x)
{
if(x>='0' && x<='9’)
return 1;
else
return 0;
}
void push(float x)
{
if(s.top==MAX-1)
printf("Stack is full\nStack overflow\n");
else
{
s.top++;
s.str[s.top]=x;
}
}
void push(float x)
{
if(s.top==MAX-1)
printf("Stack is full\nStack overflow\n");
else
{
s.top++;
s.str[s.top]=x;
}
}
float pop()
{
if(s.top==-1)
{
printf("Stack is emplty\nSTACK UNDERFLOW\n");
getch();
}
else
{
s.top--;
return s.str[s.top+1];
float operate(float op1,float op2,char a)
{
switch(a)
{
case '+':return op2+op1;
case '-':return op2-op1;
case '*':return op2*op1;
case '/':return op2/op1;
case '^':return pow(op2,op1);
}
}
Reasons for why to substract 48 from e in above program:

If I type value as 8, it will read it as the character ASCII value of 56. If I also type value 9, it will read
it as the character ASCII value of 57.

If you add them, the program will do 58 + 59 and give you the wrong answer. So to actually get to
8 from 56, you subtract 48. 56 – 48 = 8. And 57 – 48 = 9.

So after converting the ASCII values to the actual integer value, you can proceed with 8 + 9 = 17.
Ackermann function
 Use of Ackermann function

• The Ackermann function, due to its definition in terms of extremely

deep recursion, can be used as a benchmark of a compiler's ability to
optimize recursion.

• the Ackermann function has also been used to measure performance

of implementations of recursive subroutine calls in programming
languages ..
What is Least Common Multiple
(LCM)?
• The least common multiple of two or more numbers is the smallest
number among all common multiples of the given numbers.
• Let us take two numbers, 2 and 5. Each will have its own set of
multiples.
• Multiples of 2 are 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, …
• Multiples of 5 are 5, 10, 15, 20, …
• LCM of 2 and 5 is 10.
 How do you find the LCM?

• Step 1: List the first few multiples of A and B.

• Step 2: Mark the common multiples from the multiples of both

numbers.

• Step 3: Select the smallest common multiple. That lowest common

multiple is the LCM of the two numbers.
 What gcd means?

• greatest common divisor

• The greatest common divisor (GCD) of two or more numbers is the

greatest common factor number that divides them, exactly. It is also
called the highest common factor (HCF)
#include <stdio.h>
int hcf(int n1, int n2);
int main() {
int n1, n2;
printf("Enter two positive integers: ");
scanf("%d %d", &n1, &n2);
printf("G.C.D of %d and %d is %d.", n1, n2, hcf(n1, n2));
return 0;
}

int hcf(int n1, int n2) {

if (n2 != 0)
return hcf(n2, n1 % n2);
else
return n1;
}
#include <stdio.h>
int gcd(int x, int y); //function prototype

int main()
{
int num1, num2, hcf, lcm;

printf("Enter two integer Values:\n");

scanf("%d %d", &num1, &num2);

hcf = gcd(num1, num2);

printf("GCD: %d", hcf);
printf("\nLCM: %d", (num1 * num2) / hcf);
return 0;
} //recursive function
int gcd(int x, int y)
{
if (y == 0) //recursion termination condition
{
return x;
}
else
{
return gcd(y, x % y); //calls itself
}
#include <stdio.h>

int factorial(int n) {
//base case
if(n == 0) {
return 1;
} else {
return n * factorial(n-1);
}
}
int fibbonacci(int n) {
if(n == 0){
return 0;
} else if(n == 1) {
return 1;
} else {
return (fibbonacci(n-1) + fibbonacci(n-2));
}
}

int main() {
int n = 5;
int i;

printf("Factorial of %d: %d\n" , n , factorial(n));

printf("Fibbonacci of %d: " , n);

for(i = 0;i<n;i++) {
printf("%d ",fibbonacci(i));
}
}
Factorial of 5: 120
Fibonacci of 5: 0 1 1 2 3
 QUEUES
• A queue is a linear data structure that stores the
elements sequentially. It uses the FIFO approach (First In
First Out) for accessing elements.
 Applications of Queue

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

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

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

• For example, people waiting in line for a rail ticket form a queue.
 Basic Operations of Queue

• Enqueue: Add an element to the end of the queue

• Dequeue: Remove an element from the front of the queue

• IsEmpty: Check if the queue is empty

• IsFull: Check if the queue is full

• Peek: Get the value of the front of the queue without removing it
 Working of Queue

• Queue operations work as follows:

• two pointers FRONT and REAR

• FRONT track the first element of the queue

• REAR track the last element of the queue

• initially, set value of FRONT and REAR to -1

 Drawbacks of QUEUES

• 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.
Enqueue Operation

• check if the queue is full

• for the first element, set the value of FRONT to 0

• increase the REAR index by 1

• add the new element in the position pointed to by REAR

void insert()
{
int element;
if (rear == CAPACITY - 1)
printf("Queue is full\n");
else
{
if (front == - 1)

front = 0;
printf("Enter element which is to be inserted ");
scanf("%d", &element);
rear = rear + 1;
queue_array[rear] = element;
}
} /* End of insert() */
 Dequeue Operation

• check if the queue is empty

• return the value pointed by FRONT

• increase the FRONT index by 1

• for the last element, reset the values of FRONT and REAR to -1
void delete()
{
if (front == - 1 || front > rear)
{
printf("Queue is empty we cannot delete an element \
n");
return ;
}
else
{
printf("Element deleted from queue is : %d\n",
queue_array[front]);
front = front + 1;
}
} /* End of delete()
void display()
{
int i;
if (front==-1 || front > rear)
printf("Queue is empty \n");
else
{
printf("Elements of Queue are: \n");
for (i = front; i <= rear; i++)
printf("%d ", queue_array[i]);
printf("\n");
}
}
 Circular queue

• Circular Queue is a special version of queue where the last element

of the queue is connected to the first element of the queue forming
a circle.

• The operations are performed based on FIFO (First In First Out)

principle. It is also called 'Ring Buffer'.
void enqueue(int element)
{
if(front==-1 && rear==-1) // condition to check queue is
empty
{
front=0;
rear=0;
queue[rear]=element;
}
else if((rear+1)%max==front) // condition to check queue is
full
{
printf("Queue is overflow..");
}
else
{
rear=(rear+1)%max; // rear is incremented
queue[rear]=element; // assigning a value to the queue at
the rear position.
}
}
int dequeue()
{
if((front==-1) && (rear==-1)) // condition to check queue is
empty
{
printf("\nQueue is underflow..");
}
else if(front==rear)
{
printf("\nThe dequeued element is %d", queue[front]);
front=-1;
rear=-1;
}
else
{
printf("\nThe dequeued element is %d", queue[front]);
front=(front+1)%max;
}
}
void display()
{
int i=front;
if(front==-1 && rear==-1)
{
printf("\n Queue is empty..");
}
else
{
printf("\nElements in a Queue are :");
while(i<=rear)
{
printf("%d,", queue[i]);
i=(i+1)%max;
}
}
 Data Structure Multiple Stack

• A single stack is sometimes not sufficient to store a large amount of data.

• To overcome this problem, we can use multiple stack. For this, we have used a single array having
more than one stack. The array is divided for multiple stacks.

• Suppose there is an array STACK[n] divided into two stack STACK A and STACK B, where n = 10.

• STACK A expands from the left to the right, i.e., from 0th element.

• STACK B expands from the right to the left, i.e., from 10th element.

• The combined size of both STACK A and STACK B never exceeds 10.
 Stacks vs multiple stacks
• Storage Efficiency: When we create a stack using a single array, it may
not be sufficient to store a large amount of data. By employing multiple
stacks within the same array, we can efficiently utilize memory space.
Each stack operates independently, allowing us to manage different data
sets effectively12.

• Dividing Workloads: Imagine an array called STACK[n] divided into

two stacks: STACK A and STACK B. This division allows us to handle
distinct tasks or workloads separately. For example, one stack could be
used for function calls, while the other manages temporary variables or
other data1.
 Stacks vs multiple stacks
• Balancing Load: In scenarios where we need to maintain two separate
stacks (e.g., for different purposes or different parts of an algorithm),
multiple stacks help balance the load. Each stack can grow independently,
ensuring that neither stack exceeds the predefined array size1.

• Directional Growth: When using two stacks within the same array, they
can grow in opposite directions. For instance:

• Stack A grows from left to right.

• Stack B grows from right to lef
 Multiple queues in data structures
• When we implement a queue using an array, the size of the array must
be known in advance.
• If the queue is allocated less space, then frequent overflow conditions
will be encountered. To deal with this problem, the code will have to be
modified to reallocate more space for the array.
• In case we allocate a large amount of space for the queue, it will result
in sheer wastage of the memory. Thus, there lies a tradeoff between the
frequency of overflows and the space allocated.
• So a better solution to deal with this problem is to have multiple queues
or to have more than one queue in the same array of sufficient size
What is a Dequeues (or double-
ended queue)
• The deque stands for Double Ended Queue. Deque is a
linear data structure where the insertion and deletion
operations are performed from both ends.
 Types of Dequeues

• Input restricted queue

• Output restricted queue

 Input restricted Queue
• In input restricted queue, insertion operation can be performed at only
one end, while deletion can be performed from both ends.
 Output restricted Queue
• In output restricted queue, deletion operation can be performed at only
one end, while insertion can be performed from both ends.
 Operations on Dequeue

• Insertion at front

• Insertion at rear

• Deletion at front

• Deletion at rear
Insertion at the front end
• in this operation, the element is inserted from the front end of the
queue. Before implementing the operation, we first have to check
whether the queue is full or not. If the queue is not full, then the
element can be inserted from the front end by using the below
conditions -
• If the queue is empty, both rear and front are initialized with 0. Now,
both will point to the first element.
• Otherwise, check the position of the front if the front is less than 1
(front < 1), then reinitialize it by front = n - 1, i.e., the last index of
the array.
 Insertion at the rear end
• In this operation, the element is inserted from the rear end of the
queue. Before implementing the operation, we first have to check
again whether the queue is full or not. If the queue is not full, then the
element can be inserted from the rear end by using the below
conditions –
• If the queue is empty, both rear and front are initialized with 0. Now,
both will point to the first element.
• Otherwise, increment the rear by 1. If the rear is at last index (or size -
1), then instead of increasing it by 1, we have to make it equal to 0.
 Deletion at the front end
• in this operation, the element is deleted from the front end of the
queue. Before implementing the operation, we first have to check
whether the queue is empty or not.
• If the queue is empty, i.e., front = -1, it is the underflow condition, and
we cannot perform the deletion. If the queue is not full, then the
element can be inserted from the front end by using the below
conditions –
• If the deque has only one element, set rear = -1 and front = -1.
• Else if front is at end (that means front = size - 1), set front = 0.
• Else increment the front by 1, (i.e., front = front + 1).
 Deletion at the rear end
• In this operation, the element is deleted from the rear end of the queue.
Before implementing the operation, we first have to check whether the
queue is empty or not.
• If the queue is empty, i.e., front = -1, it is the underflow condition, and
we cannot perform the deletion.
• If the deque has only one element, set rear = -1 and front = -1.
• If rear = 0 (rear is at front), then set rear = n - 1.
• Else, decrement the rear by 1 (or, rear = rear -1).
 Priority Queue
• Priority is a special type of data structure in which items can be
inserted or deleted based on the priority. The priority of the elements
in a priority queue determines the order in which elements are served
(i.e., the order in which they are removed).
• Properties of Priority Queue
• Every item has a priority associated with it.
• An element with high priority is dequeued before an element with low
priority.
• If two elements have the same priority, they are served according to
their order in the queue.
Types of Priority Queue

• Ascending order priority queue:

• Descending order priority queue

Ascending order priority queue:
• In ascending order priority queue, a lower priority number is given as
a higher priority in a priority. For example, we take the numbers from
1 to 5 arranged in an ascending order like 1,2,3,4,5; therefore, the
smallest number, i.e., 1 is given as the highest priority in a priority
queue.
Descending order priority queue
• In descending order priority queue, a higher priority
number is given as a higher priority in a priority. For
example, we take the numbers from 1 to 5 arranged in
descending order like 5, 4, 3, 2, 1; therefore, the largest
number, i.e., 5 is given as the highest priority in a
priority queue.
Representation of priority queue
In the case of priority queue, lower priority number is considered the higher priority, i.e., lower
priority number = higher priority.

Step 1: In the list, lower priority number is 1, whose data value is 300, so it will be inserted in the
list as shown in the below diagram:

Step 2: After inserting 300, priority number 2 is having a higher priority, and data values
associated with this priority are 200 and 100. So, this data will be inserted based on the FIFO
principle; therefore 200 will be added first and then 100.

Step 3: After inserting the elements of priority 2, the next higher priority number is 4 and data
elements associated with 4 priority numbers are 400, 500, 700. In this case, elements would be
inserted based on the FIFO principle; therefore, 400 will be added first, then 500, and then 700.

Step 4: After inserting the elements of priority 4, the next higher priority number is 5, and the
value associated with priority 5 is 600, so it will be inserted at the end of the queue.
 Real-time application of Queue:

• ATM Booth Line

• Ticket Counter Line

• Key press sequence on the keyboard

• CPU task scheduling

• Waiting time of each customer at call centers.

 Advantages of Queue:

• A large amount of data can be managed efficiently with ease.

• Operations such as insertion and deletion can be performed with ease as it

follows the first in first out rule.

• Queues are useful when a particular service is used by multiple consumers.

• Queues are fast in speed for data inter-process communication.

• Queues can be used in the implementation of other data structures.

 Disadvantages of Queue:

• The operations such as insertion and deletion of elements from the middle are
time consuming.

• Limited Space.

• In a classical queue, a new element can only be inserted when the existing
elements are deleted from the queue.

• Searching an element takes O(N) time.

• Maximum size of a queue must be defined prior.

Real-time Applications of Circular Queue:

• Months in a year: Jan – Feb – March – and so on upto Dec- Jan – . . .

• Eating: Breakfast – lunch – snacks – dinner – breakfast – . . .

• Traffic Light is also a real-time application of circular queue.

Advantages of Circular Queue:

• It provides a quick way to store FIFO data with a maximum size.

• Efficient utilization of the memory.

• Doesn’t use dynamic memory.

• Simple implementation.

• All operations occur in O(1) constant time.

 Disadvantages of Circular Queue:

• In a circular queue, the number of elements you can store is only as

much as the queue length, you have to know the maximum size

beforehand.
 Applications of Deque:

• It is used in job scheduling algorithms.

• It supports both stack and queue operations.

 Real-time Application of Deque:
• in a web browser’s history, recently visited URLs are added
to the front of the deque and the URL at the back of the
deque is removed after some specified number of operations
of insertions at the front.
• Storing a software application’s list of undo operations
 Advantages of Deque:

• You are able to add and remove items from the both front and back of
the queue.

• Deques are faster in adding and removing the elements to the end or
beginning.

• The clockwise and anti-clockwise rotation operations are faster in a

deque.
 Disadvantages of Deque:

• Deque has no fixed limitations for the number of elements they may
contain. This interface supports capacity-restricted deques as well as
the deques with no fixed size limit.

• They are less memory efficient than a normal queue.