Data Structure Questions and Answers – Double Ended Queue (Dequeue)

«
»

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

1. 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
View Answer

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.
advertisement

2. 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)

advertisement
advertisement
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)

advertisement
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)

advertisement
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++;
}
View Answer
Answer: a
Explanation: Create a new node, if the current list is empty, the ‘head’ points to this node and this new node points to ‘trail’. Otherwise, ‘head’ points to the new node and this in turn points to the current first element(head.getNext()).
 
 
3. 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
View Answer

Answer: b
Explanation: If the list is empty, this new node will point to ‘trail’ and will be pointed at by ‘head’. Otherwise, traverse till the end of the list and insert the new node there.
advertisement

4. 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
View Answer

Answer: d
Explanation: All of the mentioned can be implemented with a dequeue.

5. 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;
	}
}
View Answer
Answer: b
Explanation: Have two pointers, one(temp) pointing to the first element and the other(cur) pointing to the second element. Make the ‘head’ point to the second element, this removes all reference for ‘temp’.
 
 
6. 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;
	}
}
View Answer
Answer: c
Explanation: Traverse till the end of the list with a pointer ‘temp’ and another ‘cur’ which is trailing behind temp, make ‘cur’ point to trail, this removes all reference for ‘temp’.
 
 
7. 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)
View Answer
Answer: c
Explanation: Since a singly linked list is used, first you have to traverse till the end, so the complexity is O(n).

8. 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
View Answer

Answer: d
Explanation: A careful tracing of the given operation yields the result.
10
20 10
20 10 30
10 30
10 30 40
10 30 40 10
10 30 40
10 30 40 15

Sanfoundry Global Education & Learning Series – Data Structure.

To practice all areas of Data Structure, here is complete set of 1000+ Multiple Choice Questions and Answers.

Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

advertisement
advertisement
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn | Youtube | Instagram | Facebook | Twitter