Introduction to Stack

A Stack is a linear data structure that follows the Last In, First Out (LIFO) principle.
It supports the following operations:

1. Push: Add an element to the top of the stack.

2. Pop: Remove the top element from the stack.

3. Peek/Top: Return the top element without removing it.

4. IsEmpty: Check if the stack is empty.

5. IsFull: (For array-based stack) Check if the stack is full.

Visit part 1 to know more in detail : here

Visit the series to get all previously uploaded blogs related to this topic : here

1.PUSH Operation

Using Array

Algorithm

1. Start

2. If top == size - 1, print "Stack Overflow" and exit.

3. Increment top by 1.

4. Set stack[top] = value.

5. Print "Value pushed".

6. End

Pseudocode (Array-Based)

Function PUSH(value):
    If top == size - 1:
        Print "Stack Overflow"
        Return
    End If

    top = top + 1
    stack[top] = value
    Print "Value pushed"
End Function

C Code (Array-Based)

#include <stdio.h>
#define SIZE 5

int stack[SIZE], top = -1;

void push(int value) {
    if (top == SIZE - 1) {
        printf("Stack Overflow\n");
        return;
    }
    top++;
    stack[top] = value;
    printf("Pushed %d\n", value);
}

int main() {
    push(10);
    push(20);
    push(30);
    return 0;
}

Using Linked List

Algorithm

1. Start

2. Create a new node temp.

3. If memory allocation fails, print "Stack Overflow" and exit.

4. Set temp->data = value.

5. Set temp->next = top.

6. Update top = temp.

7. Print "Value pushed".

8. End

Pseudocode (Linked List-Based)

Function PUSH(value):
    temp = create_new_node()
    If temp == NULL:
        Print "Stack Overflow"
        Return
    End If

    temp.data = value
    temp.next = top
    top = temp
    Print "Value pushed"
End Function

C Code (Linked List-Based)

#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node* next;
};
struct Node* top = NULL;

void push(int value) {
    struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
    if (temp == NULL) {
        printf("Stack Overflow\n");
        return;
    }
    temp->data = value;
    temp->next = top;
    top = temp;
    printf("Pushed %d\n", value);
}

int main() {
    push(10);
    push(20);
    push(30);
    return 0;
}

2. POP Operation

Using Array

Algorithm

1. Start

2. If top == -1, print "Stack Underflow" and exit.

3. Print stack[top] as the value to be popped.

4. Decrement top by 1.

5. End

Pseudocode (Array-Based)

Function POP():
    If top == -1:
        Print "Stack Underflow"
        Return
    End If

    Print "Popped value: ", stack[top]
    top = top - 1
End Function

C Code (Array-Based)

void pop() {
    if (top == -1) {
        printf("Stack Underflow\n");
        return;
    }
    printf("Popped value: %d\n", stack[top]);
    top--;
}

Using Linked List

Algorithm

1. Start

2. If top == NULL, print "Stack Underflow" and exit.

3. Create a temporary node temp = top.

4. Print temp->data as the value to be popped.

5. Update top = top->next.

6. Free the memory of temp.

7. End

Pseudocode (Linked List-Based)

Function POP():
    If top == NULL:
        Print "Stack Underflow"
        Return
    End If

    temp = top
    Print "Popped value: ", temp.data
    top = top.next
    Free(temp)
End Function

C Code (Linked List-Based)

void pop() {
    if (top == NULL) {
        printf("Stack Underflow\n");
        return;
    }
    struct Node* temp = top;
    printf("Popped value: %d\n", temp->data);
    top = top->next;
    free(temp);
}

3. PEEK Operation

Using Array

Algorithm

1. Start

2. If top == -1, print "Stack is Empty" and exit.

3. Print stack[top] as the top value.

4. End

C Code (Array-Based)

void peek() {
    if (top == -1) {
        printf("Stack is Empty\n");
        return;
    }
    printf("Top value: %d\n", stack[top]);
}

Using Linked List

Algorithm

1. Start

2. If top == NULL, print "Stack is Empty" and exit.

3. Print top->data as the top value.

4. End

C Code (Linked List-Based)

void peek() {
    if (top == NULL) {
        printf("Stack is Empty\n");
        return;
    }
    printf("Top value: %d\n", top->data);
}

4. ISEMPTY Operation

Using Array

Algorithm

1. Start.

2. Check if the stack is empty:

   • If top == -1, the stack is empty.

   • Otherwise, the stack is not empty.

3. Print the result.

4. End.

Pseudocode

Function isEmpty():
    If top == -1:
        Print "Stack is Empty"
        Return True
    Else:
        Print "Stack is not Empty"
        Return False
End Function

C Code

#include <stdio.h>
#define SIZE 5

int stack[SIZE], top = -1;

int isEmpty() {
    if (top == -1) {
        printf("Stack is Empty\n");
        return 1;
    } else {
        printf("Stack is not Empty\n");
        return 0;
    }
}

int main() {
    isEmpty(); // Stack is Empty
    return 0;
}

Using Linked List

Algorithm

1. Start.

2. Check if the stack is empty:

   • If top == NULL, the stack is empty.

   • Otherwise, the stack is not empty.

3. Print the result.

4. End.

Pseudocode

Function isEmpty():
    If top == NULL:
        Print "Stack is Empty"
        Return True
    Else:
        Print "Stack is not Empty"
        Return False
End Function

C Code

#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node* next;
};
struct Node* top = NULL;

int isEmpty() {
    if (top == NULL) {
        printf("Stack is Empty\n");
        return 1;
    } else {
        printf("Stack is not Empty\n");
        return 0;
    }
}

int main() {
    isEmpty(); // Stack is Empty
    return 0;
}

5. ISFULL Operation

Using Array

Algorithm

1. Start.

2. Check if the stack is full:

   • If top == SIZE - 1, the stack is full.

   • Otherwise, the stack is not full.

3. Print the result.

4. End.

Pseudocode

Function isFull():
    If top == SIZE - 1:
        Print "Stack is Full"
        Return True
    Else:
        Print "Stack is not Full"
        Return False
End Function

C Code

#include <stdio.h>
#define SIZE 5

int stack[SIZE], top = -1;

int isFull() {
    if (top == SIZE - 1) {
        printf("Stack is Full\n");
        return 1;
    } else {
        printf("Stack is not Full\n");
        return 0;
    }
}

int main() {
    isFull(); // Stack is not Full
    return 0;
}

Using Linked List

The isFull operation does not apply to linked lists as they are dynamic and only limited by system memory.

Key Differences Between Array and Linked List Implementation

Stack Operations and Their Complexities

1. PUSH Operation

Using Array

• Operation: Inserting an element at the top of the stack.

• Time Complexity:

  • Best Case: O(1) — Insert operation directly at the top index.

  • Worst Case: O(1) — Always constant since no iteration or resizing is involved in a fixed-size array.

  • Average Case: O(1)

• Space Complexity: O(1) — No additional memory is used beyond the stack array.

Using Linked List

• Operation: Creating a new node and inserting it at the top.

• Time Complexity:

  • Best Case: O(1) — Adding a new node to the top pointer.

  • Worst Case: O(1) — Same as best case.

  • Average Case: O(1)

• Space Complexity: O(1) — Memory is allocated only for the new node (constant space).

---

2. POP Operation

Using Array

• Operation: Removing the element from the top of the stack.

• Time Complexity:

  • Best Case: O(1) — Decrementing the top pointer and accessing the element.

  • Worst Case: O(1) — Always constant.

  • Average Case: O(1)

• Space Complexity: O(1) — No extra memory is used.

Using Linked List

• Operation: Removing the node from the top of the linked list.

• Time Complexity:

  • Best Case: O(1) — Adjusting the top pointer and freeing memory.

  • Worst Case: O(1) — Same as best case.

  • Average Case: O(1)

• Space Complexity: O(1) — Only memory for the node being freed.

---

3. PEEK Operation

Using Array

• Operation: Accessing the element at the top index.

• Time Complexity:

  • Best Case: O(1)

  • Worst Case: O(1)

  • Average Case: O(1)

• Space Complexity: O(1)

Using Linked List

• Operation: Accessing the data in the node pointed to by top.

• Time Complexity:

  • Best Case: O(1)

  • Worst Case: O(1)

  • Average Case: O(1)

• Space Complexity: O(1)

---

4. ISEMPTY Operation

Using Array

• Operation: Checking if top == -1.

• Time Complexity:

  • Best Case: O(1)

  • Worst Case: O(1)

  • Average Case: O(1)

• Space Complexity: O(1)

Using Linked List

• Operation: Checking if top == NULL.

• Time Complexity:

  • Best Case: O(1)

  • Worst Case: O(1)

  • Average Case: O(1)

• Space Complexity: O(1)

---

5. ISFULL Operation

Using Array

• Operation: Checking if top == SIZE - 1.

• Time Complexity:

  • Best Case: O(1)

  • Worst Case: O(1)

  • Average Case: O(1)

• Space Complexity: O(1)

Using Linked List

• Operation: The isFull function does not apply directly to linked lists since the size grows dynamically.

• Time Complexity: O(1) if a limit is implemented; otherwise, it does not apply.

• Space Complexity: O(1)

Summary of Complexities

PYQ of MAKAUT university based on the topic covered in part 1 and part 2 ( try to solve by yourself )

Extra question answers ( it can contain more topics which have any type of relation with stack)

Special Question:

How many stacks are required to implement mutual recursion?

Answer:

Only 1 stack is required to implement mutual recursion.

In mutual recursion, although two or more functions call each other alternately (e.g., A calls B and B calls A), all function calls are managed within a single call stack. The stack keeps track of the active function calls, regardless of which function is calling which. Each time a function is called, its information is pushed onto the stack, and when a function returns, its frame is popped off the stack.

Thus, even in the case of mutual recursion, all function calls use the same stack.

1. Define a stack and explain its operations.

Answer:
A stack is a linear data structure that follows the Last In First Out (LIFO) principle. The basic operations of a stack are:

• Push: Adds an element to the top of the stack.

• Pop: Removes the top element from the stack.

• Peek (Top): Returns the top element without removing it.

• IsEmpty: Checks if the stack is empty.

• IsFull: Checks if the stack is full (in array-based implementation).

---

2. What are the different ways to implement a stack? Compare array-based and linked list-based implementations.

Answer:
A stack can be implemented using:

• Array-based implementation:

  • Pros: Simple and fast for small stack sizes, direct access to elements.

  • Cons: Fixed size, limited flexibility.

• Linked list-based implementation:

  • Pros: Dynamic size, no overflow issues.

  • Cons: Requires extra memory for pointers, slightly more complex.

---

3. Explain the time complexity of the basic operations (push, pop, peek) in a stack.

Answer:
The time complexity for all basic operations in a stack (push, pop, and peek) is O(1), as each operation involves accessing the top element of the stack, which is a constant-time operation.

---

4. What is the difference between a stack and a queue?

Answer:

• Stack: Follows Last In First Out (LIFO) principle, where the last element added is the first to be removed.

• Queue: Follows First In First Out (FIFO) principle, where the first element added is the first to be removed.

---

5. Explain the concept of stack overflow and underflow with examples.

Answer:

• Stack Overflow: Occurs when trying to push an element onto a stack that is already full (in array-based stacks).

• Stack Underflow: Occurs when trying to pop an element from an empty stack.

---

6. What is the use of the stack data structure in function calls and recursion?

Answer:
In function calls, the call stack stores the execution context (local variables, return addresses) for each function. Recursion uses the stack to store each recursive call’s context until the base case is reached.

---

7. What is the stack frame? How does it work in recursion?

Answer:
A stack frame is the data structure that holds the information (like local variables and return address) of a single function call. In recursion, each recursive call pushes a new stack frame onto the stack, and it is popped off when the base case is reached.

---

8. What is a recursive function? Explain how recursion works with an example.

Answer:
A recursive function is one that calls itself to solve a smaller subproblem. For example, the factorial function:

factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);
}

---

9. What is mutual recursion? Provide an example. How does it differ from direct recursion?

Answer:
Mutual recursion occurs when two or more functions call each other recursively.
Example:

A(int n) { if (n > 0) B(n - 1); }
void B(int n) { if (n > 0) A(n - 1); }

In direct recursion, a function calls itself. In mutual recursion, two or more functions call each other.

---

10. Explain the advantages and disadvantages of using recursion.

Answer:

• Advantages:

  • Simplifies code for problems like tree traversals or divide-and-conquer algorithms.

  • Can be more intuitive and easier to implement for certain problems.

• Disadvantages:

  • Uses more memory (call stack).

  • Can be slower than iterative solutions for large inputs.

---

11. What is the base case in recursion? Why is it important in recursive function calls?

Answer:
The base case is the condition under which the recursive function stops calling itself. It prevents infinite recursion and allows the function to return a result.

---

12. Explain the different types of recursion (direct, indirect, mutual recursion).

Answer:

• Direct recursion: A function calls itself directly.

• Indirect recursion: A function calls another function, which calls the first function.

• Mutual recursion: Two or more functions call each other recursively.

---

13. What is the time complexity of a recursive algorithm? How do you determine it?

Answer:
The time complexity of a recursive algorithm is determined by the number of recursive calls and the work done per call. It can be analyzed using:

• Recurrence relations

• Master theorem

---

14. What is a function call stack, and how is it used in recursion?

Answer:
A function call stack is used to store information about the active function calls. Each time a function is called, a new frame is pushed onto the stack. Recursion uses this stack to store each recursive call’s state until the base case is reached.

---

15. Explain the concept of stack-based memory allocation and how the stack grows during function calls.

Answer:
In stack-based memory allocation, function calls are stored on the call stack. As functions are called, new stack frames are pushed onto the stack. When functions return, their stack frames are popped, freeing memory.

---

16. How does the stack help in parsing expressions (e.g., infix to postfix or infix to prefix conversion)?

Answer:
Stacks are used in parsing expressions to hold operators and operands temporarily while converting expressions (infix to postfix or prefix). The stack helps maintain the correct order of operations and precedence during the conversion.

---

17. What is a depth-first search (DFS) and how is it implemented using a stack?

Answer:
Depth-first search (DFS) is a graph traversal algorithm that explores as far down a branch as possible before backtracking. It can be implemented using a stack, which stores the nodes to visit next.

---

18. Discuss the space complexity of recursive algorithms and how it relates to the call stack.

Answer:
The space complexity of recursive algorithms is determined by the maximum depth of the recursion, which is directly related to the size of the call stack. Each recursive call adds a new frame to the stack, so deeper recursions use more space.

---

19. Explain the difference between static and dynamic memory allocation in the context of stacks.

Answer:

• Static memory allocation: Memory size is fixed at compile time (e.g., array-based stack).

• Dynamic memory allocation: Memory size is flexible and allocated at runtime (e.g., linked list-based stack).

---

20. What is a stack-based calculator, and how can it be implemented using a stack data structure?

Answer:
A stack-based calculator evaluates expressions in postfix notation using a stack. The algorithm involves:

1. Pushing operands onto the stack.

2. When an operator is encountered, popping operands from the stack, performing the operation, and pushing the result back onto the stack.

In the next part, we will be wrapping up with the last concept in stacks: different types of notation (such as infix, postfix, and prefix) and the conversion between them. Understanding these notations is crucial for evaluating expressions efficiently, especially when dealing with stack-based algorithms. We will explore how stacks help in converting infix expressions to postfix and prefix notations, and how to evaluate these expressions using stacks.