Recall that a standard queue maintains a sequence of items and supports the following oper-ations: PUSH(x) (add an item r to the end of the sequence), PULL (remove and return theitem at the beginning of the sequence), and SIZE (returns the current length of the sequence).Using a doubly- linked list, you can easily implement a queue so that the worst case time foreach of these operations is O(1).Suppose we introduce a new operation called HALVE that removes every alternate elementfrom the sequence. It is implemented in the following way. The algorithm maintains a countervariable i, initially set to 0, and another variable n set to the result of SIZE. When i is even,it executes a PULL, discarding the result. When i is odd, it executes a PUSH(PULL()), pullingthe front element and pushing it to the back of the queue. In either case, i is incremented byone. The algorithm halts at the end of the n'th iteration (before i equals n).Prove that in any sequence of PUSH, PULL, and HALVE operations, the amortized cost ofeach operation is 0(1). Use the accounting method.

Queue: Queue is a linear data structure which follows the principle of First in First Out or Last in…

Answered: Recall that a standard queue maintains…

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Similar questions

The regular queue is a FIFO structure, meaning that you can only enqueue at the rear and dequeue at the front. Suppose that the dequeue operation can also be performed at the rear (so you can remove and return the last element on the queue), which of the following describes the correct and efficient way of using a linked list to implement this queue? OUsing a singly linked list with a reference to the head only, the dequeue method traverses it, stops at the last node and removes it. O Using a singly linked list with a reference to the head only, the dequeue method traverses it, stops at the second to last node and removes the last node. O Using a singly linked list with references that point to the first and the last nodes respectively, the dequeue method removes the last node via the corresponding reference. OUsing a doubly linked list with references that point to the first and the last nodes respectively, the dequeue method can remove the last node via the corresponding reference. O…
Use a SinglyLinked List to implement a Queuea. Define a Queue interface.b. Define a LinkedQueue class (Node class)..c. Define a Test class to test all methods help me make a test class first code package LinkedQueue; import linkedstack.Node; public class SLinkedList<E> { private Node <E> head = null; private Node <E> tail = null; private int size = 0; public SLinkedList() { head = null; tail = null; size = 0; } public int getSize() { return size; } public boolean isEmpty() { return size == 0; } public E getFirst() { if(isEmpty()) { return null; } return head.getElement(); } public E getLast() { if(isEmpty()) { return null; } return tail.getElement(); } public void addFirst(E e) { Node<E> newest = new Node<>(e, null); newest.setNext(head); head = newest; if(getSize()==0) { tail = head; } size++; } public void addLast(E e) { Node<E> newest = new Node<>(e, null); if(isEmpty()) { head = newest; } else {…
For a List implemented with a linked-list, the method bool Reverse() is implemented as follows: void List::Reverse() { } if (front==NULL) return; Node *temp1, *temp2, *temp3; temp2=front; temp3=front->next; while (temp3!=NULL) { } temp1=temp3->next; temp3->next=front; //missing line temp3=temp1; temp2->next=NULL; The missing line should be: O a. front-temp2; O b. front-temp1; O c. temp2=NULL; O d. temp1-temp3; O e. front-temp3;
Write an algorithm for the following problem in java: Find the numbers that are greater than the number d between n and m node values in the linked list Write a java code that implementing the algorithm? What is the time complexity of your code?
Consider the Double ended output restricted Queue implemented as a circular array based queue at the right. How will it look like after following operations have been performed on it in the given order: EnqueueFront(5) EnqueueFront(8) Dequeue() EnqueueRear(6) Dequeue() EnqueueRear(9)
Consider a linked list (SLL or DLL your choice) in which, to delete anelement from the list, we simply mark that node for the deletion.Whenever the number of deleted nodes in the list exceeds the number ofnon-deleted nodes, we simply delete all nodes which were marked fordeletion. Implement the following operations for such a linked list.1. addFirst2. addLast3. delFirst4. delLast5. Delete (mark for deletion) an ith node in the list.6. display all non-deleted nodes in the list7. Size : number of non-deleted nodes in the list.8. Recall the last deleted node in the list.
Given a linked list of N nodes ..
Add more methods to the doubly linked list class then test them• search(e) // Return one node with 3 values (stuID, stuName, stuScore) which matches agiven key e (studentID).• addAfter(e, stuID, stuName, stuScore) //Add a new node with 3 values (stuID,stuName, stuScore) after the node with the key e (studentID).• removeAt(e) //Remove a node which matches a given key e (studentID)• count() //Return a number of nodes of list.• update(stuID, stuName, stuScore) //Update the values of one node first code below package DlinkedList;public class DLinkedList<A,B,C> { private Node<A,B,C> header; private Node<A,B,C> trailer; private int size; public DLinkedList() { header = new Node<>(null, null, null); trailer = new Node<>(null, null, null); header.setNext(trailer); trailer.setPrev(header); } public int getSize() { return size; } public boolean isEmpty() { return size==0; } public A…
3) Consider an empty Queue of maximum size = 5; show only the contents of the queue after executing the following sequence of operations? Queue for (int k= 40; k>=10; k = k - 10) addQueue (k); 0. for (int k = 1; k <= 3; k++) deleteQueue(); for (int k = 50; k<= 80; k = k + 10) addQueue (k); 4. 3.

Recommended textbooks for you

Database System Concepts

Computer Science

ISBN:

9780078022159

Author:

Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:

McGraw-Hill Education

Starting Out with Python (4th Edition)

Computer Science

ISBN:

9780134444321

Author:

Tony Gaddis

Publisher:

PEARSON

Digital Fundamentals (11th Edition)

Computer Science

ISBN:

9780132737968

Author:

Thomas L. Floyd

Publisher:

PEARSON

Database System Concepts

Computer Science

ISBN:

9780078022159

Author:

Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:

McGraw-Hill Education

Starting Out with Python (4th Edition)

Computer Science

ISBN:

9780134444321

Author:

Tony Gaddis

Publisher:

PEARSON

Digital Fundamentals (11th Edition)

Computer Science

ISBN:

9780132737968

Author:

Thomas L. Floyd

Publisher:

PEARSON

C How to Program (8th Edition)

Computer Science

ISBN:

9780133976892

Author:

Paul J. Deitel, Harvey Deitel

Publisher:

PEARSON

Database Systems: Design, Implementation, & Manag…

Computer Science

ISBN:

9781337627900

Author:

Carlos Coronel, Steven Morris

Publisher:

Cengage Learning

Programmable Logic Controllers

Computer Science

ISBN:

9780073373843

Author:

Frank D. Petruzella

Publisher:

McGraw-Hill Education

SEE MORE TEXTBOOKS