Queue Data Structure MCQS Questions & Answers
By practicing these MCQs of Queue MCQs (Data Structure ) MCQs – Latest Competitive MCQs , an individual for exams performs better than before. This post comprising of objective questions and answers related to “Queue MCQs (Data Structure ) mcqs “. As wise people believe “Perfect Practice make a Man Perfect”. It is therefore practice these mcqs of Data Structure to approach the success. Tab this page to check “Queue MCQs (Data Structure)” for the preparation of competitive exmas.
The most occurred mcqs of Queue MCQs ( Data Structure ) in past papers. Past papers of Queue MCQs (Data structure ) Mcqs. Past papers of Queue MCQs (Data Structure ) Mcqs . Mcqs are the necessary part of any competitive / job related exams. The Mcqs having specific numbers in any written test. It is therefore everyone have to learn / remember the related Queue MCQs ( Data Structure ) Mcqs. The Important series of Queue MCQs ( Data Structure ) Mcqs are given below:
This set of Data Structure Multiple Choice Questions & Answers (MCQs) focuses on “Queue Operations”.
1. A linear list of elements in which deletion can be done from one end (front) and insertion can take place only at the other end (rear) is known as _____________
a) Stack
b) Queue
c) Tree
d) Linked list
Explanation: Linear list of elements in which deletion is done at front side and insertion at rear side is called Queue. In stack we will delete the last entered element first.
2. The data structure required for Breadth First Traversal on a graph is?
a) Stack
b) Array
c) Tree
d) Queue
Explanation: In Breadth First Search Traversal, BFS, starting vertex is first taken and adjacent vertices which are unvisited are also taken. Again, the first vertex which was added as an unvisited adjacent vertex list will be considered to add further unvisited vertices of the graph. To get the first unvisited vertex we need to follows First In First Out principle. Queue uses FIFO principle.
3. A queue follows __________
a) LIFO (Last In First Out) principle
b) Ordered array
c) FIFO (First In First Out) principle
d) Linear tree
Explanation: Element first added in queue will be deleted first which is FIFO principle.
4. Circular Queue is also known as ________
a) Square Buffer
b) Ring Buffer
c) Rectangle Buffer
d) Curve Buffer
Explanation: Circular Queue is also called as Ring Buffer. Circular Queue is a linear data structure in which last position is connected back to the first position to make a circle. It forms a ring structure.
5. If the elements “A”, “B”, “C” and “D” are placed in a queue and are deleted one at a time, in what order will they be removed?
a) ABDC
b) DCBA
c) DCAB
d) ABCD
Explanation: Queue follows FIFO approach. i.e. First in First Out Approach. So, the order of removal elements are ABCD.
6. A data structure in which elements can be inserted or deleted at/from both ends but not in the middle is?
a) Queue
b) Circular queue
c) Priority queue
d) Dequeue
Explanation: In dequeuer, we can insert or delete elements from both the ends. In queue, we will follow first in first out principle for insertion and deletion of elements. Element with least priority will be deleted in a priority queue.
7. A normal queue, if implemented using an array of size MAX_SIZE, gets full when?
a) Front = (rear + 1)mod MAX_SIZE
b) Front = rear + 1
c) Rear = front
d) Rear = MAX_SIZE – 1
Explanation: When Rear = MAX_SIZE – 1, there will be no space left for the elements to be added in queue. Thus queue becomes full.
8. Queues serve major role in ______________
a) Simulation of recursion
b) Simulation of arbitrary linked list
c) Simulation of heap sort
d) Simulation of limited resource allocation
Explanation: Simulation of recursion uses stack data structure. Simulation of arbitrary linked lists uses linked lists. Simulation of resource allocation uses queue as first entered data needs to be given first priority during resource allocation. Simulation of heap sort uses heap data structure.
9. Which of the following is not the type of queue?
a) Ordinary queue
b) Circular queue
c) Single ended queue
d) Priority queue
Explanation: Queue always has two ends. So, single ended queue is not the type of queue.
10. A linear list of elements in which deletion can be done from one end (front) and insertion can take place only at the other end (rear) is known as _____________
a) Stack
b) Tree
c) Queue
d) Linked list
Explanation: Linear list of elements in which deletion is done at front side and insertion at rear side is called Queue. In stack we will delete the last entered element first.
11. The data structure required for Breadth First Traversal on a graph is?
a) Stack
b) Array
c) Queue
d) Tree
Explanation: In Breadth First Search Traversal, BFS, starting vertex is first taken and adjacent vertices which are unvisited are also taken. Again, the first vertex which was added as an unvisited adjacent vertex list will be considered to add further unvisited vertices of the graph. To get the first unvisited vertex we need to follows First In First Out principle. Queue uses FIFO principle.
12. A queue follows __________
a) LIFO (Last In First Out) principle
b) Ordered array
c) FIFO (First In First Out) principle
d) Linear tree
Explanation: Element first added in queue will be deleted first which is FIFO principle.
13. Circular Queue is also known as ________
a) Square Buffer
b) Rectangle Buffer
c) Ring Buffer
d) Curve Buffer
Explanation: Circular Queue is also called as Ring Buffer. Circular Queue is a linear data structure in which last position is connected back to the first position to make a circle. It forms a ring structure.
14. If the elements “A”, “B”, “C” and “D” are placed in a queue and are deleted one at a time, in what order will they be removed?
a) ABDC
b) DCBA
c) DCAB
d) ABCD
Explanation: Queue follows FIFO approach. i.e. First in First Out Approach. So, the order of removal elements are ABCD.
15. A data structure in which elements can be inserted or deleted at/from both ends but not in the middle is?
a) Queue
b) Dequeue
c) Circular queue
d) Priority queue
Explanation: In dequeuer, we can insert or delete elements from both the ends. In queue, we will follow first in first out principle for insertion and deletion of elements. Element with least priority will be deleted in a priority queue.
16. A normal queue, if implemented using an array of size MAX_SIZE, gets full when?
a) Front = (rear + 1)mod MAX_SIZE
b) Rear = MAX_SIZE – 1
c) Front = rear + 1
d) Rear = front
Explanation: When Rear = MAX_SIZE – 1, there will be no space left for the elements to be added in queue. Thus queue becomes full.
17. Queues serve major role in ______________
a) Simulation of recursion
b) Simulation of limited resource allocation
c) Simulation of arbitrary linked list
d) Simulation of heap sort
Explanation: Simulation of recursion uses stack data structure. Simulation of arbitrary linked lists uses linked lists. Simulation of resource allocation uses queue as first entered data needs to be given first priority during resource allocation. Simulation of heap sort uses heap data structure.
18. Which of the following is not the type of queue?
a) Single ended queue
b) Ordinary queue
c) Circular queue
d) Priority queue
Explanation: Queue always has two ends. So, single ended queue is not the type of queue.
19. In linked list implementation of queue, if only front pointer is maintained, which of the following operation take worst case linear time?
a) Insertion
b) Deletion
c) Both Insertion and To empty a queue
d) To empty a queue
Explanation: Since front pointer is used for deletion, so worst time for the other two cases.
20. In linked list implementation of a queue, where does a new element be inserted?
a) At the head of link list
b) At the centre position in the link list
c) At any position in the linked list
d) At the tail of the link list
Explanation: Since queue follows FIFO so new element inserted at last.
21. In linked list implementation of a queue, front and rear pointers are tracked. Which of these pointers will change during an insertion into a NONEMPTY queue?
a) Only front pointer
b) Both front and rear pointer
c) Only rear pointer
d) No pointer will be changed
Explanation: Since queue follows FIFO so new element inserted at last.
22. In linked list implementation of a queue, front and rear pointers are tracked. Which of these pointers will change during an insertion into EMPTY queue?
a) Both front and rear pointer
b) Only front pointer
c) Only rear pointer
d) No pointer will be changed
Explanation: Since its the starting of queue, so both values are changed.
23. In case of insertion into a linked queue, a node borrowed from the __________ list is inserted in the queue.
a) FRONT
b) AVAIL
c) REAR
d) NULL
Explanation: All the nodes are collected in AVAIL list.
24. In linked list implementation of a queue, from where is the item deleted?
a) At the centre position in the link list
b) At the tail of the link list
c) At the head of link list
d) Node before the tail
Explanation: Since queue follows FIFO so new element deleted from first.
25. In linked list implementation of a queue, the important condition for a queue to be empty is?
a) LINK is empty
b) FRONT==REAR-1
c) FRONT is null
d) REAR is null
Explanation: Because front represents the deleted nodes.
26. The essential condition which is checked before insertion in a linked queue is?
a) Underflow
b) Front value
c) Rear value
b) Overflow
Explanation: To check whether there is space in the queue or not.
27. The essential condition which is checked before deletion in a linked queue is?
a) Overflow
b) Underflow
c) Front value
d) Rear value
Explanation: To check whether there is element in the list or not.
28. Which of the following is true about linked list implementation of queue?
a) In push operation, if new nodes are inserted at the beginning, then in pop operation, nodes must be removed from the beginning
b) In push operation, if new nodes are inserted at the beginning of linked list, then in pop operation, nodes must be removed from end
c) In push operation, if new nodes are inserted at the end, then in pop operation, nodes must be removed from end
d) In push operation, if new nodes are inserted at the end, then in pop operation, nodes must be removed from beginning
Explanation: It can be done by both the methods.
This set of Data Structure Multiple Choice Questions & Answers (MCQs) focuses on “Priority Queue”.
29. With what data structure can a priority queue be implemented?
a) Array
b) List
c) Tree
d) Heap
Explanation: Priority queue can be implemented using an array, a list, a binary search tree or a heap, although the most efficient one being the heap.
30. Which of the following is not an application of priority queue?
a) Undo operation in text editors
b) Huffman codes
c) Interrupt handling in operating system
d) Bayesian spam filter
Explanation: Undo operation is achieved using a stack.
31. Select the appropriate code that inserts elements into the list based on the given key value.
(head and trail are dummy nodes to mark the end and beginning of the list, they do not contain any priority or element)
a)
public void insert_key(int key,Object item) { if(key<0) { Systerm.our.println("invalid"); System.exit(0); } else { Node temp = new Node(key,item,null); if(count == 0) { head.setNext(temp); temp.setNext(trail); } else { Node dup = head.getNext(); Node cur = head; while((key>dup.getKey()) && (dup!=trail)) { dup = dup.getNext(); cur = cur.getNext(); } cur.setNext(temp); temp.setNext(dup); } count++; } }
b)
public void insert_key(int key,Object item) { if(key<0) { Systerm.our.println("invalid"); System.exit(0); } else { Node temp = new Node(key,item,null); if(count == 0) { head.setNext(temp); temp.setNext(trail); } else { Node dup = head.getNext(); Node cur = dup; while((key>dup.getKey()) && (dup!=trail)) { dup = dup.getNext(); cur = cur.getNext(); } cur.setNext(temp); temp.setNext(dup); } count++; } }
c)
public void insert_key(int key,Object item) { if(key<0) { Systerm.our.println("invalid"); System.exit(0); } else { Node temp = new Node(key,item,null); if(count == 0) { head.setNext(temp); temp.setNext(trail); } else { Node dup = head.getNext(); Node cur = head; while((key>dup.getKey()) && (dup!=trail)) { dup = dup.getNext(); cur = cur.getNext(); } cur.setNext(dup); temp.setNext(cur); } count++; } }
d)
public void insert_key(int key,Object item) { if(key<0) { Systerm.our.println("invalid"); System.exit(0); } else { Node temp = new Node(key,item,null); if(count == 0) { head.setNext(temp); temp.setNext(trail); } else { Node dup = head.getNext(); Node cur = head; while((key>dup.getKey()) && (dup!=trail)) { dup = cur cur = cur.getNext(); } cur.setNext(dup); temp.setNext(cur); } count++; } }
Explanation: Have two temporary pointers ‘dup’ and ‘cur’ with ‘cur’ trailing behind ‘dup’. Traverse through the list until the given key is greater than some element with a lesser key, insert the new node ‘temp’ in that position.
32. What is the time complexity to insert a node based on key in a priority queue?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n2)
Explanation: In the worst case, you might have to traverse the entire list.
33. What is the functionality of the following piece of code?
public Object delete_key() { if(count == 0) { System.out.println("Q is empty"); System.exit(0); } else { Node cur = head.getNext(); Node dup = cur.getNext(); Object e = cur.getEle(); head.setNext(dup); count--; return e; } }
a) Delete the second element in the list
b) Delete the first element in the list
c) Return but not delete the second element in the list
d) Return but not delete the first element in the list
Explanation: A pointer is made to point at the first element in the list and one more to point to the second element, pointer manipulations are done such that the first element is no longer being pointed by any other pointer, its value is returned.
34. What is not a disadvantage of priority scheduling in operating systems?
a) A low priority process might have to wait indefinitely for the CPU
b) If the system crashes, the low priority systems may be lost permanently
c) Indefinite blocking
d) Interrupt handling
Explanation: The lower priority process should wait until the CPU completes the processing higher priority process. Interrupt handling is an advantage as interrupts should be given more priority than tasks at hand so that interrupt can be serviced to produce desired results.
35. Which of the following is not an advantage of a priority queue?
a) Easy to delete elements in any cast
b) Easy to implement
c) Processes with different priority can be efficiently handled
d) Applications with differing requirements
Explanation: In worst case, the entire queue has to be searched for the element having the highest priority. This will take more time than usual. So deletion of elements is not an advantage.
36. What is the time complexity to insert a node based on position in a priority queue?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n2)
Explanation: In the worst case, you might have to traverse the entire list.
37. What is a dequeue?
a) A queue implemented with a doubly linked list
b) A queue implemented with both singly and doubly linked lists
c) A queue with insert/delete defined for front side of the queue
d) A queue with insert/delete defined for both front and rear ends of the queue
Explanation: A dequeue or a double ended queue is a queue with insert/delete defined for both front and rear ends of the queue.
38. 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)
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++; }
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()).
39. 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) Fetch the element at the rear end of the dequeue
c) Fetch the element at the front end of the dequeue
d) Insert at the rear end of the dequeue
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.
40. 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
Explanation: All of the mentioned can be implemented with a dequeue.
41. 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; } }
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’.
42. 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; } }
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’.
43. What is the time complexity of deleting from the rear end of the dequeue implemented with a singly linked list?
a) O(nlogn)
44. 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 40 15
b) 10 30 10 15
c) 20 30 40 15
d) 20 30 40 10
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
45. A Double-ended queue supports operations such as adding and removing items from both the sides of the queue. They support four operations like addFront(adding item to top of the queue), addRear(adding item to the bottom of the queue), removeFront(removing item from the top of the queue) and removeRear(removing item from the bottom of the queue). You are given only stacks to implement this data structure. You can implement only push and pop operations. What are the total number of stacks required for this operation?(you can reuse the stack)
a) 1
b) 2
c) 3
d) 4
Explanation: The addFront and removeFront operations can be performed using one stack itself as push and pop are supported (adding and removing element from top of the stack) but to perform addRear and removeRear you need to pop each element from the current stack and push it into another stack, push or pop the element as per the asked operation from this stack and in the end pop elements from this stack to the first stack.
46. You are asked to perform a queue operation using a stack. Assume the size of the stack is some value ‘n’ and there are ‘m’ number of variables in this stack. The time complexity of performing deQueue operation is (Using only stack operations like push and pop)(Tightly bound).
a) O(n)
b) O(m)
c) O(m*n)
d) Data is insufficient
Explanation: To perform deQueue operation you need to pop each element from the first stack and push it into the second stack. In this case you need to pop ‘m’ times and need to perform push operations also ‘m’ times. Then you pop the first element from this second stack (constant time) and pass all the elements to the first stack (as done in the beginning)(‘m-1’ times). Therfore the time complexity is O(m).
47. Consider you have an array of some random size. You need to perform dequeue operation. You can perform it using stack operation (push and pop) or using queue operations itself (enQueue and Dequeue). The output is guaranteed to be same. Find some differences?
a) The memory used will not be different
b) There are chances that output might be different
c) No differences
d) They will have different time complexities
Explanation: To perform operations such as Dequeue using stack operation you need to empty all the elements from the current stack and push it into the next stack, resulting in a O(number of elements) complexity whereas the time complexity of dequeue operation itself is O(1). And there is a need of a extra stack. Therefore more memory is needed.
48. Consider you have a stack whose elements in it are as follows.
5 4 3 2 << top
Where the top element is 2.
You need to get the following stack
6 5 4 3 2 << top
The operations that needed to be performed are (You can perform only push and pop):
a) Push(pop()), push(6), push(pop())
b) Push(pop()), push(6)
c) Push(pop()), push(pop()), push(6)
d) Push(6)
Explanation: By performing push(pop()) on all elements on the current stack to the next stack you get 2 3 4 5 << top.Push(6) and perform push(pop()) you’ll get back 6 5 4 3 2 << top. You have actually performed enQueue operation using push and pop.
49. A double-ended queue supports operations like adding and removing items from both the sides of the queue. They support four operations like addFront(adding item to top of the queue), addRear(adding item to the bottom of the queue), removeFront(removing item from the top of the queue) and removeRear(removing item from the bottom of the queue). You are given only stacks to implement this data structure. You can implement only push and pop operations. What’s the time complexity of performing addFront and addRear? (Assume ‘m’ to be the size of the stack and ‘n’ to be the number of elements)
a) O(m) and O(n)
b) O(n) and O(1)
c) O(1) and O(n)
d) O(n) and O(m)
Explanation: addFront is just a normal push operation. Push operation is of O(1). Whereas addRear is of O(n) as it requires two push(pop()) operations of all elements of a stack.
50. Why is implementation of stack operations on queues not feasible for a large dataset (Asssume the number of elements in the stack to be n)?
a) Because of its time complexity O(log(n))
b) Extra memory is not required
c) Because of its time complexity O(n)
d) There are no problems
Explanation: To perform Queue operations such as enQueue and deQueue there is a need of emptying all the elements of a current stack and pushing elements into the next stack and vice versa. Therfore it has a time complexity of O(n) and the need of extra stack as well, may not be feasible for a large dataset.
51. Consider yourself to be in a planet where the computational power of chips to be slow. You have an array of size 10.You want to perform enqueue some element into this array. But you can perform only push and pop operations .Push and pop operation both take 1 sec respectively. The total time required to perform enQueue operation is?
a) 20
b) 40
c) 43
d) 42
Explanation: First you have to empty all the elements of the current stack into the temporary stack, push the required element and empty the elements of the temporary stack into the original stack. Therfore taking 10+10+1+11+11= 43 seconds.
52. You have two jars, one jar which has 10 rings and the other has none. They are placed one above the other. You want to remove the last ring in the jar. And the second jar is weak and cannot be used to store rings for a long time.
a) Empty the first jar by removing it one by one from the first jar and placing it into the second jar
b) There exists no possible way to do this
c) Empty the first jar by removing it one by one from the first jar and placing it into the second jar and empty the second jar by placing all the rings into the first jar one by one
d) Break the jar and remove the last one
Explanation: This is similar to performing dequeue operation using push and pop only. Elements in the first jar are taken out and placed in the second jar. After removing the last element from the first jar, remove all the elements in the second jar and place them in the first jar.
53. Given only a single array of size 10 and no other memory is available. Which of the following operation is not feasible to implement (Given only push and pop operation)?
a) Push
b) Pop
c) Enqueue
d) Returntop
Explanation: To perform Enqueue using just push and pop operations, there is a need of another array of same size. But as there is no extra available memeory, the given operation is not feasible.
54. Given an array of size n, let’s assume an element is ‘touched’ if and only if some operation is performed on it(for example, for performing a pop operation the top element is ‘touched’). Now you need to perform Dequeue operation. Each element in the array is touched atleast?
a) Once
b) Twice
c) Thrice
d) Four time
Explanation: First each element from the first stack is popped, then pushed into the second stack, dequeue operation is done on the top of the stack and later the each element of second stack is popped then pushed into the first stack. Therefore each element is touched four times.
55. To implement a stack using queue(with only enqueue and dequeue operations), how many queues will you need?
a) 1
b) 2
c) 3
d) 4
Explanation: Either the push or the pop has to be a costly operation, and the costlier operation requires two queues.
56. Making the push operation costly, select the code snippet which implements the same.(let q1 and q2 be two queues)
a)
public void push(int x) { if(empty()) { q1.offer(x); } else{ if(q1.size()>0) { q2.offer(x); int size = q1.size(); while(size>0) { q2.offer(q1.poll()); size--; } } else if(q2.size()>0) { q1.offer(x); int size = q2.size(); while(size>0) { q1.offer(q2.poll()); size--; } } } }
b)
public void push(int x) { if(empty()) { q1.offer(x); } else { if(q1.size()>0) { q1.offer(x); int size = q1.size(); while(size>0) { q2.offer(q1.poll()); size--; } } else if(q2.size()>0) { q2.offer(x); int size = q2.size(); while(size>0) { q1.offer(q2.poll()); size--; } } } }
c)
public void push(int x) { if(empty()) { q1.offer(x); } else { if(q1.size()>0) { q2.offer(x); int size = q1.size(); while(size>0) { q1.offer(q2.poll()); size--; } } else if(q2.size()>0) { q1.offer(x); int size = q2.size(); while(size>0) { q2.offer(q1.poll()); size--; } } } }
d)
public void push(int x) { if(empty()) { q1.offer(x); } else { if(q1.size()>0) { q2.offer(x); int size = q1.size(); while(size>0) { q2.offer(q2.poll()); size--; } } else if(q2.size()>0) { q1.offer(x); int size = q2.size(); while(size>0) { q2.offer(q1.poll()); size--; } } } }
Explanation: Stack follows LIFO principle, hence a new item added must be the first one to exit, but queue follows FIFO principle, so when a new item is entered into the queue, it will be at the rear end of the queue. If the queue is initially empty, then just add the new element, otherwise add the new element to the second queue and dequeue all the elements from the second queue and enqueue it to the first one, in this way, the new element added will be always in front of the queue. Since two queues are needed to realize this push operation, it is considered to be costlier.
57. Making the push operation costly, select the code snippet which implements the pop operation.
a)
publicvoid pop()
{ if(q1.size()>0) { q2.poll(); } else if(q2.size()>0) { q1.poll(); } }
b)
public void pop() { if(q1.size()>0) { q1.poll(); } else if(q2.size()>0) { q2.poll(); } }
c)
public void pop() { q1.poll(); q2.poll(); }
d)
public void pop() { if(q2.size()>0) { q1.poll(); } else { q2.poll(); } }
Explanation: As the push operation is costly, it is evident that the required item is in the front of the queue, so just dequeue the element from the queue.
58. Select the code snippet which returns the top of the stack.
a)
publicint top()
{ if(q1.size()>0) { return q1.poll(); } else if(q2.size()>0) { return q2.poll(); } return 0; }
b)
public int top() { if(q1.size()==0) { return q1.peek(); } else if(q2.size()==0) { return q2.peek(); } return 0; }
c)
public int top() { if(q1.size()>0) { return q1.peek(); } else if(q2.size()>0) { return q2.peek(); } return 0; }
d)
public int top() { if(q1.size()>0) { return q2.peek(); } else if(q2.size()>0) { return q1.peek(); } return 0; }
Explanation: Assuming its a push costly implementation, the top of the stack will be in the front end of the queue, note that peek() just returns the front element, while poll() removes the front element from the queue.
59. Select the code snippet which return true if the stack is empty, false otherwise.
a)
publicboolean empty()
{ return q2.isEmpty(); }
b)
public boolean empty() { return q1.isEmpty() || q2.isEmpty(); }
c)
public boolean empty() { return q1.isEmpty(); }
d)
public boolean empty() { return q1.isEmpty() & q2.isEmpty(); }
Explanation: If both the queues are empty, then the stack also is empty.
60. Making the pop operation costly, select the code snippet which implements the same.
a)
public int pop() { int res=-999,count=0; if(q1.size()>0) { count = q1.size(); while(count>0) q2.offer(q1.poll()); res = q1.poll(); } if(q2.size()>0) { count = q2.size(); while(count>0) q1.offer(q2.poll()); res = q2.poll(); } return res; }
b)
public int pop() { int res=-999,count=0; if(q1.size()>0) { count = q1.size(); while(count>1) q2.offer(q1.poll()); res = q2.poll(); } if(q2.size()>0) { count = q2.size(); while(count>1) q1.offer(q2.poll()); res = q1.poll(); } return res; }
c)
public int pop() { int res=-999,count=0; if(q1.size()>0) { count = q1.size(); while(count>1) q2.offer(q1.poll()); res = q1.poll(); } if(q2.size()>0) { count = q2.size(); while(count>1) q1.offer(q2.poll()); res = q2.poll(); } return res; }
d)
public int pop() { int res=-999,count=0; if(q1.size()>0) { count = q2.size(); while(count>1) q2.offer(q1.poll()); res = q1.poll(); } if(q2.size()>0) { count = q1.size(); while(count>1) q1.offer(q2.poll()); res = q2.poll(); } return res; }
Explanation: Here the pop operation is costly, hence we need two queues, other than the first element, all the the elements from one queue are dequeued and enqueued to the second queue, hence only one element remains in the first queue which is the item we want, so dequeue it and return the result.
61. What is the functionality of the following piece of code?
public void fun(int x) { q1.offer(x); }
a) Perform push() with push as the costlier operation
b) Perform push() with pop as the costlier operation
c) Perform pop() with push as the costlier operation
d) Perform pop() with pop as the costlier operation
Explanation: offer() suggests that it is a push operation, but we see that it is performed with only one queue, hence the pop operation is costlier.
Answer: a
a) Stack
64. Let the following circular queue can accommodate maximum six elements with the following data
front = 2 rear = 4
queue = _______; L, M, N, ___, ___
What will happen after ADD O operation takes place?
a) front = 2 rear = 5
queue = ______; L, M, N, O, ___
queue = L, M, N, O, ___
queue = ______; L, M, N, O, ___
queue = L, M, N, O, ___
Answer: a)
a) FIFO (First In First Out) list
Answer: a)
a) Stack
Answer: b) Queue
a) ABCD
Answer: a) ABCD
68. In linked list implementation of a queue, where does a new element be inserted?
a) At the head of link list
Answer: b) At the tail of the link list
a) Insertion
Answer: d) None
Answer: d) Both a) and c)
a) rear=(rear%1)+MAX_SIZE
Answer: c) rear=(rear+1)%MAX_SIZE
a) Front=rear= -1
73. A circular queue is implemented using an array of size 10. The array index starts with 0, front is 6, and rear is 9. The insertion of next element takes place at the array index.
a) 0
Answer: a) 0
74. If the MAX_SIZE is the size of the array used in the implementation of circular queue, array index start with 0, front point to the first element in the queue, and rear point to the last element in the queue. Which of the following condition specify that circular queue is EMPTY?
a) Front=rear=0
Answer: b) Front= rear=-1
a) Queue
76. In linked list implementation of a queue, front and rear pointers are tracked. Which of these pointers will change during an insertion into a NONEMPTY queue?
a) Only front pointer
Answer: b) Only rear pointer
a) Rear=MAX_SIZE-1
Answer: a) Rear=MAX_SIZE-1
78. In linked list implementation of a queue, front and rear pointers are tracked. Which of these pointers will change during an insertion into EMPTY queue?
a) Only front pointer
Answer: c) Both front and rear pointer
a) Zero
Answer: d) MAX_SIZE
80. Suppose a circular queue of capacity (n-1) elements is implemented with an array of n elements. Assume that the insertion and deletion operations are carried out using REAR and FRONT as array index variables, respectively. Initially REAR=FRONT=0. The conditions to detect queue full and queue is empty are?
a) Full: (REAR+1)mod n == FRONT
Empty: REAR==FRONT
Empty: (FRONT+1) mod n == REAR
Empty: (REAR+1) mod n==FRONT
Empty: REAR==FRONT
Answer: a)
Multiqueue(Q)
{
m=k;
while(Q is not empty) and (m > 0)
{
DEQUEUE(Q)
m=m-1
}
What is the worst case time complexity of a sequence of n queue operations on an initially empty queue?
a) θ (n)
Anwer: a) θ (n)