CBSE Class 12 Computer Science Arrays Stacks Queues And Linked List Worksheet Set 01

Defination of Datastructure

A data structure is a logical method of representing data in memory using the simple and complex data types provided by the language.

Arrays:

An array is collection of the homogeneous elements that are referred by a common name. It is also called a subscripted variable as the elements of an array are used by the name of an array and an index or subscript.

Array are of two types:

1. One-dimensional arrays 2. Multi-dimensional arrays.

Address Calculation:

The array elements are stored in contiguous memory locations by sequential allocation technique.

Address of arr[i] = B+(I-LB)*S

Sequential Allocation:

The process of storing elements in a fixed order in a data structure where the time required for such access is dependent on the order of the elements.

Using Row Major order the add of a [i] [j] is given by,

Address of a [i] [j]= B+[(i-LB1)*N+(j-LB2)]*S

Using column Major order the add of a [i] [j] is given by,

Address of a [i] [j]= B+[(i-LB1)+(j-LB2)*M]*

One Dimensional Array:

The simplest type of data structure is a one dimensional array in which each elements of a linear array is referenced by one subscript. 

The operations one normally perform on any linear structure include the following:

Definition of Data Structure

A data structure refers to a systematic way of organizing and storing data within a computer's memory. This is achieved by utilizing both basic and composite data types that the programming language offers.

Arrays

An array represents a set of similar (homogeneous) data items grouped under a single identifier. Because we locate individual elements using the array's name along with a specific index or subscript, it is also referred to as a subscripted variable. Arrays are categorized into two main groups:
1. One-dimensional arrays
2. Multi-dimensional arrays

Address Calculation

Array components reside in continuous blocks of memory through a sequential allocation approach. The location of any element \( \text{arr}[i] \) can be computed using the following relation:
\[ \text{Address of arr}[i] = B + (i - LB) \times S \]
Where \( B \) represents the base address, \( LB \) is the lower bound of the index, and \( S \) is the size of each element.

Sequential Allocation

This refers to the arrangement of elements in a predetermined sequence within a storage structure. Here, the duration required to retrieve an element depends directly on its position in the sequence.

For row-major storage, the memory location of \( a[i][j] \) is determined by:
\[ \text{Address of a}[i][j] = B + [(i - LB1) \times N + (j - LB2)] \times S \]

For column-major storage, the memory location of \( a[i][j] \) is determined by:
\[ \text{Address of a}[i][j] = B + [(i - LB1) + (j - LB2) \times M] \times S \]

One Dimensional Array

The most fundamental linear data structure is the single-dimensional array, where a lone subscript or index is used to access each element.

We can perform several basic operations on any linear data structure, including:

• Traversal: Visiting and processing each item in the collection exactly once.
• Searching: Locating the position of a target value or key.
  • Linear Search: A sequential lookup technique that checks every element from the start until the matching item is found.
  • Binary Search: A highly efficient lookup algorithm that operates on a pre-sorted list by repeatedly halving the search interval.
• Insertion: Introducing a new item into the collection.
• Deletion: Removing an existing item from the collection.
• Sorting: Organizing elements into a specific sequence.
  • Insertion Sort: This technique partitions the collection into sorted and unsorted segments. It sequentially takes the first element from the unsorted part and places it into its correct position in the sorted segment, repeating this process until all items are sorted.
  • Selection Sort: A straightforward sorting algorithm that repeatedly identifies the minimum element from the unsorted portion and swaps it with the first unsorted element.
  • Bubble Sort: A simple approach that repeatedly compares adjacent elements from left to right, swapping them if they are in the wrong order. This continues until the largest element "bubbles up" to its correct position at the end after the first complete pass.
• Merging: The process of uniting two or more pre-sorted arrays into a single, fully sorted destination array.

Concatenation of Two Linear Arrays

Concatenation involves appending the elements of one array to another to construct a single combined array. This is achieved by first copying all items from the first array, followed by all items from the second array. The destination array must have a capacity equal to or larger than the combined sizes of the two source arrays.

Two Dimensional Array

A two-dimensional array uses two subscripts (rows and columns) and is ideal for representing grids, tables, or matrices.

• Traversal: Iterating through every element in the grid systematically.
• Matrix Addition and Subtraction: To calculate the sum or difference of two \( N \times M \) matrices, we add or subtract their corresponding elements. The resulting values are stored in a new \( N \times M \) array or displayed directly.

