STACK

### Stack Definition

A stack is a linear data structure that follows the Last In First Out (LIFO) principle.

This means the last element added to the stack is the first to be removed. Stacks are used for various purposes in computing and are fundamental to many algorithms and processes.

### Properties of Stack

1. LIFO Order: The last element added (pushed) is the first one to be removed (popped). This means that in a last-in, first-out (LIFO) data structure, the most recently added element is the first to be removed.

2. Dynamic Size: The size of the stack can grow or shrink as elements are added or removed.

3. Top Operation: Allows access to the most recently added element.

4. Push Operation: Adds an element to the top of the stack.

5. Pop Operation: Removes the element from the top of the stack.

### Stack Applications

1. Expression Evaluation:

- Postfix Expression: Used to evaluate postfix (Reverse Polish notation) expressions.

- Infix to Postfix Conversion: Used to convert infix expressions to postfix expressions for easier evaluation.

2. Function Call Management:

- Recursion: Used to store return addresses and local variables of active function calls in recursive programming.

3. Syntax Parsing:

- Compiler Design: Used in parsing expressions and checking syntax in compilers.

4. Undo Mechanisms:

- Text Editors: Used to implement undo functionality by storing previous states.

5. Depth-First Search (DFS):

- Graph Algorithms: Used in DFS algorithms to keep track of vertices to be explored.

Stack Applications

1. Function Call Management:

   • Recursion: Each recursive call is placed on the stack, managing the function calls and local variables.

2. Expression Evaluation and Syntax Parsing:

   • Compilers: Used for parsing expressions and evaluating postfix and infix expressions.

   • Syntax Checkers: Used to check the balance of parentheses in expressions.

3. Undo Mechanism:

   • Text Editors: Keeps track of changes for the undo functionality.

   • Photo Editors: Allows reverting to previous states of editing.

4. Navigation:

   • Browser History: Maintains a stack of pages visited to implement the back function.

   • Pathfinding: Used in algorithms that navigate paths, like depth-first search in mazes.

5. Memory Management:

   • Memory Allocation: Manages function calls and local variables in languages like C and C++.

### Operations Performed on Stacks

1. Push Operation

- Purpose: Adds an element to the top of the stack.

- Process:

1. Check if the stack is full (stack overflow).

2. If not full, increment the top pointer.

3. Add the new element at the position indicated by the top pointer.

- Time Complexity: \(O(1)\).

2. Pop Operation

- Purpose: Removes the top element from the stack.

- Process:

1. Check if the stack is empty (stack underflow).

2. If not empty, retrieve the element from the top of the stack.

3. Decrement the top pointer.

4. Return the retrieved element.

- Time Complexity: \(O(1)\).

3. Peek (Top) Operation

- Purpose: Returns the top element without removing it from the stack.

- Process:

1. Check if the stack is empty.

2. If not empty, return the element at the top of the stack.

- Time Complexity: \(O(1)\).

4. isEmpty Operation

- Purpose: Checks if the stack is empty.

- Process:

1. Compare the top pointer with the initial value (typically -1).

2. Return true if the stack is empty, false otherwise.

- Time Complexity: \(O(1)\).

5. isFull Operation

- Purpose: Checks if the stack is full.

- Process:

1. Compare the top pointer with the maximum size minus one.

2. Return true if the stack is full, false otherwise.

- Time Complexity: \(O(1)\).

### Example Code for Stack Operations in C

```c

#include <stdio.h>

#include <stdlib.h>

#define MAX 100

typedef struct {

int items[MAX];

int top;

} Stack;

// Initialize stack

void initStack(Stack *s) {

s->top = -1;

}

// Push operation

void push(Stack *s, int item) {

if (s->top == MAX - 1) {

printf("Stack Overflow\n");

return;

}

s->items[++(s->top)] = item;

}

// Pop operation

int pop(Stack *s) {

if (s->top == -1) {

printf("Stack Underflow\n");

return -1;

}

return s->items[(s->top)--];

}

// Peek operation

int peek(Stack *s) {

if (s->top == -1) {

printf("Stack is empty\n");

return -1;

}

return s->items[s->top];

}

// Check if stack is empty

int isEmpty(Stack *s) {

return s->top == -1;

}

// Check if stack is full

int isFull(Stack *s) {

return s->top == MAX - 1;

}

int main() {

Stack s;

initStack(&s);

push(&s, 10);

push(&s, 20);

push(&s, 30);

printf("Top element is %d\n", peek(&s));

while (!isEmpty(&s)) {

printf("Popped element is %d\n", pop(&s));

}

return 0;

}

```

### Summary of Stack Operations

- Push: Adds an element to the top of the stack. Time complexity \(O(1)\).

- Pop: Removes and returns the top element of the stack. Time complexity \(O(1)\).

- Peek: Returns the top element without removing it. Time complexity \(O(1)\).

- isEmpty: Checks if the stack is empty. Time complexity \(O(1)\).

- isFull: Checks if the stack is full. Time complexity \(O(1)\).

These operations provide a robust mechanism for managing a stack, enabling efficient addition, removal, and inspection of elements while maintaining the LIFO principle.

### Common Conditions in Stack Operations

1. Overflow: Occurs when trying to push an element onto a full stack.

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

### Stack Implementation Algorithms

#### Stack Operations

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

```c

void push(int stack[], int *top, int element, int max_size) {

if (*top == max_size - 1) {

printf("Stack Overflow\n");

} else {

stack[++(*top)] = element;

}

}

```

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

```c

int pop(int stack[], int *top) {

if (*top == -1) {

printf("Stack Underflow\n");

return -1; // Indicating stack underflow

} else {

return stack[(*top)--];

}

}

```

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

