Question

Hello, I am currently taking software design and analysis class and have a question about those 3 in cpp, can you please help me? thank you

- What is the complexity of pop()? push()? top()? size()? isEmpty()?

- Write a C++ implementation of push() in a linked-chain implementation of stack

- Write a C++ implementation of pop() in a linked-chain implementation of stack

Answer 1

- What is the complexity of pop()? push()? top()? size()? isEmpty()?
Answer: All these functions are of O(1) i.e constant time

========================

- Write a C++ implementation of push() in a linked-chain implementation of stack
- Write a C++ implementation of pop() in a linked-chain implementation of stack

struct node
{
   int val;
   node *next;
};

class stack{
   private:
       node *top;
   public:
       stack(){
           top = nullptr;
       }
      
       void push(int x){
           node *n = new node;
           n->val = x;
           n->next = top;
           top = n;
       }
      
       bool pop(int &x){
           if(top != nullptr){
               x = top->val;
               node *n = top;
               top = top->next;
               delete n;
               return true;
           }
           else
               return false;
       }
};