For example, the sum of two arrays \( A \) and \( B \) of size \( 3 \times 2 \) is shown below:
\[ A = \begin{pmatrix} 4 & 6 \\ 7 & 1 \\ 5 & 3 \end{pmatrix}, \quad B = \begin{pmatrix} 5 & 2 \\ 1 & 8 \\ 2 & 4 \end{pmatrix}, \quad \text{Resultant} = \begin{pmatrix} 9 & 8 \\ 8 & 9 \\ 7 & 7 \end{pmatrix} \]

If the difference of two arrays of size \( 3 \times 3 \) is required, we obtain the result as follows:
\[ A = \begin{pmatrix} 40 & 25 & 73 \\ 18 & 55 & 29 \\ 70 & 62 & 47 \end{pmatrix}, \quad B = \begin{pmatrix} 31 & 20 & 41 \\ 10 & 36 & 15 \\ 20 & 32 & 17 \end{pmatrix}, \quad \text{Resultant} = \begin{pmatrix} 9 & 5 & 32 \\ 8 & 19 & 14 \\ 50 & 30 & 30 \end{pmatrix} \]

Interchanging Row and Column Elements in a Two Dimensional Array

Swapping rows with columns (finding the transpose of a matrix) in place requires a square matrix of size \( N \times N \) since the modifications are stored within the original memory allocation.
For instance:
\[ \text{Given Array} = \begin{pmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{pmatrix} \implies \text{Array after interchange} = \begin{pmatrix} 1 & 4 & 7 \\ 2 & 5 & 8 \\ 3 & 6 & 9 \end{pmatrix} \]

Stacks

A stack is a linear collection where additions and removals occur exclusively at a single end, designated as the TOP. Consequently, elements are retrieved in the exact opposite order of their insertion. This behavior characterizes the stack as a Last-In, First-Out (LIFO) structure.

• Push: The operation of adding an item onto the stack.
• Pop: The operation of removing the top-most item from the stack.

Queue

A queue is a sequential container where items are removed from one end, known as the "front", and inserted at the opposite end, called the "rear". These specific access points are characteristic of a queue, making it a First-In, First-Out (FIFO) list.

Linked List

A linked list consists of a chain of elements called nodes, where each node contains a data field and a reference (or pointer) pointing to the succeeding node.

Stack As A Linked List

Implementing a stack using a linked list provides dynamic allocation, meaning we do not need to define the size beforehand. The stack structure inherits this flexibility. To push an item, we allocate a new node and adjust the TOP pointer so that it points directly to this newly added node. Popping also requires resetting TOP to point to the next node in the chain.

Solved Questions

Question Q1. What is the difference between linear and non- linear data structures?
Answer: Linear data structures organize their elements sequentially on a single level, where each element is adjacent to its previous and next elements (for example, stacks, queues, and linked lists). In contrast, non-linear data structures are hierarchical or multi-level, meaning their elements do not follow a sequential path (examples include trees and graphs).
In simple words: Linear data structures keep elements in a straight line, one after the other. Non-linear data structures arrange elements in levels or complex networks, like trees.

Exam Tip: To secure full marks, always provide a clear comparison and back it up with standard examples like stacks/queues for linear, and trees/graphs for non-linear structures.

Question Q2. Describe the similarities and differences between queues and stacks.
Answer:
Similarities:
(a) Both structures represent specialized versions of sequential or linear lists.
(b) Both can be built using static arrays or dynamic linked lists.
Differences:
(a) A stack follows the Last-In-First-Out (LIFO) model, whereas a queue is structured on the First-In-First-Out (FIFO) principle.
(b) Standard stacks generally lack structural variants, but queues can take several forms, such as circular queues or double-ended queues (deques).
In simple words: Stacks and queues are both linear collections of items. Stacks remove the newest item first (like a stack of plates), while queues remove the oldest item first (like a line at a ticket counter).

Exam Tip: Be sure to write the full forms of LIFO (Last-In-First-Out) and FIFO (First-In-First-Out) in exams to impress the examiner.

Question Q3. What is meant by the term “Overflow” & “Underflow”?
Answer: An overflow condition occurs when a program attempts to insert a new element into a collection that is already completely full and lacks free space. Conversely, an underflow condition happens when there is an attempt to remove or delete an element from a collection that contains no data.
In simple words: Overflow is like trying to add water to a cup that is already full. Underflow is like trying to drink from an empty cup.

Exam Tip: Always associate overflow with insertion in a full memory structure, and underflow with deletion from an empty structure.

Question Q4 . Distinguish between infix, prefix and postfix algebric expression giving examples of each.
Answer:
Infix Notation: This representation positions the mathematical operator directly between its two operands, which is the standard way we write arithmetic. Examples: \( A+B \), \( (A-C)* B \)
Prefix Notation: In this style, the operator is placed immediately ahead of its operands. Examples: \( +AB \), \( *-ACB \)
Postfix Notation: This format places the operator immediately following its operands. Examples: \( AB+ \), \( AC-B* \), \( ABC*+ \)
In simple words: Infix has the symbol in the middle (A + B), prefix has it at the start (+ A B), and postfix has it at the end (A B +).

Exam Tip: Be precise with parentheses when converting expressions. Prefix and postfix notations do not need any parentheses to define operator precedence.

Question Q5 . Evaluate the following postfix notation of expression, show status of stack for each operation
500, 20, 30, + , 10, * , +
Answer:
To evaluate this postfix expression, we scan each token from left to right. Numeric values are pushed directly onto the stack. When an operator is encountered, the top two elements are popped from the stack, the corresponding operation is performed, and the outcome is pushed back onto the stack. The step-by-step stack contents are shown below:

The final value in the stack is 1000.
In simple words: Put the numbers on the stack one by one. When you see a symbol like + or *, pop the last two numbers, do the math, and put the result back. The last number left is your final answer.

Exam Tip: Showing the step-by-step stack status in a clean tabular format is the best way to earn full marks on evaluation questions.

Unsolved Questions

Question Q. 1. How is computer memory allotted for a 2D array?
Answer: Because computer memory is physically linear (one-dimensional), a two-dimensional array must be mapped sequentially using one of two primary memory allotment schemes:
1. Row-Major Order: The array is stored row-by-row in continuous memory. The elements of the first row are saved first, followed by the elements of the second row, and so on. This is the default approach in languages like C and C++.
2. Column-Major Order: The array is stored column-by-column. All elements of the first column are written first, followed by the entire second column, and so on. This format is used in languages like Fortran.
In simple words: Since computer memory is just a long line, we must store a 2D grid either by writing it row after row, or column after column.

Exam Tip: Be sure to name both Row-Major and Column-Major order and provide a brief explanation of how each stores elements to get full marks.

Question Q. 2. Binary search is to be used on the following sorted array to search for 30 and 60.
Index: 1 2 3 4 5 6 7 8 9 10
Value: 11 22 30 33 40 44 55 60 66 70
Give the index of the element that would be compared with at every step. Repeat the process replacing 30 by 60.
Answer:
Search for 30:
Let \( L \) be the lower bound and \( R \) be the upper bound. Initially, \( L = 1 \) and \( R = 10 \).
* Step 1: Calculate \( \text{mid} = \lfloor(L + R)/2\rfloor = \lfloor(1 + 10)/2\rfloor = 5 \). Compare target 30 with value at index 5 (40). Since \( 30 < 40 \), the search space is restricted to the left half: \( R = \text{mid} - 1 = 4 \).
* Step 2: Calculate \( \text{mid} = \lfloor(1 + 4)/2\rfloor = 2 \). Compare target 30 with value at index 2 (22). Since \( 30 > 22 \), the search space is restricted to the right: \( L = \text{mid} + 1 = 3 \).
* Step 3: Calculate \( \text{mid} = \lfloor(3 + 4)/2\rfloor = 3 \). Compare target 30 with value at index 3 (30). The element is found successfully.
The index comparison sequence for 30 is: 5, 2, 3.

Search for 60:
Initially, \( L = 1 \) and \( R = 10 \).
* Step 1: Calculate \( \text{mid} = \lfloor(1 + 10)/2\rfloor = 5 \). Compare target 60 with value at index 5 (40). Since \( 60 > 40 \), the search space is restricted to the right half: \( L = \text{mid} + 1 = 6 \).
* Step 2: Calculate \( \text{mid} = \lfloor(6 + 10)/2\rfloor = 8 \). Compare target 60 with value at index 8 (60). The element is found successfully.
The index comparison sequence for 60 is: 5, 8.
In simple words: Binary search starts in the exact middle. If the target is smaller, it repeats in the left half; if larger, it repeats in the right half, halving the choices each time until the number is located.

Exam Tip: Be explicit about showing how the mid-point is calculated at each step using the floor function \( \lfloor \dots \rfloor \) to avoid fractional indexes.

Question Q. 3. Consider the single dimensional array AAA [45] having base address 300 and 4 bytes is the size of each element of the array. Find the address of AAA [10], AAA [25] and AAA [40].
Answer:
Assuming the lower bound (\( LB \)) of the array is \( 0 \) (indexing from \( 0 \) to \( 44 \)), we use the address formula for a 1D array:
\[ \text{Address of AAA}[i] = B + (i - LB) \times S \]
Given:
* Base Address \( B = 300 \)
* Element Size \( S = 4 \) bytes
* Lower Bound \( LB = 0 \)

1. Address of AAA[10]:
\[ \text{Address of AAA}[10] = 300 + (10 - 0) \times 4 = 300 + 40 = 340 \]
2. Address of AAA[25]:
\[ \text{Address of AAA}[25] = 300 + (25 - 0) \times 4 = 300 + 100 = 400 \]
3. Address of AAA[40]:
\[ \text{Address of AAA}[40] = 300 + (40 - 0) \times 4 = 300 + 160 = 460 \]
In simple words: To find where an item is in memory, multiply its index by the size of each element (4 bytes) and add this to the start address (300).

Exam Tip: Clearly state whether you assume the lower bound to be 0 or 1, as both conventions are used, although 0 is standard in C++.

Question Q. 4. Given two dimensional array A[10][20], base address of A being 100 and width of each element is 4 bytes, find the location of A[8][15] when the array is stored as a) column wise b) Row wise.
Answer:
Given details for array \( A[M][N] \):
* Number of rows, \( M = 10 \)
* Number of columns, \( N = 20 \)
* Base address, \( B = 100 \)
* Element size (width), \( W = 4 \) bytes
* Target indices: \( i = 8 \), \( j = 15 \)
* Lower bounds: \( LB1 = 0 \) (row index starts at 0), \( LB2 = 0 \) (column index starts at 0)

a) Column-wise storage (Column-Major Order):
Formula:
\[ \text{Address of A}[i][j] = B + \left[ (i - LB1) + (j - LB2) \times M \right] \times W \]
Substituting the values:
\[ \text{Address of A}[8][15] = 100 + \left[ (8 - 0) + (15 - 0) \times 10 \right] \times 4 \]

\implies \text{Address} = 100 + [8 + 150] \times 4

\implies \text{Address} = 100 + 158 \times 4 = 100 + 632 = 732

b) Row-wise storage (Row-Major Order):
Formula:
\[ \text{Address of A}[i][j] = B + \left[ (i - LB1) \times N + (j - LB2) \right] \times W \]
Substituting the values:
\[ \text{Address of A}[8][15] = 100 + \left[ (8 - 0) \times 20 + (15 - 0) \right] \times 4 \]

\implies \text{Address} = 100 + [160 + 15] \times 4

\implies \text{Address} = 100 + 175 \times 4 = 100 + 700 = 800
In simple words: To find where an element sits in memory, we calculate how many items are stored before it. In row-major, we count row-by-row; in column-major, we count column-by-column.

Exam Tip: Be careful not to swap \( M \) (number of rows) and \( N \) (number of columns) in the formulas; using the wrong dimension is a very common student mistake.

