Question

Implement the stack ADT in a fully generic manner (through the use of templates) by means of a singly linked list. (Give your implementation “from scratch,” without the use of any classes from the Standard Template Library ).

Answer 1

Answer:-

template <class T>

class Stack {

private:

struct Node {

T data;

Node* next;

};

Node* top;

public:

Stack() : top(nullptr){}

Stack(Stack const& value);

Stack<T>(Stack<T>&& move) noexcept;

Stack<T>& operator=(Stack&& move) noexcept;

~Stack();

Stack& operator=(Stack const& rhs);

friend std::ostream& operator<<(std::ostream& str, Stack<T> const& data) {

data.show(str);

return str;

}

bool isEmpty();

int getSize();

void push(const T& theData);

void pop();

void show(std::ostream &str) const;

};

template <class T>

Stack<T>::Stack(Stack const& value) : top(nullptr) {

for(Node* loop = value->data; loop != nullptr; loop = loop->next) {

push(loop->data);

}

}

template <class T>

Stack<T>::Stack(Stack<T>&& move) noexcept : top(nullptr) {

move.swap(*this);

}

template <class T>

Stack<T>& Stack<T>::operator=(Stack<T> &&move) noexcept {

move.swap(*this);

return *this;

}

template <class T>

Stack<T>::~Stack() {

while(top != nullptr) {

pop();

}

}

template <class T>

Stack<T>& Stack<T>::operator=(Stack const& rhs) {

Stack copy(rhs);

swap(copy);

return *this;

}

template <class T>

bool Stack<T>::isEmpty() {

if(top == nullptr) {

return true;

}

else {

return false;

}

}

template <class T>

int Stack<T>::getSize() {

int size = 0;

Node* current = top;

while(current != nullptr) {

size++;

current = current->next;

}

return size;

}

template <class T>

void Stack<T>::push(const T &theData) {

Node* newNode = new Node;

newNode->data = theData;

newNode->next = nullptr;

if(top != nullptr) {

newNode->next = top;

}

top = newNode;

}

template <class T>

void Stack<T>::pop() {

Node* temp;

if(top == nullptr) {

throw std::invalid_argument("Trying to pop from empty list....");

}

temp = top;

top = top->next;

delete temp;

}

template <class T>

void Stack<T>::show(std::ostream &str) const {

for(Node* loop = top; loop != nullptr; loop = loop->next) {

str << loop->data << "\t";

}

str << "\n";