Question & Answer: Using a Stack based on a singly linked list, write the PUSH and POP functions that takes O(1) time……

Using a Stack based on a singly linked list, write the PUSH and POP functions that takes O(1) time.

Expert Answer

 

#include<iostream>

using namespace std;

struct node{

int data;
struct node *next;
};

class Stack {
private:
node *start;
public:
Stack(){
start = NULL;
}
void PUSH(int a) {    // Assuming a linked list of integers and “start” is pointing at the top
// of the stack.It is of O(1)

node *ptr,*temp;
ptr = start;

temp = new node;
temp->data = a;
start = temp;
start->next = ptr;

}

node *POP() {    // Assuming a linked list of integers and “start” is pointing at top
// of the stack.It is of O(1)

node *ptr,*temp;
ptr = start;
start = start->next;
return ptr;

}
void printStack(){
node *ptr;
ptr = start;
while (ptr != NULL){
cout << ptr->data << ” “;
ptr = ptr->next;
}
}

};

int main(){

node *ptr;
Stack st;
st.PUSH(12);
st.PUSH(13);
st.PUSH(14);

st.printStack();
cout << endl;
ptr = st.POP();
cout << ptr->data << endl;
return 0;
}

Still stressed from student homework?
Get quality assistance from academic writers!