Stacks

Stacks terminology
Q. What is Stacks and its works?
Stack is a linear data structure that follows a particular order in which
the operations are performed. The order may be LIFO (Last In First Out)
or FILO (First In Last Out). LIFO implies that the element that is
inserted last, comes out first and FILO implies that the element that is
inserted first, comes out last.

There are many real-life examples of a stack. Consider an example of

plates stacked over one another in the canteen. The plate which is at the
top is the first one to be removed, i.e. the plate which has been placed at
the bottommost position remains in the stack for the longest period of
time. So, it can be simply seen to follow LIFO (Last In First Out)/FILO
(First In Last Out) order.
Application of Stack in real life:
• CD/DVD stand.
• Stack of books in a book shop.
• Call center systems.
• Undo and Redo mechanism in text editors.
• The history of a web browser is stored in the form of a stack.
• Call logs, E-mails, and Google photos in any gallery are also
stored in form of a stack.
• YouTube downloads and Notifications are also shown in LIFO
format (the latest appears first).
• Allocation of memory by an operating system while executing a
process.

Advantages of Stack:

• Easy implementation: Stack data structure is easy to implement using

arrays or linked lists, and its operations are simple to understand and
implement.
• Efficient memory utilization: Stack uses a contiguous block of
memory, making it more efficient in memory utilization as compared to
other data structures.
• Fast access time: Stack data structure provides fast access time for
adding and removing elements as the elements are added and removed
from the top of the stack.
• Helps in function calls: Stack data structure is used to store function
calls and their states, which helps in the efficient implementation of
recursive function calls.
• Supports backtracking: Stack data structure supports backtracking
algorithms, which are used in problem-solving to explore all possible
solutions by storing the previous states.
• Used in Compiler Design: Stack data structure is used in compiler
design for parsing and syntax analysis of programming languages.
• Enables undo/redo operations: Stack data structure is used to enable
undo and redo operations in various applications like text editors,
graphic design tools, and software development environments.

Disadvantages of Stack:

• Limited capacity: Stack data structure has a limited capacity as it can

only hold a fixed number of elements. If the stack becomes full, adding
new elements may result in stack overflow, leading to the loss of data.
• No random access: Stack data structure does not allow for random
access to its elements, and it only allows for adding and removing
elements from the top of the stack. To access an element in the middle
of the stack, all the elements above it must be removed.
• Memory management: Stack data structure uses a contiguous block
of memory, which can result in memory fragmentation if elements are
added and removed frequently.
• Not suitable for certain applications: Stack data structure is not
suitable for applications that require accessing elements in the middle
of the stack, like searching or sorting algorithms.
• Stack overflow and underflow: Stack data structure can result in
stack overflow if too many elements are pushed onto the stack, and it
can result in stack underflow if too many elements are popped from the
stack.
• Recursive function calls limitations: While stack data structure
supports recursive function calls, too many recursive function calls can
lead to stack overflow, resulting in the termination of the program.
Q. Explain Representation of Stacks in memory.
A stack may be represented in the memory in various ways. There are two
main ways: using a one-dimensional array and a single linked list. Array
Representation of Stacks: First we have to allocate a memory block of
sufficient size to accommodate the full capacity of the stack.
1. One–dimensional array representation

Array implementation of Stack is static and limited by the array size. The stack
cannot store elements beyond its capacity. But, arrays work faster for push and
pop operations because of the continuous memory. So, use the array-based
implementation for the fixed amount of data. In doing a representation of a
stack using an array, the arrays are used to create the stack. Arrays are used
for all activities related to the stack implementation.
 Implementation of Stack using Array (Memory representation)

Push Operation

A push operation occurs when you add an element to the top of the stack.
The next two steps are involved in the push operation:

1. The top variable on the stack should be increased so it may refer to the
next memory address.
2. At the top of the increment, add a data element.

When you attempt to put an element into the stack after it is complete, the
stack data structure declares an overflow situation.
 Algorithm for push operation

Algorithm for push operation while doing representation of stack using

array:

• Begin
• If top == n
• The stack is completely filled
• top = top + 1
• Stack (top) = item
• end
Pop Operation

The term "pop operation" refers to the removal of a data element from the
stack data structure. The pop operation has the four phases listed below:

• Every time you remove an item from the stack, the top variable’s value is
increased by one.
• The variable at the top of the stack is put in a different variable, and its
value is then reduced by one.
• The deleted element that was saved in another variable as a result is
returned by the pop operation.
• When a data element is attempted to be deleted when the stack is already
empty, the stack data structure reports an underflow problem.
 Algorithm for pop operation

