Queue

Question 1

Is Queue Random or Sequential Access?

Answer 1

Sequential

Question 2

A Queue is a data structure in which we add elements and remove elements according to LIFO or FIFO?

Answer 2

FIFO. First In, First Out.

Question 3

What is a real life analogy of a Queue.

Answer 3

An actual queue of people. The first one to join the queue is the first one to leave the queue.

Question 4

The back of a Queue is also called the…

Answer 4

Rear or Tail

Question 5

The front of a Queue is also called the…

Answer 5

Front or Head

Question 6

We add elements to the …. of the Queue.

Answer 6

Back or Tail

Question 7

We remove elements from the …. of the Queue.

Answer 7

Front or Head

Question 8

What method do we use to add an element to a Queue?

Answer 8

Enqueue

Question 9

What method do we use to remove an element from a Queue?

Answer 9

Dequeue [not to be confused with double-ended queue]

Question 10

What are the four fairly standard Queue methods?

Answer 10

enqueue, dequeue, peek, contains

Question 11

What does the peek() method do?

Answer 11

It returns the element at the front/head of the queue without removing it from the Queue.

Question 12

What does the contains() method do?

Answer 12

Returns whether or not the Queue contains an element.

Question 13

What is the BigO for ACCESSING an element in a Queue?

Answer 13

O(n). Worst-case the element you want will be at the tail of the queue.

Question 14

What is the BigO for SEARCHING an element in a Queue?

Answer 14

O(n). Linear Search.

Question 15

What is the BigO for INSERTING an element in a Queue?

Answer 15

O(1)

Question 16

What is the BigO for DELETING an element in a Queue?

Answer 16

O(1)

Question 17

What are some use cases for Queues?

Answer 17

Queues are widely used as waiting lists for a single shared resource like a printer, disk, CPU.

Queues are used in the asynchronous transfer of data (where data is not being transferred at the same rate between two processes) for eg. pipes, file IO, sockets.

Queues are used as buffers in most of the applications like MP3 media player, CD player, etc.

Queues are used to maintain the playlist in media players to add and remove the songs from the play-list.

Queues are used in operating systems for handling interrupts.

They can also be used for scheduling.

Printer Queuing

Question 18

what is a priority queue?

Answer 18

A priority queue is a container ADT where each element has a key (usually a real number) called its priority.
There are operations allowing us to insert an element, and to find and delete the element of highest priority. A general find or delete or retrieve is not available

Question 19

Priority queues can be implemented in many ways what are some ways?

Answer 19

unsorted list, sorted list, binary heap, binomial heap

Question 20

What is a queue?

Answer 20

A queue is a linear container that allows us to insert at one end [Rear],
and delete and retrieve only at the other end [Front].

There is no general find operation

A queue is FIFO (first in, first out)

Question 21

What are the drawbacks of array implementation of Queue?

Answer 21

Memory Wastage: The space of the array, which is used to store queue elements, can never be reused to store the elements of that queue because the elements can only be inserted at front end and the value of front might be so high so that, all the space before that, can never be filled.

Array Size: There might be situations in which, we may need to extend the queue to insert more elements if we use an array to implement queue, It will almost be impossible to extend the array size, therefore deciding the correct array size is always a problem in array implementation of queue.

Question 22

What is the minimum number of queues that can be used to implement a priority queue?

Answer 22

Two queues are needed. One queue is used to store the data elements, and another is used for storing priorities.

Question 23

Breadth first search

Answer 23

Using a queue to traverse a tree to f graph

Covers each breadth [ present depth ] first