Question

C++ Data Structures: Implement a Stack and a Queue using Linked list

In this lab you will implement the functionality of a stack and a queue using a linked list. Your program must use of the declaration of the Stack and Queue class in Stack.h and Queue.h

You have to implement the functionalities of queue (enq, deq, displayQueue) in a file called Queue.cpp. All the functions in Queue.cpp should follow the prototypes declared in Queue.h.

Your code should make use of external pointers ‘front’ and ‘rear’ properly. Remember

queue: rear increments on enq and front increments on deq.

Both enq and deq should be O(1). That is they should not have any loop.

----------------------------- Queue.h ------------------------------------

#pragma once
#include
using namespace std;

class Queue {
   struct Node {
       int x;
       Node *next = NULL;
   };
public:
   // Functions for Stack
   Queue(); //You need to implement the constructor
   void enq(int item);
   void deq();
   void displayQueue();

   // private member
private:
   Node *front; // this is the private member variable. It is just a pointer to the first Node
   Node *rear; // this is the private member variable. It is just a pointer to the first Node
};

---------------------Stack.h----------------------------------------------------

#pragma once
#include
using namespace std;

class Stack {
   struct Node {
       int x;
       Node *next = NULL;
   };
public:
   // Functions for Stack
   Stack();
   void push(int item);
   void pop();
   void displayStack();

   // private member
private:
   Node *top; // this is the private member variable. It is just a pointer to the first Node
};

----------------------------------Stack.cpp------------------------------------

#include "Stack.h"

// constructor
Stack::Stack() {
   top = NULL;
}

void Stack::push(int val)
{
   // Grow the list in a reverse direction.

   Node *n = new Node(); // create a new node
   n->x = val; // set the value to the value field of the new node
   n->next = top; // make the new node to point to the current top element
   top = n; // finally, move the top pointer so point the new node
}

void Stack::pop()
{
   struct Node* ptr = top; // temporary pointer pointing to the current top.
// Required because you have to delete the node
   top = top->next; // Move the top to point to the next node
   delete(ptr); // delete the previous top
}

void Stack::displayStack()
{
   struct Node* ptr = top; // Initialization: temporary pointer pointing at top
   while (ptr != NULL) { //Condition: Loop untill NULL (i.e. traverse the entire list)
       cout << ptr->x << " "; //Body: Print the loop
       ptr = ptr->next; //Increment: move the temporary pointer to the next node
   }
   cout << endl;
}

Answer 1

Code

Queue,cpp

#include"Queue.h"

Queue::Queue()

{

front=NULL;

rear=NULL;

}

void Queue::enq(int item)

{

Node *newNode=new Node();

newNode->x=item;

newNode->next=NULL;

if(front==NULL)

{

front = rear = newNode;

return;

}

rear->next = newNode;

rear = newNode;

}

void Queue:: deq()

{

// If queue is empty, return NULL.

if (front == NULL)

return;

Node* temp = front;

delete(temp);

front = front->next;

// If front becomes NULL, then

// change rear also as NULL

if (front == NULL)

rear = NULL;

}

void Queue::displayQueue()

{

struct Node* ptr = front; // Initialization: temporary pointer pointing at top

while (ptr != NULL) { //Condition: Loop untill NULL (i.e. traverse the entire list)

cout << ptr->x << " "; //Body: Print the loop

ptr = ptr->next; //Increment: move the temporary pointer to the next node

}

}

Main.cpp for test Queue.cpp

#include <iostream>

#include "Queue.h"

using namespace std;

int main()

{

Queue que;

que.enq(10);

que.enq(20);

que.enq(30);

que.enq(40);

cout<<"Main queue \n";

que.displayQueue();

que.deq();

que.deq();

cout<<"\n\nAfter performing 2 deq operation queue is : \n";

que.displayQueue();

}

output

If you have any query regarding the code please ask me in the comment i am here for help you. Please do not direct thumbs down just ask if you have any query. And if you like my work then please appreciates with up vote. Thank You.