Algorithm for pop operation while doing representation of stack using

array:

• Begin
• if top = 0
• stack is completely empty
• item = stack(top)
• top = top – 1
• end

Here is a representation of a stack using an array with all the operations

i.e. push and pop operations.

Algorithm for Peek Operation

Peek allows the user to see what value is on top of the stack, and pop allows the
user to remove the top value from the stack. When we push a value onto the stack,
the value being pushed becomes the new top.

1. START
2. Return the element at the top of the stack
3. END

This operation is used to check the status of the stack with the help of the top
pointer.
Implementation of Stack using Linklist (Memory representation)
To implement a stack using the singly linked list concept, all the singly linked
list operations should be performed based on Stack operations LIFO (last in first
out) and with the help of that knowledge, we are going to implement a stack
using a singly linked list.
So we need to follow a simple rule in the implementation of a stack which
is last in first out and all the operations can be performed with the help of a
top variable. Let us learn how to perform Pop, Push, Peek, and Display
operation.

The main advantage of using a linked list over arrays is that it is possible to
implement a stack that can shrink or grow as much as needed. Using an array
will put a restriction on the maximum capacity of the array which can lead to
stack overflow. Here each new node will be dynamically allocated. So overflow
is not possible.
Stack Operations:

• push(): Insert a new element into the stack i.e just insert a new element
at the beginning of the linked list.
• pop(): Return the top element of the Stack i.e simply delete the first
element from the linked list.
• peek(): Return the top element.

Push Operation: (Algorithm)

• Initialise a node
• Update the value of that node by data i.e. node->data = data
• Now link this node to the top of the linked list
• And update top pointer to the current node

Pop Operation: (Algorithm)

• First Check whether there is any node present in the linked list or not, if
not then return
• Otherwise make pointer let say temp to the top node and move forward
the top node by 1 step
• Now free this temp node

Peek Operation: (Algorithm)

• Check if there is any node present or not, if not then return.

• Otherwise return the value of top node of the linked list
 Q. Explain Operations of Stacks.
There are various stack operations that are applicable on a stack. Stack operations
are generally used to extract information and data from a stack data structure.
Some of the stack operations are given below.

Basic Operations on Stack

• push() to insert an element into the stack.
• pop() to remove an element from the stack.
• Peek/top() Returns the top element of the stack.
• isEmpty() returns true if stack is empty else false.
• size() returns the size of stack.

Algorithm for push operation

Algorithm for push operation to add the element.

• Begin
• If top == n
• The stack is completely filled
• top = top + 1
• Stack (top) = item
• end

Algorithm for pop operation

• Begin
• if top = 0
• stack is completely empty
• item = stack(top)
• top = top – 1
• end
Algorithm for Peek/TOP() Operation

Peek allows the user to see what value is on top of the stack.
1. START
2. Return the element at the top of the stack
3. END

Algorithm for Empty() 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.

1. START
2. If the top value is -1, the stack is empty.
3. Otherwise, return 1.
4. END

Algorithm for isFull()/Size() operation

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.

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
[Link] Does Polish Notation Mean?

Polish notation is a notation form for expressing arithmetic, logic and

algebraic equations. Its most basic distinguishing feature is that
operators are placed on the left of their operands. If the operator has a
defined fixed number of operands, the syntax does not require brackets
or parenthesis to lessen ambiguity Polish notation is also known as
prefix notation, prefix Polish notation, normal Polish notation, Warsaw
notation.

Polish Notation

Polish logician and philosopher, in order to simplify sentential logic.

The idea is simply to have a parenthesis-free notation that makes each
equation shorter and easier to parse in terms of defining the evaluation
priority of the operators.

Example:

Infix notation with parenthesis: (3 + 2) * (5 – 1)

Polish notation: * + 3 2 – 5 1

When used as the syntax for programming language interpreters, Polish

notation can be readily parsed into an abstract syntax tree and stored in
a stack. In traditional infix notation with brackets, the equation has to
be parsed, the brackets removed, and the operator and operands
repositioned. This is not the case with Polish notation, which is why
LISP and other related languages use this notation to define their
syntax. In computer science, reverse Polish notation is used in stack-
oriented programming languages such as Forth, STOIC, PostScript,
RPL, and Joy.
Translation of infix to postfix and prefix expression

A program to convert an Infix expression to postfix form.

Infix expression: The expression of the form “an 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: ABCD*+-
Input: X/Y*Z
Output: XYZ*/

A program to convert an Infix expression to prefix form.

