Queues

Description

• FIFO
• Perfect line
• Useful in many data management situations

Queue ADT

• offer(E e) - Adds an item to the end queue
• E peek() - Returns, but does not remove an item from the front of the queue
• E poll() - Returns and removes an item from the front of the queue
• Java's Queue

Array Implementation

• Keep track of two pointers, front and rear
• Set initial front to 0
• Set initial rear to array.length - 1
• On offer, increment rear (mod length), insert at array[rear]
• On poll, return array[front], and increment front
• On peek, return array[front]
• Allow both front and rear to wrap around array (use modulus)
• Size should be updated on each offer, poll
• If size is going to be > array.length, reallocate()
• Peek and poll return null on empty queues (no exceptions)

List Implementation

• Use double linked list (pointers to head and tail (front and rear))
• Empty queue should have head and tail pointing to null
• A queue with a single item will have head and tail pointing to that item
• On offer, add new item at end of list
• On poll, return data at head of list, update head => head.next
• On peek, return data at head of list
• Keep track of size on offers and polls
• Peek and poll should return null on empty queue

In-lab exercise

• Show how you can use two stacks to create a queue
• Show how you can use two queues to create a stack