Question Q. 5. Write a C++ function to find and display the sum of each row and each column of a 2 dimensional array of type float. Use the array and its size as parameters with float as the return type.
Answer:
Below is the C++ function that calculates and displays the sum of each individual row and column, and returns the total sum of all elements in the 2D array:

#include <iostream>

float calculateAndDisplaySums(float arr[100][100], int rows, int cols) {
    float grandTotal = 0.0;

    // Calculate and print the sum of each row
    for (int i = 0; i < rows; i++) {
        float rowSum = 0.0;
        for (int j = 0; j < cols; j++) {
            rowSum += arr[i][j];
        }
        std::cout << "Sum of Row " << i + 1 << " = " << rowSum << std::endl;
        grandTotal += rowSum;
    }

    std::cout << std::endl;

    // Calculate and print the sum of each column
    for (int j = 0; j < cols; j++) {
        float colSum = 0.0;
        for (int i = 0; i < rows; i++) {
            colSum += arr[i][j];
        }
        std::cout << "Sum of Column " << j + 1 << " = " << colSum << std::endl;
    }

    return grandTotal;
}

In simple words: This code uses nested loops to traverse rows first (adding elements horizontally), then columns (adding elements vertically), and returns the overall sum.

Exam Tip: When declaring a 2D array in C++ parameters, you must specify the second dimension size (the column size) so the compiler can correctly compute memory offsets.

