UNIT-II

Stack ADT-Operations:
What is Stack?
A stack is a linear data structure in which the insertion of a new
element and removal of an existing element takes place at the same end
represented as the top of the stack.

To implement the stack, it is required to maintain the pointer to the top of the
stack, which is the last element to be inserted because we can access the
elements only on the top of the stack.

LIFO( Last In First Out ):

This strategy states that the element that is inserted last will come out first. You
can take a pile of plates kept on top of each other as a real-life example. The
plate which we put last is on the top and since we remove the plate that is at the
top, we can say that the plate that was put last comes out first.

Basic Operations on Stack

In order to make manipulations in a stack, there are certain operations provided
to us.
 push() to insert an element into the stack
 pop() to remove an element from the stack
 top() Returns the top element of the stack.
 isEmpty() returns true if stack is empty else false.
 size() returns the size of stack.
Applications of the stack:
 Infix to Postfix /Prefix conversion
 Redo-undo features at many places like editors, photoshop.
 Forward and backward features in web browsers
 Used in many algorithms like Tower of Hanoi, tree traversals, stock span
problems, and histogram problems.
 Backtracking is one of the algorithm designing techniques. Some examples
of backtracking are the Knight-Tour problem, N-Queen problem, find your
way through a maze, and game-like chess or checkers in all these problems
we dive into someway if that way is not efficient we come back to the
previous state and go into some another path. To get back from a current
state we need to store the previous state for that purpose we need a stack.
 In Graph Algorithms like Topological Sorting and Strongly Connected
Components
 In Memory management, any modern computer uses a stack as the primary
management for a running purpose. Each program that is running in a
computer system has its own memory allocations
 String reversal is also another application of stack. Here one by one each
character gets inserted into the stack. So the first character of the string is
on the bottom of the stack and the last element of a string is on the top of the
stack. After Performing the pop operations on the stack we get a string in
reverse order.
 Stack also helps in implementing function call in computers. The last called
function is always completed first.
 Stacks are also used to implement the undo/redo operation in text editor.

Arithmetic Expression Evaluation:

The stack organization is very effective in evaluating arithmetic expressions.
Expressions are usually represented in what is known as Infix notation, in
which each operator is written between two operands (i.e., A + B). With this
notation, we must distinguish between ( A + B )*C and A + ( B * C ) by using
either parentheses or some operator-precedence convention. Thus, the order of
operators and operands in an arithmetic expression does not uniquely
determine the order in which the operations are to be performed.
1. Polish notation (prefix notation) –
It refers to the notation in which the operator is placed before its two operands.
Here no parentheses are required, i.e.,
+AB
2. Reverse Polish notation(postfix notation) –
It refers to the analogous notation in which the operator is placed after its two
operands. Again, no parentheses is required in Reverse Polish notation, i.e.,
AB+
Stack-organized computers are better suited for post-fix notation than the
traditional infix notation. Thus, the infix notation must be converted to the postfix
notation. The conversion from infix notation to postfix notation must take into
consideration the operational hierarchy.

There are 3 levels of precedence for 5 binary operators as given below:

Highest: Exponentiation (^)
Next highest: Multiplication (*) and division (/)
Lowest: Addition (+) and Subtraction (-)
For example –
Infix notation: (A-B)*[C/(D+E)+F]
Post-fix notation: AB- CDE +/F +*
Here, we first perform the arithmetic inside the parentheses (A-B) and (D+E).
The division of C/(D+E) must be done prior to the addition with F. After that
multiply the two terms inside the parentheses and bracket.
Now we need to calculate the value of these arithmetic operations by using a
stack.
The procedure for getting the result is:
1. Convert the expression in Reverse Polish notation( post-fix notation).
2. Push the operands into the stack in the order they appear.
3. When any operator encounters then pop two topmost operands for executing
the operation.
4. After execution push the result obtained into the stack.
5. After the complete execution of expression, the final result remains on the
top of the stack.
For example –
Infix notation: (2+4) * (4+6)
Post-fix notation: 2 4 + 4 6 + *
Result: 60
The stack operations for this expression evaluation is shown below:
Conversion of infix to postfix expression:
infix expression: The expression of the form “a operator b” (a + b) i.e., when
an operator is in-between every pair of operands.
Postfix expression: The expression of the form “a b operator” (ab+) i.e., When
every pair of operands is followed by an operator.

