DSA chapter 5

queue

• Data structure in which the first element put into the list is the first element we can take out (FIFO)

• Elements are stored by order of insertion

• Elements can only be added to the back

• Only the first element can be accessed/removed

goal of queue

Every operation on a queue should be O(1)

operations on a queue

• Offer or enqueue

• Remove or dequeue

• Peek

• Clear all elements/Initialize()

• isEmpty()

• getSize()

• isFull()

• display()

enqueue operation

Operation of adding a new element at the rear

dequeue operation

Operation of taking the element in the front of a queue

array-implementation of queue

• Keeps track of the number of items in the queue size and the index of the first & last element

• When an element is dequeued, the size is decremented and first changes

• When an element is queued, the size is incremented and the last changes too

circular array implementation of queue

• A problem with simple arrays is we run out of space even if the queue never reaches the size of the array

• This implementation of queue can be used to solve this problem because freed spaces are re-used to store data

• If we reach the end of the array, the new element goes at the front of the array (if that spot isn’t already used)

linked list implementation of queue

A queue implemented with both a head(start) and tail(end) pointer

deque

• Double-ended queue

• Insertion and deletion can occur at either end

• Implementation similar to that of queue

• Best implemented using doubly linked list

basic operations of deque

• EnqueueFront

• DequeueFront

• EnqueueRear

• DequeueRear

priority queue

• Queue where each data has an associated key provided at time of insertion

• Dequeue operation deletes data having highest priority in the list

demerging queues

• The process of creating two or more queues from a single queue

• Used to give priority for some groups of data

merging queues

• The process of creating a priority queue from two or more queues

• The ordinary dequeue implementation can be used to delete data in the newly created priority queue

application of queues

1. Access to shared resources (ex. printer)

2. Disk Driver (queue of disk I/O requests)

3. Task scheduler in multiprocessing system (priority queues of processes)

4. Telephone calls in busy environment (queue of telephone calls)

5. Simulation of waiting line (queue of people)