Infix Expression: The expression of type an ‘operator’ b (a+b, where + is
an operator) i.e., when the operator is between two operands.

Prefix Expression: The expression of type ‘operator’ a b (+ab where + is an

operator) i.e., when the operator is placed before the operands.
Examples:

Input: A * B + C / D
Output: *+/A B C D

Input: X*Y/Z
Output: */XYZ

One advantage of infix expressions is that they are more natural to read and write
for humans, especially in mathematical contexts. However, they can be more
difficult for computers to parse and evaluate, as they require operator precedence
and associativity rules to ensure the correct order of operations. It is very
convenient for evaluating formulas on computers with stacks. Third, infix
operators have precedence.

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.
approach(1) – Simply adding one by one
f(n) = 2 + 4+ 6 +……..+ n
but there is another mathematical approach by using recursion of representing
this,

approach(2)- recursive process

Consider the sequence: 2, 4, 6, 8, 10, …

The above sequence is an arithmetic sequence because each term in the

sequence is increased by 2. Hence, the common difference is 2. Thus, the
recursive formula for the sequence is an = an-1 + 2.

Explanation:

Here, a1 = 2

Thus, a2 = a(2-1)+2 = a1+2 =2+2 = 4

a3 = a(3-1) +2 = a2+2=4+2 = 6

a4 = a(4-1) +2 = a3+2=6+2 = 8, and the process continues.

Advantages of recursion

1. The code may be easier to write.

2. To solve such problems which are naturally recursive such as tower of Hanoi.
3. Reduce unnecessary calling of function.
4. Extremely useful when applying the same solution.
5. Recursion reduce the length of code.
6. It is very useful in solving the data structure problem.
7. Stacks evolutions and infix, prefix, postfix evaluations etc.

Disadvantages of recursion

1. Recursive functions are generally slower than non-recursive function.

2. It may require a lot of memory space to hold intermediate results on the system
stacks.
3. Hard to analyse or understand the code.
4. It is not more efficient in terms of space and time complexity.
5. The computer may run out of memory if the recursive calls are not properly
checked.
Q. Explain quick sort using Tower of Hanoi problem with
Example.

Quick Sort is a sorting algorithm based on the Divide and Conquer

algorithm that picks an element as a pivot and partitions the given
array around the picked pivot by placing the pivot in its correct
position in the sorted array. The key process in quickSort is
a partition(). The target of partitions is to place the pivot (any element
can be chosen to be a pivot) at its correct position in the sorted array
and put all smaller elements to the big one, and all greater elements to
the right of the pivot.
Partition is done recursively on each side of the pivot after the pivot
is placed in its correct position and this finally sorts the array.

Tower of Hanoi is a mathematical puzzle where we have three rods

(A, B, and C) and N disks. Initially, all the disks are stacked in
decreasing value of diameter i.e., the smallest disk is placed on the top
and they are on rod A. The objective of the puzzle is to move the entire
stack to another rod (here considered C), obeying the following 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 may be placed on top of a smaller disk.
Examples:

Total 7 moves
Move disk 1 from rod A to rod C
Move disk 2 from rod A to rod B
Move disk 1 from rod C to rod B
Move disk 3 from rod A to rod C
Move disk 1 from rod B to rod A
Move disk 2 from rod B to rod C
Move disk 1 from rod A to rod C
Time complexity: O (2N), The possibilities for every disk.
Therefore, 2 * 2 * 2 * . . . * 2(N times) is 2N-1 means 23-1
It means total numbers of moves is 7.

Q. Explain major problems of recursion.

1. Memory usage. – Recursion can be memory-intensive, as each

recursive function call creates a new stack frame. This can lead to
memory usage issues, especially in programs that use recursion
extensively or on large datasets.
2. Stack overflow. – Recursion can lead to stack overflow errors,
which occur when the call stack exceeds its allocated size. This
can happen when a recursive function calls itself too many times,
or when the recursion depth is too deep.
3. Difficulty in understanding and debugging. – Recursion can
be difficult to understand and debug, especially in complex
programs. Recursive functions may have multiple exit conditions,
and it can be challenging to determine which one is being
triggered at any given time.
4. Slower execution time. – Recursion can be slower than iterative
solutions, as each function call incurs overhead costs such as
parameter passing and stack manipulation. This can lead to
slower execution times in programs that use recursion
frequently.
5. Limited applicability. – Recursion may not be applicable or
efficient for all programming problems. Some problems may
have more efficient iterative solutions, and others may not lend
themselves well to recursive solutions at all.

************************