Queue Flashcards

1
Q

Is Queue Random or Sequential Access?

A

Sequential

2
Q

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

A

FIFO. First In, First Out.

3
Q

What is a real life analogy of a Queue.

A

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

4
Q

The back of a Queue is also called the…

A

Rear or Tail

5
Q

The front of a Queue is also called the…

A

6
Q

We add elements to the …. of the Queue.

A

Back or Tail

7
Q

We remove elements from the …. of the Queue.

A

8
Q

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

A

Enqueue

9
Q

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

A

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

10
Q

What are the four fairly standard Queue methods?

A

enqueue, dequeue, peek, contains

11
Q

What does the peek() method do?

A

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

12
Q

What does the contains() method do?

A

Returns whether or not the Queue contains an element.

13
Q

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

A

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

14
Q

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

A

O(n). Linear Search.

15
Q

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

A

O(1)

16
Q

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

A

O(1)

17
Q

What are some use cases for Queues?

A

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

18
Q

what is a priority queue?

A

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

19
Q

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

A

unsorted list, sorted list, binary heap, binomial heap

20
Q

What is a queue?

A

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)

21
Q

What are the drawbacks of array implementation of Queue?

A

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.

22
Q

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

A

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

23
Q