Question

Goals This assignment is an individual assignment and you will work on it on your own....

Goals

This assignment is an individual assignment and you will work on it on your own. The goal of this assignment is to be able to use stacks and queues, and to master and have an in-depth understanding of such primitive ADTs. In this assignment you will build a more complex ADT using the primitive stack and queue ADTs. Moreover, an important goal of this assignment is to be able to analyze an ADT that you will build yourself using more primitive ADTs, and to be able to compute the time and space complexity using the Big-O notation. Based on that you are asked also to enhance your first implementation to achieve better performance.

Details

In this assignment you are required to build a Queue ADT using a Stack ADT. You are required to use the linked list stack implementation we presented in class and included in the lecture slides. You are required to use exactly two stack instances in your Queue ADT implementation.

In this assignment you are required to perform two attempts. In the first attempt, you are required to use the linked list stack implementation as is, and you are not allowed to change it, which will not result in a very optimum implementation; basically you are not allowed to use except the push and pop methods. Nevertheless, your implementation of the new Queue ADT should be as optimum and efficient as possible within these boundaries; using the linked list stack implementation as is.

In the second attempt, you will be allowed to introduce changes to the stack implementation to provide better performance and hence better running time. It is mandatory to utilize all object oriented techniques, such as inheritance, to minimized the amount of amendments as much as possible, and to provide copy and move constructors if needed to reduce memory operations overhead.

The new ADT Queue implementations in both attempts should account for any size and any data item type, thus you are required to utilize templates. Moreover, you are required to implement all data validations needed and handle/report errors whenever needed.

Finally, You are required to analyze the new Queue ADT, in both attempts, using the Big-O notation for the new Queue ADT operations, precisely the enqueue and

dequeue. Moreover, you need to show that your second attempt results in a better running time than the first one.

0 0
Add a comment Improve this question Transcribed image text
Answer #1

This code will explain how queues is implemented with two stack

Attempt one:

  struct Queue {

    stack<int> s;

void enQueue(int x)

    {

        s.push(x);

    }

    int deQueue()

    {

        if (s.empty()) {

            cout << "Q is empty";

            exit(0);

        }

    int x = s.top();

s.pop();

   if (s.empty())

            return x;   

        int item = deQueue();

  s.push(x);

   return item; } };

  int main()

{

    Queue q;

    q.enQueue(1);

    q.enQueue(2);

    q.enQueue(3);

    cout << q.deQueue() << '\n';

    cout << q.deQueue() << '\n';

    cout << q.deQueue() << '\n';

  

    return 0;

}

The worst case running time to implement above code is 0(N ) Because you need to transfer each element from stack 1 to stack 2.

Attempt 2: using oops concept
class Stack
{
    int top;
    public:
    int a[10]; 
    Stack()
    {
        top = -1;
    }
    
       void push(int x);
    int pop();
    bool isEmpty();
};


void Stack::push(int x)
{
    if(top >= 10)
    {
        cout << "Stack Overflow \n";
    }
    else
    {
        a[++top] = x;
        cout << "Element Inserted into Stack\n";
    }
}


int Stack::pop()
{
    if(top < 0)
    {
        cout << "Stack Underflow \n";
        return 0;
    }
    else
    {
        int d = a[top--];
        return d;
    }
}


bool Stack::isEmpty()
{
    if(top < 0)
    {
        return true;
    }
    else
    {
        return false;
    }
}


class Queue {
    public:
    Stack S1, S2;
    
   
    void enqueue(int x);
    
 int dequeue();
};


void Queue :: enqueue(int x) 
{
    S1.push(x);
    cout << "Element Inserted into Queue\n";
}


int Queue :: dequeue() 
{
    int x, y;
    while(!S1.isEmpty()) 
    {
                x = S1.pop();
       
        S2.push(x);
    }
  
   
    y = S2.pop();
  
  
    while(!S2.isEmpty()) 
    {
        x = S2.pop();
        S1.push(x);
    }
  
    return y;
}