```c

int peek(int stack[], int top) {

if (top == -1) {

printf("Stack is empty\n");

return -1; // Indicating stack is empty

} else {

return stack[top];

}

}

```

4. IsEmpty: Check if the stack is empty.

```c

int isEmpty(int top) {

return top == -1;

}

```

5. IsFull: Check if the stack is full.

```c

int isFull(int top, int max_size) {

return top == max_size - 1;

}

```

### Example Code for Stack Implementation in C

```c

#include <stdio.h>

#include <stdlib.h>

#define MAX 100

typedef struct {

int items[MAX];

int top;

} Stack;

// Initialize stack

void initStack(Stack *s) {

s->top = -1;

}

// Push operation

void push(Stack *s, int item) {

if (s->top == MAX - 1) {

printf("Stack Overflow\n");

return;

}

s->items[++(s->top)] = item;

}

// Pop operation

int pop(Stack *s) {

if (s->top == -1) {

printf("Stack Underflow\n");

return -1;

}

return s->items[(s->top)--];

}

// Peek operation

int peek(Stack *s) {

if (s->top == -1) {

printf("Stack is empty\n");

return -1;

}

return s->items[s->top];

}

// Check if stack is empty

int isEmpty(Stack *s) {

return s->top == -1;

}

// Check if stack is full

int isFull(Stack *s) {

return s->top == MAX - 1;

}

int main() {

Stack s;

initStack(&s);

push(&s, 10);

push(&s, 20);

push(&s, 30);

printf("Top element is %d\n", peek(&s));

while (!isEmpty(&s)) {

printf("Popped element is %d\n", pop(&s));

}

return 0;

}

```

This code provides a basic implementation of a stack in C, with functions for push, pop, peek, checking if the stack is empty, and checking if the stack is full. This stack can be used in various applications such as expression evaluation, function call management, syntax parsing, undo mechanisms, and graph algorithms like depth-first search.

### Usage of Stack in Recursion

#### How Stack is Used in Recursion

1. Function Call Management: Each recursive function call is pushed onto the call stack, maintaining the state of each function call including local variables and return address.

2. Return Address Storage: When a function calls itself, the return address (where the function should return after completing) is stored in the stack.

3. Local Variables: Each call's local variables are stored in a new stack frame, ensuring each call is independent of others.

4. Recursive Case Handling: The recursive case keeps making new calls, adding new stack frames.

5. Base Case Handling: When the base case is reached, the function starts returning, popping stack frames, and completing the function calls.

#### Example: Factorial Function in C

```c

#include <stdio.h>

int factorial(int n) {

if (n == 0) {

return 1; // Base case

} else {

return n * factorial(n - 1); // Recursive case

}

}

int main() {

int number = 5;

printf("Factorial of %d is %d\n", number, factorial(number));

return 0;

}

```

In this example:

- Base Case: When n is 0, the function returns 1.

- Recursive Case: The function calls itself with n-1, stacking each call until the base case is reached.

### Applications of Stack in Recursion

1. Tree Traversal:

- Pre-order, In-order, and Post-order Traversal: Each recursive call is managed via the stack, allowing traversal of each node.

2. Graph Algorithms:

- Depth-First Search (DFS): Uses recursion to explore all vertices and edges. The call stack keeps track of the visited nodes.

3. Backtracking Algorithms:

- Sudoku Solver, N-Queens Problem: Recursive backtracking uses the stack to manage state and backtrack when needed.

4. Dynamic Programming:

- Memoization Techniques: Recursive calls with memoization to solve problems like Fibonacci sequence efficiently.

5. Divide and Conquer Algorithms:

- Merge Sort, Quick Sort: Uses recursion to divide the problem into subproblems, sorting and merging them.

### Is Stack Better for Recursion?

#### Advantages

1. Simplified Code: Recursion often results in cleaner, more readable code for complex problems like tree and graph traversals.

2. Natural Fit: Many problems are naturally recursive, making recursion with stack management intuitive.

3. Implicit Stack Management: The call stack is managed by the system, reducing the need for manual stack handling.

#### Disadvantages

1. Overhead: Recursive calls can add overhead due to repeated function calls and stack frame creation.

2. Memory Usage: Deep recursion can lead to stack overflow if the recursion depth exceeds the call stack size.

3. Performance: Iterative solutions might be more efficient in terms of time and space for problems that can be solved both iteratively and recursively.

### Summary in Points

1. Function Call Management: Stack manages each recursive function call independently.

2. State Preservation: Each call’s state (local variables, return address) is preserved in the stack.

3. Base and Recursive Cases: Stack handles both base cases and recursive cases, ensuring proper execution order.

4. Tree and Graph Traversal: Recursive algorithms for traversing trees and graphs rely heavily on stack operations.

5. Backtracking: Algorithms like N-Queens and Sudoku solver use recursion and stack for managing choices and backtracking.

6. Divide and Conquer: Sorting algorithms like merge sort and quicksort use recursion to break down problems, managed by the stack.

7. Memory and Performance Considerations: While intuitive and cleaner, recursion can lead to higher memory usage and potential stack overflow.

Using a stack in recursion leverages the natural call stack of the system to manage the execution of recursive functions, making it a powerful tool for solving complex problems that can be broken down into smaller, repetitive tasks.

• Stack:

  1. Last In, First Out (LIFO)

  2. Operations: push, pop

  3. Access to only top element

  4. Limited access points

  5. Recursive function calls

  6. Memory-efficient

  7. Depth-first search

• Queue:

  1. First In, First Out (FIFO)

  2. Operations: enqueue, dequeue

  3. Access to both front and rear

  4. Multiple access points

  5. Breadth-first search

  6. Time-efficient

  7. Used in scheduling algorithms