Answer to Question #329904 in C++ for Umer Mushtaq

Question

Note: Use Linked List to implement stack.

A stack is an object that allows the following operations:

 Push: Add an element to the top of a stack

 Pop: Remove an element from the top of a stack

 IsEmpty: Check if the stack is empty

 Peek: Get the value of the top element without removing it

Create a class to define above mention operations of stack along with some addition functionality:

i. Copy a stack to another one.

ii. Delete an element at a specified location.

iii. Returns the count of elements in a stack.

iv. Insert an element at a specified location.

Write a main function to test the functionality of above class.

Remember: To access any element that is not at top, you have to first pop all other elements on the top of that.

Note: Use Linked List to implement stack.

Answer 1

#include <iostream>


template<class T>
class Stack {
  private:
    // Linked list
    struct Node {
      T data;
      Node* prev;
      Node* next;
    } * top;
    void clear() {
      while (top != nullptr) {
        Node* temp = top;
        top = top->prev;
        delete temp;
      }
    }
    void copy(const Stack& stack) {
      Node* ptr = stack.top;
      Node* node;
      if (ptr != nullptr) {
        node = top = new Node{ptr->data, nullptr, nullptr};
      }
      ptr = ptr->prev;
      while (ptr != nullptr) {
        Node* temp = node;
        node = new Node{ptr->data, nullptr, node};
        temp->prev = node;
        ptr = ptr->prev;
      }
    }
  public:
    Stack() : top(nullptr) {}
    Stack(const Stack& stack) {
      copy(stack);
    }
    Stack(Stack&& stack) : top(stack.top) {
      stack.top = nullptr;
    }
    Stack& operator =(const Stack& stack) {
      // Self-assigning check
      if (&stack == this) {
        return *this;
      }
      clear();
      copy(stack);
      return *this;
    }
    Stack& operator =(Stack&& stack) {
      if (&stack == this) {
        return *this;
      }
      clear();
      top = stack.top;
      stack.top = nullptr;
      return *this;
    }
    void push(T item) {
      top = new Node{item, top, nullptr};
    }
    T pop() {
      Node* temp = top;
      top = top->prev;
      T value = temp->data;
      delete temp;
      return value;
    }
    T peek() {
      return top->data;
    }
    // Returns false if index is out of the stack range
    bool remove(int index) {
      if (index < 0 || top == nullptr) return false;
      Node* ptr = top;
      int pos = 0;
      while (pos != index) {
        if (ptr->prev == nullptr) return false;
        ptr = ptr->prev;
        ++pos;
      }
      if (ptr->prev != nullptr) {
        ptr->prev->next = ptr->next;
      }
      if (ptr->next != nullptr) {
        ptr->next->prev = ptr->prev;
      }
      return true;
    }
    // Returns false if index is out of the stack range
    bool insert(int index, T data) {
      if (index < 0) return false;
      if (top == nullptr) {
        top = new Node{data, nullptr, nullptr};
        return true;
      }
      Node* ptr = top;
      int pos = 0;
      while (pos != index) {
        if (ptr->prev == nullptr) {
          return false;
        }
        ptr = ptr->prev;
        ++pos;
      }
      Node* newNode = new Node{data, ptr, ptr->next};
      if (ptr->next != nullptr) {
        ptr->next->prev = newNode;
      }
      return true;
    }
    bool isEmpty() {
      return top == nullptr;
    }
    // Returns the count of elements in a stack
    int size() {
      int s = 0;
      Node* ptr = top;
      // Go down while there are nodes
      while (ptr != nullptr) {
        ++s;
        ptr = ptr->prev;
      }
      return s;
    }
    friend std::ostream& operator <<(std::ostream& os, Stack s) {
      Node* ptr = s.top;
      std::cout << ptr->data;
      ptr = ptr->prev;
      while (ptr != nullptr) {
        std::cout << ' ' << ptr->data;
        ptr = ptr->prev;
      }
      return os;
    }
    ~Stack() {
      clear();
    }
};


int main() {
  Stack<int> s;
  s.push(1);
  s.push(2);
  std::cout << "Stack: " << s << '\n';
  std::cout << "Top element: " << s.peek() << '\n';
  s.push(3);
  std::cout << "Top element after pushing 3: " << s.pop() << '\n';
  std::cout << "Top element after removing: " << s.peek() << '\n';
  Stack<int> s1 = s;
  std::cout << "Stack copy: " << s1 << '\n';
  s1.insert(1, 12);
  std::cout << "After inserting second element: " << s1 << '\n';
  s1.remove(1);
  std::cout << "After removing second element: " << s1 << '\n';
  return 0;
}