Question Q. 6. Differentiate between a FIFO list and LIFO list.
Answer:
The main differences between FIFO and LIFO systems are detailed below:
* FIFO (First-In, First-Out): In this data organization method, the very first element inserted is the first one to be deleted. Any insertion happens at the back (rear), while deletions occur at the front. A classic implementation of a FIFO structure is a queue.
* LIFO (Last-In, First-Out): In this method, the most recently added element is the first one to be removed. Both insertions and deletions take place at a single point called the top. A classic implementation of a LIFO structure is a stack.
In simple words: FIFO is like a queue at a grocery store where the first person in line gets served first. LIFO is like a stack of plates where the last plate placed on top is the first one taken off.

Exam Tip: Use real-world analogies (like a ticket line vs. a plate stack) along with programming terms to explain these concepts clearly.

Question Q. 7. Transform the following expression to prefix and postfix form: (A+B*C-D)/E*F
Answer:
Let us convert the expression \( (A + B * C - D) / E * F \) using operator precedence (multiplication and division have higher precedence than addition and subtraction, and are evaluated from left to right):

1. Postfix Conversion:
* First, convert inside the parentheses: \( A + B * C - D \)

\implies A + (BC*) - D \quad \text{[Processing *]}

\implies (ABC*+) - D \quad \text{[Processing +]}

\implies ABC*+D- \quad \text{[Processing -]}
* Let \( X = ABC*+D- \). The expression becomes: \( X / E * F \)
* Evaluate \( / \) first (left-to-right precedence):

\implies XE/ * F
* Evaluate \( * \):

\implies XE/F*
* Substitute back \( X \):

\implies \mathbf{ABC*+D-E/F*}

2. Prefix Conversion:
* First, convert inside the parentheses: \( A + B * C - D \)

\implies A + (*BC) - D \quad \text{[Processing *]}

\implies (+A*BC) - D \quad \text{[Processing +]}

\implies -+A*BCD \quad \text{[Processing -]}
* Let \( Y = -+A*BCD \). The expression becomes: \( Y / E * F \)
* Evaluate \( / \) first (left-to-right precedence):

\implies /YE * F
* Evaluate \( * \):

\implies */YEF
* Substitute back \( Y \):

\implies \mathbf{*/-+A*BCDEF}
In simple words: Postfix moves all operator symbols to the end of their operands, while prefix pulls them to the front, following standard math precedence rules.

Exam Tip: Show the step-by-step evaluation using intermediate variables (like X or Y) to avoid errors and demonstrate a clear understanding to the grader.

High Order Thinking Skills (HOTS)

Question Q1. What are preconditions for Binary search to be performed on a single dimensional array?
Answer:
For a binary search to be executed successfully on a single-dimensional array, two key prerequisites must be met:
(a) The elements within the array must be pre-sorted in either ascending or descending order.
(b) The lower bound (starting index) and upper bound (ending index) of the array must be clearly defined.
In simple words: You can only use binary search if your list is already sorted in order and you know where the list starts and ends.

Exam Tip: If the array is not sorted, linear search must be used instead, or the array must be sorted first, which increases the total time complexity.

Question Q2. How is computer memory allotted for two dimensional array?
Answer:
Memory allocation for a two-dimensional array is carried out in a continuous linear fashion using one of two techniques:
* Row-Major Form: The array is stored row-by-row. In this approach, all elements of the first row are placed in consecutive memory addresses first, followed by the second row, third row, and so on. This is typically the default mapping method.
* Column-Major Form: The array is stored columnwise. Here, all elements of the first column are placed in consecutive memory addresses first, followed by the second column, third column, and so forth.
In simple words: 2D grids are stored in a single line of memory either row-by-row (row-major) or column-by-column (column-major).

Exam Tip: Mentioning which languages use which format (such as C/C++ using Row-Major) is an excellent way to add technical value to your answer.

