Topic: Stack Implementation using Linked List

Question 1 (Scenario)

A web browser's "Back" button functionality is a classic real-world example of a stack. When a
user navigates from Page A to Page B, and then to Page C, how does a stack (implemented
with a linked list) manage this history to allow the user to go back from C to B, and then from
B to A?

Solution 1

A stack operates on a Last-In, First-Out (LIFO) principle, which is exactly how the "Back"
button should work. The last page you visited is the first one you go back from.

Step-by-Step Solution:
1.​ User visits Page A:
○​ The URL of Page A is pushed onto the stack. The linked list's top pointer points to the
Page A node.
○​ Stack: (Top) -> [Page A] -> NULL.
2.​ User navigates to Page B:
○​ The URL of Page B is pushed onto the stack. The new node for Page B becomes the
new top, and its next pointer links to the Page A node.
○​ Stack: (Top) -> [Page B] -> [Page A] -> NULL.
3.​ User navigates to Page C:
○​ The URL of Page C is pushed onto the stack.
○​ Stack: (Top) -> [Page C] -> [Page B] -> [Page A] -> NULL.
4.​ User clicks the "Back" button:
○​ The pop operation is performed. The item at the top of the stack (Page C) is removed
and displayed to the user.
○​ The top pointer moves to the next item in the list (Page B).
○​ Stack: (Top) -> [Page B] -> [Page A] -> NULL. The user is now on Page B.
5.​ User clicks "Back" again:
○​ The pop operation is performed again. Page B is removed.
○​ The top pointer moves to Page A.
○​ Stack: (Top) -> [Page A] -> NULL. The user is now on Page A.
Question 2 (Scenario)

In many programming languages, function calls are managed using a call stack. If a main()
function calls functionA(), and functionA() in turn calls functionB(), explain how a stack is used
to ensure that when functionB() finishes, control returns to functionA(), and when functionA()
finishes, control returns to main().

Solution 2
The call stack stores "stack frames," where each frame contains information about a function
call (like its local variables and the return address). The LIFO nature of the stack ensures
functions are exited in the reverse order they were called.

Step-by-Step Solution:
1.​ Program Starts: The main() function begins execution. A stack frame for main() is
pushed onto the call stack.
○​ Call Stack: (Top) -> [Frame: main()].
2.​ main() calls functionA():
○​ Execution of main() is paused at the point of the call. The return address (the next
line in main()) is stored.
○​ A new stack frame for functionA() is pushed onto the stack.
○​ Call Stack: (Top) -> [Frame: functionA()] -> [Frame: main()].
3.​ functionA() calls functionB():
○​ Execution of functionA() is paused.
○​ A stack frame for functionB() is pushed onto the stack.
○​ Call Stack: (Top) -> [Frame: functionB()] -> [Frame: functionA()] -> [Frame: main()].
4.​ functionB() finishes:
○​ The stack frame for functionB() is popped from the stack.
○​ The system uses the return address stored in the now-top frame (functionA()) to
resume its execution.
○​ Call Stack: (Top) -> [Frame: functionA()] -> [Frame: main()].
5.​ functionA() finishes:
○​ The stack frame for functionA() is popped.
○​ Control returns to main(), which resumes execution.
○​ Call Stack: (Top) -> [Frame: main()].
6.​ main() finishes: The main() frame is popped, the stack is empty, and the program
terminates.
Question 3 (Scenario)

You need to write a program that reverses a string. For instance, if the input is "hello", the
output should be "olleh". How can you use a stack implemented with a linked list to solve this
problem?

Solution 3

A stack is perfect for reversing sequences. By pushing each character onto the stack and then
popping them all off, the characters will naturally come out in the reverse order.

Step-by-Step Solution:
1.​ Initialization: Create an empty stack.
2.​ Push Phase (Traversal and Insertion):
○​ Iterate through the input string "hello" from left to right.
 ○​ Push 'h' onto the stack. Stack: (Top) -> ['h'].
○​ Push 'e' onto the stack. Stack: (Top) -> ['e'] -> ['h'].
○​ Push 'l' onto the stack. Stack: (Top) -> ['l'] -> ['e'] -> ['h'].
○​ Push the second 'l'. Stack: (Top) -> ['l'] -> ['l'] -> ['e'] -> ['h'].
○​ Push 'o' onto the stack. Stack: (Top) -> ['o'] -> ['l'] -> ['l'] -> ['e'] -> ['h'].
3.​ Pop Phase (Traversal and Deletion):
○​ Create an empty string for the result.
○​ Enter a loop that continues until the stack is empty.
○​ Pop a character and append it to the result string.
○​ Pop 'o'. Result: "o".
○​ Pop 'l'. Result: "ol".
○​ Pop 'l'. Result: "oll".
○​ Pop 'e'. Result: "olle".
○​ Pop 'h'. Result: "olleh".
4.​ Final Result: The stack is now empty, and the result string contains "olleh".
Question 4 (Scenario)

A text editor's "Undo" feature needs to support multiple levels of undo. If a user types "A",
then makes it bold, then types "B", the undo stack should record these actions. How would a
stack manage these distinct actions to allow the user to undo them in the reverse order they
were performed?

Solution 4

Each action the user performs (typing, formatting, etc.) is encapsulated as an object or
structure and pushed onto an "undo" stack. The "Undo" command simply pops the most
recent action and reverses it.

Step-by-Step Solution:
1.​ User types "A":
○​ An action object, Action(type="Insert", text="A"), is created and pushed onto the
stack.
○​ Stack: (Top) -> [Action: Insert "A"].
2.​ User makes the text bold:
○​ An action object, Action(type="Format", style="Bold"), is pushed onto the stack.
○​ Stack: (Top) -> [Action: Format "Bold"] -> [Action: Insert "A"].
3.​ User types "B":
○​ An action object, Action(type="Insert", text="B"), is pushed onto the stack.
○​ Stack: (Top) -> [Action: Insert "B"] -> [Action: Format "Bold"] -> [Action: Insert "A"].
4.​ User clicks "Undo":
○​ The pop operation is called. The [Action: Insert "B"] object is removed.
○​ The editor performs the reverse of this action: it deletes the character "B".
○​ Stack state: (Top) -> [Action: Format "Bold"] -> [Action: Insert "A"].
 5.​ User clicks "Undo" again:
○​ The pop operation is called. The [Action: Format "Bold"] object is removed.
○​ The editor reverses the action: it removes the bold formatting.
○​ Stack state: (Top) -> [Action: Insert "A"].
Question 5 (Scenario)

A compiler needs to check if the parentheses, brackets, and braces in a line of code are
balanced and properly nested, like in ({x * [y + z]}). An invalid example would be ([)]. How can
a stack be used to validate the code?

Solution 5

A stack can be used to track opening delimiters. The logic is to push opening symbols onto
the stack and pop them when their corresponding closing symbol is found.

Step-by-Step Solution:
1.​ Initialization: Create an empty stack. Scan the expression ({x * [y + z]}) from left to right.
2.​ Scanning the Expression:
○​ '(': This is an opening delimiter. Push it onto the stack. Stack: (.
○​ '{': Opening delimiter. Push it. Stack: {, (.
○​ '[': Opening delimiter. Push it. Stack: [, {, (.
○​ ']': This is a closing delimiter.
■​ Look at the top of the stack. It's [. This is the correct matching pair.
■​ Pop the stack. Stack: {, (.
○​ '}': Closing delimiter.
■​ The top of the stack is {. Correct match.
■​ Pop the stack. Stack: (.
○​ ')': Closing delimiter.
■​ The top of the stack is (. Correct match.
■​ Pop the stack. Stack is now empty.
3.​ Final Check:
○​ At the end of the expression, the stack is empty. This means all delimiters were
correctly balanced and nested. The expression is valid.
○​ If the stack were not empty, it would mean there were unclosed opening delimiters. If
a mismatch occurred during a pop (e.g., finding a ) when [ is at the top), the
expression would be invalid.