1) Define a class called Stack that implements a stack using a linked list. *Eac
ID: 3554617 • Letter: 1
Question
1) Define a class called Stack that implements a stack using a linked list.
*Each node should be a struct containing int data and a pointer to the next node.
*The top of the stack should be the first node.
*There should be a constructor and 3 public functions.
* The constructor creates a linked list in which the pointer head is NULL.
void Push(int).
int Pop( ).
int IsEmpty( ), which returns a one if the stack is empty and zero otherwise.
a) Push(int n) should create a new node that will be the new top of the stack, and it should point to the old top node. The head pointer must be made to point to the new top node.
b) int Pop( ) should delete the top node and make the head pointer point to its successor node. If there is no successor node, then set head = NULL.
c) IsEmpty just keeps track of whether the stack is empty or not. An empty stack will be an empty linked list, and a nonempty stack will be a nonempty linked list.
2) Define a class called Queue that implements a queue using a (singly) linked list.
*Two nodes will be special
a) the front node at the beginning of the linked list, similar to the top of a stack
b) the tail node at the end of the linked list.
*It should be possible to find the tail node without traversing the list.
*For this reason, a pointer to the tail node should be stored in the dummy head node. That pointer will be updated whenever the function enqueue(int) appends a new tail node to the linked list.
Public functions(not questions)
1) enqueue(int n) will append a tail node containing integer data n. It will also update the pointer to the tail that is stored in the dummy node head.
2) int dequeue( ) will remove the front node and return its int data.
3) IsEmpty will keep track of whether the queue is empty.
Explanation / Answer
part A
void stack::push()
{
int value;
struct node *ptr;
cout<<"Enter a number to insert: ";
cin>>value;
ptr=new node;
ptr->data=value;
ptr->next=NULL;
if(top!=NULL)
ptr->next=top;
top=ptr;
}
part B
void stack::pop()
{
struct node *temp;
if(top==NULL)
{
cout<<" The stack is empty"<<endl;
return;
}
temp=top;
top=top->next;
cout<<" Poped value is "<<temp->data<<endl;
delete temp;
}
part C
void stack::show()
{
struct node *ptr1=top;
cout<<" The stack is ";
while(ptr1!=NULL)
{
cout<<ptr1->data<<" ->";
ptr1=ptr1->next;
}
cout<<"NULL ";
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.