The purpose of this lab is to practice writing Linked List implementations and i

Question

The purpose of this lab is to practice writing Linked List implementations and implementing the Queue ADT with a different underlying data structure.

Complete the implementations of the Queue_Fast_Front and Queue_Fast_Back ADTs to have O(1) dequeue and enqueue respectively. Compare the times.(for this question, your answer maybe not exactly the same as the output file.)

Implement a variation of Hot Potato, where at the end of each passing cycle, the direction of play is reversed. In addition to the queue from the original game, you will need to use a stack.

Add a count(item) function to the SimpleLinkedList ADT which returns the number of times the given item is found in the linked list.

code with python3

input example:dog cat fish cat horse snake cat dog tarrasque
cat dog snake tarrasque
output1:

What should the size of the queue be? 1000
For Queue_Fast_Front with 1000 elements, the estimated running time for enqueue was 2 s.
For Queue_Fast_Back with 1000 elements, the estimated running time for enqueue was 1 s.
For Queue_Fast_Front with 1000 elements, the estimated running time for dequeue was 1 s.
For Queue_Fast_Back with 1000 elements, the estimated running time for dequeue was 2 s.

What should the size of the queue be? 10000
For Queue_Fast_Front with 10000 elements, the estimated running time for enqueue was 10 s.
For Queue_Fast_Back with 10000 elements, the estimated running time for enqueue was 1 s.
For Queue_Fast_Front with 10000 elements, the estimated running time for dequeue was 1 s.
For Queue_Fast_Back with 10000 elements, the estimated running time for dequeue was 15 s.

What should the size of the queue be? 20000
For Queue_Fast_Front with 20000 elements, the estimated running time for enqueue was 21 s.
For Queue_Fast_Back with 20000 elements, the estimated running time for enqueue was 1 s.
For Queue_Fast_Front with 20000 elements, the estimated running time for dequeue was 4 s.
For Queue_Fast_Back with 20000 elements, the estimated running time for dequeue was 30 s.

output 2 example:

How many times should the potato be passed every round? 0
Winner: Sue

How many times should the potato be passed every round? 1
Winner: Bob

How many times should the potato be passed every round? 3
Winner: Bob

How many times should the potato be passed every round? 18
Winner: Sue

output 3 example:

Occurrences of cat: 3
Occurrences of dog: 2
Occurrences of snake: 1
Occurrences of tarrasque: 1

it`s also have 3 example .py files but i cant upate them.

Explanation / Answer

ELECTROFRIENDS.COMSOURCE CODESSOFTWARE PROGRAMSC++ PROGRAMSDATA STRUCTUREC++ PROGRAM TO IMPLEMENT THE QUEUE ADT USING A SINGLE LINKED LIST
C++ program to implement the Queue ADT using a single linked list

/* Write C++ programs to implement the Queue ADT using a singly linked list */

#include<iostream>
#include<conio.h>
#include<stdlib.h>
using namespace std;
class node
{
public:
class node *next;
int data;
};

class queue : public node
{
node *head;
int front,rare;
   public:
queue()
    {
   front=-1;
    rare=-1;
}
void push(int x)
    {
   if (rare < 0 )
        {
            head =new node;
       head->next=NULL;
   head->data=x;
    rare ++;
}
else
{
   node *temp,*temp1;
    temp=head;
   if(rare >= 4)
{
   cout <<"queue over flow";
    return;
}
rare++;
while(temp->next != NULL)
   temp=temp->next;
temp1=new node;
temp->next=temp1;
temp1->next=NULL;
temp1->data=x;
} }

void display()
    {
node *temp;
temp=head;
if (rare < 0)
{
cout <<" queue under flow";
return;
}
while(temp != NULL)
{
    cout <<temp->data<< " ";
temp=temp->next;
}
}
void pop()
{
   node *temp;
    temp=head;
if( rare < 0)
{
   cout <<"queue under flow";
    return;
}
if(front == rare)
{
   front = rare =-1;
    head=NULL;
return;
}
front++;
head=head->next;
}
};
main()
{
   queue s1;
   int ch;
   while(1)
{
       cout <<" 1.PUSH 2.POP 3.DISPLAY 4.EXIT enter ru choice:";
       cin >> ch;
       switch(ch)
       {
case 1:
    cout <<" enter a element";
   cin >> ch;
    s1.push(ch); break;

case 2: s1.pop();break;
case 3: s1.display();break;
   case 4: exit(0);
       }
}
return (0);
}
OUTPUT

1.PUSH 2.POP 3.DISPLAY 4.EXIT
enter ru choice:1
enter a element23

1.PUSH 2.POP 3.DISPLAY 4.EXIT
enter ru choice:1
enter a element54

1.PUSH 2.POP 3.DISPLAY 4.EXIT
enter ru choice:3
23 54
1.PUSH 2.POP 3.DISPLAY 4.EXIT
enter ru choice:2

1.PUSH 2.POP 3.DISPLAY 4.EXIT
enter ru choice:2

1.PUSH 2.POP 3.DISPLAY 4.EXIT
enter ru choice:2
queue under flow
1.PUSH 2.POP 3.DISPLAY 4.EXIT
enter ru choice:4

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.