Lecture on Data Structures and C++: Implementing Stacks

Introduction

Topic: Building a Stack from scratch in C++ & using internal built-in stacks
Focus: Coding implementations of stacks
Pre-requisites: Knowledge of Linked Lists and other data structures like arrays
Relevance: Understanding problems and theoretical concepts behind stacks

Covered Data Structures So Far

Arrays
Linked Lists
Queue (Completed)

Today's Focus: Stacks

What is a Stack?: Linear data structure following Last In First Out (LIFO) principle
Operations on Stack:
- Push: Add an element to the top
- Pop: Remove the top element
- Top/Peek: Access the top element
- IsEmpty: Check if the stack is empty
- IsFull: Check if the stack is full
- Size: Get current size of the stack

Stack Operations Explained

Push: Adds an element at the top
Pop: Removes the top element
IsEmpty: Returns true if the stack is empty
IsFull: Returns true if the stack is full
Size: Returns current size of the stack
Top: Returns the top-most element without removing it

Key Topics for Implementation

Stack Implementation using Arrays
- Create a class for stack with capacity and array
- Use a top variable to keep track of the top element
- Conditions for Overflow & Underflow to manage exceptions
- Implement push and pop methods respecting capacity constraints
Stack Implementation using Linked Lists
- Node structure: Data + Pointer to next node
- Maintain head pointer to denote the stack's top
- Operations on the linked list to add and remove nodes at the head
- Manage memory to avoid dangling pointers

Overflow and Underflow Conditions

Overflow: Attempt to push when stack is full
Underflow: Attempt to pop when stack is empty

Example of Implementation (Array-Based Stack)

class Stack {
   int capacity;
   int* array;
   int top;
public:
   Stack(int cap) { 
      capacity = cap;
      array = new int[capacity];
      top = -1;
   }
   void push(int element) {
      if (top == capacity - 1) throw overflow_error("Stack Overflow");
      array[++top] = element;
   }
   int pop() {
      if (top == -1) throw underflow_error("Stack Underflow");
      return array[top--];
   }
   bool isEmpty() { return top == -1; }
   bool isFull() { return top == capacity - 1; }
   int size() { return top + 1; }
   int getTop() { 
      if (top == -1) throw underflow_error("Stack is Empty"); 
      return array[top]; 
   }
};

Implementation using Linked List

Node Structure struct Node { int data; Node* next; Node(int val) : data(val), next(nullptr) {} };
Push (Insert at Head) void push(int element) { Node* newNode = new Node(element); newNode->next = head; head = newNode; }
Pop (Remove from Head) int pop() { if (!head) throw underflow_error("Stack is Empty"); int topVal = head->data; Node* temp = head; head = head->next; delete temp; return topVal; }
Helper Methods:
- isEmpty(): Checks if head is nullptr
- size(): Traverse through nodes to count elements

Using C++ STL Stack

Methods: push, pop, top, empty, size

#include <stack>

std::stack<int> s;
s.push(10);
s.push(20);
int top = s.top(); // Access the top element
s.pop(); // Remove the top element

Practical Implementations and Examples

Problem 1: Copy Stack

Objective: Copy elements from one stack to another in the same order
Steps:
- Use an auxiliary stack to reverse the order twice
- Code Example
void copyStack(std::stack<int>& src, std::stack<int>& dest) { std::stack<int> temp; while (!src.empty()) { temp.push(src.top()); src.pop(); } while (!temp.empty()) { dest.push(temp.top()); temp.pop(); } }

Problem 2: Insert at Bottom

Objective: Insert an element at the bottom of the stack
Recursive Approach void insertAtBottom(std::stack<int>& s, int element) { if (s.empty()) { s.push(element); } else { int topElement = s.top(); s.pop(); insertAtBottom(s, element); s.push(topElement); } }

Problem 3: Reverse a Stack

Objective: Reverse the stack using recursion or another stack void reverseStack(std::stack<int>& s) { if (s.empty()) return; int topElement = s.top(); s.pop(); reverseStack(s); insertAtBottom(s, topElement); }

Conclusion

Stack is a fundamental data structure with various applications
Understanding both array and linked list implementations are crucial
Practicing problems using these implementations solidifies the concept
Next Steps: Explore advanced stack applications and related problems