Stack

Introduction to 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) in Stack:

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, certain operations are 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 the stack is empty else false.
 size() returns the size of the stack.
Implementation of Stack using Singly Linked List:

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 operations in the following article:

In the stack Implementation, a stack contains a top pointer. Which is the “head” of the stack
where pushing and popping items happens at the head of the list. The first node has a null in
the link field and second node-link has the first node address in the link field and so on and the
last node address is in the “top” pointer.

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.

Push Operation:

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

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

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

 Otherwise return the value of top node of the linked list

Display Operation:

 Take a temp node and initialize it with top pointer

 Now start traversing temp till it encounters NULL
 Simultaneously print the value of the temp node
Application of Stack Data Structure:
 Function calls and recursion: When a function is called, the current state of the program
is pushed onto the stack. When the function returns, the state is popped from the stack to
resume the previous function’s execution.
 Undo/Redo operations: The undo-redo feature in various applications uses stacks to keep
track of the previous actions. Each time an action is performed, it is pushed onto the stack.
To undo the action, the top element of the stack is popped, and the reverse operation is
performed.
 Expression evaluation: Stack data structure is used to evaluate expressions in infix,
postfix, and prefix notations. Operators and operands are pushed onto the stack, and
operations are performed based on the stack’s top elements.
 Browser history: Web browsers use stacks to keep track of the web pages you visit. Each
time you visit a new page, the URL is pushed onto the stack, and when you hit the back
button, the previous URL is popped from the stack.
 Balanced Parentheses: Stack data structure is used to check if parentheses are balanced or
not. An opening parenthesis is pushed onto the stack, and a closing parenthesis is popped
from the stack. If the stack is empty at the end of the expression, the parentheses are
balanced.
 Backtracking Algorithms: The backtracking algorithm uses stacks to keep track of the
states of the problem-solving process. The current state is pushed onto the stack, and when
the algorithm backtracks, the previous state is popped from the stack.

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

Infix to Postfix Operation in Stack:

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

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

Postfix Evaluation using Stack:

To evaluate a postfix expression we can use a stack.

Iterate the expression from left to right and keep on storing the operands into a stack. Once an
operator is received, pop the two topmost elements and evaluate them and push the result in the
stack again.

Towers of Hanoi using Stack:

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.

Follow the steps below to solve the problem:

 Create a function towerOfHanoi where pass the N (current number of

disk), from_rod, to_rod, aux_rod.
 Make a function call for N – 1 th disk.
 Then print the current the disk along with from_rod and to_rod
 Again make a function call for N – 1 th disk.
 A 100, 200, 400, 300

B 200, 300, 400, 100

C 400, 200, 100, 300

D 300, 200, 400, 100

Answer: B, C, D

Explanation: It is given that the size of S1 stack is 4, size of S2 stack is 2. we can push and
pop at any time but for printing the element is only from the stack S1.

Option B):200,300,400,100
Here first Pop two items 400,300 form S1 and push it into S2
S1=200,100;S2=300,400 from top to bottom. Print 200 as output.
Pop 300 from S2 and push it into S1, Print 300. Now S1=100, S2=400
Pop 400 form S2 and push it back into S1. Print 400,100.
In this way, we can generate 200,300,400,100 as output.
Option C) 400,200,100,300
First print 400 which top most elements in S1.
Pop 300 from S1 and push it into S2.
Now print 200,100 from S1
Pop 300 from S2 and push it into S1. Print 300
In this way, we can generate 400,200,100,300
Option D) 300,200,400,100
Pop 400 from S1 and push into S2. Print 300,200
Pop 400 from S2 and push it into S1.
So S1=400,100. Now print 400,100
In this way, we can generate 300,200,400,100
Option A) cannot be generated to print 100 we have to first pop 400,300,200 which is not
possible because the size of S2 is two.

Hence, options B, C, D are correct.

Question 2:

Consider the following sequence of operations on an empty stack.

push(54); push(52); pop(); push(55); push(62); s=pop();
Consider the following sequence of operations on an empty queue.
enqueue(21); enqueue(24); dequeue(); enqueue(28); enqueue(32); q=dequeue();

The value of s+q is ___________.

Answer: 86

Explanation:

Stack:

 Push 54, push 52, pop (remove top element of stack)

 Now stack 54 (remove 52), push 55, push 62, pop
 Now top element is 62 (remove 62 as S)
 S=62

Queue

 Enqueue 21, Enqueue 24 dequeue (remove first element of queue)

 Now queue 24 (remove 21), Enqueue 28, Enqueue 32, dequeue
 Starting element is 24 (remove 24 as Q)
 Q=24

S+Q=62+24=86
Question 3:

A stack is implemented with an array of ′A[0…N−1]′′A[0…N−1]′ and a

variable ’pos’. ’pos’. The push and pop operations are defined by the following code.