Question Q3. Calculate the address of X[ 4,3] in a two dimensional arrayX[1….5,1….4] stored in a row major order in the main memory. Assume the base address to be 1000 and that each element requires 4 words of storage.
Answer:
We can calculate the address using the Row-Major address calculation formula for a 2D array:
\[ \text{Address of X}[I, J] = B + W \times [n \times (I - L1) + (J - L2)] \]
Given values:
* Base address, \( B = 1000 \)
* Storage size per element, \( W = 4 \) words
* Number of columns, \( n = 4 \) (derived from column range \( 1 \dots 4 \))
* Lower bound of row index, \( L1 = 1 \)
* Lower bound of column index, \( L2 = 1 \)
* Target row index, \( I = 4 \)
* Target column index, \( J = 3 \)

Substituting these values into the formula:
\[ \text{Address of X}[4, 3] = 1000 + 4 \times [4 \times (4 - 1) + (3 - 1)] \]

\implies \text{Address} = 1000 + 4 \times [4 \times 3 + 2]

\implies \text{Address} = 1000 + 4 \times [12 + 2]

\implies \text{Address} = 1000 + 4 \times [14]

\implies \text{Address} = 1000 + 56 = 1056
In simple words: First find how many rows are fully skipped (3 rows) and multiply by the row size (4 columns), then add the skipped columns in the current row (2 columns). Multiply the total skipped slots by 4 words each, and add to the start address.

Exam Tip: Be sure to write the formula and state all your variables clearly before starting the substitution steps to prevent calculation errors.

Question Q. 4. Transform the following expressions to infix form:
1. + - ABC
2. + A - BC
Answer:
To convert these prefix expressions (operators placed before operands) to infix form (operators between operands):

1. Conversion of \( + - ABC \):
* Identify the first sub-expression from right to left with a binary operator followed by two operands: \( - AB \)
* Convert \( - AB \) to infix: \( (A - B) \)
* The expression now becomes: \( + (A - B) C \)
* Convert this to infix: \( \mathbf{(A - B) + C} \)

2. Conversion of \( + A - BC \):
* Identify the first sub-expression from right to left with a binary operator followed by two operands: \( - BC \)
* Convert \( - BC \) to infix: \( (B - C) \)
* The expression now becomes: \( + A (B - C) \)
* Convert this to infix: \( \mathbf{A + (B - C)} \)
In simple words: Group operators with their immediate operands starting from the right, then move the operator symbols to the middle of those operands.

Exam Tip: Using brackets to show the order of conversion step-by-step ensures that you do not lose marks for incorrect operator precedence.

Question Q. 5. Evaluate the following postfix expression using a stack and show the contents of the stack after execution of each operation:
5, 6, 9, +, 80, 5, *, -, /
Answer:
To evaluate this postfix expression, we scan each element from left to right. Numbers are pushed onto the stack. When an operator is scanned, the top two elements are popped, the operation is executed, and the result is pushed back onto the stack:

The final evaluated value of the expression is \( -\frac{1}{77} \) (or approximately \( -0.013 \)).
In simple words: The numbers are stored on a stack, and whenever an operator appears, we pop the top two numbers to perform the calculation, then push the result back. The final division gives -1/77.

Exam Tip: Be careful with the order of operands in subtraction and division. The first popped element is the divisor/subtrahend (right-hand operand), and the second popped is the dividend/minuend (left-hand operand).

Question Q 6. Give the necessary declaration of a linked implemented stack containing integer type numbers; also write a user defined function in C++ to pop a number from this stack.
Answer:
Here is the declaration for a node in a linked stack along with the C++ function to perform the pop operation:

#include <iostream>

// Structure definition for a stack node
struct Node {
    int data;
    Node* next;
};

// Global pointer pointing to the top of the stack
Node* top = nullptr;

// Function to pop a value from the stack
int pop() {
    // Check for stack underflow
    if (top == nullptr) {
        std::cout << "Stack Underflow!" << std::endl;
        return -1; // Return -1 to indicate error
    }

    Node* temp = top;        // Keep a temporary reference to the top node
    int poppedValue = temp->data; // Extract the data
    top = top->next;         // Move top pointer to the next node
    delete temp;             // Deallocate memory of the popped node

    return poppedValue;      // Return the retrieved value
}

In simple words: A linked stack node contains an integer and a pointer to the next node. Popping involves retrieving the top node's data, moving the top pointer down, and deleting the old top node to free up memory.

Exam Tip: Always include an underflow check (verifying if `top == nullptr`) in your pop functions to avoid segment faults and secure full marks.