1. We sometimes see a stack implemented with a sentinel node which does not hold actual data but is used to locate the top of the stack Write the necessary methods to complete the program stacksentinel.cpp For marking purposes, push 1, 2, 3, and 4 onto the stack, write the stack to the file, pop twice and write to the file. // File: stacksentinal.cpp / This program implements a simple stack of integers using a linked list // with a sentinel #include #include using namespace std; class node friend class stack; // stack needs access to node's members private int data; / this is the data in a stack node node *next; // pointer to the next stack node public: node (int x); // data x, nextNULI class stack t private node sentinel; // sentinel for the stack public: stack (void); void push(int x); int pop (void); bool empty (void) const; void write (ostream &out) const; // constructor // check for empty stack // write the stack to out A stack looks like a chain of nodes l data I next top of l dataI l data I l next next l-.. next NULI bottom of stack sentinel stack sentinel is an obiect which acts as a marker for the top of the stack sentinel.next points to the top of the stack which will be NULL if the stack is empty. The value stored in sentinel.data is not part of the stack so we can put any value there The value at the top of the stack is sentinel.next->data. */