push (x)
A[pos] <- x
pos <- pos -1
end push
pop()
pos <- pos+1
return A[pos]
end pop

Which of the following will initialize an empty stack with capacity N for the above
implementation?
1. pos ←−1
2. pos ←0
3. pos ←1
4. pos ←N-1

Answer: D

Explanation:

Stack is growing downwards, and on pushing an item, the top [pos] is decrementing by one,
meaning the on the topmost position [pos] will be 0, or (N - 1 - (N - 1)], so the initial value of
[pos] will be N – 1

Question 4:

What is the equivalent infix expression of the following postfix expression?

M, N, O, +, *, P, /, Q, R, S, T, /, +, *, –
1. N*(M+Q)/Q-P*(S+R/T)
2. (((M*(N+O))/P)-(Q*(R+(S/T))))
3. O * (M + N)/P – Q * (R + S/T)
4. M * (N + O)/Q – P * (R/S + T)
Answer: Option 2: (((M * (N + O)) / P) – (Q * (R + (S / T))))
Explanation:
Let's apply this algorithm to the given postfix expression - M, N, O, +, *, P, /, Q, R, S, T, /, +,
*, –
Step 1 - Push M, N, O onto the stack Stack - O, N, M
Step 2 - Pop O, N, M and concatenate them with + and * Stack - (M*(N+O))
Step 3 - Push P onto the stack Stack - P, (M*(N+O))
Step 4 - Pop P and concatenate it with / Stack - ((M*(N+O))/P)
Step 5 - Push Q, R, S, T onto the stack Stack - T, S, R, Q, ((M*(N+O))/P)
Step 6 - Pop T, S, R, Q and concatenate them with / and + and * Stack - ((Q*(R+(S/T))),
((M*(N+O))/P)
Step 7 - Pop the final expression from the stack after "-" Infix expression - (((M*(N+O))/P) -
((Q*(R+(S/T))))

Question 5:

What is the postfix representation of the following infix expression?

(A + B) * C – D * E / F
1. A B + C * D E * F - /
2. A B * C + D E * F / -
3. A B + C – D E * F / *
4. A B + C * D E * F / -
Answer: Option 4: A B + C * D E * F / -
Explanation:
() has highest precedence
* and / has same precedence while + and – has same precedence
(* and /) and higher precedence than (+, -)
Associativity is left to right:
(A + B) * C – D * E / F
AB+*C–D*E/F
AB+C*–D*E/F
AB+C*–DE*/F
AB+C*–DE*F/
AB+C*DE*F/–
Question 6:

The result evaluating the postfix expression 10 5 + 60 6 / * 8 − is

1. 284
2. 213
3. 142
4. 71
Answer: Option 3: 142

Question 7:

The five items P, Q, R, S and T are pushed in a stack, one after the other starting from P. The
stack is popped four times and each element is inserted in a queue. Then two elements are
deleted from the queue and pushed back on the stack. now one item is popped from the stack.
The popped item is:
1. P
2. R
3. Q
4. S
Answer: Option 4: S
Question 8:

Consider the following postfix expression with single digit operands:

623*/42*+68*-
The top two elements of the stack after second * is evaluated, are:
1. 6, 3
2. 8, 1
3. 8, 2
4. 6, 2
Answer: Option 2: 8, 1

Question 9:

What is the outcome of the prefix expression +, -, *, 3, 2, /, 8, 4, 1?

1. 12
2. 5
3. 11
4. 4
Answer: Option 2: 5

Question 10:

A stack is implemented with an array of ‘A [0..N – 1]’ and a variable ‘pos’. The push and pop
operations are defined by the following code.
push(x)
A[pos] ← x
pos ← pos – 1
end push
pop( )
pos ← pos + 1
return A[pos]
end pop
Which of the following will initialize an empty stack with capacity N for the above
implementation?
1. pos ← -1
2. pos ← 0
3. pos ← 1
4. pos ← N - 1

Answer: Option 4: pos ← N - 1

Question 11:

A stack can be implemented using queue, but then we need to use atleast:
1. 3 queues
2. 2 queues
3. only one queue is sufficient
4. none of the options

Answer: Option 2: 2 queues

Question 12:

Which of the following applications may use a stack?

(a) Parenthesis balancing program
(b) Process scheduling operating system
(c) Conversion of infix arithmetic expression to postfix form
 (a) and (b)
 (b) and (c)
 (a) and (c)
 (a), (b) and (c)

Answer: Option 3: (a) and (c)

Question 13:

What is the value of the postfix expression 6 3 2 4 + – *?

a) 1
b) 40
c) 74
d) -18
Answer: d
Explanation: Postfix Expression is (6*(3-(2+4))) which results -18 as output. 10.

Question 14:

Here is an infix expression: 4 + 3*(6*3-12). Suppose that we are using the usual stack algorithm
to convert the expression from infix to postfix notation. The maximum number of symbols that
will appear on the stack AT ONE TIME during the conversion of this expression?
a) 1
b) 2
c) 3
d) 4
Answer: d
Explanation: When we perform the conversion from infix to postfix expression +, *, (, *
symbols are placed inside the stack. A maximum of 4 symbols are identified during the entire
conversion.
Question 15:

Convert the pre-fix expression to in-fix −∗+ABC∗−DE+FG−∗+ABC∗−DE+FG

a) (A−B)∗C+(D∗E)−(F+G)
b) (A+B)∗C−(D−E)∗(F−G)
c) (A+B−C)∗(D−E)∗(F+G)
d) (((A+B)∗C)−((D−E)∗(F+G)))

Answer: d
Explanation:

Questions on Linked List

Q1. What is the worst-case time complexity of inserting n elements into an empty linked list, if
the linked list needs to be maintained in sorted order?
(A) Θ(n)
(B) Θ(n log n)
(C) Θ(n2)
(D) Θ(1)
Answer: (C)
Explanation: If we want to insert n elements into an empty linked list that needs to be
maintained in sorted order, the worst-case time complexity would be O(n^2). This is because
we would need to traverse the list for each element we want to insert, to find the correct
position for the element in the sorted list.
Q2. What does the following function do for a given Linked List with first node as head?
void fun1(struct node* head)
{
if(head == NULL)
return;

fun1(head->next);
printf("%d ", head->data);
}
(A) Prints all nodes of linked list
(B) Prints all nodes of linked list in reverse order
(C) Prints alternate nodes of Linked List
(D) Prints alternate nodes in reverse order

Answer: (B)
Explanation: It first checks if the head is NULL, and if it is, it returns without doing anything.
Otherwise, it calls the fun1 function recursively with the next node in the linked list (head-
>next). This continues until the last node is reached, which is the node whose next pointer
is NULL. At this point, the function starts returning, and as it returns it prints the value of each
node in the linked list starting from the last node, working its way backwards to the first node.
This is achieved through the printf statement which prints the value of head->data.

Q3. Which of the following points is/are true about Linked List data structure when it is
compared with array?
(A) Arrays have better cache locality that can make them better in terms of performance.
(B) It is easy to insert and delete elements in Linked List
(C) Random access is not allowed in a typical implementation of Linked Lists
(D) The size of array has to be pre-decided, linked lists can change their size any time.
(E) All of the above
Answer: (E)
Explanation: The following points are true when comparing Linked List data structure with an
array:
 Insertion and deletion: Linked lists allow for efficient insertion and deletion operations at
any point in the list, as they involve simply adjusting pointers, while in an array, these
operations can be expensive as all the elements after the insertion or deletion point need to
be shifted.
 Memory allocation: Linked lists use dynamic memory allocation, so they can grow or
shrink as needed, while arrays have a fixed size and need to be allocated a contiguous
block of memory upfront.
 Access time: Arrays provide constant-time access to any element in the array (assuming the
index is known), while accessing an element in a linked list takes linear time proportional
to the number of elements in the list, as the list needs to be traversed from the beginning to
find the desired element.
 Random access: Arrays support random access, which means that we can directly access
any element in the array with its index, while linked lists do not support random access and
we need to traverse the list to find a specific element.
Q4. Which of the following sorting algorithms can be used to sort a random linked list with
minimum time complexity?
 (A) Insertion Sort
 (B) Quick Sort
 (C) Heap Sort
 (D) Merge Sort
Answer: (D)

Explanation: Both Merge sort and Insertion sort can be used for linked lists. The slow
random-access performance of a linked list makes other algorithms (such as quicksort) perform
poorly, and others (such as heapsort) completely impossible. Since worst case time complexity
of Merge Sort is O(nLogn) and Insertion sort is O(n^2), merge sort is preferred. See following
for implementation of merge sort using Linked List.

Q5. The following function takes a single-linked list of integers as a parameter and rearranges
the elements of the list. The function is called with the list containing the integers 1, 2, 3, 4, 5,
6, 7 in the given order. What will be the contents of the list after the function completes
execution?
class Node {
public:
int value;
Node* next;

Node(int value) {
this->value = value;
this->next = nullptr;
}
};

void rearrange(Node* list) {

Node* p;
Node* q;
int temp;
if (list == nullptr || list->next == nullptr) {
return;
}
p = list;
q = list->next;
while (q != nullptr) {
temp = p->value;
p->value = q->value;
q->value = temp;
p = q->next;
q = p != nullptr ? p->next : nullptr;
}
}
(A) 1,2,3,4,5,6,7
(B) 2,1,4,3,6,5,7
(C) 1,3,2,5,4,7,6
(D) 2,3,4,5,6,7,1
Answer: (B)
Explanation: The function rearrange() exchanges data of every node with its next node. It
starts exchanging data from the first node itself.
For eg. 2,1,4,3,6,5,7