Question

In: Computer Science

In C++ In this lab we will be creating a stack class and a queue class,...

In C++

In this lab we will be creating a stack class and a queue class, both with a hybrid method combining linked list and arrays in addition to the Stack methods(push, pop, peek, isEmpty, size, print) and Queue methods (enqueue, deque, peek, isEmpty, size, print).

DO NOT USE ANY LIBRARY, implement each method from scratch.

Both the Stack and Queue classes should be generic classes.

Don't forget to comment your code.

Solutions

Expert Solution

Stack using Link List

// C++ program to Implement a stack 
//using singly linked list 
#include <bits/stdc++.h> 
using namespace std; 

// Declare linked list node 

struct Node 
{ 
        int data; 
        struct Node* link; 
}; 

struct Node* top; 

// Utility function to add an element 
// data in the stack insert at the beginning 
void push(int data) 
{ 
        
        // Create new node temp and allocate memory 
        struct Node* temp; 
        temp = new Node(); 

        // Check if stack (heap) is full. 
        // Then inserting an element would 
        // lead to stack overflow 
        if (!temp) 
        { 
                cout << "\nHeap Overflow"; 
                exit(1); 
        } 

        // Initialize data into temp data field 
        temp->data = data; 

        // Put top pointer reference into temp link 
        temp->link = top; 

        // Make temp as top of Stack 
        top = temp; 
} 

// Utility function to check if 
// the stack is empty or not 
int isEmpty() 
{ 
        return top == NULL; 
} 

// Utility function to return top element in a stack 
int peek() 
{ 
        
        // Check for empty stack 
        if (!isEmpty()) 
                return top->data; 
        else
                exit(1); 
} 

// Utility function to pop top 
// element from the stack 
void pop() 
{ 
        struct Node* temp; 

        // Check for stack underflow 
        if (top == NULL) 
        { 
                cout << "\nStack Underflow" << endl; 
                exit(1); 
        } 
        else
        { 
                
                // Top assign into temp 
                temp = top; 

                // Assign second node to top 
                top = top->link; 

                // Destroy connection between 
                // first and second 
                temp->link = NULL; 

                // Release memory of top node 
                free(temp); 
        } 
} 

// Function to print all the 
// elements of the stack 
void display() 
{ 
        struct Node* temp; 

        // Check for stack underflow 
        if (top == NULL) 
        { 
                cout << "\nStack Underflow"; 
                exit(1); 
        } 
        else
        { 
                temp = top; 
                while (temp != NULL) 
                { 

                        // Print node data 
                        cout << temp->data << "-> "; 

                        // Assign temp link to temp 
                        temp = temp->link; 
                } 
        } 
} 

// Driver Code 
int main() 
{ 
        
        // Push the elements of stack 
        push(11); 
        push(22); 
        push(33); 
        push(44); 

        // Display stack elements 
        display(); 

        // Print top element of stack 
        cout << "\nTop element is "
                << peek() << endl; 

        // Delete top elements of stack 
        pop(); 
        pop(); 

        // Display stack elements 
        display(); 

        // Print top element of stack 
        cout << "\nTop element is "
                << peek() << endl; 
                
        return 0; 
} 

Stack using array

/* C++ program to implement basic stack 
operations */
#include <bits/stdc++.h> 

using namespace std; 

#define MAX 1000 

class Stack { 
        int top; 

public: 
        int a[MAX]; // Maximum size of Stack 

        Stack() { top = -1; } 
        bool push(int x); 
        int pop(); 
        int peek(); 
        bool isEmpty(); 
}; 

bool Stack::push(int x) 
{ 
        if (top >= (MAX - 1)) { 
                cout << "Stack Overflow"; 
                return false; 
        } 
        else { 
                a[++top] = x; 
                cout << x << " pushed into stack\n"; 
                return true; 
        } 
} 

int Stack::pop() 
{ 
        if (top < 0) { 
                cout << "Stack Underflow"; 
                return 0; 
        } 
        else { 
                int x = a[top--]; 
                return x; 
        } 
} 
int Stack::peek() 
{ 
        if (top < 0) { 
                cout << "Stack is Empty"; 
                return 0; 
        } 
        else { 
                int x = a[top]; 
                return x; 
        } 
} 

bool Stack::isEmpty() 
{ 
        return (top < 0); 
} 

// Driver program to test above functions 
int main() 
{ 
        class Stack s; 
        s.push(10); 
        s.push(20); 
        s.push(30); 
        cout << s.pop() << " Popped from stack\n"; 

        return 0; 
} 

Queue using link list

#include <bits/stdc++.h> 
using namespace std; 

struct QNode { 
        int data; 
        QNode* next; 
        QNode(int d) 
        { 
                data = d; 
                next = NULL; 
        } 
}; 

struct Queue { 
        QNode *front, *rear; 
        Queue() 
        { 
                front = rear = NULL; 
        } 

        void enQueue(int x) 
        { 

                // Create a new LL node 
                QNode* temp = new QNode(x); 

                // If queue is empty, then 
                // new node is front and rear both 
                if (rear == NULL) { 
                        front = rear = temp; 
                        return; 
                } 

                // Add the new node at 
                // the end of queue and change rear 
                rear->next = temp; 
                rear = temp; 
        } 

        // Function to remove 
        // a key from given queue q 
        void deQueue() 
        { 
                // If queue is empty, return NULL. 
                if (front == NULL) 
                        return; 

                // Store previous front and 
                // move front one node ahead 
                QNode* temp = front; 
                front = front->next; 

                // If front becomes NULL, then 
                // change rear also as NULL 
                if (front == NULL) 
                        rear = NULL; 

                delete (temp); 
        } 
}; 

// Driven Program 
int main() 
{ 

        Queue q; 
        q.enQueue(10); 
        q.enQueue(20); 
        q.deQueue(); 
        q.deQueue(); 
        q.enQueue(30); 
        q.enQueue(40); 
        q.enQueue(50); 
        q.deQueue(); 
        cout << "Queue Front : " << (q.front)->data << endl; 
        cout << "Queue Rear : " << (q.rear)->data; 
} 

Queue using Array

// C++ program to implement a queue using an array 
#include <bits/stdc++.h> 
using namespace std; 

struct Queue { 
        int front, rear, capacity; 
        int* queue; 
        Queue(int c) 
        { 
                front = rear = 0; 
                capacity = c; 
                queue = new int; 
        } 

        ~Queue() { delete[] queue; } 

        // function to insert an element 
        // at the rear of the queue 
        void queueEnqueue(int data) 
        { 
                // check queue is full or not 
                if (capacity == rear) { 
                        printf("\nQueue is full\n"); 
                        return; 
                } 

                // insert element at the rear 
                else { 
                        queue[rear] = data; 
                        rear++; 
                } 
                return; 
        } 

        // function to delete an element 
        // from the front of the queue 
        void queueDequeue() 
        { 
                // if queue is empty 
                if (front == rear) { 
                        printf("\nQueue is empty\n"); 
                        return; 
                } 

                // shift all the elements from index 2 till rear 
                // to the left by one 
                else { 
                        for (int i = 0; i < rear - 1; i++) { 
                                queue[i] = queue[i + 1]; 
                        } 

                        // decrement rear 
                        rear--; 
                } 
                return; 
        } 

        // print queue elements 
        void queueDisplay() 
        { 
                int i; 
                if (front == rear) { 
                        printf("\nQueue is Empty\n"); 
                        return; 
                } 

                // traverse front to rear and print elements 
                for (i = front; i < rear; i++) { 
                        printf(" %d <-- ", queue[i]); 
                } 
                return; 
        } 

        // print front of queue 
        void queueFront() 
        { 
                if (front == rear) { 
                        printf("\nQueue is Empty\n"); 
                        return; 
                } 
                printf("\nFront Element is: %d", queue[front]); 
                return; 
        } 
}; 

// Driver code 
int main(void) 
{ 
        // Create a queue of capacity 4 
        Queue q(4); 

        // print Queue elements 
        q.queueDisplay(); 

        // inserting elements in the queue 
        q.queueEnqueue(20); 
        q.queueEnqueue(30); 
        q.queueEnqueue(40); 
        q.queueEnqueue(50); 

        // print Queue elements 
        q.queueDisplay(); 

        // insert element in the queue 
        q.queueEnqueue(60); 

        // print Queue elements 
        q.queueDisplay(); 

        q.queueDequeue(); 
        q.queueDequeue(); 

        printf("\n\nafter two node deletion\n\n"); 

        // print Queue elements 
        q.queueDisplay(); 

        // print front of the queue 
        q.queueFront(); 

        return 0; 
} 

Related Solutions

In this lab, using C++, you will create two data structures: a stack and a queue....
In this lab, using C++, you will create two data structures: a stack and a queue. You will use STL containers to demonstrate basic ADTs. Queue For the queue, you will simulate a buffer. Remember it is first-in-first-out. The user will enter a number for the number of rounds to run your simulation. You need one function that randomly generates a number. You will also have a user specified percentage, and the function uses this percentage to randomly put the...
C++ Data Structures: Implement a Stack and a Queue using Linked list In this lab you...
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...
We started creating a Java class for Car. In this lab we are going to complete...
We started creating a Java class for Car. In this lab we are going to complete it in the following steps: 1- First create the Car class with some required instance variables, such make, model, year, price, speed, maxSpeed, isOn, isMoving, and any other properties you like to add. 2- Provide couple of constructors for initializing different set of important properties, such as make, model, year, and price. Make sure that you do not repeat initialization of instance variables in...
Q1 A- What are stack and queue? What are the differences between stack and queue? B-...
Q1 A- What are stack and queue? What are the differences between stack and queue? B- What is the priority queue? What are the differences between queue and priority queue
In C++ In this lab we will creating two linked list classes: one that is a...
In C++ In this lab we will creating two linked list classes: one that is a singly linked list, and another that is a doubly linked list ( This will be good practice for your next homework assignment where you will build your own string class using arrays and linked list ) . These LinkedList classes should both be generic classes. and should contain the following methods: Print Add - Adds element to the end of the linked list. IsEmpty...
Compare the list, stack and queue
Compare the list, stack and queue
In C++ please: In this lab we will creating two linked list classes: one that is...
In C++ please: In this lab we will creating two linked list classes: one that is a singly linked list, and another that is a doubly linked list ( This will be good practice for your next homework assignment where you will build your own string class using arrays and linked list ) . These LinkedList classes should both be generic classes. and should contain the following methods: Print Add - Adds element to the end of the linked list....
Implement the stack class (called Stack2) using queue, meaning that the only operations that can be...
Implement the stack class (called Stack2) using queue, meaning that the only operations that can be used are the ones defined in the Queue class. class Queue: def __init__(self): self.items = [] def isEmpty(self): return self.items == [] def enqueue(self, item): self.items.insert(0, item) def dequeue(self): return self.items.pop() def size(self): return len(self.items) The codes to fill: """ 1. Stack2 class Implement stack data structure using queue """ class Stack2: def __init__(self): # Write your definition for __init__ here def isEmpty(self): #...
In C++: In this lab we will creating twos arrays of Generic objects, searching through those...
In C++: In this lab we will creating twos arrays of Generic objects, searching through those arrays using BINARY and SEQUENTIAL sorts, calculate the run-time of each method, and determine the BIG O, OMEGA and THETA notation. In our object we should have some way to compare elements to determine if one element is LESS THAN, GREATER THAN, and EQUAL TO. After this Generic Class is defined with a method that allows for comparison is completed, then you will create...
Lab 1 – Databases, Schemas, and Basic Tables For this lab we will be creating a...
Lab 1 – Databases, Schemas, and Basic Tables For this lab we will be creating a small Student Loan Database. Make sure to open your screenshot word document. Include the required screenshots of your code in the document. Database: Create a new database: StudentLoan_LastName. Schemas: Create the following schemas. Make sure to screenshot and run your code: 1. Student 2. Guarantor 3. Institution 4. Activity 5. Loan 6. Lender Tables: First complete the word document for designing the tables like...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT