Queues - Interview Questions

What are queues?

 

Queues are programmatic data structures that allow access to only one item at a time, the first item inserted. Queues internally use other data structures such as arrays for their implementation. A queue is a First-In-First-Out (FIFO) storage mechanism, because the first item inserted is the first to be removed.

What are the key public interfaces provided by queues?

 

Queues usually provide the following key interfaces.

insert() - Inserts a new data item oat the end of queue.

remove() - Removes the item from the end of the queue

peek() - Returns the item from the front of the queue without removing it.

isFull() - Returns true if the queue is full.

isEmpty() - Returns true if the queue is empty.

Write a program to implement queue functionality?

 

Following Java program implements the queue functionality. It internally uses an array for the implementation.

class MyQueue {

 private int maxSize;
 private int[] queueArray;
 private int front;
 private int rear;
 private int numberOfItems;

 //constructor
 public MyQueue(int maxSize) {
  this.maxSize = maxSize;
  queueArray = new int[maxSize];
  front = 0;
  rear = -1;
numberOfItems = 0; }

 //insert an item to queue
 public void insert(int i) {
  //increment rear and insert item
  queueArray[++rear] = i;
  nItems++;
 }

 //remove an item from queue
 public int remove() {
  //return item and decrement top
  int temp = queueArray[front++];  nItems--;
  return temp;
 }

 //view item from top of stack
 public void peek() {
  return queueArray[front];
 }

 //check if stack is empty
 public void isEmpty() {
  return (numberOfItems== -1);
 }

 //check if stack is full
 public void isFull() {
  return numberOfItems == maxSize);
 }
}

What is the time efficiency of the push and pop implementations of queues?

 

The push() and pop() methods implemented in stacks take constant time to execute. i.e. the time to execute is very quick and is not dependent on the number of items on the stack. In Big O notation this is represented as O(1).

What are some common scenarios where queues are used?

 

Following are some of the common scenarios in which Stacks can be Used.

- To check if delimiters (parenthesis, brackets etc.) are balanced in a computer program

- To reverse strings

- To traverse the nodes of a binary tree.

- To search the vertices of a graph.

MASTER THE CODING INTERVIEW: DATA STRUCTURES + ALGORITHMS - TOP SELLING COURSE ON UDEMY.
 
GO TO COURSE
 

What are Deques?

 

Deques are double-ended queues in which you can insert items either at the front or rear, and can delete items either from the front or rear. Deques provide the methods similar to insertLeft(), insertRight(), removeLeft() and removeRight() to insert and remove from both ends.

What are Priority Queues?

 

A priority queue is a specialized queue in which the items are ordered, so that the lowest (or highest) key is always in the front. So when you get an item from a priority queue then you always get the lowest value item (or highest value item based on how the items are ordered).

Write a program to implement priority queue functionality?

 

Following Java program implements the priority queue functionality. It internally uses an array for the implementation. The array items are ordered in ascending order, and the insert() function inserts an item in the correct position in the array.

class MyPriorityQueue {

 private int maxSize;
 private int[] queueArray;
 private int numberOfItems;

 //constructor
 public MyPriorityQueue(int maxSize) {
  this.maxSize = maxSize;
  queueArray = new int[maxSize];
numberOfItems = 0; }

 //insert an item to queue
 public void insert(int i) {
  //increment rear and insert item
  if(numberOfItems==0){
    queueArray[numberOfItems] = i;
  } else {
    for(int j=numberOfItems-1; j>=0; j--) {
      if(i > queueArray[j]) {        queueArray[j+1] = queueArray[j];      } else {        break;      }    }    queueArray[++rear] = i;
    nItems++;
  }
 }

 //remove an item from queue
 public int remove() {
  //return item and decrement count
  return queueArray[--numberOfItems]; }

 //view item from top of stack
 public void peek() {
  return queueArray[numberOfItems-1];
 }

 //check if stack is empty
 public void isEmpty() {
  return (numberOfItems == 0);
 }

 //check if stack is full
 public void isFull() {
  return (numberOfItems == maxSize);
 }
}
 
Subscribe to our Questions

 

Data Structures - Interview Questions

ArraysLinked ListsStacksQueuesBinary TreesRed-Black Trees2-3-4 TreesHash TablesHeapsGraphsTrie
 
MASTER Data Structures  

Top ranked courses to help you master Data Structures skills.
Master the Coding Interview: Data Structures + Algorithms

iconicon

Offered By - Andrei Neagoie
Platform - Udemy
Rating - * * * * *
Students Enrolled - 100,000 +

RECOMMENDED RESOURCES
Behaviorial Interview
Top resource to prepare for behaviorial and situational interview questions.

STAR Interview Example