Queues Interview Questions and Answers

A queue is a container of objects (a linear collection) that are inserted and removed according to the first-in first-out (FIFO) principle. The process to add an element into queue is called Enqueue and the process of removal of an element from queue is called Dequeue.

Queue, as the name suggests is used whenever we need to manage any group of objects in an order in which the first one coming in, also gets out first while the others wait for their turn, like in the following scenarios: Serving requests on a single shared resource, like a printer, CPU task scheduling etc. In real life scenario, Call Center phone systems uses Queues to hold people calling them in an order, until a service representative is free. Handling of interrupts in real-time systems. The interrupts are handled in the same order as they arrive i.e First come first served.

Problem

Suppose we have two stacks and no other temporary variable. Is to possible to "construct" a queue data structure using only the two stacks?

Solution

Keep two stacks, let's call them inbox and outbox . Enqueue: Push the new element onto inbox Dequeue: If outbox is empty, refill it by popping each element from inbox and pushing it onto outbox Pop and return the top element from outbox Complexity Analysis: Time Complexity: O(1) Space Complexity: O(1) In the worst case scenario when outbox stack is empty, the algorithm pops n elements from inbox stack and pushes n elements to outbox, where n is the queue size. This gives 2*n operations, which is O(n) . But when outbox stack is not empty the algorithm has O(1) time complexity that gives amortised O(1) . Implementation: CS public class Queue where T : class

{
  private Stack<T> input = new Stack<T>();
  private Stack<T> output = new Stack<T>();
  public void Enqueue(T t)
  {
    input.Push(t);
  }
public T Dequeue()
{
  if (output.Count == 0)
  {
    while (input.Count != 0)
    {
      output.Push(input.Pop());
    }
}

return output.Pop();
}
}
Java
public class Queue<E>
{
  private Stack<E> inbox = new Stack<E>();
  private Stack<E> outbox = new Stack<E>();
  public void queue(E item) {
    inbox.push(item);
  }
public E dequeue() {
  if (outbox.isEmpty()) {
    while (!inbox.isEmpty()) {
      outbox.push(inbox.pop());
    }
}
return outbox.pop();
}
}
PY
class Queue(object):
def __init__(self):
self.instack=[]
self.outstack=[]
def enqueue(self,element):
self.instack.append(element)
def dequeue(self):
if not self.outstack:
while self.instack:
self.outstack.append(self.instack.pop())
return self.outstack.pop()
JS
import { Stack } from "./Stack";
class QueueUsingTwoStacks {
  constructor() {
    this.stack1 = new Stack();
    this.stack2 = new Stack();
  }
enqueue(data) {
  this.stack1.push(data);
}
dequeue() {
  //if both stacks are empty, return undefined
  if (this.stack1.size() === 0 && this.stack2.size() === 0)
  return undefined;//if stack2 is empty, pop all elements from stack1 to stack2 till stack1 is empty
  if (this.stack2.size() === 0) {
    while (this.stack1.size() !== 0) {

      this.stack2.push(this.stack1.pop());
    }
}//pop and return the element from stack 2
return this.stack2.pop();
}
}
export { QueueUsingTwoStacks };

Queue can be classified into following types: Simple Queue - is a linear data structure in which removal of elements is done in the same order they were inserted i.e., the element will be removed first which is inserted first. Circular Queue - is a linear data structure in which the operations are performed based on FIFO (First In First Out) principle and the last position is connected back to the first position to make a circle. It is also called Ring Buffer. Circular queue avoids the wastage of space in a regular queue implementation using arrays. Priority Queue - is a type of queue where each element has a priority value and the deletion of the elements is depended upon the priority value In case of max-priority queue, the element will be deleted first which has the largest priority value In case of min-priority queue the element will be deleted first which has the minimum priority value. De-queue (Double ended queue) - allows insertion and deletion from both the ends i.e. elements can be added or removed from rear as well as front end. Input restricted deque - In input restricted double ended queue, the insertion operation is performed at only one end and deletion operation is performed at both the ends.

Output restricted deque - In output restricted double ended queue, the deletion operation is performed at only one end and insertion operation is performed at both the ends.

Because they help manage your data in more a particular way than arrays and lists. It means that when you're debugging a problem, you won't have to wonder if someone randomly inserted an element into the middle of your list, messing up some invariants. Arrays and lists are random access. They are very flexible and also easily corruptible. If you want to manage your data as FIFO or LIFO it's best to use those, already implemented, collections. More practically you should: Use a queue when you want to get things out in the order that you put them in (FIFO) Use a stack when you want to get things out in the reverse order than you put them in (LIFO) Use a list when you want to get anything out, regardless of when you put them in (and when you don't want them to automatically be removed).

Queues offer random access to their contents by shifting the first element off the front of the queue. You have to do this repeatedly to access an arbitrary element somewhere in the queue. Therefore, access is

O(
n) .

Searching for a given value in the queue requires iterating until you find it. So search is

O(
n) .

Inserting into a queue, by definition, can only happen at the back of the queue, similar to someone getting in line for a delicious Double-Double burger at In 'n Out. Assuming an efficient queue implementation, queue insertion is

O(
1) .

Deleting from a queue happens at the front of the queue. Assuming an efficient queue implementation, queue deletion is `

O(
1) .

Queue can be classified into following types: Simple Queue - is a linear data structure in which removal of elements is done in the same order they were inserted i.e., the element will be removed first which is inserted first. Circular Queue - is a linear data structure in which the operations are performed based on FIFO (First In First Out) principle and the last position is connected back to the first position to make a circle. It is also

called Ring Buffer. Circular queue avoids the wastage of space in a regular queue implementation using arrays. Priority Queue - is a type of queue where each element has a priority value and the deletion of the elements is depended upon the priority value In case of max-priority queue, the element will be deleted first which has the largest priority value In case of min-priority queue the element will be deleted first which has the minimum priority value. De-queue (Double ended queue) - allows insertion and deletion from both the ends i.e. elements can be added or removed from rear as well as front end. Input restricted deque - In input restricted double ended queue, the insertion operation is performed at only one end and deletion operation is performed at both the ends. Output restricted deque - In output restricted double ended queue, the deletion operation is performed at only one end and insertion operation is performed at both the ends.

An inefficient queue implementation would be a naively-manipulated array, wherein all elements are shifted to accommodate an operation at one end of the array. This would be O(n) for one of the operations (enqueue/dequeue). This is because adding to or removing from the first location (that is, index position 0) is very slow O(n).

To achieve efficient O(1) performance, you can implement a queue as either: a doubly-linked list, which naturally allows you to manipulate each end as a single operation. a "circular dynamic array", where you keep track of pointers that tells you where the front and back of the queue reside. The "front" and "back" can float around the array arbitrarily. Note there is one subtle complexity. The block of values stored in the collection can wrap around from the end back to the beginning. The classic way to implement a priority queue is using a data structure called a binary heap. A binary heap will allow us to enqueue or dequeue items in O(logn) .

1. In circular queue, memory is utilized. If we delete any element that position is used later.
2. Circular queue consumes less memory than linear queue because in queue while doing insertion after deletion operation it allocate an extra space the first remaining vacant but in circular queue the first is used as it comes immediate after the last.
3. In CQ the memory of the deleted process can be used by some other new process.
4. A standard queue suffers from a rebuffering problem during deque operations. By making the queue circular and linking the head to the tail, this alleviates the problem and allows insertion and deletion in constant time.

Queue backed by a singly-linked list. Enqueuing into the linked list can be implemented by appending to the back of the singly-linked list, which takes worst-case time

O(
1) . Dequeuing can be implemented by

removing the first element, which also takes worst-case time

O(
1) . This also requires a new allocation per
enqueue, which may be slow.

Queue backed by a growing circular buffer. Enqueuing into the circular buffer works by inserting something at the next free position in the circular buffer. This works by growing the array if necessary, then inserting the new element. Using a similar analysis for the dynamic array, this takes best-case time

O(
1) ,
worst-case time
O(
n) , and amortized time
O(
1) . Dequeuing from the buffer works by removing the first

element of the circular buffer, which takes time

O(
1) in the worst case.

To summarise, all of the structures support pushing and popping n elements in

O(
n) time. The linked list

versions have better worst-case behavior, but may have a worse overall runtime because of the number of allocations performed. The array versions are slower in the worst-case, but have better overall performance if the time per operation isn't too important.

When this situation occurs, your queue is full. You have a few options when to deal with new items that can be pushed:

1. discard the pushed event: only when some other item is popped can now items be pushed again. Neither head nor tail is updated. Example: Think of an event queue that has filled up, new requests are simple ignored.
2. discard (pop) the oldest event on the queue: in this case you update both the head and tail pointer one place. Example: buffering incoming image frames from a webcam for processing. For a 'live' feed you may prefer to discard the older frames when the processing has a hickup.
3. create a bigger queue: that is, allocate more memory on the fly Example: you use a circular queue since it an efficient implementation that doesn't require memory allocation most of the time when you push items. However, you do not want to loose items on the queue so you allow reallocating more memory once in a while What the right action is depends on your application.

A doubly linked list, has all the computational complexity attributes, but poor cache locality. A ring buffer (array) that allows for appending and removing at head and tail has the same complexity characteristics. It uses a dynamic array and requires reallocation, once the number of elements grows beyond it's capacity. Similar to an array list/vector generally being faster in practice for sequential access versus a linked list. In most cases it will be faster and more memory efficient than using a doubly linked list implementation.

If you have an ADT Queue with only push_front() and pop_back() as its interface, there is no way to use it as a stack. A queue is normally a FIFO container, while a stack is LIFO. This means that you cannot just copy the data in sequential order from your queue to your stack, since that will make the elements appear in the "wrong" order. If you merely want to copy the data from the queue onto a stack, then you need to reverse the data first, which is impossible without allocating memory for all the elements in the queue, if your queue has only that interface mentioned above. There is no good way (performance wise) to reverse a queue. A queue is a one-way container, internally an element only has to know about the next element in line, not about the previous one. This means that you cannot iterate through the queue starting at the back, and that iteration always is

O(
n) .

If you have access to the internals of the queue, then its a trivial question, you can reverse the data in place.

Answer coming soon.