Question: Implement the Stack ADT as a Singly Linked List of integers. You will implement the push(int), pop( ), peek( ) and isEmpty( ) functions of
Implement the Stack ADT as a Singly Linked List of integers. You will implement the push(int), pop( ), peek( ) and isEmpty( ) functions of the Stack. All the functions operate with the node at the beginning of the List. So, an element pushed to the Stack will be inserted as the first element in the List (i.e., as the next node of the head node). The peek operation will read the value of the first element in the List, whereas the pop operation will delete the first element from the List. The isEmpty function will check whether the next node of the head node is NULL or not. You will test your code with a main function that inputs 5 integers from the user (or generated randomly), pushes each of them to stack, reads/prints the top value of the Stack after pushing the 5 integers and finally pops all the elements of the Stack as well as prints the value of the integers popped. For reference, you are given the code for the implementation of Stack as a Doubly Linked List.
#include
#include
#include
using namespace std;
// implementing a doubly linked list
class Node{
private:
int data;
Node* nextNodePtr;
Node* prevNodePtr;
public:
Node(){}
void setData(int d){
data = d;
}
int getData(){
return data;
}
void setNextNodePtr(Node* nodePtr){
nextNodePtr = nodePtr;
}
Node* getNextNodePtr(){
return nextNodePtr;
}
void setPrevNodePtr(Node* nodePtr){
prevNodePtr = nodePtr;
}
Node* getPrevNodePtr(){
return prevNodePtr;
}
};
class Stack{
private:
Node* headPtr;
Node* tailPtr;
public:
Stack(){
headPtr = new Node();
tailPtr = new Node();
headPtr->setNextNodePtr(0);
tailPtr->setPrevNodePtr(0);
}
Node* getHeadPtr(){
return headPtr;
}
Node* getTailPtr(){
return tailPtr;
}
bool isEmpty(){
if (headPtr->getNextNodePtr() == 0)
return true;
return false;
}
void push(int data){
Node* newNodePtr = new Node();
newNodePtr->setData(data);
newNodePtr->setNextNodePtr(0);
Node* lastNodePtr = tailPtr->getPrevNodePtr();
if (lastNodePtr == 0){
headPtr->setNextNodePtr(newNodePtr);
newNodePtr->setPrevNodePtr(0);
}
else{
lastNodePtr->setNextNodePtr(newNodePtr);
newNodePtr->setPrevNodePtr(lastNodePtr);
}
tailPtr->setPrevNodePtr(newNodePtr);
}
int pop(){
Node* lastNodePtr = tailPtr->getPrevNodePtr();
Node* prevNodePtr = 0;
int poppedData = -100000; //empty stack
if (lastNodePtr != 0){
prevNodePtr = lastNodePtr->getPrevNodePtr();
poppedData = lastNodePtr->getData();
}
else
return poppedData;
if (prevNodePtr != 0){
prevNodePtr->setNextNodePtr(0);
tailPtr->setPrevNodePtr(prevNodePtr);
}
else{
headPtr->setNextNodePtr(0);
tailPtr->setPrevNodePtr(0);
}
return poppedData;
}
int peek(){
Node* lastNodePtr = tailPtr->getPrevNodePtr();
if (lastNodePtr != 0)
return lastNodePtr->getData();
else
return -100000; // empty stack
}
void IterativePrint(){
Node* currentNodePtr = headPtr->getNextNodePtr();
while (currentNodePtr != 0){
cout << currentNodePtr->getData() << " ";
currentNodePtr = currentNodePtr->getNextNodePtr();
}
cout << endl;
}
void ReversePrint(){
Node* currentNodePtr = tailPtr->getPrevNodePtr();
while (currentNodePtr != 0){
cout << currentNodePtr->getData() << " ";
currentNodePtr = currentNodePtr->getPrevNodePtr();
}
cout << endl;
}
};
int main(){
int stackSize;
cout << "Enter the number of elements you want to insert: ";
cin >> stackSize;
Stack stack; // Create an empty stack
srand(time(NULL));
int maxValue;
cout << "Enter the maximum value for an element: ";
cin >> maxValue;
cout << "Pushed: ";
for (int i = 0; i < stackSize; i++){
int value = rand() % maxValue;
stack.push(value);
cout << value << " ";
}
cout << endl;
cout << "top of the stack: " << stack.peek() << endl;
cout << "Popped: ";
while (!stack.isEmpty()){
cout << stack.pop() << " ";
}
cout << endl;
return 0;
}
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help