Lesson 7

Constructing a dynamically sized stack Conclusion

In this module, you explored how to use classes to construct a dynamically sized stack. By closely examining this implementation of a useful data structure, you learned:

How a constructor member function can be overloaded to allow different initializations
How to use a copy constructor
How a destructor member function works

A stack lets you insert and remove elements at one end only, traditionally called the top of the stack. To visualize a stack, think of a stack of books.
New items can be added to the top of the stack. Items are removed from the top of the stack as well. Therefore, they are removed in the order that is opposite from the order in which they have been added, also called last in, first out or LIFO order. For example, if you insert strings "Tom", "Dick", and "Harry" into a stack, and then remove them, then you will first see "Harry", then "Dick", and finally "Tom". To obtain a stack in the standard C++ library, you use the stack template:

stack <string> s;
s.push("Tom");
s.push("Dick");
s.push("Harry");
while (s.size() > 0){
  cout << s.top() << "\n";
  s.pop();
}

Creating a Dynamically sized stack in C++ using Dynamic Memory Allocation

Creating a dynamically sized stack in C++ can be achieved by using dynamic memory allocation and a vector or a custom class.
Here's how you can do it:
Using `std::vector`
The `std::vector` class from the C++ Standard Library inherently provides a dynamically sized array, which can be used as a stack with some additional methods. Here's how you might implement it:

Include Necessary Headers:
```
#include <vector>
#include <iostream>
```

Define Your Stack Class:

template <typename T>
class DynamicStack {
private:
std::vector<T> elements;

public:
// Push an element onto the stack
void push(const T& value) {
   elements.push_back(value);
}

// Pop the top element from the stack
void pop() {
   if (!empty()) {
	   elements.pop_back();
   }
}

// Return the top element without removing it
T& top() {
   return elements.back();
}

// Check if the stack is empty
bool empty() const {
   return elements.empty();
}

// Get the size of the stack
size_t size() const {
   return elements.size();
}
};

Using the Stack:

int main() {
   DynamicStack<int> stack;

   stack.push(10);
   stack.push(20);
   stack.push(30);

   std::cout << "Top element: " << stack.top() << std::endl;
   std::cout << "Stack size: " << stack.size() << std::endl;

   stack.pop();
   std::cout << "After pop, top element: " << stack.top() << std::endl;

   return 0;
}

Using Custom Memory Management
If you want to manage memory manually, you could use 1) pointers and 2) dynamic memory allocation:

Include Necessary Headers:

#include <iostream>
#include <stdexcept>

Define Your Stack Class:

template <typename T>
class DynamicStack {
private:
   T* arr;
   int capacity;
   int topIndex;

   // Helper function to resize the array
   void resize(int newCapacity) {
	   T* newArr = new T[newCapacity];
	   for (int i = 0; i <= topIndex; ++i) {
		   newArr[i] = arr[i];
	   }
	   delete[] arr;
	   arr = newArr;
	   capacity = newCapacity;
   }

public:
   // Constructor
   DynamicStack(int size = 1) : capacity(size), topIndex(-1) {
	   arr = new T[capacity];
   }

   // Destructor
   ~DynamicStack() {
	   delete[] arr;
   }

   // Push an element onto the stack
   void push(const T& value) {
	   if (topIndex + 1 == capacity) {
		   resize(capacity * 2);
	   }
	   arr[++topIndex] = value;
   }

   // Pop the top element from the stack
   void pop() {
	   if (empty()) {
		   throw std::out_of_range("Stack underflow");
	   }
	   --topIndex;
   }

   // Return the top element without removing it
   T& top() {
	   if (empty()) {
		   throw std::out_of_range("Stack is empty");
	   }
	   return arr[topIndex];
   }

   // Check if the stack is empty
   bool empty() const {
	   return topIndex == -1;
   }

   // Get the size of the stack
   size_t size() const {
	   return topIndex + 1;
   }
};

Using the Stack:

int main() {
   DynamicStack stack;

   stack.push(10);
   stack.push(20);
   stack.push(30);

   std::cout << "Top element: " << stack.top() << std::endl;
   std::cout << "Stack size: " << stack.size() << std::endl;

   stack.pop();
   std::cout << "After pop, top element: " << stack.top() << std::endl;

   return 0;
}

Key Points:

Using `std::vector`: This is the recommended approach as it handles memory management for you, reducing the risk of memory leaks and making your code more efficient and safer.
Manual Memory Management: This approach gives you more control but requires careful handling of memory to avoid leaks or corruption.

Both methods provide a dynamically sized stack, but `std::vector` is generally preferred for its ease of use and safety features in modern C++.