Please implement a stack using only a singly linked list L u

Please, implement a stack using only a singly linked list L (using c++). Please provide the pseudo-code for operations (Push and Pop and include error checking). Make sure that both operations run in O(1) time, and give a little explanation about the running time.

Solution

Here is the code for Stack using singly linked list:

#include <iostream>
#include <cstddef>
using namespace std;
using std::cout;
using std::endl;

/* definition of the list node class */
class node
{
friend class linked_list;
private:
int _value;
node *_next_node;
public:
node(void) : _next_node(NULL){ }
node(int val) : _value(val), _next_node(NULL){ }
node(int val, node* next) : _value(val), _next_node(next) { }

/* accessors */
int get_value() { return _value; }
node * getNext(){ return _next_node; }
};
/* definition of the linked list class */
class linked_list
{
  
private:
node *_head;
node *_tail;
public:
linked_list();
linked_list(int val);
void print();
void add(node * n);
int remove();
};
linked_list::linked_list()
{
_head = _tail = NULL;
}
linked_list::linked_list(int val)
{
_head = new node(val);
_tail = _head;
}
void linked_list::print()
{
node * n = _head;
// Check to see if empty
if (_head == NULL)
{
cout << \"The stack is empty\" << endl;
return;
}
cout << \"Elements in stack are: \";
while (n != NULL)
{
cout << n->_value;
n = n->_next_node;
cout << \" \";
}
cout << endl;
}

void linked_list::add(node * n)
{
//set new node to point to current head
n->_next_node = _head;
//make our new node the head
_head = n;
}
int linked_list::remove(){
int val;
node * p = NULL;
p = _head;
if(p == NULL)
return -1;
_head = p->_next_node;
val = p->_value;
delete p;
return val;
}
  

int main(int argc, const char * argv[])
{
int choice, ele;
node *n;
linked_list list;
while(1)
{
cout<<\"Stack Operations\"<<endl;
cout<<\"1. PUSH.\"<<endl;
cout<<\"2. POP.\"<<endl;
cout<<\"3. DISPLAY.\"<<endl;
cout<<\"4.EXIT.\"<<endl;
cout<<\"Enter your choice: \";
cin>>choice;
switch(choice)
{
case 1:
       cout<<\"Enter the element to PUSH: \";
       cin>>ele;
       n = new node(ele);
       list.add(n);
       break;
case 2:
       ele = list.remove();
       if(ele == -1)
       cout<<\"No element to POP.\"<<endl;
       else
       cout<<\"The popped element is: \"<<ele;
       break;
case 3:
       list.print();
       break;
case 4:
       exit(0);
default: cout<<\"Invalid MENU option. Please choose from the menu.\"<<endl;
}
}
}

And the pseudo code for Push and Pop operations is:

Push(element)

Insert element at the head of the list.

As you\'re accessing the head of the list, and no need to move further, the time required to push an element to the Stack is O(1).

Pop()

If list is empty,

return -1; //Which means Stack underflow.

Update head = head->next; //Bypasses the first node of the list.

Here again, as you\'re accessing the head of the list, the efficiency is O(1).