Examples:
Input: A + B * C + D
Output: ABC*+D+
Input: ((A + B) – C * (D / E)) + F
Output: AB+CDE/*-F+

How to convert an Infix expression to a Postfix

expression?
To convert infix expression to postfix expression, use the stack data structure.
Scan the infix expression from left to right. Whenever we get an operand, add it
to the postfix expression and if we get an operator or parenthesis add it to the
stack by maintaining their precedence.
Below are the steps to implement the above idea:
1. Scan the infix expression from left to right.
2. If the scanned character is an operand, put it in the postfix expression.
3. Otherwise, do the following
 If the precedence and associativity of the scanned operator are greater
than the precedence and associativity of the operator in the stack [or the
stack is empty or the stack contains a ‘(‘ ], then push it in the stack. [‘^‘
operator is right associative and other operators like ‘+‘,’–‘,’*‘ and ‘/‘ are
left-associative].
 Check especially for a condition when the operator at the top of
the stack and the scanned operator both are ‘^‘. In this
condition, the precedence of the scanned operator is higher due
to its right associativity. So it will be pushed into the operator
stack.
 In all the other cases when the top of the operator stack is the
same as the scanned operator, then pop the operator from the
stack because of left associativity due to which the scanned
operator has less precedence.
 Else, Pop all the operators from the stack which are greater than or equal
to in precedence than that of the scanned operator.
 After doing that Push the scanned operator to the stack. (If you
encounter parenthesis while popping then stop there and push
the scanned operator in the stack.)
4. If the scanned character is a ‘(‘, push it to the stack.
5. If the scanned character is a ‘)’, pop the stack and output it until a ‘(‘ is
encountered, and discard both the parenthesis.
6. Repeat steps 2-5 until the infix expression is scanned.
7. Once the scanning is over, Pop the stack and add the operators in the
postfix expression until it is not empty.
8. Finally, print the postfix expression.
Illustration:
Follow the below illustration for a better understanding
Consider the infix expression exp = “a+b*c+d”
and the infix expression is scanned using the iterator i, which is initialized as i =
0.
1st Step: Here i = 0 and exp[i] = ‘a’ i.e., an operand. So add this in the postfix
expression. Therefore, postfix = “a”.

2nd Step: Here i = 1

and exp[i] = ‘+’ i.e., an operator. Push this into the stack. postfix =
“a” and stack = {+}.
Push ‘+’ in the stack

3rd Step: Now i = 2 and exp[i] = ‘b’ i.e., an operand. So add this in the postfix
expression. postfix = “ab” and stack = {+}.

Add ‘b’ in the postfix

4th Step: Now i = 3 and exp[i] = ‘*’ i.e., an operator. Push this into the
stack. postfix = “ab” and stack = {+, *}.
Push ‘*’ in the stack

5th Step: Now i = 4 and exp[i] = ‘c’ i.e., an operand. Add this in the postfix
expression. postfix = “abc” and stack = {+, *}.

Add ‘c’ in the postfix

6th Step: Now i = 5 and exp[i] = ‘+’ i.e., an operator. The topmost element of
the stack has higher precedence. So pop until the stack becomes empty or the
top element has less precedence. ‘*’ is popped and added in postfix. So postfix
= “abc*” and stack = {+}.
Pop ‘*’ and add in postfix

Now top element is ‘+‘ that also doesn’t have less precedence. Pop it. postfix =
“abc*+”.

Pop ‘+’ and add it in postfix

Now stack is empty. So push ‘+’ in the stack. stack = {+}.

Push ‘+’ in the stack

7th Step: Now i = 6 and exp[i] = ‘d’ i.e., an operand. Add this in the postfix
expression. postfix = “abc*+d”.

Add ‘d’ in the postfix

Final Step: Now no element is left. So empty the stack and add it in the postfix
expression. postfix = “abc*+d+”.
Pop ‘+’ and add it in postfix

Queue ADT:
What is Queue Data Structure?
A Queue is defined as a linear data structure that is open at both ends and the
operations are performed in First In First Out (FIFO) order.

We define a queue to be a list in which all additions to the list are made at one
end, and all deletions from the list are made at the other end. The element
which is first pushed into the order, the operation is first performed on that.
FIFO Principle of Queue:
 A Queue is like a line waiting to purchase tickets, where the first person in
line is the first person served. (i.e. First come first serve).
 Position of the entry in a queue ready to be served, that is, the first entry that
will be removed from the queue, is called the front of the
queue(sometimes, head of the queue), similarly, the position of the last entry
in the queue, that is, the one most recently added, is called the rear (or
the tail) of the queue. See the below figure.
Characteristics of Queue:
 Queue can handle multiple data.
 We can access both ends.
 They are fast and flexible.

Types of Queues:
There are five different types of queues that are used in different
scenarios. They are:
1. Input Restricted Queue (this is a Simple Queue)
2. Output Restricted Queue (this is also a Simple Queue)
3. Circular Queue
4. Double Ended Queue (Deque)
5. Priority Queue
 Ascending Priority Queue
 Descending Priority Queue
1. Circular Queue: Circular Queue is a linear data structure in which the
operations are performed based on FIFO (First In First Out) principle and the
last position is connected back to the first position to make a circle. It is also
called ‘Ring Buffer’. This queue is primarily used in the following cases:
1. Memory Management: The unused memory locations in the case of
ordinary queues can be utilized in circular queues.
2. Traffic system: In a computer-controlled traffic system, circular queues are
used to switch on the traffic lights one by one repeatedly as per the time set.
3. CPU Scheduling: Operating systems often maintain a queue of processes
that are ready to execute or that are waiting for a particular event to occur.
The time complexity for the circular Queue is O(1).
2. Input restricted Queue: In this type of Queue, the input can be taken from
one side only(rear) and deletion of elements can be done from both sides(front
and rear). This kind of Queue does not follow FIFO(first in first out). This queue
is used in cases where the consumption of the data needs to be in FIFO order
but if there is a need to remove the recently inserted data for some reason and
one such case can be irrelevant data, performance issue, etc.

Input Restricted Queue

Advantages of Input restricted Queue:

 Prevents overflow and overloading of the queue by limiting the number of
items added
 Helps maintain stability and predictable performance of the system
Disadvantages of Input restricted Queue:
 May lead to resource wastage if the restriction is set too low and items are
frequently discarded
 May lead to waiting or blocking if the restriction is set too high and the queue
is full, preventing new items from being added.
3. Output restricted Queue: In this type of Queue, the input can be taken from
both sides(rear and front) and the deletion of the element can be done from
only one side(front). This queue is used in the case where the inputs have
some priority order to be executed and the input can be placed even in the first
place so that it is executed first.

Output Restricted Queue

4. Double ended Queue: Double Ended Queue is also a Queue data structure
in which the insertion and deletion operations are performed at both the ends
(front and rear). That means, we can insert at both front and rear positions and
can delete from both front and rear positions. Since Deque supports both stack
and queue operations, it can be used as both. The Deque data structure
supports clockwise and anticlockwise rotations in O(1) time which can be useful
in certain applications. Also, the problems where elements need to be removed
and or added both ends can be efficiently solved using Deque.

Double Ended Queue

5. Priority Queue: A priority queue is a special type of queue in which each

element is associated with a priority and is served according to its priority.
There are two types of Priority Queues. They are:
1. Ascending Priority Queue: Element can be inserted arbitrarily but only
smallest element can be removed. For example, suppose there is an array
having elements 4, 2, 8 in the same order. So, while inserting the elements,
the insertion will be in the same sequence but while deleting, the order will
be 2, 4, 8.
2. Descending priority Queue: Element can be inserted arbitrarily but only the
largest element can be removed first from the given Queue. For example,
suppose there is an array having elements 4, 2, 8 in the same order. So,
while inserting the elements, the insertion will be in the same sequence but
while deleting, the order will be 8, 4, 2.
The time complexity of the Priority Queue is O(logn).
Applications of a Queue:

The queue is used when things don’t have to be

processed immediately, but have to be processed in First In First Out order
like Breadth First Search. This property of Queue makes it also useful in the
following kind of scenarios.
1. When a resource is shared among multiple consumers. Examples
include CPU scheduling, Disk Scheduling.
2. When data is transferred asynchronously (data not necessarily received at
the same rate as sent) between two processes. Examples include IO
Buffers, pipes, file IO, etc.
3. Linear Queue: A linear queue is a type of queue where data elements are
added to the end of the queue and removed from the front of the queue.
Linear queues are used in applications where data elements need to be
processed in the order in which they are received. Examples include printer
queues and message queues.
4. Circular Queue: A circular queue is similar to a linear queue, but the end of
the queue is connected to the front of the queue. This allows for efficient use
of space in memory and can improve performance. Circular queues are used
in applications where the data elements need to be processed in a circular
fashion. Examples include CPU scheduling and memory management.
5. Priority Queue: A priority queue is a type of queue where each element is
assigned a priority level. Elements with higher priority levels are processed
before elements with lower priority levels. Priority queues are used in
applications where certain tasks or data elements need to be processed with
higher priority. Examples include operating system task scheduling and
network packet scheduling.
6. Double-ended Queue: A double-ended queue, also known as a deque, is a
type of queue where elements can be added or removed from either end of
the queue. This allows for more flexibility in data processing and can be
used in applications where elements need to be processed in multiple
directions. Examples include job scheduling and searching algorithms.
7. Concurrent Queue: A concurrent queue is a type of queue that is designed
to handle multiple threads accessing the queue simultaneously. Concurrent
queues are used in multi-threaded applications where data needs to be
shared between threads in a thread-safe manner. Examples include
database transactions and web server requests.
Queue Operations:
The queue is an abstract data type which is defined by following structure and
operations.
Queue is structured as an ordered collection of items which are added at one
end called rear end, and other end called front end.
The queue operations are as follows:
1. create
2. enqueue
3. dequeue
4. isEmpty
5. isFull
6. size
1) create : Creates and initializes new queue that is empty, it does not require
any parameter and returns an empty queue.
2) enqueue: Add a new element to the rear of queue . It requires the element
to be added and returns nothing.
3) dequeue: removes the elements from the front of queue. It does not require
any parameters and returns the deleted item.
4) isEmpty: Check the whether the queue is empty or not. It does not require
any parameter and returns a Boolean value.
Given N integers, the task is to insert those elements in the queue. Also,
given M integers, the task is to find the frequency of each number in the Queue.
Examples:
Input:
N=8
1 2 3 4 5 2 3 1 (N integers)
M=5
1 3 2 9 10 (M integers)
Output:
2 2 2 -1 -1
Explanation:
After inserting 1, 2, 3, 4, 5, 2, 3, 1 into the queue, frequency of 1 is 2, 3 is 2, 2
is 2, 9 is -1 and 10 is -1 (since, 9 and 10 is not there in the queue).
Input:
N=5
5 2 2 4 5 (N integers)
M=5
2 3 4 5 1 (M integers)
Output:
2 -1 1 2 -1
Approach: The given problem can be solved by using a simple queue. The
idea is to insert N integers one by one into the queue and then check the
frequency of M integers. Separate functions will be created to perform both
operations. Follow the steps below to solve the problem.
 Create a queue and push all given integers into the queue.
 After pushing all the elements into the queue create another function for
counting the frequency of given M elements one by one.
 Take a variable cntFrequency to keep track of frequency of current
element.
 Pop all the elements from queue till its size and each time check if current
element in queue is equal to element for which we are checking for
frequency.
– if both are equal, increment cntFrequency by 1
– else, do nothing.
 Push the current element back to the queue so that for next case queue will
not get disturbed.
 Print the frequency of each element found.