queue ADT

Work in Progress

Summary

Queue ADT

  • first in first out(FIFO)

Circular array implementation - arrays

OperationMethodPerformance
enqueue(v)add after tail-
dequeue()remove from head-
peek()get head-
a1a2...an...01n-1nm-1headtailinitialenqueuing:a1...axay...am0m-1headtailaftersomedequeuing:

array “wraps” around to avoid having to shift all the elements during insertion/removal

Two stacks implementation

  • enqueue to the bottom or dequeue from the bottom
OperationMethodPerformance
enqueue(v)Expensive enqueue: pop items in stack1 to stack2, push v to bottom of stack1, push rest of elements back to stack1
Push: push v to stack1		- , expensive enqueue
- , push to primary
dequeue()Pop: pop v from stack1
Expensive dequeue: pop items in stack1 to stack2, pop v from top of stack 2, push rest of elements back to stack2		- , pop from primary
- , expensive dequeue
peek()similar to dequeue- , peek the primary
- , expensive dequeue

SLL implementation

OperationMethodPerformance
enqueue(v)insert at tail-
dequeue()remove from head-
peek()get head-
a1a2...anheadtailinout

java.util.Queue interface

Concept

Queue operations

  • enqueue(v)
    • add v to the back of the queue
  • dequeue()
    • get the first item in the queue and remove it
  • peek()
    • get the first item in the queue without removing it
4321inout

Monotonic queue

Application