Dynamic Stack  «Prev  Next»
 Lesson 2 Design of the Stack Objective Examine the design of a dynamically sized stack.

# Design of the Stack in C++

I am working as a systems programmer for a Fortune 500 company using the C++ programming language. Write for me a dynamically sized 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:

1. 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) {}
};
```
2. 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");
}
}

// Check if stack is empty
bool isEmpty() const {
}

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

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

## Usage:

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.