Queues�

Lecture 6

mic

Queues

​

The Queue ADT

A Queue is a collection of objects inserted and removed according to the

First In First Out (FIFO) principle. Think of a queue of people to Rubios.

Queue operations

Enqueue (insert) and Dequeue (remove) are the two main operations

​

Question

When using enqueue operation to place the following items in a queue:

enqueue(10)

enqueue(20)

enqueue(30)

enqueue(0)

enqueue(-30)

​

​

​

​

The output when dequeuing from the queue is:

Implementation. Arrays. O(1)

Main update methods:

• Enqueue(e)
• Dequeue( )

​

Additional useful methods

• Peek(): Same as dequeue, but does not remove the element
• Empty(): Boolean, True when the queue is empty
• Size(): Returns the size of the queue

​

(Incorrect) Attempts to implement it

Regular array: dequeue

​

​

Select the correct code to delete from below:

​

A:

B:

C:

D: None of these are correct

Regular array: enqueue

​

​

Select the correct code to insert from below:

​

A:

B:

C:

D: None of these are correct

Issues

Dequeue:

Issues

Dequeue:

​

​

​

Enqueue:

Regular Array

Queues using circular arrays

Queues using circular arrays

Queues using circular arrays

Queues using circular arrays

​

​

Select the correct code to insert from below:

​

A:

B:

C:

D: None of these are correct

​

​

Select the correct code to insert from below:

​

A:

B:

C:

D: None of these are correct

Complexity of an Array based queues