Lesson 2	Design of the Stack
Objective	Examine the design of a dynamically sized stack.

Design of the Stack in C++

A dynamically sized stack can be effectively implemented using a doubly linked list in C++, wherein each node of the list would represent an element of the stack. Let's dive into the design and implementation:
Design and Implementation of a Dynamically Sized Stack:

Node Structure: To begin, let's define the structure of a node in our doubly linked list.

template<typename T>
struct Node {
    T data;
    Node<T>* prev;
    Node<T>* next;

    Node(T val) : data(val), prev(nullptr), next(nullptr) {}
};

Stack Class: We will now encapsulate the stack functionality within a class:

template<typename T>
class DynamicStack {
private:
    Node<T>* top; // points to the top element of the stack
    size_t size;  // stores the current size of the stack

public:
    DynamicStack() : top(nullptr), size(0) {}

    // Push operation
    void push(T val) {
        Node<T>* newNode = new Node<T>(val);
        if (top != nullptr) {
            newNode->prev = top;
            top->next = newNode;
        }
        top = newNode;
        size++;
    }

    // Pop operation
    T pop() {
        if (isEmpty()) {
            throw std::runtime_error("Stack is empty");
        }
        Node<T>* temp = top;
        T poppedValue = top->data;
        top = top->prev;
        if (top != nullptr) {
            top->next = nullptr;
        }
        delete temp;
        size--;
        return poppedValue;
    }

    // Peek at the top element without popping
    T peek() const {
        if (isEmpty()) {
            throw std::runtime_error("Stack is empty");
        }
        return top->data;
    }

    // Check if stack is empty
    bool isEmpty() const {
        return top == nullptr;
    }

    // Return size of the stack
    size_t getSize() const {
        return size;
    }

    // Destructor to free memory
    ~DynamicStack() {
        while (!isEmpty()) {
            pop();
        }
    }
};

Usage of the DynamicStack

To use the DynamicStack, simply instantiate it with the desired data type:

int main() {
    DynamicStack<int> stack;
    stack.push(10);
    stack.push(20);
    stack.push(30);

    std::cout << "Top element: " << stack.peek() << std::endl;
    std::cout << "Popped element: " << stack.pop() << std::endl;
    std::cout << "Current size: " << stack.getSize() << std::endl;

    return 0;
}

The presented DynamicStack class employs a doubly linked list to dynamically manage its size. By encapsulating the logic within class methods, we ensure the integrity and abstraction of our stack's operations. The stack's dynamic nature ensures adaptability to varying workload sizes without manual resizing, making it a potent tool for systems programming scenarios in C++ environments.

A constructor can also be used to allocate space from free store. To illustrate this, let us modify the ch_stack type we looked at in a previous module so that its maximum length is initialized by a constructor.

//ch_stack implementation with constructor.
class ch_stack {
public:
//the public interface for the ADT ch_stack
   explicit ch_stack(int size):
   max_len(size), top(EMPTY) {
      assert(size > 0);
      s = new char[size];
      assert(s);
   }
   void  reset() { top = EMPTY; }
   void  push(char c) {
      assert(top != FULL);
      top++;
      s[top] = c;
   }
   char  pop() {
      assert(top!= EMPTY);
      return s[top--];
   }
   char  top_of() {
      assert(top!= EMPTY);
      return s[top];
   }
   bool  empty() const
     { return (top == EMPTY); }
   bool  full() const
     { return (top == max_len - 1); }
private:
   enum  { EMPTY = -1 };
   char*  s;    //changed from s[max_len]
   int    max_len;
   int    top;
};

The design of the class ch_stack includes hidden implementation detail.
Data members are placed in the private access region of class ch_stack. Remember that generally data is part of an implementation choice. It should be accessed through public member functions.

Accessor and mutator functions in C++

Member functions that are public are called accessor functions when they do not change the object's data. Accessor functions should be declared const. In ch_stack, top_of() and empty() are accessor functions.
Some of these functions, such as push() and pop(), are called mutator functions because they do change data in the ch_stack object.
The constructor member functions have the job of creating and initializing ch_stack objects.