Double Ended Queue (Dequeue)

Uncategorized

This set of Data Structure Multiple Choice Questions & Answers (MCQs) focuses on “Double Ended Queue (Dequeue)”.

1. Select the function which performs insertion at the front end of the dequeue?
A)

public void function(Object item)
{
	Node temp = new Node(item,null);
	if(isEmpty())
	{
		temp.setNext(trail);
		head.setNext(temp);
	}
	else
	{
		Node cur = head.getNext();
		temp.setNext(cur);
		head.setNext(temp);
	}
	size++;
}

B)

public void function(Object item)
{
	Node temp = new Node(item,null);
	if(isEmpty())
	{
		temp.setNext(trail);
		head.setNext(trail);
	}
	else
	{
		Node cur = head.getNext();
		temp.setNext(cur);
		head.setNext(temp);
	}
	size++;
}

C)

public void function(Object item)
{
	Node temp = new Node(item,null);
	if(isEmpty())
	{
		Node cur = head.getNext();
		temp.setNext(cur);
		head.setNext(temp);
	}
	else
	{
		temp.setNext(trail);
		head.setNext(temp);
	}
	size++;
}

D)advertisementhttps://4733ddf5a1f20e1833b3db0e52fedd4f.safeframe.googlesyndication.com/safeframe/1-0-38/html/container.html

public void function(Object item)
{
	Node temp = new Node(item,null);
	if(isEmpty())
	{
		Node cur = head.getNext();
		temp.setNext(cur);
		cur.setNext(temp);
	}
	else
	{
		head.setNext(trail);
		trail.setNext(temp);
	}
	size++;
}

Answer: A
Explanation: If the current list is empty, create a new node, with the ‘head' pointing to it and the ‘trail' pointing to it. Otherwise, ‘head' refers to the newly generated node, which in turn refers to the current first element (head.getNext()).

2. What are the applications of dequeue?
A) A-Steal job scheduling algorithm
B) Can be used as both stack and queue
C) To find the maximum of all sub arrays of size k
D) To avoid collision in hash tables

Answer: D
Explanation: A dequeue can be used to execute all of the above.

3. Which of the following can be used to delete an element from the rear end of the queue?
A)
public Object deleteRear() throws emptyDEQException { if(isEmpty()) throw new emptyDEQException("Empty"); else { Node temp = head.getNext(); Node cur = temp; while(temp.getNext() != trail) { temp = temp.getNext(); cur = cur.getNext(); } Object e = temp.getEle(); cur.setNext(trail); size--; return e; } }
B)
public Object deleteRear() throws emptyDEQException { if(isEmpty()) throw new emptyDEQException("Empty"); else { Node temp = head.getNext(); Node cur = head; while(temp != trail) { temp = temp.getNext(); cur = cur.getNext(); } Object e = temp.getEle(); cur.setNext(trail); size--; return e; } }
C)
public Object deleteRear() throws emptyDEQException { if(isEmpty()) throw new emptyDEQException("Empty"); else { Node temp = head.getNext(); Node cur = head; while(temp.getNext()!=trail) { temp = temp.getNext(); cur = cur.getNext(); } Object e = temp.getEle(); cur.setNext(trail); size--; return e; } }
D)
public Object deleteRear() throws emptyDEQException { if(isEmpty()) throw new emptyDEQException("Empty"); else { Node temp = head.getNext(); Node cur = head; while(temp.getNext()!=trail) { temp = temp.getNext(); cur = cur.getNext(); } Object e = temp.getEle(); temp.setNext(trail); size--; return e; } }

Answer: C
Explanation: With a pointer ‘temp’ at the end of the list and another ‘cur’ trailing behind temp, make ‘cur’ point to trail, removing all references to ‘temp’.

4. After performing these set of operations, what does the final list look contain?

InsertFront(10);
InsertFront(20);
InsertRear(30);
DeleteFront();
InsertRear(40);
InsertRear(10);
DeleteRear();
InsertRear(15);
display();

A) 10 30 10 15
B) 20 30 40 15
C) 20 30 40 10
D) 10 30 40 15

Answer: D
Explanation: The result is obtained by carefully tracing the given operation.
10
20 10
20 10 30
10 30
10 30 40
10 30 40 10
10 30 40
10 30 40 15

5. What is the time complexity of deleting from the rear end of the dequeue implemented with a singly linked list?
A) O(nlogn)
B) O(logn)
C) O(n)
D) O(n2)

Answer: c
Explanation: Since a singly linked list is used, you must first traverse all the way to the end, so the difficulty is O. (n).

6. Which of the following can be used to delete an element from the front end of the queue?
A)

public Object deleteFront() throws emptyDEQException
{
	if(isEmpty())
		throw new emptyDEQException("Empty");
	else
	{
		Node temp = head.getNext();
		Node cur = temp;
		Object e = temp.getEle();
		head.setNext(cur);
		size--;
		return e;
	}
}

B)

public Object deleteFront() throws emptyDEQException
{
	if(isEmpty())
		throw new emptyDEQException("Empty");
	else
	{
		Node temp = head.getNext();
		Node cur = temp.getNext();
		Object e = temp.getEle();
		head.setNext(cur);
		size--;
		return e;
	}
}

C)

public Object deleteFront() throws emptyDEQException
{
	if(isEmpty())
		throw new emptyDEQException("Empty");
	else
	{
		Node temp = head.getNext();
		Node cur = temp.getNext();
		Object e = temp.getEle();
		head.setNext(temp);
		size--;
		return e;
	}
}

D)

public Object deleteFront() throws emptyDEQException
{
	if(isEmpty())
		throw new emptyDEQException("Empty");
	else
	{
		Node temp = head.getNext();
		Node cur = temp.getNext();
		Object e = temp.getEle();
		temp.setNext(cur);
		size--;
		return e;
	}
}
Answer: B
Explanation: Have two pointers, one for the first element (temp) and the other for the second element (cur). Make the ‘head' point to the second part, and all references to ‘temp' will be removed.

7. What is the functionality of the following piece of code?
public void function(Object item) { Node temp=new Node(item,trail); if(isEmpty()) { head.setNext(temp); temp.setNext(trail); } else { Node cur=head.getNext(); while(cur.getNext()!=trail) { cur=cur.getNext(); } cur.setNext(temp); } size++; }
A) Insert at the front end of the dequeue
B) Insert at the rear end of the dequeue
C) Fetch the element at the rear end of the dequeue
D) Fetch the element at the front end of the dequeue


Answer: B
Explanation: This new node will point to ‘trail' if the list is empty, and ‘head' will point to it. Otherwise, go all the way to the end of the list and add the new node there.

8. What is a dequeue?
A) A queue with insert/delete defined for both front and rear ends of the queue
B) A queue implemented with a doubly linked list
C) A queue implemented with both singly and doubly linked lists
D) A queue with insert/delete defined for front side of the queue

Answer: A
Explanation: A dequeue or a double ended queue is a queue with insert/delete defined for both front and rear ends of the queue.

A deque, also known as a double-ended queue, is an ordered group of objects that functions similarly to a queue. It has two ends, a front and a back, and the objects in the set remain in place. This hybrid linear system, in a way, incorporates the features of stacks and queues into a single data structure. A queue, unlike stacks, is open on both ends. The one end is often used to insert data (enqueue), while the other is always used to delete data (dequeue) (dequeue). A queue is set up such that items are added to the end and removed from the beginning. Dequeue, on the other hand, represents a queue in which you can insert and delete items from both ends.

Leave a Reply

Your email address will not be published. Required fields are marked *