int main()
{
    Queue q;
    q.enqueue(10);
    q.enqueue(100);
    q.enqueue(1000);
    cout << "Removing element from queue" << q.dequeue();
    
    return 0;
}
Add a comment
Know the answer?
Add Answer to:
Goals This assignment is an individual assignment and you will work on it on your own....
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for? Ask your own homework help question. Our experts will answer your question WITHIN MINUTES for Free.
Similar Homework Help Questions
  • Short answer in your own word: 1. Describe the role of a “Back-End” computer engineer in...

    Short answer in your own word: 1. Describe the role of a “Back-End” computer engineer in creating software. Give examples of decisions back end engineers make. Use the relationship between long-term and short-term memory as context for decision examples. 2. Identify Stack or Heap storage in RAM. a) Hash Map with static array as underlying storage b) Doubly Linked LIst - Stack Implementation c) Binary Search Tree with 10,000 Nodes d) Static Array - Stack Implementation c) Doubly Linked List...

  • Create a Java code that includes all the methods from the Lecture slides following the ADTs...

    Create a Java code that includes all the methods from the Lecture slides following the ADTs LECTURE SLIDES Collect/finish the Java code (interface and the complete working classes) from lecture slides for the following ADTS: 4) Queue ADT that uses a linked list internally (call it LQueue) Make sure you keep the same method names as in the slides (automatic testing will be performed)! For each method you develop, add comments and estimate the big-O running time of its algorithm....

  • It is C++ problems, please explain your each line of code as well. Task 1: Implement/...

    It is C++ problems, please explain your each line of code as well. Task 1: Implement/ Hard Code a Doubly Linked Lists and make it a Stack. Do not use ::list:: class from the STD library for this example. The user will input a string and the program will output the string backwards. Displaying correct Stack implementation. Utilize the conventional static methods as needed. push() pop() empty() peek() peek() Sample Execution Please input String: happy yppah Task 2: Implement /...

  • In this assignment you will be implementing two Abstract Data Types (ADT) the Queue ADT and...

    In this assignment you will be implementing two Abstract Data Types (ADT) the Queue ADT and the Stack ADT. In addition, you will be using two different implementations for each ADT: Array Based Linked You will also be writing a driver to test your Queue and Stack implementations and you will be measuring the run times and memory use of each test case. You will also be adding some functionality to the TestTimes class that you created for Homework 1....

  • » Part A: Stack Create a Stack struct that is a wrapper for your linked list o You should impleme...

    Using C Please comment » Part A: Stack Create a Stack struct that is a wrapper for your linked list o You should implement the following functions that take a stack o void push(Stack * stack, int value) ● int pop(Stack * stack) Prompt the user to input 5 integers, and use the stack to reverse the integers Print the result to the screen. o o » Part B: Queue o Create a Queue struct that is a wrapper for...

  • Overview For this assignment, we will practice using stacks and queues. In this exercise, you will...

    Overview For this assignment, we will practice using stacks and queues. In this exercise, you will create two stacks and a queue to keep track of cars using a parking lot. We will use the nature of the stacks and queues to solve the problem. Specifications Rules FIU has opened a new valet parking lot next to the PC building that requires a special decal to park. If the car does not have the correct parking decal, the driver should...

  • Overview For this assignment, we will practice using stacks and queues. In this exercise, you will...

    Overview For this assignment, we will practice using stacks and queues. In this exercise, you will create two stacks and a queue to keep track of cars using a parking lot. We will use the nature of the stacks and queues to solve the problem. Specifications Rules FIU has opened a new valet parking lot next to the PC building that requires a special decal to park. If the car does not have the correct parking decal, the driver should...

  • Please Write Pseudocode or Python code! Thanks! P1. b) is the following: W1. (6 marks) Write...

    Please Write Pseudocode or Python code! Thanks! P1. b) is the following: W1. (6 marks) Write the pseudocode for removing and returning only the second element from the Stack. The top element of the Stack will remain the top element after this operation. You may assume that the Stack contains at least two items before this operation. (a) Write the algorithm as a provider implementing a Stack using a contiguous memory implementation. You can refer to the implementation given in...

  • Exereise 1: 7 рoints Write a program in C/C++ to enter a string of characters i.e....

    Exereise 1: 7 рoints Write a program in C/C++ to enter a string of characters i.e. your name, then try to compute this string in reverse order using a Stack structure with the Linked List principle. For example: "Nguyen Van A""A Nav Neyugn Exercise 2: 8 points Assume that a queue of N passengers waiting to enter a train car Only the first person in the queue can enter at a time New persons arrive will go to the end...

  • HI USING C++ CAN YOU PLEASE PROGRAM THIS ASSIGNMENT AND ADD COMMENTS: stackARRAY: #include<iostream> #define SIZE...

    HI USING C++ CAN YOU PLEASE PROGRAM THIS ASSIGNMENT AND ADD COMMENTS: stackARRAY: #include<iostream> #define SIZE 100 #define NO_ELEMENT -999999 using namespace std; class Stack { int arr[SIZE]; // array to store Stack elements int top; public: Stack() { top = -1; } void push(int); // push an element into Stack int pop(); // pop the top element from Stack int topElement(); // get the top element void display(); // display Stack elements from top to bottom }; void Stack...

ADVERTISEMENT
Free Homework Help App
Download From Google Play
Scan Your Homework
to Get Instant Free Answers
Need Online Homework Help?
Ask a Question
Get Answers For Free
Most questions answered within 3 hours.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT